(中南大学 信息科学与工程学院, 长沙 410083)
关键词:椭圆曲线密码体制; 标量乘法; 仿射坐标; 求逆; NAF
Fast algorithm for scalar multiplication in elliptic curves cryptography
LIU Lianhao, SHEN Yong
(School of Information Science & Engineering, Central South University, Changsha 410083, China)
Abstract:A field inversion is the most expensive operation on scalar multiplication, and the number of inversion determines the performance of scalar multiplication. Trading inversions for multiplications can decrease the number of inversion. Based on the idea,this paper proposed an efficient algorithm to compute 3P+Q directlyover Fp in terms of affine coordinates, its computational complexity was 1I+3S+16M, saving one field inversion compared to Ciet’s method. Moreover, also gave an improvement to compute 3kP directly, which was more efficient than k repeated 3P. Finally, applied the two algorithms to scalar multiplication combined with the representation of 3NAFw.The result suggests that the scalar multiplication using 3P+Q and 3kP is faster than traditional methods, such as NAF, NAF4 and so on, and the ration I/M of breakeven point can be reduced to 5.4. ......