高速Ed25519验签算法硬件架构的设计与实现

doi:10.11959/j.issn.1000-436x.2022061

Abstract

Abstract:

Aiming at the high performance requirements of signature verification for specific scenarios such as blockchain, a high-speed hardware architecture of Ed25519 was proposed.To reduce the number of calculations for point addition and point double, a multiple point multiplication algorithm based on interleaving NAF was conducted by using pre-computation and lookup tables.The modular multiplication operation was realized by using the Karatsuba multiplication and fast reduction method, and the point addition and point double operation was designed without modular addition and subtraction, which could effectively improve the performance of point addition and point double.Given that modular exponentiation was the most time-consuming operation in the decompression process, a new modular exponentiation approach was developed by parallelizing modular inverse and modular multiplication, and therefore the performance of the de-compression operation could be improved.The proposed architecture fully considers the use of resources and is implemented on the Zynq-7020 FPGA platform with 13 695 slices, achieving 8 347 verifications per second at 81.6 MHz.

Key words: Edwards-curve, digital signature, multiple point multiplication, hardware implementation

CLC Number:

TN918

Yiming XUE, Shurong LIU, Shuheng GUO, Yan LI, Cai’e HU. High-speed hardware architecture design and implementation of Ed25519 signature verification algorithm[J]. Journal on Communications, 2022, 43(3): 101-112.

Figures/Tables 13

References 22

[1]	KOBLITZ N . Elliptic curve cryptosystems[J]. Mathematics of Computation, 1987,48(177): 203-209.
[2]	MILLER V S , . Use of elliptic curves in cryptography[C]// Lecture Notes in Computer Science. Berlin:Springer, 1986: 417-426.
[3]	王婧, 吴黎兵, 罗敏 ,等. 安全高效的两方协同 ECDSA 签名方案[J]. 通信学报, 2021,42(2): 12-25.
	WANG J , WU L B , LUO M ,et al. Secure and efficient two-party ECDSA signature scheme[J]. Journal on Communications, 2021,42(2): 12-25.
[4]	BERNSTEIN D J , DUIF N , LANGE T ,et al. High-speed high-security signatures[J]. Journal of Cryptographic Engineering, 2012,2(2): 77-89.
[5]	JOSEFSSON S , LIUSVAARA I . Edwards-curve digital signature algorithm (EdDSA)[R]. 2017.
[6]	GAYOSO M V , HERNáNDEZ E L , MARTíN M A ,et al. Secure elliptic curves and their performance[J]. Logic Journal of the IGPL, 2018,27(2): 277-238.
[7]	姚前, 张大伟 . 区块链系统中身份管理技术研究综述[J]. 软件学报, 2021,32(7): 2260-2286.
	YAO Q , ZHANG D W . Survey on identity management in block-chain[J]. Journal of Software, 2021,32(7): 2260-2286.
[8]	RESCORLA E . The transport layer security (TLS) protocol version 1.3[R]. 2018.
[9]	GROBSCH?DL J , FRANCK C , LIU Z . Lightweight EdDSA signature verification for the ultra-low-power Internet of things[C]// Information Security Practice and Experience. Berlin:Springer, 2021: 263-282.
[10]	FAZ-HERNáNDEZ A , LóPEZ J , DAHAB R . High-performance implementation of elliptic curve cryptography using vector instructions[J]. ACM Transactions on Mathematical Software, 2019,45(3): 1-35.
[11]	FUJII H , ARANHA D F . Curve25519 for the Cortex-M4 and beyond[C]// International Conference on Cryptology and Information Security in Latin America. Berlin:Springer, 2017: 109-127.
[12]	SCOTT M . On the deployment of curve based cryptography for the Internet of things[J]. IACR Cryptol ePrint Arch,2020, 2020:514.
[13]	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.
[14]	YANG H J , SHIN K W . A hardware implementation of point scalar multiplication on Edwards25519 curve[C]// Proceedings of 2021 International Conference on Electronics,Information,and Communication (ICEIC). Piscataway:IEEE Press, 2021: 1-3.
[15]	MEHRABI M A , DOCHE C . Low-cost,low-power FPGA implementation of ED25519 and Curve25519 point multiplication[J]. Information, 2019,10(9): 285.
[16]	TURAN F , VERBAUWHEDE I . Compact and flexible FPGA implementation of Ed25519 and X25519[J]. ACM Transactions on Embedded Computing Systems, 2019,18(3): 1-21.
[17]	于斌, 黄海, 刘志伟 ,等. 高性能 Ed25519 算法硬件架构设计与实现[J]. 电子与信息学报, 2021,43(7): 1821-1827.
	YU B , HUANG H , LIU Z W ,et al. High-performance hardware archi-tecture design and implementation of Ed25519 algorithm[J]. Journal of Electronics ＆ Information Technology, 2021,43(7): 1821-1827.
