Research on Fast Algorithms for Scalar Multiplication of Elliptic Curve over GF(2m)

作者: 孙 俐 , 周 梦 :北京航空航天大学数学与系统科学学院LMIB,北京;

关键词: 椭圆曲线标量乘加速算法求逆Elliptic Curve Scalar Multiplication Accelerated Algorithm Inversion

椭圆曲线密码自提出以来便因其优良的性质而得到了广泛的应用。本文针对椭圆曲线上关键的标量乘运算,根据将耗时较多的求逆转换为乘法的思想,推导出了 上计算 的递推公式,将求逆次数减少到一次。同时提出了计算 的加速算法,比直接计算节省了2次求逆。分析表明,在逆乘率分别大于7.4和5.9时,改进算法的效率优于逐次计算。

Elliptic curve cryptography finds numerous applications because of its excellent and unique properties. This paper focused on the scalar multiplication of Elliptic curve. We proposed the recursion formula to compute over based on the idea of trading inversions for multiplications, which reduced the inversion to only once. At the same time, this paper also gave an ac- celerated algorithm for computing , which saved two inversions compared to computing it directly. The result suggests that the proposed algorithms are more efficient than the normal al- gorithms when the ratios are more than 7.4 and 5.9 respectively.

文章引用: 孙 俐 , 周 梦 (2014) GF(2m)上椭圆曲线标量乘快速算法研究。 计算机科学与应用, 4, 76-84. doi: 10.12677/CSA.2014.44013


[1] Miller, V. (1986) Use of elliptic curves in cryptography. Lecture Notes in Computer Science, 218, 417-426.

[2] Koblitz, N. (1987) Elliptic curve crystosyestems. Mathematics of Computation, 48, 203-209

[3] Fong, K., et al. (2004) Field inversion and point halving revisited. IEEE Transactions on Computers, 53, 1047-1059.

[4] Guajardo, J. and Christof, P. (1997) Efficient algorithms for elliptic curve cryptosystems. Springer Berlin Heidelberg, Berlin.

[5] Sakai, Y. and Kouichi, S. (2001) Efficient scalar multiplications on elliptic curves with direct computations of several doublings. IEICE Transactions on Fundamentals of Electronics. Communications and Computer Sciences, 84, 120-129.

[6] Ciet, M., et al. (2006) Trading inversions for multiplications in elliptic curve cryptography. Designs, Codes and Cryp- tography, 39, 189-206.

[7] 刘连浩, 申勇 (2009) 椭圆曲线密码体制中标量乘法的快速算法. 计算机应用研究, 3, 1104-1108.

[8] Hankerson, D., Julio, L.H. and Alfred, M. (2000) Software implementation of elliptic curve cryptography over binary fields. Lecture Notes in Computer Science, 1965, 1-24.