Fast Algorithm For Scalar Multiplication In Elliptic Curves Cryptography

Since Koblitz and Miller independently proposed elliptic curve cryptosystem(ECC),the potential for the use of this public-key cryptosystems has been recognized.Encryption algorithm based on ECC allows for shorter key lengths,has a high safety property,faster speed, requires fewer storage and bandwidth compared to another famous public-key algorithm based on RSA.Because of these advantages,many professionals think that elliptic curve cryptosystem will be the common standards of public key cryptosystem.With regard to the fast implementation problems of ECC,the key factor is the computation of scalar multiplicationκP,and it is very difficult to make operation on the elliptic curve cryptosystem.So making operations quickly of scalar multiplication became the research focus of many cryptology experts.Firstly,some basic concepts,motivations and the developments are expounded in this thesis,the definition of scalar multiplication is inducted by introducing the elliptic curve discretelogarithm problems(ECDLP), the general algorithms for scalar multiplication are analyzed and discussed,advantages and disadvantages are concluded.And then an improved algorithm for computing 3P+Q in terms of affine coordinates is presented by trading inversions for multiplications, saving one field inversion compared to Ciet's method.Moreover,a novel algorithm for computing 3~κP(κ＞1) directly is given in this thesis,which is more efficient thanκrepeated 3P.The two new algorithms for 3~κP and 3P+Q are applied to improving the scalar multiplication combined with the representation of 3-NAF_w,the result suggests that the scalar multiplication using 3P+Q and 3~κP is faster than the traditional methods such as NAF.Of course,the algorithm for 3~κP can make the Double Base Number System(DBNS) get very good results when combined with the algorithm for 2~κP.The precomputation affects the efficiency of scalar multiplication.The fixed base comb algorithm is studied in detail,and an effective improvement for the algorithm is presented using two algorithms(2~κP and 2P+Q),which improve the efficiency of the precomputation stage and the primary cycle stage.And a new algorithm for computing 2P,3P and 5P simultaneity is given to improve the precomputation stage of window method,the algorithm costs only one field inversion and is better than the computations of 2P,3P and 5P respectively.Finally,the Koblitz curve is studied,the two steps(reduction moduloτ~m-1 andτ-adic NAF) to scalar multiplication of Koblitz curve is analyzed,and an improvement for scalar multiplication on Koblitz curves over a finite field of characteristic 2 and characteristic 3 is presented, which expresses scalarκwith the baseτ~2 rather thanτin the Sollinas's method,and reduced the length and Hamming ofκ.The result suggests that the method can improve the efficiency evidently.The research in this thesis improves the efficiency of scalar multiplication,and it will be good for ECC.