Fast Realization Of Scalar Multiplication Algorithms On Elliptic Curve

Elliptic Curve Cryptography(ECC)is an outstanding public key cryptosystem.However,there are still some key issues need to be further studied.The efficiency of scalar multiplication will affect the implementation efficiency of ECC.Therefore,it becomes the focus of intensive research of many cryptographers.The work of the paper are as follows:(1)A new representation algorithm of a scalar k in the form of d(1/2)a3b5c7z is proposed and a new multibase scalar multiplication algorithm relys on the representation.This representation is a combination of the method of Extended DBNS and point halving.In the United States National Institute of Standards and Technology recommended elliptic curve including NIST B-163,NIST B-233,NIST B-283,the experimental results show that the new approach can effectively reduce the complexity of the algorithm and improve the efficiency of scalar multiplication algorithm at the cost of a few pre-computations and storages,so that the scalar multiplication is more efficient.Compared to related work,the new approach is improved about 14.4%-41.4%.Therefore,the new algorithm can be applied to the limited computing and storage resources area.(2)A new efficient multi-scalar multiplication is proposed.This new algorithm is a combination of the method of sliding window method and multibase scalar multiplication algorithm,which effectively improves the efficiency of the elliptic curve cryptography.The experimental results show that the new algorithm costs less compared with Shamir's trick and interleaving with NAF's method.The new approach can effectively improve the efficiency of scalar multiplication algorithm,so that the scalar multiplication is more efficient.Compared to related work,the new approach is improved about 7.9%-20.6%.