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

DOI: 10.12677/AAM.2015.44049, PDF, HTML, XML, 下载: 1,564  浏览: 4,973  国家自然科学基金支持

Abstract: 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.

 [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.