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

doi:10.19665/j.issn1001-2400.2022.01.009

Abstract

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

CLC Number:

TP309

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.

Figures/Tables 7

References 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

Low computation-complexity multi-scalar multiplication algorithm for the ECDSA

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 28

Related Articles 2

Metrics

Comments

Recommended 0

[1]	SHI Yan;LIU Zeng-ji;SHENG Min. A novel network resource allocation algorithm with load balance guarantees [J]. J4, 2005, 32(6): 885-889.
[2]	HAO Yan-hua;JIANG Zheng-tao;WANG Yu-min. Scalar multiplication of hyperelliptic curves with the efficient algorithm for inversion [J]. J4, 2005, 32(3): 418-422.