Research On Fast Scalar Multiplication Algorithms In Hyperelliptic Curve Cryptosystem

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.