Research On Ecient Algorithms And Safety Foundation For Elliptic Curve Cryptosystems

Scalar multiplication, pairing computation and discrete logarithm problemare fundamental problems in elliptic curve cryptography. Scalar multiplicationand pairing computation are key to the efficiency of elliptic curve cryptosystemswhile discrete logarithm problem is key to the security of elliptic curve cryptosystems.Researches on scalar multiplication and pairing computation makecryptosystems more efficient and wider utilization. Track down investigations ondiscrete logarithm problem can estimate the security of cryptosystems in timewhich reduces the risk of being broken. In this thesis, we consider such problemsas scalar multiplication, pairing computation and discrete logarithm problem.1. Elliptic curves over binary fields can be represented by affine coordinates,standard projective coordinates, Jacobian projective coordinates and Lop′ez-Dahab projective coordinates. Point addition and doubling are fastest inLop′ez-Dahab projective coordinates, and then in Jacobian projective coordinates.We propose efficient formulas to compute 3P in Lop′ez-Dahabprojective coordinates. This leads scalar multiplication using double basechain in Lop′ez-Dahab projective coordinates to be about 12% faster thanin Jacobian projective coordinates.2. In Asiacrypt'07, Avanzi et.al. proposed complex double base chain tocompute scalar multiplication for Koblitz curves. However, their scalarrecoding algorithm needs a lot of divisions in complex field. We reduce thedivisions via isomorphism to speed up the scalar recoding algorithm.3. In elliptic curve signature schemes, verifers have to compute multi-scalarmultiplication. Doche et.al. presented a method of using double base chainto compute multi-scalar multiplication in Eurocrypt'09. We give a wayto compute multi-scalar multiplication by multi-base chain. Theoreticalanalysis shows that the length of scalar recoding can be reduced about10% which speeds up the multi-scalar multiplication. 4. Pairings have many applications in a lot of cryptographic protocols suchas identity-based encryption, the tripartite Diffie Hellman protocols. Forimplementing such protocols, it is essential to have an efficient algorithmof pairing computation. Miller proposed the first algorithm for computingpairings on Weierstrass curves. In 2009, Ar`ene et.al. showed how tocompute the Tate pairing on Edwards curves. But elliptic curves in moststandards can't be mapped to Edwards curves at present. However, Smartpointed out that some elliptic curves from IEEE, SECG standards can betransformed into Hessian curves. So we develop explicit formulas for computingTate pairings on Hessian curves originally. Analysis shows that ouralgorithm is fastest among all known algorithms for Tate pairing computationexcept for special Weierstrass curves with a4 = 0,a6 = b2.5. For elliptic curves over binary fields, the GHS method reduces the ellipticcurve discrete logarithm problem to a discrete logarithm problem forhyperelliptic curves and the hyperelliptic curve discrete logarithm problemcan be solved within subexponential time. The extended GHS attack hasstronger power, and the idea is to find an isogenous curve which is vulnerableunder the GHS attack. For elliptic curves over finite fields GF(2N),we give an alternative algorithm to find such isogenous curves.6. It is necessary to compute isogeny in the extended GHS attack. However,for general elliptic curves, the complexity of computing isogeny is exponential.Researcheres from Microsoft proposed a polynomial time algorithmto compute isogeny for elliptic curves over prime fields, only if the imaginequadratic field containing the endomorphism ring has small class number.Thus, the class number problem for imagine quadratic fields is an importantissue in cryptography. We prove the Sohen-Sonn conjecture assuming theextended Riemann hypothesis: the class number of an imagine quadraticfield is 3 if and only if Onod=3 and ?d≡3 (mod 4) is prime.