Research On Hyperelliptic Curve Crytosystems

The Elliptic Curve Cryptosystems (ECC) was proposed by Neal Koblitz and Victor Millerin 1985. It has been studied for more than ten years and has been widely put into practicaluse. In 1989, Neal Koblitz proposed the hyperelliptic curve cryptosystems (HCC) as anatural generalization of ECC. HCC is based on the discrete logarithm problem on theJacobian of hyperelliptic curves over finite fields. The algorithm of Cantor provided aneffective method to implement the group operation on the Jacobian of a hyperelliptic curve.At the same level of security, the basis field of hyperelliptic curve cryptosystems is smallerthan that of ECC, and almost all protocols based on the standard DLP such as DSA andElGamal can be planted to HCC. On the same domain field, the bigger the genus(g~4), themore the number of curves, and the wider the region for the choice of secure curves to beused in cryptography. As HCC is an extension of ECC, the general techniques in HCC canalso be used in ECC. This is significant to the study of the theory as well as theimplementation of ECC. HCC should be faster than elliptic curve cryptosystems, as theusage of multiprecision integer arithmetic can be avoided for appropriate parameters. SinceHCC has many obvious advantages over the other cryptosystems, the study of HCC hasbeen drawing the attention of more and more researchers.However, the study of HCC is still in the stage of theoretical research, and there aremany problems remain to be solved.The main work in this thesis is as follows:1.The DH protocol, ElGamal encryption and ElGamal signature scheme, DSA areextended to Hypereliptic curves, and a new message recovery signature schemebased on Hyperelliptic curves is presented. And it is proved that this new messagerecovery signature scheme is not strong equivalent to HC-ElGamal signaturescheme.2.A very efficient probability message coding scheme of hyperelliptic curvecryptosystems based on GF(p~)(p*2 ) and a new divisor compression scheme ofhyperelliptic curve over GF(p) are presented.3.A compact representation of the domain parameters of HCC is presented, and theequation of hyperelliptic curves over finite field is shortened.4.The secure hyperelliptic curves that can be used for HCC over finite fields GF(3),GF(4), GF(5), and GF(8) are found using Weil conjecture algorithm.5.The Weil Descent's algebraic method for DLP in the Jacobian of hyperellipticcurves(HCDLP) which generalized by Galbraith is analyzed, and the problem ofwhether or not the Weil Descent' method can be used to attack the HCDLP withthe form of v2-~-xx =J(x) defined over GF(q~) is discussed in detail. We get thefollowing conclusions: the Weil Descent's algebraic attack method is not a threatto hyperelliptic curves with the form of y2+xy=J(x) defined over GF(2r) when r islarge.6.The problem of scalar multiplication on the Jacobians of hyperelliptic curves isstudied. A fast algorithm for scalar multiplication on the Jacobians of a kind ofhyperelliptic curves based subfield is proposed with its computational costanalyzed.