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

doi:10.16180/j.cnki.issn1007-7820.2023.09.011

摘要/Abstract

摘要：

针对经典椭圆数字签名算法中存在的签名效率低以及伪造签名攻击等问题,文中提出了可证明安全性的双参数椭圆曲线数字签名方案,并通过硬件进行实现。在现有研究基础上,利用Lopez-Dahab投影坐标系减少签名过程中模逆运算的使用次数,并对群运算层采用部分并行运算以此提高点乘算法的运算效率。对于有限域运算,通过串并混合结构的快速模乘算法、快速模平方算法以及改进的Itoh-Tsujii模逆算法来实现。方案安全性分析结果表明,该方案可以有效抵抗伪造攻击和随机数替换攻击,可确保消息传递过程中的安全性。时序仿真结果表明,实现一次点乘运算占用23 087个逻辑单元且运算过程仅需要476个时钟数,相比于同类点乘运算的时钟数减少了75%。

关键词: ECDSA, 模运算, 伪造签名, 安全性, 并行运算, 状态机, 消息, 密钥对

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

中图分类号:

方应李,方玉明. GF(2^m)域双参数ECDSA算法优化设计[J]. 电子科技, 2023, 36(9): 73-78.

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.

图/表 13

图1

表1

图2

图3

表2

模逆运算过程"

次序	计算式
初始化	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$

表2

图4

表3

PA、PD并行模型的输入输出"

输入/输出	数据
仿射点坐标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$

表3

图5

图6

图7

图8

表4

表5

参考文献 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.

方案	抗伪造安全	前向安全	抗替换随机数
文献[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