论文标题:超椭圆曲线密码体制研究
Researches on Hyperelliptic Curve Cryptosystems
论文作者 游林
论文导师 王天明,论文学位 博士,论文专业 计算数学
论文单位 大连理工大学,点击次数 100,论文页数 134页File Size4747k
2002-11-01论文网 http://www.lw23.com/lunwen_632914907/ 超椭圆曲线;超椭圆曲线密码体制;超椭圆曲线数字签名一般方程;Jacobian群;Frobenius自同态;特征多项式;除子标量乘;快速算法;τ-展开式
hyperelliptic curve,hyperelliptic curve cryptosystem,general equations of hyperelliptic curve digital signature algorithm,Jacobian group,Probenius endomorphism,characteristic polynomial,divisor scalar multiplication,fast algorithm,r-adic expansion
超椭圆曲线密码体制是椭圆曲线密码体制的自然推广，但不仅仅是一种简单的推广。超椭圆曲线密码体制所基于的除子类群，又称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．第六章?
Hyperelliptic curve cryptosystems(HECC) is a natural generalization of elliptic curve cryptosystems. but it is not only a simple generalization. The divisor class group, often called Jacobian group, based on which hyperelliptic curve cryptosystems are constructed, is much complicated than the elliptic curve rational point group. Since the order of a Jacobian group can be constructed to have a much large prime factor over a small base field, and there exist a lot of hyperelliptic curves suitable for cryptographical applications, hyperelliptic curve cryptosystems has gotten much attention more and more.When a message is encrypted in (H)ECC, there will be a large amount of message expansion. Due to this fact, (H)ECC is often applied in Diffie-Hellman key agreement protocols and digital signature schemes, though ECC encrypting cards have appeared but only devised for some special kind of small data area.In the application of hyperelliptic curve cryptosystems, the key operation is divisor scalar multiplication. The general methods applied for computing divisor scalar multiplications are Binary method and its improved versions.Probenius endomorphism was first applied to speed up rational point scalar multiplication on an elliptic curve by Koblitz [53]. Later, Koblitz"s method was modified by Meier and Staffelbach[60], they proposed a method which is three times faster than Binary method for anomalous elliptic curves in characteristic 2 , and in 1997 it was improved by Solinas [104] for a class of elliptic curves in characteristic 2. Based on Koblitz"s idea, Fangguo Zhang and etc.[117] proposed a fast algorithm to compute divisor scalar multiplications for a special class of hyperelliptic curves in characteristic 2 with sparse characteristic polynomials P(T). They compute q9D by (-P() + q9)D and convert the multiplier into q9-adic form.In [71], Miiller computed rational point scalar multiplications on elliptic curves over small finite fields of characteristic 2 by representing the multipliers into Probenius expansion, that is, r-adic expansion. One year later, Smart [101] applied Miiller"s idea to propose an algorithm to compute rational point scalar multiplications on elliptic curves over small finite fields of characteristic odd.In [38], Giinther and etc. applied their ideas of Meier & Staffelbach([60]), Koblitz([53, 51] and Solinas([l04]) to compute divisor scalar multiplications on two special hyperelliptic curves (v2 + uv - u5 + au2 + 1, a = 0, 1). In fact, their algorithmic idea is similar to that of Miiller.Since for every finite field there exists a normal basis, and for an even characteristic field there exists an optimal normal basis(ONB), we suppose that, in this thesis, field arithmetics are based on some normal basis when we apply Probenius endomorphism to optimize divisor or rational point scalar multiplications. Thus, the cost of the evaluations of Frobenius endomor-phism can be considered free if compared with the cost of the computation of one divisor scalar or point addition.The work in this thesis mainly includes the following five aspects :1. In Ch.2, we first introduce the basic theory about the Jacobian group of hyperelliptic curves and the computation algorithms for divisor addings. By using Riemann-Roch Theorem we give a short proof that any divisor of degree 0 is uniquely equivalent to a reduced divisor. Our proof is much simpler than the constructional proof given by Koblitz [52]. We also show that every pair of the polynomials (a,b) that satisfies the condition a(u)\(b2(u) + b(u)h(u)-f(u)) uniquely determines a reduced divisor.2. In Ch.3, we propose several general equations of (hyper)elliptic curve digital signature algo-rithms((H)ECDSA), From these signature general equations, we can extract both efficient and secure (H)ECDSAs for practical cryptographic applications. Later, we briefly discuss their securities.3. In Ch.4, by using Probenius endomorphism, we propose a new fast algorithm to compute scalar multiplications, that is, first search a suitable small
|
