面向ECDSA的低复杂度多标量乘算法设计

doi:10.19665/j.issn1001-2400.2022.01.009

摘要/Abstract

摘要：

随着电子商务的飞速发展,信息安全的重要性日益剧增。密码技术在信息安全中可以确保数据在通信过程中的安全、保密、完整且不被篡改。诸如ECDSA等数字签名算法为安全电子商务提供了关键技术。ECDSA设计架构通常采用不同的多标量乘算法和单标量乘算法分别进行运算处理,从而导致计算复杂度提升。针对该问题,提出了一种面向ECDSA的低复杂度多标量乘算法,该算法采用取模法构建联合多基链算法,对不能同时被基底{2,3}整除的部分进行3^x2^y取模运算,对得到的余数进行预处理。与现有联合多基链算法采用的贪心法相比,所生产的基链长度减小,有效地降低了多标量乘法的计算复杂度。实验结果表明,在curve-P256曲线下多标量乘和单标量乘的复杂度分别降低了约9.84%~30.75%和3.88%~26.81%;在联合处理的情况下,复杂度至少降低了约16.65%;预计算点相较于wNAF和联合多基链算法减少了约25.00%。通过Python搭建模型,相较于现有算法至少提高了14.80%的运行速度。

关键词: 标量乘, 预处理, 多基链

Abstract:

With the rapid development of E-commerce,the importance of information security is increasing.Cryptography can ensure the safety,confidentiality,integrity and no tampering of data in the process of communication.Digital signature algorithms such as Elliptic Curve Digital Signature Algorithm (ECDSA) provide key technologies for secure e-commerce.But,the de-sign architecture of the ECDSA adopts different algorithms for multi-scalar multiplication and algorithms for single-scalar multiplication to separately execute operation,which will increase the computational complexity generally.The algorithm uses the fetching-mode method to construct the JDBC,fetching-mode operation for the part that is indivisible by the base,and at the same time,and pre-computes the obtained remainder.Compared with the greedy method used in the existing JDBC,the length of the produced base chain is reduced,and the computational complexity of the multi-scalar multiplication method is significantly reduced.Experimental results indicate that the algorithm for multi-scalar multiplication of low complexity reduces complexities by 9.84%~30.75% and by 3.88%~26.81% in terms of multi-scalar multiplication and single-scalar multiplication under the curve-P256 curve.In addition,this algorithm also reduces a complexity of 16.65% in joint processing,and thus it is estimated that the counting point of this algorithm is reduced by 25.00% when compared with the wNAF and JDBC.The running speed increases at least by 14.80% compared with those of the current algorithms by building a model through Python.

Key words: scalar multiplication, pre-computation, multi-base chain

中图分类号:

TP309

黄海,那宁,刘志伟,于斌,赵石磊. 面向ECDSA的低复杂度多标量乘算法设计[J]. 西安电子科技大学学报, 2022, 49(1): 92-101.

HUANG Hai,NA Ning,LIU Zhiwei,YU Bin,ZHAO Shilei. Low computation-complexity multi-scalar multiplication algorithm for the ECDSA[J]. Journal of Xidian University, 2022, 49(1): 92-101.

图/表 7

图1

表1

表2

表3

表4

图2

表5

参考文献 28

[1]	李晓伟, 杨邓奇, 曾新, 等. 车联网环境下跨域间认证与密钥协商协议[J]. 西安电子科技大学学报, 2021, 48(1):141-148.
	LI Xiaowei, YANG Dengqi, ZHENG Xin, et al. Cross-Domain Authentication and the Key Agreement Protocol in VANETs[J]. Journal of Xidian University, 2021, 48(1):141-148.
