GF(2m)域双参数ECDSA算法优化设计

doi:10.16180/j.cnki.issn1007-7820.2023.09.011

Abstract

Abstract:

In view of the problems of the classical elliptic digital signature algorithm, such as low signature efficiency and forgery signature attack, a provably secure double parameter elliptic curve digital signature scheme is proposed and implemented by hardware in this study. Based on the existing research, the Lopez-Dahab projection coordinate system is used to reduce the number of modular inverse operations in the signature process, and the group operation layer is partially parallel operations to improve the efficiency of the high point multiplication algorithm.For finite field operations, fast modular multiplication algorithm of serial parallel hybrid structure, fast modular square operation and improved Itoh-Tsujii modular inverse algorithm are adopted.The security analysis result of the scheme shows that the scheme can effectively resist forgery attack and random number replacement attack, and ensure the security in the process of message transmission. The timing simulation results show that the implementation of a point multiplication operation occupies 23 087 logic units, the operation process only needs 476 clocks,and the number of clocks is reduced by 75% when compared with similar point multiplication operations.

Key words: ECDSA, modular arithmetic, forged signature, safety, parallel operation, state machine, message, key pair

CLC Number:

FANG Yingli,FANG Yuming. Optimal Design of Double Parameter ECDSA Algorithm over GF (2^m)[J].Electronic Science and Technology, 2023, 36(9): 73-78.

Figures/Tables 13

Figure 1.

Table 1.

Figure 2.

Figure 3.

Table 2.

Modular inverse operation process"

次序	计算式
初始化	A(x)=β₁= $α 21 - 1$
1	β₂=β₁₊₁= $β 1 21$ ×β₁= $α 22 - 1$
2	β₃=β₂₊₁= $β 2 21$ ×β₁= $α 23 - 1$
3	β₆=β₃₊₃= $β 3 23$ ×β₃= $α 26 - 1$
4	β₇=β₆₊₁= $β 6 21$ ×β₁= $α 27 - 1$
5	β₁₄=β₇₊₇= $β 7 27$ ×β₇= $α 214 - 1$
6	β₂₈=β₁₄₊₁₄= $β 14 214$ ×β₁₄= $α 228 - 1$
7	β₂₉=β₂₈₊₁= $β 28 21$ ×β₁= $α 229 - 1$
8	β₅₈=β₂₉₊₂₉= $β 29 229$ ×β₂₉= $α 258 - 1$
9	β₁₁₆=β₅₈₊₅₈= $β 58 258$ ×β₅₈= $α 2116 - 1$
10	A(x)^-1=β₂₃₂=β_116+116= $β 116 2116$ ×β₁₁₆= $α 2232 - 1$

Table 2.

Figure 4.

Table 3.

Input and output of PA and PD parallel models"

输入/输出	数据
仿射点坐标P₀	P₀(x₀,y₀)
LD投影坐标P₁、P₂	P₁(X₁,Z₁), P₂(X₂,Z₂)
点加坐标P₁+P₂=(X_PA,Z_PA)	X_PA=x₀Z₃+X₁Z₂X₂Z₁, Z_PA=(X₁Z₂+X₂Z₁)²
倍点坐标2P₂=(X_PD,Z_PD)	X_PD= $X 2 4$ + $Z 2 4$ ,Z_PD= $X 2 2 Z 2 2$

Table 3.

Figure 5.

Figure 6.

Figure 7.

Figure 8.

Table 4.

Table 5.

References 18

