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

An Efficient Scalar Multiplication Algorithm on Montgomery-Form Elliptic Curve

作　　者：庞世春[1,2] 刘淑芬[1] 从福仲[2] 姚志林[1] 

机构地区：[1]吉林大学计算机科学与技术学院,吉林长春130022 [2]空军航空大学基础部,吉林长春130012

出　　处：《电子学报》2011年第4期865-868,共4页Acta Electronica Sinica

基　　金：吉林省重大项目(No.20060328);国家科技攻关项目(No.2004BA907A20)

摘　　要：椭圆曲线标量乘法是椭圆曲线密码系统的基本运算,安全高效的标量乘法将直接提高椭圆曲线密码系统的效率和安全性.本文将Fibonacci数列的概念进行了扩展,提出了Fibonacci型数列的概念,并用Fibonacci型数列将Montgomery型曲线上点的加法运算公式进行了简化,得到了新的点加公式fibAdd.利用黄金比率加法链方法计算任意整数k的Fibonacci型数列.将二种方法结合,构造了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.

关 键 词：标量乘法 Montgomery曲线 黄金比率加法链 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]