Efficient Implementation Of Scalar Multiplication On Ec And Hec

Elliptic curve cryptosystem (ECC), which is independently proposed by Miller and Koblitz, is based on the elliptic curve discrete logarithm problem. The basic operation in ECC is the scalar multiplication sP, where P is a point on elliptic curves and s is an integer.Transforming the scalar into some special forms with lower Hamming weight (the number of non-zero bits) helps speeding up scalar multiplication. The algorithms for computing scalar multiplication are mostly based on the binary expansions of scalars, such as the non-adjacent form (NAF) and wNAF (sliding window method). Representing scalars using more bases can speed up the scalar multiplication further, such as double-base chain method. Some other methods also proposed based on the idea of double-base chain, such as multi-base chain, extended double-base chain and tree-based double-base chain methods. These representations of integers are produced by greedy algorithms, and their average Hamming weights are difficult to be analyzed. The variables in these methods are chosen by experience or simulations. Furthermore, it is not easy to get the average cost of these methods.mbNAF, wmbNAF and extended wmbNAF methods are also double-base (multi-base) methods, which were proposed by Longa and Miri in2008. In this thesis, we give a formal analysis of the Hamming weight of the extended wmbNAF method for scalar multiplication on general elliptic curves over large prime fields. After that, the cost of this method is compared with NAF and other double-base methods. The analysis shows that we obtain the most efficient algorithm when using (2,3,5)NAF{1,1,0}, which is9.0%faster than the NAF method without extra storage requirement. Moreover, the recoding algorithm of the extended wmbNAF method is just as simple and fast as that of the NAF method.Some identity-based cryptographyic schemes are designed using the Weil/Tate parings on supersingular elliptic curves, and some of them are more efficient in terms of bandwidth over finite field of characteristic three. Smart et al showed how to implement scalar multiplication efficiently elliptic curves over finite field of character three. In this thesis, we design faster formulas for point operations on these curves. We also further speed up scalar multiplication on these curves using extended wmbNAF method. The analysis shows that the scalar multiplication on ternary fields using the (2,3)NAFo,3method is at least22.5%faster than the triple-and-add method proposed by Smart et al.Bernstein obtained a very fast implementation for scalar multiplication on general elliptic curves using binary Edwards curves and Montgomery ladder method. Typically a general curve has a number of equivalent binary Edwards curves, and working with some may be more efficient; for example one binary Edwards curve with sparse variants from many curves that are produced according to the birationally equivalent original Weierstrass curve. In this thesis, we propose a fast algorithm that converts elliptic curves in Weierstrass form into binary Edwards form. The new algorithm is25.2%faster than what has appeared before according to our theoretical analysis. The theorem in this paper also gives the details of birationally equivalence between ordinary elliptic curves and binary Edwards curves. Simulation results based on Magma and NTL implementations verifies the proposed claims.Scalar multiplication on hyperelliptic curves is similar to that on elliptic curves. Montgomery Ladder algorithm is an efficient and important algorithm to implement scalar multiplications for being against side channel attacks. In this thesis, we improve the addition formulae for divisor classes for the first time to speed up Montgomery Ladder algorithm. The analysis and experiment shows that the new formulae are faster than previous ones. Over fields of character two and Type â…¡ curves, the new formulae is4%-8.4%faster than the ones appeared before. And the Montgomery Ladder algorithm implemented in this paper is security against side channel attacks.In the last part of this thesis, we implement scalar multiplication using pipeline method. Over field Fp with log2p=n, the analysis shows that our implementation is about12.5%faster than Mishra's scheme. When using wNAF method, we get more improvement, which is about14.3%.