[1]	Miller V S. Use of elliptic curves in cryptography[C]. Berlin:Conference on the Theory and Application of Cryptographic Techniques, 1985:41-46.
[2]	Koblitz N. Elliptic curve cryptosystems[J]. Mathematics of Computation, 1987, 48(7):203-209. doi: 10.1090/mcom/1987-48-177
[3]	Johnson D, Menezes A, Vanstone S. The elliptic curve digital signature algorithm[J]. International Journal of Information Security, 2001, 1(1):36-63. doi: 10.1007/s102070100002
[4]	Brown M, Hankerson D, López J, et al. Software implementation of the NIST elliptic curves over prime fields[C]. Berlin:Cryptographers’Track at the RSA Conference, 2001:20-24.
[5]	李复才, 张永平, 孙宁. 椭圆曲线数字签名方案的研究与改进[J]. 计算机工程与设计, 2007, 28(21):5241-5242.
	Li Fucai, Zhang Yongping, Sun Ning. Study and improvement of signing schedules with elliptic curve cryptography[J]. Computer Engineering and Design, 2007, 28(21):5241-5242.
[6]	张庆胜, 郭宝安, 徐树民, 等. 快速椭圆曲线签名验证算法[J]. 计算机工程与设计, 2008, 29(17):4425-4427.
	Zhang Qingsheng, Guo Baoan, Xu Shumin, et al. Fast elliptic curve digital signature and verify algorithm[J]. Computer Engineering and Design, 2008, 29(17):4425-4427.
[7]	Rashidi B, Farashahi R R, Sayedi S M. High-performance and high-speed implementation of polynomial basis ItohTsujii inversion algorithm over GF(2^m)[J]. IET Information Security, 2017, 11(2):66-77. doi: 10.1049/ise2.v11.2
[8]	Rashidi B. Low-cost and fast hardware implementations of point multiplication on binary edwards curves[C]. Mashhad: Iranian Conference on Electrical Engineering, 2018:63-71.
[9]	Kalaiarasi M, Venkatasubramani V R, Rajaram S. A Hex Itoh-Tsujii inversion algorithm for FPGA platforms[J]. IEICE Electronics Express, 2021, 18(9):1-8.
[10]	戈勇, 李华, 宁永成. 基于FPGA的DES加密算法实现[J]. 电子科技, 2013, 26(7):172-176.
	Ge Yong, Li Hua, Ning Yongcheng. The implementation of DES algorithm based on FPGA[J]. Electronic Science and Technology, 2013, 26(7):172-176.
[11]	Qiang Z, Zhen Y. Research and implementation of poi-nt multiplication over elliptic curve GF(2^m) based onVLSI[M]. Singapore:Springer, 2021:81-84.
[12]	Hauksdóttir A S, Sigursson S. Proving routh's theorem using the euclidean algorithm and cauchy's theorem[J]. IFAC-Papers On Line, 2020, 53(2):4460-4467.
[13]	Khan Z, Benaissa M. High speed and low latency ECC implementation over GF(2^m) on FPGA[J]. IEEE Transactions on Very Large Scale Integration Systems, 2016, 25(1):165-176. doi: 10.1109/TVLSI.2016.2574620
[14]	Harb S S, Ahmad M O, Swamy M N S. High-performance pipelined FPGA implementation of the elliptic curve cryptography over GF(2ⁿ)[C]. Guangzhou: The Sixteenth International Conference on Security and Cryptography, 2019:33-38.
[15]	Liu S G, Chen W Q, Liu J L. An efficient double parameter elliptic curve digital signature algorithm for blockchain[J]. IEEE Access, 2021(9):77058-77066.
[16]	伍红梅. 基于椭圆曲线的ELGamal数字签名方案[J]. 楚雄师范学院学报, 2010(3):44-47.
	Wu Hongmei. ELGamal digital signature scheme based on the elliptic curves[J]. Journal of Chuxiong Normal University, 2010, 25(3):44-47.
[17]	Rashid M, Imran M, Jafri A R, et al. Through put/area optimised pipelined architecture for elliptic curve crypto processor[J]. IET Computers & Digital Techniques, 2019, 13(5):361-368. doi: 10.1049/cdt2.v13.5
[18]	Rebeiro C, Roy S S, Mukhopadhyay D. Pushing the limits of high-speed GF (2^m)elliptic curve scalar multiplication on FPGAs[C]. Berlin:International Workshop on Cryptographic Hardware and Embedded Systems, 2012:57-63.

