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

Vol.04 No.04(2015), Article ID:16451,10 pages
10.12677/AAM.2015.44049

Research on Fast Algorithms for Scalar Multiplication of Elliptic Curve Cryptography over GF (3n)

Shaofang Shen, Meng Zhou*

School of Mathematics and System Science, LMIB, Beihang University, Beijing

Received: Nov. 9th, 2015; accepted: Nov. 25th, 2015; published: Nov. 30th, 2015

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.

Keywords:Elliptic Curve Cryptography (ECC), Scalar Multiplication, Recursion, Sliding Window

GF(3n)椭圆曲线密码体制中标量乘快速算法研究

1. 引言

1) ECC安全性高。在同样的攻破时间内，ECC需要的密钥比RSA要短得多，如160 bite的ECC和1024 bite的RSA有相同的安全性；

2) ECC实现性强。密钥短、存储空间占用少、宽带要求低、运算处理时间短等特点均有利于ECC实现；

3) ECC具有多重选择性。在相同基域下，ECC可以通过改变椭圆曲线方程的系数得到不同的加密算法，拥有更多的选择性，而对于给定的素数只能对应唯一的一个RSA算法。

2. ECC基础知识

2.1. 椭圆曲线的定义及分类

(2.1)

(1)

(2.2)

(2)

(2.3)

(3)

(2.4)

2.2. 椭圆曲线上点的运算法则

(1) 点加

(2) 倍点

(1) 点加

(2.5)

(2) 倍点

(2.6)

3. GF(3n)上底层域快速算法综述

4. GF(3n)上底层域快速算法介绍

4.1. 3P、9P的直接计算公式

(将分子上的多项式变换成立方项相加减的形式)

(4.1)

(4.2)

(4.3)

(4.4)

4.2. 3kP的直接计算公式

，令

(4.5)

4.3. 算法性能比较

5. 基于滑动窗口标量乘算法改进

5.1. 算法介绍

Table 1. Comparison of different methods in the underlying domain

(5.1)

(5.2)

5.2. 算法性能分析与结论

(5.3)

6. 结束语

Research on Fast Algorithms for Scalar Multiplication of Elliptic Curve Cryptography over GF (3n)[J]. 应用数学进展, 2015, 04(04): 390-399. http://dx.doi.org/10.12677/AAM.2015.44049

1. 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. 2. 汪宏, 李宝, 于伟. 特征3有限域上椭圆曲线Montgomery算法[J]. 通信学报, 2008, 29(10): 25-29.

3. 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. 4. 沈丽敏, 陈恭亮, 游永兴. 特征为3的域上的椭圆曲线点的快速计算[J]. 数学杂志, 2004, 24(5): 557-560.

5. 5. 李超. 特征为3的有限域上用于密码体制的椭圆曲线[J]. 通信保密,1994, 58(2): 42-47.

6. 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. 7. Hankerson, D., 等著, 张焕国, 译. 椭圆曲线密码学导论[M]. 北京: 电子工业出版社, 2005.

8. 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. 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. 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. 11. 侯红祥. 椭圆曲线上快速标量乘的研究[D]: [硕士学位论文]. 扬州: 扬州大学, 2008.

12. 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. 13. 刘连浩, 申勇. 椭圆曲线密码体制中标量乘法的快速算法[J]. 计算机应用研究, 2009, 26(3): 1104-1108.

14. NOTES

*通讯作者。