AAM  >> Vol. 4 No. 4 (November 2015)

    GF(3n)椭圆曲线密码体制中标量乘快速算法研究
    Research on Fast Algorithms for Scalar Multiplication of Elliptic Curve Cryptography over GF (3n)

  • 全文下载: PDF(557KB) HTML   XML   PP.390-399   DOI: 10.12677/AAM.2015.44049  
  • 下载量: 511  浏览量: 2,000   国家自然科学基金支持

作者:  

申少芳,周梦:北京航空航天大学数学与系统科学学院,LMIB,北京

关键词:
椭圆曲线密码体制标量乘递推归纳滑动窗口Elliptic Curve Cryptography (ECC) Scalar Multiplication Recursion Sliding Window

摘要:
本文研究了特征为3的椭圆曲线密码体制中标量乘的快速算法,并针对底层运算和上层运算分别进行改进。在底层运算中,采用递推归纳、乘法代替求逆、立方代替乘法的思想提出在仿射坐标下直接计算3kP的算法,将求逆运算降至1次;在上层运算中,采用滑动窗口标量乘的方法,既有效减少了非零窗口的长度又减少了算法中3倍点总的运算量。

In this paper we investigate the fast algorithm of scalar multiplication based on Elliptic Curve Cryptography (ECC) over fields of characteristic three, and make improvements both in underlying operations and upper operations respectively. In the underlying operations, we deduce a formula of calculating 3kP directly under the affine coordinates based upon the idea of recursion, trading inversion for multiplication and trading multiplication for cube, which reduces the inversion to once; in the upper operations, we adopt the sliding window scalar multiplication method, which reduces the length of the non-zero windows and the total computations of 3P effectively.











文章引用:
申少芳, 周梦. GF(3n)椭圆曲线密码体制中标量乘快速算法研究[J]. 应用数学进展, 2015, 4(4): 390-399. http://dx.doi.org/10.12677/AAM.2015.44049

参考文献

[1] Koblitz, N. (1987) Elliptic Curve Cryptosystems. Mathematics of Computation, 48, 203-209.
http://dx.doi.org/10.1090/S0025-5718-1987-0866109-5
[2] 汪宏, 李宝, 于伟. 特征3有限域上椭圆曲线Montgomery算法[J]. 通信学报, 2008, 29(10): 25-29.
[3] Kim, K.H., Kim, S.I. and Choe, J.S. (2007) New Fast Algorithms for Arithmetic on Elliptic Curves over Fields of Characteristic Three. Cryptology ePrint Archive: Report 2007/179. http://eprint.iacr.org/2007/179
[4] 沈丽敏, 陈恭亮, 游永兴. 特征为3的域上的椭圆曲线点的快速计算[J]. 数学杂志, 2004, 24(5): 557-560.
[5] 李超. 特征为3的有限域上用于密码体制的椭圆曲线[J]. 通信保密,1994, 58(2): 42-47.
[6] Kim, K.H. (2007) A Note on Point Multiplication on Supersingular Elliptic Curves over Ternary Fields. Cryptology ePrint Archive: Report 2007/310. http://eprint.iacr.org/2007/310
[7] Hankerson, D., 等著, 张焕国, 译. 椭圆曲线密码学导论[M]. 北京: 电子工业出版社, 2005.
[8] Smart, N.P. and Westwood, E.J. (2003) Point Multiplication on Ordinary Elliptic Curves over Fields of Characteristic Three. Applicable Algebra in Engineering, Communication and Computing, 13, 485-497.
http://dx.doi.org/10.1007/s00200-002-0114-0
[9] Al-Daoud, E., Mahmod, R., Rushdan, M. and Kilicman, A. (2002) A New Addition Formula for Elliptic Curves over GF(2n). IEEE Transactions on Computers, 51, 972-975.
http://dx.doi.org/10.1109/TC.2002.1024743
[10] Solinas. J.A. (2000) Efficient Arithmetic on Koblitz Curves. Designs, Codes and Cryptography, 19, 195-249.
http://dx.doi.org/10.1023/A:1008306223194
[11] 侯红祥. 椭圆曲线上快速标量乘的研究[D]: [硕士学位论文]. 扬州: 扬州大学, 2008.
[12] Takagi, T., Yen, S.M. and Wu, B.C. (2004) Radix-r Non-Adjacent Form. Proceedings of 7th Information Security Conference, ISC 2004, Palo Alto, 27-29 September 2004, 2004, 99-110.
http://dx.doi.org/10.1007/978-3-540-30144-8_9
[13] 刘连浩, 申勇. 椭圆曲线密码体制中标量乘法的快速算法[J]. 计算机应用研究, 2009, 26(3): 1104-1108.