利用多基数系统的高效椭圆曲线多标量乘算法

doi:10.19678/j.issn.1000-3428.0057438

计算机工程 ›› 2021, Vol. 47 ›› Issue (2): 182-187. doi: 10.19678/j.issn.1000-3428.0057438

利用多基数系统的高效椭圆曲线多标量乘算法

尤文珠, 葛海波

西安邮电大学电子工程学院, 西安 710121

收稿日期:2020-02-20 修回日期:2020-03-23 出版日期:2021-02-15 发布日期:2020-03-27
作者简介:尤文珠(1995-),女,硕士研究生,主研方向为物联网安全;葛海波,教授。
基金资助:
陕西省自然科学基金（2011JM8038）；陕西省重点产业创新链（群）项目（S2019-YF-ZDCXL-ZDLGY-0098）。

Efficient Algorithm for Multi-Scalar Multiplication of Elliptic Curves Using Multi-Base Number System

YOU Wenzhu, GE Haibo

School of Electronic Engineering, Xi'an University of Posts and Telecommunications, Xi'an 710121, China

Received:2020-02-20 Revised:2020-03-23 Online:2021-02-15 Published:2020-03-27

摘要/Abstract

摘要： 针对椭圆曲线密码体制中标量乘与多标量乘运算耗时过长的问题，设计以2、3、7为基元的多基整数表示方法，并结合多基数系统（MBNS）及滑动窗口算法，提出基于MBNS滑动窗口（Sliding MBNS）和交错MBNS滑动窗口（I-MBNS）的多标量乘快速算法，分析并比较两种多标量乘快速算法在二元域和素域及不同窗口宽度下的平均运算量。实验结果表明，与Shamir和交错非邻接形式算法相比，Sliding MBNS和I-MBNS算法在标量长度为160 bit的二元域上的平均运算量分别减少了10.00%、1.69%和13.00%、4.97%，具有更低的运算复杂度和更高的标量乘算法效率。

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

Abstract: To address the time-consuming scalar multiplication and multi-scalar multiplication in Elliptic Curve Cryptography(ECC) system,this paper designs a multi-base integer representation method based on 2,3 and 7.On this basis,it combines Multi-Base Number System(MBNS) and sliding window algorithm to proposes two fast multi-scalar multiplication algorithms based on MBNS sliding window and interleaved MBNS sliding window,called Sliding MBNS and I-MBNS.The average computation amounts of two fast multi-scalar multiplication algorithms in the binary domain,prime domain and different window widths are analyzed and compared.Experimental results show that compared with the Shamir and interleaved Non-Adjacent Form(NAF) algorithm,Sliding MBNS and I-MBNS reduce the average computation amount by 10.0%,1.69% and 13.00%,4.97% respectively on a binary field with a scalar length of 160 bit.Their computational complexity is reduced,and the efficiency of the scalar multiplication algorithm is improved.

Key words: multi-scalar multiplication, Elliptic Curve Cryptography(ECC), Multi-Base Number System(MBNS), public key cryptosystem, sliding window algorithm

中图分类号:

TP309

尤文珠, 葛海波. 利用多基数系统的高效椭圆曲线多标量乘算法[J]. 计算机工程, 2021, 47(2): 182-187.

YOU Wenzhu, GE Haibo. Efficient Algorithm for Multi-Scalar Multiplication of Elliptic Curves Using Multi-Base Number System[J]. Computer Engineering, 2021, 47(2): 182-187.

https://www.ecice06.com/CN/Y2021/V47/I2/182

图/表 8

20210225092252

20210225092255

20210225092259

20210225092302

20210225092304

20210225092307

20210225092312

20210225092315

参考文献 22