[18]	BISHEH-NIASAR M , AZARDERAKHSH R , MOZAFFARI-KERMANI M , . Cryptographic accelerators for digital signature based on Ed25519[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2021,29(7): 1297-1305.
[19]	徐明, 史量 . 基于伪四维投射坐标的多基链标量乘法[J]. 通信学报, 2018,39(5): 74-84.
	XU M , SHI L . Pseudo 4D projective coordinate-based multi-base scalar multiplication[J]. Journal on Communications, 2018,39(5): 74-84.
[20]	尤文珠, 葛海波 . 利用多基数系统的高效椭圆曲线多标量乘算法[J]. 计算机工程, 2021,47(2): 182-187.
	YOU W Z , GE H B . Efficient algorithm for multi-scalar multipli-cation of elliptic curves using multi-base number system[J]. Computer Engineering, 2021,47(2): 182-187.
[21]	HANKERSON D , VANSTONE S , MENEZES A J . Guide to elliptic curve cryptography[M]. Berlin: Springer Science ＆ Business Media, 2006.
[22]	SALARIFARD R , BAYAT-SARMADI S , . An efficient low-latency point-multiplication over Curve25519[J]. IEEE Transactions on Circuits and Systems I:Regular Papers, 2019,66(10): 3854-3862.

Related Articles 15

[1]	Yanshuo ZHANG, Ning LIU, Yuqi YUAN, Yatao YANG. Adaptor signature scheme based on ISRSAC digital signature algorithm [J]. Journal on Communications, 2023, 44(3): 178-185.
[2]	Hong WANG, Chengzhe LAI, Xiangyang LIU, Han ZENG. Orthogonal Latin square theory based group and batch verification for digital signatures [J]. Journal on Communications, 2022, 43(2): 44-54.
[3]	Zhanpeng JIANG, Mingwei SUN, Hai HUANG, Jiang XU, Zhiwei LIU, Rui BAI, Zhou FANG, Jiaxing QU. Research on $F_{p^{2}}$ -FIOSmodular multiplication algorithm for bilinear pairs and its implementation architecture [J]. Journal on Communications, 2022, 43(2): 100-108.
[4]	Rui SHI, Huamin FENG, Huiqin XIE, Guozhen SHI, Biao LIU, Yang YANG. Privacy-preserving attribute ticket scheme based on mobile terminal with smart card [J]. Journal on Communications, 2022, 43(10): 26-41.
[5]	Lei HE, Jianfeng MA, Dawei WEI. Attribute-based proxy signature scheme for unmanned aerial vehicle networks [J]. Journal on Communications, 2021, 42(11): 87-96.
[6]	Bin YU, Hai HUANG, Zhiwei LIU, Shilei ZHAO, Ning NA. Design and implementation of high-speed scalar multiplier for multi-elliptic curve [J]. Journal on Communications, 2020, 41(12): 100-109.
[7]	. Breaking novel and lightweight digital signature scheme [J]. Journal on Communications, 2013, 34(7): 17-158.
[8]	Chun-sheng GU. Breaking novel and lightweight digital _s ignature scheme [J]. Journal on Communications, 2013, 34(7): 154-158.
[9]	Ya-li LIU,Xiao-lin QIN,Xin-chun YIN,Bo-han LI. Analysis and improvement for forward security digital signature schemes based on n-th root module m [J]. Journal on Communications, 2010, 31(6): 82-88.
[10]	Hou-zhen WANG,Huan-guo ZHANG. Novel and lightweight digital signature scheme [J]. Journal on Communications, 2010, 31(11): 25-29.
[11]	Dian-jun LU,GBing-ru ZHAN,Hai-xing ZHAO. Forward-secure threshold signature scheme based on polynomial secret sharing [J]. Journal on Communications, 2009, 30(1): 45-49.
[12]	Hua-qun WANG,Ming-hai XU,Xian-jiu GUO. Cryptanalysis and improvement of several certificateless digital signature schemes [J]. Journal on Communications, 2008, 29(5): 88-92.
[13]	Deng-pan YE,Yue-yun SHANG. Multi-feature based authentication watermarking scheme for MPEG videos [J]. Journal on Communications, 2008, 29(2): 59-65.
[14]	Guo-yin ZHANG,ANGLing-ling WANG,Chun-guang MA. Survey on ring signature [J]. Journal on Communications, 2007, 28(5): 109-117.
[15]	Li KANG,Xiao-hu TANG. Digital signature scheme without hash functions and message redundancy [J]. Journal on Communications, 2006, 27(5): 18-20.

Metrics

Recommended 0

No Suggested Reading articles found!

w₁	w₂	多点乘循环运算量/次		预计算运算量/次		总运算量/次
w₁	w₂	点加	倍点	点加	倍点	点加	倍点
7	4	82	253	3	1	85	254
7	5	73	253	7	1	80	254
7	6	67	253	15	1	82	254
8	5	70	253	7	1	77	254
8	6	64	253	15	1	79	254
9	5	67	253	7	1	74	254
9	6	61	253	15	1	76	254
9	7	56	253	31	1	87	254
10	5	65	253	7	1	72	254
10	6	59	253	15	1	74	254
10	7	54	253	31	1	85	254
10	8	51	253	63	1	114	254
11	5	63	253	7	1	70	254

周期	大数乘				模p约简				加法	减法
周期	Ⅰ	Ⅱ	Ⅲ	Ⅳ	Ⅰ	Ⅱ	Ⅲ	Ⅳ	加法	减法
1	t₁=T₁d								t ₀=T₂+T₂	A ₂=Y₂-X₂
2	A=A ₁A₂	t₁							B ₂=Y₂+X₂	A ₁=Y₁-X₁
3	B=B ₁B₂	A	t₁						B ₁=Y₁+X₁
4	t ₂=Z₁Z₂	B	A	t₁
…
7				t₂	B	A	t₁
8	C=t ₀t₁				t₂	B	A	t₁
9		C				t₂	B	A
10	T ₃=EH		C				t₂	B	H =B+A	E=B-A
11		T₃		C				t₂
12			T₃		C				D=t ₂+t₂
#
15	X ₃=EF					T₃		C	G=D+C	F=D-C
16	Z ₃=FG	X₃					T₃
17	Y ₃=GH	Z₃	X₃					T₃
#
22						Y₃	Z₃	X₃
23							Y₃	Z₃
24								Y₃

周期	大数乘				模p约简				加法	减法
周期	Ⅰ	Ⅱ	Ⅲ	Ⅳ	Ⅰ	Ⅱ	Ⅲ	Ⅳ	加法	减法
1	A=X ₁X₁
2	B=Y ₁Y₁	A							t ₂=X₁+Y₁
3	t ₁=Z₁Z₁	B	A
4	t ₂=t₂t₂	t₁	B	A
…
7				t₂	t₁	B	A
8					t₂	t₁	B	A
9	Y ₂=GH					t₂	t₁	B	H =A+B	G=A-B
10		Y₂					t₂	t₁	C=t ₁+t₁
11	T ₂=EH		Y₂					t₂	F=G+C	E=H-t ₂
12	X ₂=EF	T₂		Y₂
13	Z ₂=FG	X₂	T₂		Y₂
14		Z₂	X₂	T₂		Y₂
15			Z₂	X₂	T₂		Y₂
16				Z₂	X₂	T₂		Y₂
17					Z₂	X₂	T₂
18						Z₂	X₂	T₂
19							Z₂	X₂
20								Z₂

模块	LUT/个	FF/个	DSP/个	BRAM/块
ALU模块	12 881	5 338	81	0
SHA-512	2 923	2 203	0	0
控制单元	1 502	610	0	0
寄存器	136	2 318	0	0
寄存器堆	3 245	1 647	0	0
模逆模块	1 749	515	0	0

模块	周期数/个
乘法器	4
模p约简	4
加/减法器	1
模逆	507
SHA-512	80
解压控制	1 913
模L约简	19
坐标转换	516
NAF编码	254
点加	24
倍点	20
多点乘	6 174¹

High-speed hardware architecture design and implementation of Ed25519 signature verification algorithm

RichHTML

PDF

Knowledge