[2]	GOO E H, LEE S D. Reconfigurable Real Number Field Elliptic Curve Cryptography to Improve the Security[J]. Journal of Computer Virology and Hacking Techniques, 2015, 11(3):123-128. doi: 10.1007/s11416-014-0233-8
[3]	DRUCKER N, GUERON S. Speeding-Up P-256 ECDSA Verification on x86-64 Servers[J]. IEEE Letters of the Computer Society, 2019, 2(2):12-15. doi: 10.1109/LOCS.2019.2911063
[4]	ISLAM M M, HOSSAIN M S, HASAN M K, et al. FPGA Implementation of High-Speed Area-Efficient Processor for Elliptic Curve Point Multiplication over Prime Field[J]. IEEE Access, 2019, 7:178811-178826. doi: 10.1109/ACCESS.2019.2958491
[5]	KHLEBORODOV D. FastElliptic Curve Point Multiplication Based on Binary and Binary Non-Adjacent Scalar form Methods[J]. Advances in Computational Mathematics,Advances in Computational Mathematics, 2018, 44(4):1275-1293.
[6]	WANG W, FAN S. Attacking OpenSSL ECDSA withA Small Amount of Side-Channel Information[J]. Science China Information Sciences, 2018, 61(3):1-14. doi: 10.1007/s11432-017-9235-7
[7]	DIMITROV V, IMBERT L, MISHRA P K. Efficient and Secure Elliptic Curve Point Multiplication Using Double-Base Chains[C]// International Conference on the Theory and Application of Cryptology and Information Security.Heibelheig:Springer, 2005:59-78.
[8]	CHO S M, GWAK S G, KIM C H, et al. Faster Elliptic Curve Arithmetic for Triple-Base Chain by Reordering Sequences of Field Operations[J]. Multimedia Tools and Applications, 2016, 75(22):14819-14831. doi: 10.1007/s11042-016-3272-y
[9]	XU M, SHI L. Pseudo 4DProjective Coordinate-Based Multi-Base Scalar Multiplication[J]. Journal on Communications, 2018, 39(5):74-84.
[10]	YU W, MUSA S, LI B. Double-Base Chains for Scalar Multiplications on Elliptic Curves[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques.Heibelherg:Springer, 2020:538-565.
[11]	LEIVA C, THÉRIAULT N.Optimal 2-3 Chains for Scalar Multiplication[C]// International Conference on Cryptology and Information Security in Latin America.Heibelherg:Springer, 2019:89-108.
[12]	GOUNDAR R R. Addition Chains in Application to Elliptic Curve Cryptosystems[D]. Kochi: Kochi University, 2008.
[13]	OKEYA K, KATO H, NOGAMI Y. Width-3Joint Sparse Form[C]// International Conference on Information Security Practice and Experience.Heibelherg:Springer, 2010:67-84.
[14]	MAITRA S, SINHA A. New Algorithm to Convert any Integer in TBNS[J]. International Journal of Computer Applications, 2012, 51(5):40-45.
[15]	YU W, WANG K, LI B, et al. Joint Triple-Base Number System for Multi-Scalar Multiplication[C]// International Conference on Information Security Practice and Experience.Heibelherg:Springer, 2013:160-173.
[16]	DOCHE C, SUTANTYO D. New and Improved Methods to Analyze and Compute Double-Scalar Multiplications[J]. IEEE Transactions on Computers, 2014, 63(1):230-242. doi: 10.1109/TC.2012.184
[17]	DANGER J L, GUILLEY S, HOOGVORST P, et al. Improving the Big Mac Attack on Elliptic Curve Cryptography[J]. The New Codebreakers, 2016, 9100:374-386.
[18]	DOU Y, JIANG W, MA C, et al. Fast Scalar Multiplication Algorithm Using Constrained Triple-Base Number System and Its Applications[C]// 2015 10th International Conference on Broadband and Wireless Computing,Communication and Applications (BWCCA).Piscataway:IEEE, 2015:426-431.
[19]	XU J, AIPING L, HUI Z. PAPER A Structured Multi-Dimensional Sequence Pattern Mining Method[J]. IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences, 2017, 100(9):1838-1845.
[20]	PHALAKARN K, SUPPAKITPAISARN V. Optimal Representation for Right-to-Left Parallel Scalar and Multi-Scalar Point Multiplication[J]. Journal of Chemical Information and Modeling, 2018, 8(2):166-185.
[21]	李艳梅, 殷新春, 邵梦丽. 基于多基表示的滑动窗口椭圆曲线多标量乘算法[J]. 计算机与现代化, 2019, 1:11-16.
	LI Yanmei, YIN Xinchun, SHAO Mengli. Multi-Scalar Multiplication Algorithm for Elliptic Curve Based on MBNS and Sliding Window[J]. Computer and Modernization, 2019, 1:11-16.
[22]	DOU Y, WENG J, MA C, et al. Analysis of GLV / GLS Method for Elliptic Curve Scalar Multiplication[C]// International Conference on Frontier Computing.Heidelberg:Springer, 2018:210-219.
[23]	YI H, LUO G, LIN D. Faster Scalar Multiplication on the x-Line:Three-Dimensional GLV Method with Three-Dimensional Differential Addition Chains[C]// International Conference on Codes,Cryptology,and Information Security.Heidelberg:Springer, 2019:236-253.
[24]	尤文珠, 葛海波. 利用多基链的椭圆曲线多标量乘高效算法(2021)[J/OL]. [2021-03-30]. https://www.doc88.com/p-70459499563290.html?r=1.
[25]	BOUVIER C, IMBERT L. Faster Cofactorization with ECM Using Mixed Representations[C]// IACR International Conference on Public-Key Cryptography.Heidelberg:Springer, 2020:483-504.
[26]	DE MICHELI G, PIAU R, PIERROT C. A Tale of Three Signatures:Practical Attack of ECDSA with wNAF[C]// International Conference on Cryptology in Africa.Heidelberg:Springer, 2020:361-381.
[27]	LIU L, CUI X, RAN Y, et al. A Countermeasure for Power Analysis to Scalar Multiplication of ECC Hardware[C]// 2015 IEEE 11th International Conference on ASIC (ASICON).Piscataway:IEEE, 2015:1-4.
[28]	MAITRA S, SINHA A. Triple-Base Hybrid Joint Sparse Form and its Applications[J]. International Journal of Computer Applications, 2012, 43(3):9-20. doi: 10.5120/6082-8223

算法	3^x中的x	2^y中的y	预处理点个数	预处理计算量/MB	正式计算量/MB	总计算量/MB
	1	1	6	96	3 707	3 803
	1	2	12	192	3 181	3 373
	1	3	24	384	3 178	3 562
单标量乘	2	1	18	288	3 454	3 742
	2	2	36	576	3 074	3 650
	2	3	72	1 152	3 071	4 223
	3	1	54	864	3 287	4 151
	1	1	12	192	4 535	4 727
	1	2	24	384	3 527	3 911
	1	3	48	768	3 531	4 299
多标量乘	2	1	36	576	3 990	4 566
	2	2	72	1 152	3 328	4 480
	2	3	144	2 304	3 323	5 627
	3	1	108	1 728	3 661	5 389

窗口大小	预处理点个数	预处理计算量/MB	正式计算量/MB	总计算量/MB
3	4	74	3 584	3 658
4	8	138	3 379	3 517
5	16	266	3 243	3 509
6	32	522	3 145	3 667
7	64	1 034	3 072	4 106
8	128	2 058	3 015	5 073

算法	预处理点个数	预处理计算量/MB	正式计算量/MB	总计算量/MB	优化比率/%
D&A^[4]	0	0	4 608	4 608	26.81
wNAF^[26]	16	266	3 243	3 509	3.88
DBC^[10]	0	0	3 940	3 940	14.40
文中单标量乘情况	12	192	3 181	3 373
Shamir^[12]	3	16	5 632	5 648	30.75
JSF^[27]	6	96	5 291	5 387	27.40
JDBC^[28]	36	576	3 762	4 338	9.84
文中多标量乘情况	24	384	3 527	3 911

算法		多标量乘次数	计算量		总计
多标量乘	单标量乘	多标量乘次数	单标量乘/MB	多标量乘/MB	计算量/MB	优化比率/%
		1	4 608	5 648	10 256	32.72
Shamir^[12]	D&A^[4]	2		11 296	15 904	34.44
		3		16 944	21 552	35.25
		1	3 509	5 387	8 630	20.05
JSF^[27]	wNAF^[26]	2		10 774	14 017	25.61
		3		16 161	19 404	28.09
		1	3 940	4 338	8 278	16.65
JDBC^[28]	DBC^[10]	2		8 676	12 616	17.35
		3		13 014	16 954	17.69
	文中方法	1		3 527	6 900
		2	3 373	7 054	10 427
		3		10 581	13 954

算法	单次运行时间/s	优化比率/%
D&A^[4]	0.008 790	23.88
wNAF^[26]	0.008 436	20.69
DBC^[10]	0.007 853	14.80
文中单标量乘情况	0.006 691
Shamir^[12]	0.018 049	44.81
JSF^[27]	0.023 438	57.50
JDBC^[28]	0.015 791	36.91
多标量乘情况	0.009 962