[1]	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.
[2]	MILLER V S.Use of elliptic curves in cryptography[C]//Proceedings of Conference on the Theory and Application of Cryptographic Techniques.Berlin,Germany:Springer,1985:417-426.
[3]	KOBLITZ N.Elliptic curve cryptosystems[J].Mathematics of Computation,1987,48(177):203-209.
[4]	WAZIRI V O,DANLADI H,ALHASSAN J K,et al.Web-cloud-based security services based-on elliptic curves cryptosystem[J].International Journal of Computer Applications,2015,115(23):12-18.
[5]	EZZOUAK S,AZIZI A.Improving scalar multiplication over elliptic curves[C]//Proceedings of the 2nd Inter-national Conference on Applied Mathematics.[S.l.]:AIP Publishing LLC,2019:1-9.
[6]	YIN Xinchun,ZHANG Hailing,ZHAO Rong.Fast multi-scalar multiplication using the multi-based number system[C]//Proceedings of 2009 International Conference on Computational Intelligence and Software Engineering.Washington D.C.,USA:IEEE Press,2009:1-4.
[7]	YI Jiang,YONG Shen,ZHU Qingyi.A lightweight key agreement protocol based on Chinese remainder theorem and ECDH for smart homes[J].Sensors,2020,20(5):1357-1369.
[8]	CHEN Houyou,MA Chuangui.A multiple scalar multi-plications algorithm in the elliptic curve cryptosystem[J].Journal of Software,2011,22(4):782-788.(in Chinese)陈厚友,马传贵.椭圆曲线密码中一种多标量乘算法[J].软件学报,2011,22(4):782-788.
[9]	SOLINAS J A.Low-weight binary representations for pairs of integers:CORR 2001-41[R].Centre for Applied Cryptographic Research,2001:1-7.
[10]	LI Yanmei,YIN Xinchun,SHAO Mengli.Multi-scalar multiplication algorithm for elliptic curve based on MBNS and sliding window[J].Computer and Modernization,2019,281(1):15-20.(in Chinese)李艳梅,殷新春,邵梦丽.基于多基表示的滑动窗口椭圆曲线多标量乘算法[J].计算机与现代化,2019,281(1):15-20.
[11]	DIMITROV V,IMBERT L,MISHRA P K.Efficient and secure elliptic curve point multiplication using double-base chains[C]//Proceedings of International Conference on the Theory and Application of Cryptology and Information Security.Berlin,Germany:Springer,2005:59-78.
[12]	MISHRA P K,DIMITROV V.Efficient quintuple formulas for elliptic curves and efficient scalar multiplication using multibase number representation[C]//Proceedings of Inter-national Conference on Information Security.Berlin,Germany:Springer,2007:390-406.
[13]	LIU Duo,DAI Yiqi.A new algorithm of elliptic curve multi-scalar multiplication[J].Chinese Journal of Computers,2008,31(7):1131-1137.(in Chinese)刘铎,戴一奇.计算椭圆曲线上多标量乘的快速算法[J].计算机学报,2008,31(7):1131-1137.
[14]	ANAGREH M,SAMSUDIN A,OMAR M A.Parallel method for computing elliptic curve scalar multiplication based on MOF[J].International Arab Journal of Informa-tion Technology,2014,11(6):521-525.
[15]	KHLEBORODOV D.Fast elliptic curve point multiplica-tion based on window non-adjacent form method[J].Applied Mathematics and Computation,2018,334:41-59.
[16]	ANAGREH M,VAINIKKO E,LAUD P.Accelerate performance for elliptic curve scalar multiplication based on NAF by parallel computing[C]//Proceedings of the 5th International Conference on Information Systems Security and Privacy.Berlin,Germany:Springer,2019:24-45.
[17]	ADIKARI J,DIMITROV V S,MISHRA P K.Fast multiple point multiplication on elliptic curves over prime and binary fields using the double-base number system[EB/OL].[2020-01-15].https://www.iacr.org/cryptodb/data/paper.php?pubkey=17822.
[18]	SEO H,KIM H,PARK T,et al.Fixed-base comb with window-Non-Adjacent Form(NAF) method for scalar multiplication[J].Sensors,2013,13(7):9483-9512.
[19]	HAO Yanhua,LI Lei,WANG Yumin.Efficient scalar multiplication algorithm using multibase chains[J].Journal of University of Electronic Science and Technology of China,2008,37(6):868-871.(in Chinese)郝艳华,李磊,王育民.利用多基链计算椭圆曲线标量乘的高效算法[J].电子科技大学学报,2008,37(6):868-871.
[20]	LI Yanmei,YIN Xinchun.Extended algorithm for scalar multiplication based on MBNS[J].Journal of Chinese Computer Systems,2017,38(12):2699-2702.(in Chinese)李艳梅,殷新春.一种基于多基表示的标量乘扩展算法[J].小型微型计算机系统,2017,38(12):2699-2702.
[21]	ELGAMAL T.A public key cryptosystem and a signature scheme based on discrete logarithms[J].IEEE Transactions on Information Theory,1985,31(4):469-472.
[22]	HANKERSON D,MENEZES A J,VANSTONE S A.Guide to elliptic curve cryptography[M].Berlin,Germany:Springer-Verlag,2003.

