椭圆曲线密码体制中快速标量乘方法研究

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (15): 112-115.

椭圆曲线密码体制中快速标量乘方法研究

徐凯平1，郑洪源1，刘锦峰2，顾晶晶1

1.南京航空航天大学信息科学与技术学院，南京 210016
2.重庆通信学院一系，重庆 400035

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-05-21 发布日期:2011-05-21

Study on fast method of scalar multiplication in elliptic curve cryptography

XU Kaiping1，ZHENG Hongyuan1，LIU Jinfeng2，GU Jingjing1

1.College of Information Science and Technology，Nanjing University of Aeronautics and Astronautics，Nanjing 210016，China
2.Chongqing Communication Institute，Chongqing 400035，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-05-21 Published:2011-05-21

摘要/Abstract

摘要： 椭圆曲线标量乘是椭圆密码体制中最耗时的运算，其中求逆运算的次数直接决定了标量乘法的性质。转换求逆为乘法运算能够降低求逆次数。根据这个思想，给出在素数域Fp上用仿射坐标直接计算5P的算法，比传统方法节省了两次求逆运算。同时还给出直接计算5kP的算法，比重复计算k次5P更有效。最后结合多基链把这两个新算法应用到标量乘中。实验结果表明，该方法与以往的标量乘算法相比，效率可提高6.5%~14%，相交处I/M可降到1.1。

关键词: 椭圆曲线密码体制, 标量乘法, 仿射坐标, 多基链, 求逆

Abstract: In the elliptic curve cryptosystem，scalar multiplication is the most expensive operation，and the number of inversion determines the performance of scalar multiplication.Trading inversions for multiplications can decrease the number of inversion.Based on it，an efficient algorithm is proposed to computer 5P directly over Fp in terms of affine coordinates，saving two field inversions compared to the traditional method.Moreover，a method is given to compute 5kP directly，which is more efficient than k repeated 5P.Finally，the two algorithms are applied to scalar multiplication combined with multibase chains.The experimental results show that the proposed method requires about 6.5%~14% less running time than traditional methods，and the ration I/M of break-even point can be reduced to 1.1.

Key words: Elliptic Curve Cryptography（ECC）, scalar multiplication, affine coordinates, multibase chains, field inversion

徐凯平1，郑洪源1，刘锦峰2，顾晶晶1. 椭圆曲线密码体制中快速标量乘方法研究[J]. 计算机工程与应用, 2011, 47(15): 112-115.

XU Kaiping1，ZHENG Hongyuan1，LIU Jinfeng2，GU Jingjing1. Study on fast method of scalar multiplication in elliptic curve cryptography[J]. Computer Engineering and Applications, 2011, 47(15): 112-115.

[1]	刘双根1，姚华童1，李发根2. Edwards曲线上抗SPA快速标量乘算法[J]. 计算机工程与应用, 2017, 53(1): 103-106.
[2]	李明. 新的适用于WSN网络的双方认证密钥协商协议[J]. 计算机工程与应用, 2016, 52(3): 100-102.
[3]	赖忠喜，张安洁，张占军. 椭圆曲线中一种计算7P和7kP的改进算法[J]. 计算机工程与应用, 2016, 52(1): 29-32.
[4]	赖忠喜，林君焕，张占军. 素数域[GF(P)]上椭圆曲线快速标量乘算法的研究[J]. 计算机工程与应用, 2015, 51(4): 100-104.
[5]	赖忠喜，张占军. 椭圆曲线底层域快速算法的优化[J]. 计算机工程与应用, 2015, 51(22): 115-118.
[6]	赖忠喜，张占军，陶东娅. 椭圆曲线底层域快速算法的研究[J]. 计算机工程与应用, 2014, 50(3): 67-70.
[7]	刘千里. 基于FPGA的逆QR分解SMI算法的并行实现方法[J]. 计算机工程与应用, 2012, 48(26): 71-75.
[8]	乔晓林，张建中. 基于ECC的多组织间的多级秘密共享方案[J]. 计算机工程与应用, 2011, 47(20): 56-57.
[9]	陈伯成¹，李英杰²，刘文煌¹，闫学为³. 应用于CRM的一类马氏链模型求解及其分析[J]. 计算机工程与应用, 2010, 46(4): 49-51.
[10]	童莲，钱江. 椭圆曲线中抗SPA和DPA攻击标量乘算法研究[J]. 计算机工程与应用, 2010, 46(35): 72-74.
[11]	陈振宇¹,袁毓林²,张秀松²,周强³. 亲属关系的逻辑意义及其自动推理[J]. 计算机工程与应用, 2009, 45(16): 43-47.
[12]	张鑫平,俞龙江,孙圣和. 基于身份的门限多重盲签名方案[J]. 计算机工程与应用, 2009, 45(15): 115-117.
[13]	王建峰,孟涛,孙圣和. 椭圆曲线有序多重签名中阈下信道及封闭方法[J]. 计算机工程与应用, 2009, 45(14): 79-80.
[14]	刘连浩¹,申勇^1,2. Koblitz椭圆曲线标量乘法的二次研究[J]. 计算机工程与应用, 2008, 44(4): 141-144.
[15]	殷新春,侯红祥. 一种定点快速标量乘算法的优化[J]. 计算机工程与应用, 2008, 44(4): 80-82.