C omputer Engineering and Applications 计算机工程与应用
2015，51（4）
1 引言
自 Kob litz 和 Miller 在 1985 年分别提出椭圆曲线密
码体 制（Elliptic Curve Cryptography，ECC）以来 ，由于
其安全性高，实现性能优等独特的优势被广泛地应用于
信息安全领域，并逐步成为国内外学者研究的重点。实
现椭圆曲线密码体制最耗时的运算是椭圆曲线标量乘
法，即
kP
的计算，其运算速度从整体上决定了 ECC 的
实现效率
[1-3]
。研究标量乘法通常可从两个方面来考虑，
一方面是研究标量
k
的有效表示，尽量减少上层运算，
如
k
的三元表示、NAF 及 w-NAF 等表示形式，Dimitr ov
[4]
等人提出将双基数系统
[5]
应用到椭圆曲线标量乘中，取
得了显著的效果。Mishra
[6]
等人改进了双基的思想，将
其扩展到多基，在素数域上提出了以 2，3，和 5 为底的多
基链来计算标量乘的快速算法，取得了更好的效果。另
一方面是对底层域快速算法进行研究，以减少底层域运
算量。在这一方面，Sakai
[7]
等人利用求逆转化为乘法的
思想推 导出 了
F
P
上计算 2
k
P 的 公式 ，极 大提 高 了效
率。Ciet
[8]
等人利用分母的最小公倍数思想，对
2P + Q、
3P、3P + Q、4P、4P + Q
等底层域运算进行优化。刘连浩
[9]
等人对
3P + Q
算法进行了改进，并同时给出了
F
P
上仿
射 坐标 系下的 3
k
P 递 推公式 ，大 量减 少 了求 逆 运算 。
Mishra
[6]
等人利用除法多项式提出了计算
5P
的快速算
法。之后徐凯平
[10]
等人给出了在仿射坐标系下直接计
算 5
k
P 的快速算法，进一步提高了效率。邓维勇
[11]
又进
一步改进了计算 3
k
P 的算法。此外，周梦
[12]
等人也对
F
P
上计算 2
k
P 和 3
k
P 的算法进行了一些改进。所有的这
素数域
GF(P)
上椭圆曲线快速标量乘算法的研究
赖忠喜，林君焕，张占军
LAI Zhongxi, LIN Jun huan, ZHANG Zhanjun
台州职业技术学院 机电工程学院，浙江 台州 318000
Coll ege of Mechanical and Electrical Engineering, Taizhou Vocational Technical, Taizhou, Zhejiang 318000, China
LAI Zho ngxi, LIN Junhuan, ZHAN G Zha njun. Study on fast method o f s calar multi pli cation on elliptic curves
over Prime field
GF(P)
. Computer Engineering and Applications, 2015, 51（4）：100-104 .
Abstract：Based on the idea of trading inve rsions for multiplications , an efficient algorithm is pro posed t o compute
7P
directly ov er prime field
F
P
in terms of affine coordinates, its computational complexity is I+23M+10S, saving one inver-
sion compared wit h tradition al method. Moreover, a new method is g iven to compute 7
k
P directly, which is more effi cient
than
k
repeated
7P
. Finally, apply these new algorithms to sca lar mul tiplication com bined with MBNS. The experimental
results s how that on the elliptic curves reco mmended by NIST, the efficiency of new algo rithm is superior to algorithm
given by Xu kai-ping and other traditional algorit hms, such as ternary-binary, 3-NAF, Di mitro algorithms, and the ration I/M
of break-even point can be reduced to 2 .4.
Key words：elliptic curve cryptosystem; sc alar multiplication; Multi Base Number System（MBNS）; field operation;
affine coordinate
摘 要：基于求逆转换为乘法的思想，利用仿射坐标提出了直接计算椭圆曲线上
7P
的算法，该算法运算量为 I+
23M+10S，比现有的算法节省了一次求逆运算，同时也给出了直接计算 7
k
P 的快速算法，该算法比重复计算
k
次
7P
更有效。结合多基数系统将这些新算法应用到标量乘法中，实验结果表明，在 NIST 推荐的椭圆曲线上，新算法的效
率优于徐凯平等人所提的算法及传统的 ternary-binary、3-NAF、Dimitro 算法，相交处 I/ M 可降至 2.4。
关键词：椭圆曲线密码体制；标量乘法；多基数系统；底层域运算；仿射坐标
文献标志码：A 中图分类号：TP309.7 doi：10.3778/j.issn.1002-8331.1303-0370
作者简介：赖忠喜（1984—），男，讲师，研究领域为加密技术，智能控制；林君焕（1982—），男，讲师，研究领域为加密技术，智能控
制；张占军（1979—），男，讲师，研究领域为加密技术，智能控制。E-mail：laizh ongxi@163.com
收稿日期：2013-03-24 修回日期：2013-06-13 文章编号：1002-8331（2015）04-0100-05
CNKI 网络优先出版：2013-07-0 3, http://www.cnki.net/kcms/detail/11.2127.TP.2 0130703.1144.019.html
100
评论0