圆锥曲线上的密码体制安全性浅析

李赫男

摘 要 文章对圆锥曲线密码体制的安全性进行分析与总结，分别给出大整数分解，圆锥曲线上的离线对数上安全性问题的浅析。而结合两个困难问题的密码体制也越来越成为当今圆锥密码体制的主要方向。

关键词 圆锥曲线密码体制；离散对数；大数分解；剩余类环

中图分类号：TN918 文献标识码：A 文章编号：1671-7597（2014）13-0156-01

20世纪90年代，对基于有限域Fp上的圆锥曲线Cp（a，b）及其在大整数分解和密码算法中应用的研究，引起人们很大的兴趣。近年来，圆锥曲线上的数字签名方案的研究有进一步发展。而在圆锥曲线密码体制安全性上的分析目前还没有较系统的论述，本文重点分析总结了了俩类圆锥曲线上的安全性分析。

1 圆锥曲线上大整数分解困难安全性浅析

基于环Zn上圆锥曲线的RSA类型的密码方案的安全基础主要基于此类困难性问题。对环Zn上圆锥曲线上此类困难问题的安全性，做以下总结。

1）环Zn上圆锥曲线的参数n的选取方法为n=pq，其中p，q选取为两个适当大的素数，这保证了n的规模较大以使对其进行因式分解是个困难问题，同时满足p+1=2r，q+1=2s，并且r，s也为素数，满足这样条件p，q是一种强素数，这保证了n的分解非常困难。这样，Zn上圆锥曲线的RSA型加密算法的安全性就建立在大数分解的困难性。显然，从公钥：n，a，b和e，很难得到私钥d，p，q和Nn。

2）可以抵抗小公钥指数攻击[1]。为了加快加密速率，通常RSA方案中使用小公钥，不过一般的RSA方案使用小公钥会使系统变的不安全。攻击方法有很多，如广播攻击，相关信息攻击，短填充攻击等。

对于圆锥曲线上构建的RSA方案，取公钥为3作为例字，则其密文为：P（c）=3P（m），具体计算出c=m（m2+3a）（3m2+a）-1（mod n）

上面的式子可以化成模n的三次多项式求根，针对这个问题的求解目前都需要分解n，所以在抵抗小公钥指数方面，圆锥曲线上的RSA方案有足够的安全性。

3）针对圆锥曲线上的RSA方案小解密指数d的攻击，孙琦等[2][3]人已证明其能抵抗Wiener的攻击，以及Boneh，Durfee等攻击。随后，刘铎等[4]人提出一种连分数攻击可以在私钥过小的情况下，得到私钥d，并进而分解n。该攻击的私钥时生效。因此圆锥曲线上的RSA方案私钥过小的情况下仍然是不安全的。不过，由于在圆锥曲线上的RSA方案对于选取小公钥有足够安全，而在选取e为小常数的时候，由ed=1（mod Nn） 可知d将会很大，因此系统可以在保证安全的同时也很好提高了效率。

2 圆锥曲线离散对数困难的安全性浅析

1）2000年，戴宗铎，裴定一，杨君辉等提出了一种在有限域上的广义圆锥曲线R（a，b），定义了其上的加法，并证明R（a，b）是一个加群以及至少能在扩域上构造与圆锥曲线群同构的普通乘法群。由于有限域上操作数的长度比有限域上操作数的长度多了一倍所以其上的离散对数的困难性比有限域上离散对数的困难性的安全性是更加困难的。

2）圆锥曲线参数的选取也影响圆锥曲线的安全性[5]。

由于参数a参与了加法运算，所以其值选取影响圆锥曲线的安全性。

①有限域上的圆锥曲线。

a.在有限域上Fp的圆锥曲线如果a为p的二次剩余，在已知其平方剩余的情况下，可以通过一些数学变换构造从有限域Fp上的圆锥曲线构成的点群到有限域Fp上的普通乘法群的映射，使基于圆锥曲线上的离散对数安全性降低到普通有限域乘法群上的离散对数安全性。特别的当a为p的二重根时，可以映射到有限域上的普通加法群上，这使圆锥曲线上的离散对数安全性降低到有限域加法群上的离散对数安全性，如此便毫无安全性可言，因此此种参数选取是不可取的。

b.当a不是p的二次剩余，若要构造相应的映射，必需通过扩域在规模至少为有限域Fp2的域上才有可能实现。而由于有限域Fp2上操作数的长度比有限域Fp上操作数的长度多了一倍，此时即使能够构成的相应的映射也并未降低原有的圆锥曲线上离散对数的安全性。

②Zn上的圆锥曲线。

对于剩余类环上的圆锥曲线，在不知道n的因数分解的情况下，对于求解二次剩余或平方根的问题都是没有多项式时间解法的问题，即难解问题。这样想要构造相应的映射是困难的，因此参数a的选取对安全性影响不大。但是为了避免潜在的安全漏洞，仍然取a不是n的二次剩余为宜。具体可取（a/p）=-1，（a/q）=1或（a/p）=1，（a/q）=-1，或（a/p）=-1，（a/q）=-1。同时为了使曲线中的运算落在C1，第三种参数选取为最佳选择。

3 总结

通过上述分析，在两类困难问题的安全性，各有利弊，如果能够同时结合两类困难问题，则将是一种更优的选择。而在Zn的圆锥曲线上可以很方便的构建RSA类型的大整数分解困难问题的密码，同时还可以结合其上的离散对数困难问题，从而构建基于双困难问题的密码方案，方案只有在两个困难问题被破解时才能被攻破，这可以有效的提高密码方案的安全性。因此这也将是圆锥曲线密码体制今后主流研究方向。

参考文献

[1]曹珍富.RSA与改进的RSA的圆锥曲线模拟[J].黑龙江大学学报，自然科学版，1999（4）：15-18.

[2]王标，朱文余，孙琦.基于剩余类环Zn上圆锥曲线的公钥密码体制[J].四川大学学报（工程科学版），2005（5）：112-117.

[3]周兴旺，曹炜.关于RSA型公钥密码体制与抗小解密指数攻击的注记[J].四川大学学报（自然科学版），2008（4）：

233-235.

[4]刘铎，戴一奇.对环Z/nZ上圆锥曲线RSA型公钥密码体系的小私钥d攻击[J].四川大学学报（工程科学版），2008（3）：86-89.

[5]徐旭东，靳岩岩，赵磊.圆锥曲线公钥密码算法的参数选择[J].计算机工程，2007（8）：158-159.endprint