椭圆曲线中直接计算7P的方法及其应用

doi:10.11772/j.issn.1001-9081.2013.07.1870

计算机应用 ›› 2013, Vol. 33 ›› Issue (07): 1870-1874.DOI: 10.11772/j.issn.1001-9081.2013.07.1870

椭圆曲线中直接计算7P的方法及其应用

赖忠喜,张占军,陶东娅

台州职业技术学院机电工程学院，浙江台州 318000

收稿日期:2013-01-25 修回日期:2013-03-01 出版日期:2013-07-01 发布日期:2013-07-06
通讯作者: 赖忠喜
作者简介:赖忠喜(1984-)，男，浙江台州人，讲师，硕士，主要研究方向：信息安全、智能控制；张占军(1979-)，男，内蒙古集宁人，讲师，硕士，主要研究方向：信息安全、智能控制；陶东娅(1983-)，女，浙江台州人，讲师，硕士，主要研究方向：信息安全、智能控制。

Algorithm for directly computing 7P elliptic curves and its application

LAI Zhongxi,ZHANG Zhanjun,TAO Dongya

College of Mechanical and Electrical Engineering, Taizhou Vocational and Technical College, Taizhou Zhejiang 318000, China

Received:2013-01-25 Revised:2013-03-01 Online:2013-07-06 Published:2013-07-01
Contact: LAI Zhongxi

摘要/Abstract

摘要： 为了提高椭圆曲线标量乘法的效率，根据将求逆转换为乘法运算的思想，提出了在二进制域F2n上用仿射坐标直接计算7P的两种算法。两种算法分别通过引入公因子和除法多项式来计算7P，其运算量分别为2I+7S+14M和I+6S+20M，比Purohit等提出的算法(PUROHIT G N, RAWAT S A, KUMAR M. Elliptic curve point multiplication using MBNR and Point halving. International Journal of Advanced Networking and Applications, 2012, 3(5)： 1329-1337)分别节省了一次和两次求逆运算。同时还给出直接计算7kP的快速算法，该算法比重复计算k次7P更有效。最后结合半点运算和扩展多基表示形式将这些新算法应用到标量乘法中。实验结果表明，在美国国家标准技术研究所(NIST)推荐的椭圆曲线上，当预存储点的个数为2和 5时，新算法比Purohit算法效率提高了30%和37%,比洪银芳等所提的算法(洪银芳，桂丰，丁勇.基于半点和多基表示的标量乘法扩展算法.计算机工程,2011,37(4)：163-165)效率提高了9%和13%。新算法以增加少量的预计算存储为代价，能有效降低标量乘法的运算量。

关键词: 椭圆曲线密码体制, 标量乘法, 半点运算, 扩展多基表示, 仿射坐标

Abstract: To raise the efficiency of scalar multiplication on elliptic curve, based on the idea of trading inversions for multiplications, two efficient algorithms were proposed to compute 7P directly over binary field F2n in terms of affine coordinates. The common divisor and division polynomial were respectively introduced to compute 7P in two algorithms, their computational complexity were 2I+7S+14M and I+6S+20M, saving one inversion and two inversions respectively, compared with the Purohit′s method (PUROHIT G N, RAWAT S A, KUMAR M. Elliptic curve point multiplication using MBNR and Point halving. International Journal of Advanced Networking and Applications, 2012, 3(5)： 1329-1337). Moreover, a new method was given to compute 7kP directly, which was more efficient than computing 7P for k times. Finally, these new algorithms were applied to scalar multiplication combined with point halving and extended MBNS(Multi-Base Number Representation). The experimental results show that the efficiency of the new method is improved about 30%-37% over the Purohit's method and about 9%-13% over the Hong's method (HONG Y F, GUI F, DING Y. Extended algorithm for scalar multiplication based on point halving and MBNS.Computer Engineering, 2011, 37(4)： 163-165) on the elliptic curves recommended by NIST(National Institute of Standards and Technology), when the number of pre-storages points is 2 and 5. The new method can reduce the computational complexity of scalar multiplication efficiently with a few more pre-computation storage.

Key words: Elliptic Curve Cryptosystem（ECC）, scalar multiplication, point halving, extended Multi-Base Number Representation (MBNR), affine coordinate

中图分类号:

TP309.7

赖忠喜张占军陶东娅. 椭圆曲线中直接计算7P的方法及其应用[J]. 计算机应用, 2013, 33(07): 1870-1874.

