An Efficient Scalar Multiplication Algorithm on Montgomery-Form Elliptic Curve

Elliptic curve scalar multiplication is a basic operation of elliptic curve cryptosystem.Secure and efficient scalar multiplication algorithm will directly promote efficiency and security of elliptic curve cryptosystem.In this paper,the concept of Fibonacci series is extended and proposed,which is used to simplify point addition formula on Montgomery-Form elliptic curve and to get a new point addition formula fibAdd.The Fibonacci-type series of any positive integer k is computed by using Golden Ratio Addition Chain method.By combing of both methods,the paper constructs an efficient and secure scalar multiplication algorithm for any given integer k on Montgomery-Form elliptic curve is constructed.This new algorithm is 23% faster than GRAC-258 and is 39% faster than EAC-320 in the best case.Also,because the algorithm performs only point addition operation,and there is no need for doubling operation,it possesses naturally the ability to resist side channel attack.