【作者】 郝艳华；

【导师】 王育民；

【作者基本信息】 西安电子科技大学 ， 密码学， 2007， 博士

【摘要】 作为一类特殊的代数曲线,超椭圆曲线是椭圆曲线的一种推广。与其他公钥密码体制相比,超椭圆曲线密码体制具有更短的操作长度,特别适合在受限系统中使用。由于结构复杂,所以超椭圆曲线密码体制实现速度较慢,目前对它的研究仍处于理论阶段。如何提高超椭圆曲线除子标量乘的计算速度是提高该密码体制实现速度,并使它早日走向实用的一个亟待解决的问题,本文对超椭圆曲线除子标量乘的快速算法作了深入的研究,主要工作如下:1.讨论了使用双基链计算超椭圆曲线除子标量乘的方法,给出了亏格为2的超椭圆曲线上2D₁+D₂,3D₁,3D₁+D₂,4D₁,4D₁+D₂的除子计算公式、他们的变体公式以及他们与变体公式之间联系的临界点,分析了公式的运算量。将2D₁+D₂公式用于非邻接形（NAF）和标准倍点加（double-and-add）标量乘算法中,比使用Lange的公式在平均单比特运算量上分别减少6.8%和9.2%,比使用Fan的改进公式则分别减少2.7%和2%。2.通过分析所给出的除子运算公式的运算量,结合大素数域上常见的实现环境,提出了适合我们应用的高效的超椭圆曲线双基链标量乘算法,并对该算法进行了复杂度分析。经过测算,我们的双基链标量乘算法与标准倍点加和NAF标量乘算法相比,效率分别提高25%和15.8%。该除子标量乘算法能够抵抗某些边信道攻击而且不需要任何预计算。3.给出了亏格为2的超椭圆曲线除子5D₁公式、它的变体公式以及它与变体公式之间联系的临界点,并分析了它们的运算量。给出了椭圆曲线有理点的5倍点公式以及多基链标量乘算法。4.给出了快速有效的亏格为3的超椭圆曲线退化除子运算的运算公式。将它用于总是倍点加（double-and-add-always）标量乘算法中,一次和二次退化除子标量乘分别比标准除子标量乘快25.4%和13%。该算法能够抗击简单能量分析攻击（SPA）和时间攻击（TA）,主要用于使用固定基点进行标量乘的运行环境中,如ElGamal型加密算法、Diffie-Hellman协议的发送方以及数字签名算法HECDSA中。由于退化除子特殊的结构,一次和二次除子的表示长度分别仅为标准除子的三分之一和三分之二。5.给出了求超椭圆曲线除子加法和倍点并行算法的一个易于实现的一般性方法,使用这个方法得到的并行算法的特点是:①需要运行的轮数最少;②在满足①的情况下,所需的并行运算乘法处理器的个数最少;③在满足①和②的情况下,一次需要存储的变量的最大个数最少。利用这个方法给出了亏格为3的超椭圆曲线除子加法和倍点运算的并行算法,分析结果表明,加法运算使用9个乘法处理器至少需要进行15轮运算（其中包含一个求逆轮）,倍点运算使用7个乘法处理器也至少需要进行15轮运算（其中包含一个求逆轮）。6.给出了一个有效的同时求多个域元素逆的求逆算法。将其应用到Mishra的亏格为2的超椭圆曲线除子标量乘算法中,得到了一个高效的抗简单能量分析攻击的标量乘算法。该算法比总是倍点加标量乘算法快24%～26%,比Mishra的两种标量乘算法分别快33%～35%和6%～7%。我们给出的这个求逆算法可以在任何需要求多个元素逆的应用环境中使用。更多还原

【Abstract】 As a special class of algebraic curves,hyperelliptic curves are generally viewed as generalizations of elliptic curves.With shorter operand size compared with other public key cryptosystems,hyperelliptic curve cryptosystem has showed excellent performance in embedded processors.Hyperelliptic curve cryptosystem is slow in speed for its complicated algebra structure,thus it is still at the stage of academic interest at present. It can be used in our daily life if and only if implementing speed of scalar multiplication of divisor class groups can be improved.An intensive study of fast scalar multiplication algorithms in hyperelliptic curve cryptosystem has been made in this paper and the main results are listed as follows:1.Methods of computing scalar multiplications of divisor class groups of hyperelliptic curves using double base chains are discussed,and explicit formulas and their variants for 2D₁+D₂,3D₁,3D₁+D₂,4D₁,4D₁+D₂ on genus 2 hyperlliptic curves and the corresponding cost are given.Break-even points between basic formulas and their variants are computed.NAF and standard double-and-add scalar multiplication algorithm using the explicit formula of 2D₁+D₂ saves about 6.8% and 9.2%cost respectively for per bit scalar compared with formulas given by Lange and 2.7%and 2%compared with formulas improved by Fan.2.By analyzing the cost of formulas given and general situations in large prime fields, an efficient scalar multiplication algorithm of hyperelliptic curves using double base chains is presented.The algorithm saves 25%and 15.8%cost respectively compared with the standard double-and-add and NAF scalar multiplication algorithm,which can resist some side-channel attacks and don’t need any precomputation.3.An explicit formula for 5D₁ on genus 2 hyperelliptic curves,its variant and the break-even point between them are given.At the same time,efficient quintuple formulas for elliptic curve are provided.An efficient scalar multiplication algorithm using multibase chains are given,which can be used in both elliptic curve cryptosystem and hyperelliptic curve cryptosystem.4.Efficient formulas for degenerate divisors of genus 3 hyperelliptic curve are presented.By computing,the double-and-add-always scalar multiplication algorithm using a degenerate divisor of degree 1 and degree 2 is proximately 25.4% and 13%respectively faster than that using a standard divisor under 1Ⅰ=30M.The algorithm can resist the simple power analysis attack and the timing attack and is applicable to cryptosystems with fixed base point,e.g.,ElGamal-type encryption, sender of Diffie-Hellman,and hyperelliptic curve digit signature algorithm （HECDSA）.The length of a representation of a degenerate divisor of degree 1 or degree 2 is one third or two third of that of a stand divisor respectively.5.A general methodology for obtaining parallel algorithms of explicit formulas for the addition and doubling of divisor class groups of hyperelliptic curves is presented, which is easily used.The parallel algorithms obtained by using the methodology are characterized by:1) the minimum number of rounds;2) the minimum number of multipliers when 1) is satisfied;3) the minimum number of variables needed to memory once when 1) and 2) are satisfied.Parallel formulas for the addition and the doubling of divisor classes on genus 3 hyperelliptic curves are presented using the methodology.The result shows that the explicit formula for the addition requires at least 15 parallel multiplication rounds using 9 multipliers（including an inversion round） and the explicit formula for the doubling requires at least 15 parallel multiplication rounds using 7 multipliers（including an inversion round）.6.An efficient algorithm for simultaneously obtaining the inverses of a list of underlying field elements is given.By using it in the scalar multiplication algorithm given by Mishra,an efficient scalar multiplication algorithm of genus 2 hyperelliptic curves is obtained.The scalar multiplication algorithm is 24%～26% faster than the double-and-add-always scalar multiplication algorithm and is 33%～35%and 6%～7%respectively faster than the scalar multiplication algorithms improved by Mishra.In any other applicable situation where the inverses of many elements are required,our algorithm can be applied.更多还原