LAI Zhongxi ZHANG Zhanjun TAO Dongya. Algorithm for directly computing 7P elliptic curves and its application[J]. Journal of Computer Applications, 2013, 33(07): 1870-1874.

参考文献

［1］赖忠喜，陶东娅.一种基于半点运算与双基表示的双标量乘算法［J］.计算机应用与软件,2012,29(9)：293-295.

［2］刘连浩，申勇.椭圆曲线密码体制中标量乘法的快速算法［J］.计算机应用研究,2009,26(3)：1104-1107.

［3］洪银芳，桂丰，丁勇.基于半点和多基表示的标量乘法扩展算法［J］.计算机工程,2011,37(4)：163-165.

［4］DOCHE C, IMBERT L. Extended double-base number system with applications to elliptic curve cryptography ［C］// Proceedings of the 7th International Conference on Cryptology, LNCS 4329. Berlin： Springer-Verlag, 2006： 335-348.

［5］CIET M, JOYE M, LAUTER K, et al. Trading inversions for multiplications in elliptic curve cryptography ［J］. Designs Codes and Cryptography，2006, 39(2)：189-206.

［6］MISHRA P K, DIMITROV V. Efficient quintuple formulas for elliptic curves and efficient scalar multiplication using multibase number representation ［C］// Proceedings of the 10th Information Security Conference. Berlin： Springer-Verlag, 2007：390-406.

［7］PUROHIT G N, RAWAT S A. Fast scalar multiplication in ECC using the multi base number system ［J］. International Journal of Computer Science Issues, 2011, 8(1)： 131-137.

［8］邓维勇.椭圆曲线密码体制中标量乘法研究［D］.昆明：昆明理工大学，2012.

［9］HANKERSO D, MENEZES A., VANSTONE S. Guide to elliptic curve cryptography ［M］. Berlin： Springer-Verlag, 2004： 76-81.

［10］殷新春，赵荣，侯红详，等.基于折半运算的快速双基数标量乘算法［J］.计算机应用,2009,29(5)：1285-1288.

［11］许凯平，郑洪源，刘锦峰,等.椭圆曲线密码体制中快速标量乘方法研究［J］.计算机工程与应用,2011,47(15)：112-115.

［12］WONG K W, LEE E C W, CHENG L M, et al. Fast elliptic scalar multiplication using new double-base chain and point halving ［J］. Applied Mathematics and Computation, 2006, 183(2)： 1000-1007.

［13］DIMITROV V, IMVERT L, MISHRA P K. Efficient and secure elliptic curve point multiplication using double base chain ［C］// Proceedings of the 11th International Conference on the Theory and Application of Cryptology and Information Security, LNCS 3788. Berlin： Springer-Verlag, 2005： 59-78.

［14］PUROHIT G N, RAWAT S A, KUMAR M. Elliptic curve point multiplication using MBNR and point halving ［J］. International Journal of Advanced Networking and Applications, 2012, 3(5)： 1329-1337.

[1]	王正义赵俊阁. 基于带符号双基数系统的抗功耗攻击方案算法[J]. 计算机应用, 2011, 31(11): 2973-2974.
[2]	贺毅朝曲文龙孟永刚. Edwards曲线上的快速标量乘法算法[J]. 计算机应用, 2010, 30(3): 668-670.
[3]	张秋余孙战辉. 椭圆曲线数字签名中阈下信道通信研究[J]. 计算机应用, 2010, 30(1): 196-197.
[4]	殷新春赵荣侯红祥谢立. 基于折半运算的快速双基数标量乘算法[J]. 计算机应用, 2009, 29(05): 1285-1292.
[5]	殷新春侯红祥谢立. 一种基于加法链的快速标量乘算法[J]. 计算机应用, 2008, 28(1): 56-58,6.
[6]	李明秦宝东李大兴. Koblitz曲线密码体制中一种可抵抗边带信道攻击的标量乘算法[J]. 计算机应用, 2007, 27(8): 1926-1928.
[7]	谭利平李方伟. 移动通信系统中的认证与密钥协商协议[J]. 计算机应用, 2007, 27(6): 1343-1344.
[8]	杨先文李峥. 一种GF(2m)上椭圆曲线点运算的混合坐标系[J]. 计算机应用, 2007, (12): 2962-2964.
[9]	彭长根;李祥;罗文俊. 可转换签密的几种改进方案[J]. 计算机应用, 2006, 26(5): 1068-1070.

椭圆曲线中直接计算7P的方法及其应用

Algorithm for directly computing 7P elliptic curves and its application

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics