基于多基表示的滑动窗口椭圆曲线多标量乘算法

doi:10.3969/j.issn.1006-2475.2019.01.003

计算机与现代化

基于多基表示的滑动窗口椭圆曲线多标量乘算法

(1.扬州大学广陵学院,江苏扬州225000;2.扬州大学信息工程学院,江苏扬州225000)

收稿日期:2018-05-11 出版日期:2019-01-30 发布日期:2019-01-30
作者简介:李艳梅(1991-),女,江苏徐州人,教师,硕士,研究方向:信息安全，E-mail: 1379628394@qq.com; 殷新春(1962-),男,江苏姜堰人,教授,博士生导师,博士,中国计算机学会高级会员(E200006553S),中国密码学会高级会员,中国计算机学会高性能计算专业委员会委员,研究方向:密码学,信息安全,软件质量保障,高性能计算; 邵梦丽(1991-),女,江苏盐城人,硕士,研究方向:信息安全。
基金资助:
国家自然科学基金资助项目(61472343); 扬州大学广陵学院自然科学研究重点资助项目(ZKZD18001)

Multi-scalar Multiplication Algorithm for Elliptic Curve Based on MBNS and Sliding Window

(1. Guangling College, Yangzhou University, Yangzhou 225000, China;
2. College of Information Engineering, Yangzhou University, Yangzhou 225000, China)

Received:2018-05-11 Online:2019-01-30 Published:2019-01-30

摘要/Abstract

摘要： 标量乘运算从整体上决定了椭圆曲线密码体制的快速实现效率，在一些椭圆曲线公钥密码体制中需要计算多标量乘。多基数链的标量表示长度更短、非零比特数目更少，较好地适用于椭圆曲线标量乘的快速计算。为了提高椭圆曲线密码的效率，在已有的二进制域和素域的标量乘算法的基础上，结合滑动窗口技术、多基算法，提出新的更高效的多标量乘算法。实验结果表明，新算法与传统Shamir算法和交错NAF算法相比，其所需的运算量更少，能有效地提高椭圆曲线多标量乘算法的效率，使多标量乘的运算更高效。相比于其他算法，新算法的计算效率比已有的多标量乘算法提高了约7.9%~20.6%。

关键词: 椭圆曲线密码体制, 多标量乘, 半点运算, 多基系统, 滑动窗口算法

Abstract: Scalar multiplication heavily determines the overall implementation efficiency of Elliptic Curve Cryptography(ECC), some elliptic curve cryptosystems of public keys require multi-scalar multiplication. Multi-base number system is very suitable for efficient computation of scalar multiplications of elliptic curves because of shorter representation length and less Hamming weight. In order to improve the efficiency of ECC, this paper proposes an efficient multi-scalar multiplication based on the existing scalar multiplication algorithm in binary fields and prime fields. This new algorithm is a combination of sliding window method and multi-base scalar multiplication algorithm. The experimental results show that the new algorithm costs less compared with Shamir’s trick and interleaving with NAF’s method. The new approach can effectively improve the efficiency of scalar multiplication algorithm, so that the scalar multiplication is more efficient. Compared to other algorithms, the new approach is improved about 7.9%~20.6%.

Key words: Elliptic Curve Cryptography(ECC), multi-scalar multiplication, point halving, MBNS, sliding window algorithm

中图分类号:

TP309

李艳梅1,殷新春1,2,邵梦丽2. 基于多基表示的滑动窗口椭圆曲线多标量乘算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2019.01.003.