方案	签名阶段			验证阶段
方案	模乘	模逆	点乘	模乘	模逆	点乘
文献[3]	2	1	1	2	1	2
文献[6]	2	1	1	2	0	1
本文	3	0	1	2	0	1

方案	抗伪造安全	前向安全	抗替换随机数
文献[6]	否	是	否
文献[16]	否	否	否
本文	是	是	是

方案	逻辑单元	频率/MHz	时间/μs	时钟数/个
文献[17]	18 953	357	15.78	5 633
文献[18]	23 147	154	12.50	1 925
本文	23 087	100	4.77	476

Optimal Design of Double Parameter ECDSA Algorithm over GF (2^m)

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 18

Related Articles 15

Metrics

Comments

Recommended 10

[1]	ZHAO Yingxiao,SU Yang. Design of A Multi-Channel Radar Echo Playback System Based on FPGA [J]. Electronic Science and Technology, 2023, 36(2): 1-7.
[2]	WEI Xing. Mobile Network Payment Secure Communication Protocol Model Based on Improved DNS Protocol [J]. Electronic Science and Technology, 2021, 34(9): 54-57.
[3]	TONG Zeyou,FENG Shimin,HOU Xiaoqing,DING Enjie. Recognition of Underground Miners’ Rule-Violated Behavior Based on Safety Helmet Detection [J]. Electronic Science and Technology, 2019, 32(9): 26-31.
[4]	LIU Ziqiang,CAI Wenyu,ZHANG Pengpeng. Research on Date Recycling Technology of Submerged Buoy Based on Beidou Satellite [J]. Electronic Science and Technology, 2019, 32(8): 56-60.
[5]	ZHANG Yugui,HU Xuechen,WANG Yi. Research about Bandwidth Utilization of Static Segment Based on FlexRay Bus [J]. Electronic Science and Technology, 2019, 32(6): 12-16.
[6]	LIU Yang, LI Kai, TAN Kangbo. Analysis and Study of Typical Indoor Electromagnetic Environment Protection Control [J]. , 2018, 31(4): 81-.
[7]	SUN Shuai, LI Chuanxi. Based on Linux Multithreaded Management Analysis and Implementation [J]. , 2017, 30(9): 27-.
[8]	WANG Hao1,2，WANG Xinran1,2，GUO Qifeng2， LI Yu1,2, YANG Jianxu1,2. Design and Implementation of A Kind of Message Bus Based on Shared Memory [J]. , 2017, 30(9): 93-.
[9]	HUANG Yong，WANG Yagang. Design of Vehicle GPS/GPRS Positioning System Based on STM32 [J]. , 2017, 30(4): 32-.
[10]	WANG Guixin,ZHENG Xiaozong,ZHANG Haoran,ZHANG Xiaochuan. An Algorithm for Vectoring SMS Based on Word2vec [J]. , 2016, 29(4): 49-.
[11]	ZHOU Chengming,WU Chunxue,LI Rui,YANG Guisong,WU Zhigang. Design of and Research on Independent and Security Intelligent Home Server System [J]. , 2016, 29(4): 79-.
[12]	LU Ning,YAO Xue,MA Xiaoming. Design and Implementation of Security System Based on GSM Network [J]. , 2016, 29(4): 120-.
[13]	MA Yuchao. Application of Markov Model in Functional Safety Temperature Transmitters [J]. , 2016, 29(3): 22-.
[14]	SONG Ming,ZHAO Yingxiao,LIN Qianqiang. Design and Optimization of DDR3 SDRAM Controller Based on FPGA [J]. , 2016, 29(11): 47-.
[15]	WANG Jingjing,SHANG Jianhua,HE Yan,LUO Yuan. Design of Signal Acquisition and Processing System for Laser Doppler Vibrometer [J]. , 2016, 29(1): 9-.

Optimal Design of Double Parameter ECDSA Algorithm over GF (2m)

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 18

Related Articles 15

Metrics

Comments

Recommended 10

Optimal Design of Double Parameter ECDSA Algorithm over GF (2^m)