选择文件类型/文献管理软件名称

选择包含的内容

利用多基数系统的高效椭圆曲线多标量乘算法

Efficient Algorithm for Multi-Scalar Multiplication of Elliptic Curves Using Multi-Base Number System

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 22

相关文章 15

编辑推荐

Metrics

本文评价

[1]	陈億, 杨萱, 曾涵, 李伟. 一种高速可伸缩的双域Montgomery模乘器架构[J]. 计算机工程, 2023, 49(8): 283-290.
[2]	丁晓晖, 曹素珍, 王彩芬. 智能合约辅助下满足前后向安全的动态可搜索加密方案[J]. 计算机工程, 2022, 48(7): 141-150.
[3]	吴昆, 魏国珩. 基于ECC的无证书WSN广播信息认证方案[J]. 计算机工程, 2020, 46(12): 157-162,200.
[4]	谷建光. 抗能量分析攻击的门限窗口NAF标量乘算法[J]. 计算机工程, 2019, 45(8): 296-299,308.
[5]	曹素珍,戴文洁,孙晗,王秀娅. 一种新的无证书聚合签名方案[J]. 计算机工程, 2017, 43(8): 184-187.
[6]	邬可可,李慧云,闫立军. 一种防御差分功耗分析的ECC同种映射模型[J]. 计算机工程, 2017, 43(10): 115-119,125.
[7]	刘博雅,刘年义,杨亚涛,李子臣. 基于椭圆曲线密码的无线射频识别双向认证协议[J]. 计算机工程, 2017, 43(1): 196-200.
[8]	沈海波,陈勇昌. 联邦物联网中的认证机制研究[J]. 计算机工程, 2016, 42(9): 110-115.
[9]	汤永利,王菲菲,闫玺玺,李子臣. 高效可证明安全的无证书签名方案[J]. 计算机工程, 2016, 42(3): 156-160.
[10]	刘筱茜,赵一鸣. 基于多变量公钥密码体制的环签名变体方案[J]. 计算机工程, 2015, 41(2): 96-99.
[11]	孙国栋,苏盛辉,徐茂智. 基于REESSE1+公钥密码体制的概率加密[J]. 计算机工程, 2014, 40(12): 78-82.
[12]	王天成，张建中. 基于椭圆曲线的代理多重盲签名方案[J]. 计算机工程, 2013, 39(9): 189-191,205.
[13]	黄世伟, 王云峰. 基于流水线技术的并行模幂算法硬件实现[J]. 计算机工程, 2013, 39(7): 16-20,25.
[14]	赵程程, 杨亚涛, 李子臣, 阎晓姮. 基于McEliece公钥密码体制的盲签名算法[J]. 计算机工程, 2013, 39(6): 146-149.
[15]	刘涛，熊焰，黄文超，陆琦玮，龚旭东. 基于信誉模型的WSN密钥管理方案[J]. 计算机工程, 2013, 39(11): 123-126.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

利用多基数系统的高效椭圆曲线多标量乘算法

Efficient Algorithm for Multi-Scalar Multiplication of Elliptic Curves Using Multi-Base Number System

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 22

相关文章 15

编辑推荐

Metrics

本文评价