Research And Improvement On Elliptic Curve Scalar Multiplication Algorithm

1985, N.Koblitz and V.Miller proposed elliptic curve cryptography and thismakes cryptosystem been applied in elliptic curve. Compared with traditionalpublic key cryptosystem (e.g. RSA cryptosystem), elliptic curve cryptosystem canachieve the same degree of safety using relatively shorter key. Therefore, shorterkeys makes elliptic curve cryptosystem broader range of applications, many of thetiny devices today use elliptic curve cryptography for encryption and decryption.Calculation speed is the most concerned problem in our research andapplication of elliptic curve cryptography. In the elliptic curve cryptographyalgorithm, the most time-consuming operation is scalar multiplication, whichoccupies the elliptic curve algorithm for80%of the total amount of computation.Researchers improve the efficiency of the scalar multiplication calculation in avariety of ways, and the research results are quite good. We found that most of theimprovements are concentrated on the representation of a scalar, single-base,double-base, multi-base and so on. Our paper describes and compares somecommon single-base scalar multiplication method, and proposes a new scalarmultiplication method.Convert a binary representation into1’s complement subtraction form issimple and fast, but not all the convert is valid in reducing the Hamming weight ofthe binary representation. We propose a new scalar representation method based onthe simple and fast characteristics of the conversion from the binary representationinto1’s complement subtraction form, but we donot convert the entire binaryrepresentation, we select the part in binary representation that satisfies thetransition condition and convert it into1’s complement subtraction form. We callthe new scalar representation as Partly use1’s Complement Subtraction form,referred to as PCS form. NAF representation is widely used as a scalarrepresentation in the scalar multiplication method, it reduces the amount ofcalculation significantly. Finally, we compare the PCS form and NAFrepresentation, and propose the strengths of the PCS form.