论文部分内容阅读
超椭圆曲线密码体制是椭圆曲线密码体制的自然推广,但不仅仅是一种简单的推广。超椭圆曲线密码体制所基于的除子类群,又称Jacobian群,其结构与运算比有理点群要复杂得多。但由于可以在一个很小的基域上构造具有较大素数因子阶的Jacobian群,且可应用于密码体制的超椭圆曲线比较丰富,这使得超椭圆曲线密码体制也逐渐受到人们的重视。 由于使用(超)椭圆曲线密码体制来加密信息会有较大信息量的扩展,虽然已研发出ECC加密卡,但也只是针对特定范围的小数据量而设计的,所以一般利用(超)椭圆曲线密码体制来实现密钥交换及数字签名的功能,即相应的(超)椭圆曲线数字签名体制及(超)椭圆曲线Diffie-Hellman密钥交换协议。 在实现超椭圆曲线密码体制中起关键作用的运算是除子标量乘,一般采用的方法是二元法及其各种改进的二元法。Koblitz[53]最先利用Probenius自同态来快速计算椭圆曲线上的有理点标量乘。其后Meier与Staffelbach[60]利用Koblitz的算法思想,针对特征为2的域上的一类反常椭圆曲线,提出了一种比二元法快三倍的有理点标量乘算法。1997年Solinas[104]又针对特征为2的域上的一类椭圆曲线改进了他们的算法。依据Koblitz的算法思想,在文献[117]中,张方国等人提出了一类特殊超椭圆曲线,即特征为2的域上的具有稀疏特征多项式P(T)的超椭圆曲线上的一种快速除子标量乘算法。其算法的思想是直接将乘子表成特征多项式的常数项的数进制,即q~g-进制,而除子标量乘q~gD由计算(-P(φ)+q~g)D来完成。 在[71]中,M(?)ller将有理点标量乘的乘子作Frobenius展开,即将乘子表成τ-展开式,然后利用该展开式来计算特征为2的小基域上的椭圆曲线上有理点的标量乘。一年后,Smart([101])应用M(?)ller的思想,提出计算特征为奇素数的小基域上的椭圆曲线上有理点的标量乘算法。在文献[38]中,G(?)nther,Lange与Steinto将Meier与Staffelbach([60]),Koblitz([53,51]),Solinas([104])等人的思想应用到两条特殊的超椭圆曲线(v~2+uv=u~5+au~2+1,a=0,1)上来计算除子标量乘。其实,他们的思想与M(?)ller算法思想类似。 由于任意有限域均存在一个正规基,且对于特征为2的域,则存在优化正规基(OBN)。在本论文中,当我们利用Probenius自同态来优化除子或有理点标量乘的运算时,均假定域上的运算是采用正规基来进行的。于是Frobenius赋值的运算量,与一次除子或有理点加的运算量相比,可忽略不记。 在本论文中,我们研究的内容及有关结果包含以下五个方面: 1.在第二章,首先介绍有关超椭圆曲线的Jacobian群一般理论及其元素除子加的计算方法。利用Riemann-Roch定理,证明了任何一个度数为零的除子唯一等价于一个约化除子。该证明比Koblitz在[52]中给出的一个构造性证明要简单得多。此外还证明了任何一对多项式a与b唯一确定一个约化除子的充分必要条件是a(u)|(b~2(u)+ b()h()一f(》成立. 2.在第三章,提出了若干(超)椭圆曲线数字签名算法一般方程形式及一些新的(超)椭 圆曲线数字签名算法。从提出的数字签名算法一般方程中,我们可依据实际的需求, 提取有效且安全的(超)椭圆曲线数字签名体制.对于这些(超)椭圆曲线数字签名算 法的安全性,我们也做了简要的探讨与分析. 3.在第四章,借助Frobenius自同态,提出了一种新的快速的算法来进行标量乘计算. 即先寻找一个合适的较小正整数s,使得q“的某个稀疏,一展开式中,的所有系数的 绝对值的和比q‘小得多,以使标量乘q‘D能更有效地计算出来(比H元法等方法快), 然后将乘子表成q‘一进制.也就是将robenius展开的方法与m一进制(问)方法有效 地结合起来的一种标量乘快速算法.对干许多(超)椭圆曲线来说,我们的方法可比 H元法及张方国等人提出的方法更有效.就对所给曲线所做的计算表明(表4.3);我 们的算法所需的运算量比二元法要平均减少大约60.73%,而比张的方法要平均减少 大约62.78%.此外,我们还给出了一个寻找。的一种可行的方法.对于某些(超)椭 圆曲线,我们的算法比Ghnther等人[38)的算法也要快得多. 4.在第五章我们先给出了一个单除子的标量乘的定理及算法,通过将除子多项式表示 中的第一个多项式进行因式分解,证明了一般除子标量乘可由先计算单除子的标量 乘然后再计算除子加来完成.利用所得结果,将 Duursma与 Sforurai在文献[20]中所 给出的除子标量乘快速算法推广到域E%上具有一般参数形式的Cq型超椭圆曲线 上:沪一炉十a。+0,其中 a e y,0 e IFq,a是某个奇素数月的幂.由于所得到的除 子标量乘算法是由具体公式给出的,故比二元法等算法要快得多 其运算量大约是二 元法的 60%).在本章的最后两节,我们讨论了 Cq型曲线的同构曲线及挠曲线并获得 了若干结果,并利用这些结果确定了相关的特征多项式.此后对于若干取定参数,给 出了相关的 Cq型超椭圆曲线,Jacobian群的阶及其最大素因子的比特数的一个表. 5.第六章?