Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (15): 112-115.

• 网络、通信、安全 • Previous Articles     Next Articles

Study on fast method of scalar multiplication in elliptic curve cryptography

XU Kaiping1,ZHENG Hongyuan1,LIU Jinfeng2,GU Jingjing1   

  1. 1.College of Information Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China
    2.Chongqing Communication Institute,Chongqing 400035,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-05-21 Published:2011-05-21

椭圆曲线密码体制中快速标量乘方法研究

徐凯平1,郑洪源1,刘锦峰2,顾晶晶1   

  1. 1.南京航空航天大学 信息科学与技术学院,南京 210016
    2.重庆通信学院 一系,重庆 400035

Abstract: In the elliptic curve cryptosystem,scalar multiplication is the most expensive operation,and the number of inversion determines the performance of scalar multiplication.Trading inversions for multiplications can decrease the number of inversion.Based on it,an efficient algorithm is proposed to computer 5P directly over Fp in terms of affine coordinates,saving two field inversions compared to the traditional method.Moreover,a method is given to compute 5kP directly,which is more efficient than k repeated 5P.Finally,the two algorithms are applied to scalar multiplication combined with multibase chains.The experimental results show that the proposed method requires about 6.5%~14% less running time than traditional methods,and the ration I/M of break-even point can be reduced to 1.1.

Key words: Elliptic Curve Cryptography(ECC), scalar multiplication, affine coordinates, multibase chains, field inversion

摘要: 椭圆曲线标量乘是椭圆密码体制中最耗时的运算,其中求逆运算的次数直接决定了标量乘法的性质。转换求逆为乘法运算能够降低求逆次数。根据这个思想,给出在素数域Fp上用仿射坐标直接计算5P的算法,比传统方法节省了两次求逆运算。同时还给出直接计算5kP的算法,比重复计算k次5P更有效。最后结合多基链把这两个新算法应用到标量乘中。实验结果表明,该方法与以往的标量乘算法相比,效率可提高6.5%~14%,相交处I/M可降到1.1。

关键词: 椭圆曲线密码体制, 标量乘法, 仿射坐标, 多基链, 求逆