| 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...
|
PDF Full Text Request