一种Montgomery型椭圆曲线的高效标量乘算法

摘要

椭圆曲线标量乘法是椭圆曲线密码系统的基本运算,安全高效的标量乘法将直接提高椭圆曲线密码系统的效率和安全性.本文将Fibonacei数列的概念进行了扩展,提出了Fibonacci型数列的概念,并用Fibonaeei型数列将Montgomery型曲线上点的加法运算公式进行了简化,得到了新的点加公式fibAdd.利用黄金比率加法链方法计算任意整数k的Fibonaeci型数列.将二种方法结合,构造了Montgomery型曲线上任意整数k的标量乘算法.本文提出的算法比GRAC-258快23%,在最优情况下比EAC-320快39%,同时,由于本算法只需要进行点的加法运算,不需要进行倍点运算,因而本算法天然地具有对抗边信道攻击的特性.%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.