LI Yan-mei1, YIN Xin-chun1,2,SHAO Meng-li2. Multi-scalar Multiplication Algorithm for Elliptic Curve Based on MBNS and Sliding Window[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2019.01.003.

参考文献

［1］ MILLER V S. Uses of elliptic curve in cryptography［C］// Proceedings of the CRYPTO85. 1986:417-426.
［2］ KOBLITZ N. Elliptic curve cryptosystems［J］. Mathematics of Computation, 1987,48(177):203-209.
［3］ DIMITROV V, IMBERT L, MISHRA P K. Efficient and secure elliptic curve point multiplication using double base chains［C］// Proceedings of the 11th International Conference on the Theory and Application of Cryptology and Information Security. 2005,3788:59-78.
［4］ MISHRA P K, DIMITROV V. Efficient quintuple formulas for elliptic curves and efficient scalar multiplication using multibase number representation［C］// International Conference on Information Security. 2007,4779:390-406.
［5］罗琴灵,蒋朝惠. 一种高效的多基标量乘扩展算法［J］. 计算机技术与发展, 2015,25(5):95-98.
［6］刘铎,戴一奇. 计算椭圆曲线上多标量乘的快速算法［J］. 计算机学报, 2008,31(7):1131-1137.
［7］邬可可,黄国伟,孔令晶. 一种灵活的椭圆曲线密码并行化方法［J］. 计算机与现代化, 2018(2):71-75.
［8］邬可可,高月芳,闫立军. 一种抵御差分侧信道分析的椭圆曲线同构方法［J］. 计算机与现代化, 2017(10):105-110.
［9］李艳梅,殷新春. 一种基于多基表示的标量乘扩展算法［J］. 小型微型计算机系统, 2017,38(12):2699-2702.
［10］赖忠喜,张占军,陶东娅. 椭圆曲线中直接计算7P的方法及其应用［J］. 计算机应用, 2013,33(7):1870-1874.
［11］PUROHIT G N, RAWAT A S. Fast scalar multiplication in ECC using the multi-base number system［J］. International Journal of Computer Science Issues, 2011,8(1):131-137.
［12］殷新春,赵荣,侯洪祥,等. 基于折半运算的快速双基数标量乘算法［J］. 计算机应用, 2009,29(5):1285-1288.
［13］邓维勇. 椭圆曲线密码体制中标量乘法研究［D］. 昆明:昆明理工大学, 2012.
［14］赖忠喜,林君焕,张占军. 素数域GF(P)上椭圆曲线快速标量乘算法的研究［J］. 计算机工程与应用, 2015,51(4):100-104.
［15］IEEE. IEEE Standard Computer Dictionary A Compilation of IEEE Standard Computer Glossaries［M］. IEEE, 1990.
［16］CHEN T S, HUANG K H, CHUNG Y F. Digital multi-signature scheme based on the elliptic curve cryptosystem［J］. Journal of Computer Science and Technology, 2004,19(4):570-573.
［12］SOLINAS J A. Low-weight Binary Representation for Pairs of Integers［R］. Centre for Applied Cryptographic Research, University of Waterloo, Combinatorics and Optimization Research Report CORR 2001-41, 2001.
［18］HANKERSON D, MENEZES A J, VANSTONE S A. Guide to Elliptic Curve Cryptography［M］. Springer-Verlag, 2003.
［19］殷新春,张海灵,杨婷. 基于多基数系统的优化多标量乘快速算法［J］. 通信学报, 2010,31(S1):122-126.
［20］PUROHIT G N, RAWAT A S, KUMAR M. Elliptic curve point multiplication using MBNR and point halving［J］. International Journal of Advanced Networking and Applications, 2012,3(5):1329-1337.
［21］DOCHE C, IMBERT L. Extended double-base number system with applications to elliptic curve cryptography［C］// International Conference on Cryptology in India. 2006(4329):335-348.
［22］KNUDSEN E W. Elliptic scalar multiplication using point halving［C］// Proceedings of the 11th International Conference on the Theory and Application of Cryptology and Information Security. 1999,1716:134-149.

[1]	胡越梅;温静静. ECC kP+lQ点乘算法的优化研究[J]. 计算机与现代化, 2012, 1(200): 163-04.
[2]	李春华;张玮. 一种ECC签密算法在RFID中的应用研究[J]. 计算机与现代化, 2010, 1(8): 191-193.

基于多基表示的滑动窗口椭圆曲线多标量乘算法

Multi-scalar Multiplication Algorithm for Elliptic Curve Based on MBNS and Sliding Window

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价