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

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

通信学报 ›› 2022, Vol. 43 ›› Issue (3): 101-112.doi: 10.11959/j.issn.1000-436x.2022061

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

薛一鸣¹, 刘树荣¹, 郭书恒¹, 李岩², 胡彩娥³

¹ 中国农业大学信息与电气工程学院，北京 100083
² 中国农业大学理学院，北京 100083
³ 国网北京市电力公司，北京 100031

修回日期:2022-03-09 出版日期:2022-03-25 发布日期:2022-03-01
作者简介:薛一鸣（1968- ），男，山西文水人，中国农业大学教授、硕士生导师，主要研究方向为信息安全、大规模集成电路设计
刘树荣（1997- ），男，彝族，云南楚雄人，中国农业大学硕士生，主要研究方向为信息安全、集成电路设计
郭书恒（1999- ），男，河南济源人，中国农业大学硕士生，主要研究方向为信息安全
李岩（1982- ），男，内蒙古呼和浩特人，博士，中国农业大学副教授、硕士生导师，主要研究方向为数论、编码、密码
胡彩娥（1971- ），女，山西文水人，博士，国网北京市电力公司高级工程师，主要研究方向为大数据分析与安全、电力系统自动化
基金资助:
国家自然科学基金资助项目(61872368);国家重点研发计划基金资助项目(2021QY2312)

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

Yiming XUE¹, Shurong LIU¹, Shuheng GUO¹, Yan LI², Cai’e HU³

¹ College of Information and Electrical Engineering, China Agricultural University, Beijing 100083, China
² College of Science, China Agricultural University, Beijing 100083, China
³ State Grid Beijing Electric Power Company, Beijing 100031, China

Revised:2022-03-09 Online:2022-03-25 Published:2022-03-01
Supported by:
The National Natural Science Foundation of China(61872368);The National Key Research and Development Program of China(2021QY2312)

摘要/Abstract

摘要：

针对区块链等特定场景对验签速度有较高要求的特点，设计了一种高速Ed25519验签算法的硬件架构。提出了基于交错NAF的多点乘算法，通过预计算和查表的方式，有效减少了点加、倍点的次数；采用Karatsuba乘法和快速约简方法实现模乘运算，并设计了不需要模加、模减的点加、倍点操作步骤，有效提升了点加、倍点运算的性能。针对解压过程中耗时的模幂运算，设计了模逆和模乘并行的模幂计算方法，提高了解压运算的性能。整个设计充分考虑了资源的复用，在Zynq-7020平台上实现需要13 695个Slices，在81.61 MHz的时钟频率下，每秒能够完成8 347次验签运算。

关键词: 爱德华曲线, 数字签名, 多点乘, 硬件实现

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

中图分类号:

TN918

薛一鸣, 刘树荣, 郭书恒, 李岩, 胡彩娥. 高速Ed25519验签算法硬件架构的设计与实现[J]. 通信学报, 2022, 43(3): 101-112.

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.

图/表 13

图1

图2

图3

表1

表2

表3

图4

表4

表5

表6

图5

表7

表8

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

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¹

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

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

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 22

相关文章 15

Metrics

推荐阅读 0

数据类型	数据内容
公钥	c5aa8df43f9f837bedb7442f31dcb7b1
	66d38535076f094b85ce3a2e0b4458f7
私钥	fc51cd8e6218a1a38da47ed00230f058
	0816ed13ba3303ac5deb911548908025

方案	资源/个			性能
方案	LUT	FF	DSP	频率/MHz	模p乘周期数/个	点乘周期数/个	点乘运算时间/μs
本文算法	12 881	5 338	81	81.61	7	6 174	75.66
文献[15]	8 680	3 472	0	137.00	95	86 025	627.92
文献[16]	7 911	1 041	15	82.00	18.6	120 260	608.00
文献[17]	52 512	9 342	225	13.87	2	3 895	280.80
文献[18]	9 864	3 885	81	73.00	5	9 181	126.00

方案	平台	资源/个				性能
方案	平台	Slices	LUT	FF	DSP	时钟频率/MHz	周期数/个	运算时间/μs	验签速度/(OP·s^-1)
本文算法	Zynq-7020	13 695	22 561	12 632	81	81.61	9.8×10³	119.8	8 347.0
文献[9]	MSP430F1611	—	—	—	—	8.00	1.420 67×10⁷	1 775 837.5	0.5
文献[11]	STM32F401	—	—	—	—	84.00	1.331×10⁶	15 845.2	63.0
文献[16]	Zynq SoC	2 176	2 707	962	15	82.00	3.01×10⁵	3 676.5	272.0
文献[18]	XC7Z020	16 837	34 950	16 772	81	73.00	1.42×10⁴	195.6	5 112.0

[1]	张艳硕, 刘宁, 袁煜淇, 杨亚涛. 基于ISRSAC数字签名算法的适配器签名方案[J]. 通信学报, 2023, 44(3): 178-185.
[2]	王宏, 赖成喆, 刘向阳, 曾晗. 基于正交拉丁方理论的数字签名分组批量验证[J]. 通信学报, 2022, 43(2): 44-54.
[3]	姜占鹏, 孙铭玮, 黄海, 徐江, 刘志伟, 白瑞, 方舟, 曲家兴. 面向双线性对的 $F_{p^{2}}$ -FIOS模乘算法及其实现架构研究[J]. 通信学报, 2022, 43(2): 100-108.
[4]	史瑞, 封化民, 谢惠琴, 史国振, 刘飚, 杨旸. 基于带智能卡的移动终端实现的隐私保护的属性票据方案[J]. 通信学报, 2022, 43(10): 26-41.
[5]	贺蕾, 马建峰, 魏大卫. 面向无人机网络的属性代理签名方案[J]. 通信学报, 2021, 42(11): 87-96.
[6]	于斌, 黄海, 刘志伟, 赵石磊, 那宁. 面向多椭圆曲线的高速标量乘法器设计与实现[J]. 通信学报, 2020, 41(12): 100-109.
[7]	古春生. 破解新型的轻量级数字签名方案[J]. 通信学报, 2013, 34(7): 154-158.
[8]	古春生1,2,3. 破解新型的轻量级数字签名方案[J]. 通信学报, 2013, 34(7): 17-158.
[9]	刘亚丽,秦小麟,殷新春,李博涵. 基于模m的n方根的前向安全数字签名方案的分析与改进[J]. 通信学报, 2010, 31(6): 82-88.
[10]	王后珍,张焕国. 新型的轻量级数字签名方案[J]. 通信学报, 2010, 31(11): 25-29.
[11]	王潮,时向勇,牛志华. 基于Montgomery曲线改进ECDSA算法的研究[J]. 通信学报, 2010, 31(1): 9-13.
[12]	史建红,金晨辉,潘志舒. 整数对的七元联合稀疏型及其应用[J]. 通信学报, 2009, 30(12): 113-118.
[13]	王化群,徐名海,郭显久. 几种无证书数字签名方案的安全性分析及改进[J]. 通信学报, 2008, 29(5): 88-92.
[14]	叶登攀,尚月赟. 基于多特征的MPEG视频认证方案[J]. 通信学报, 2008, 29(2): 59-65.
[15]	李志敏,王励成,郑世慧,杨义先. 随机散列函数安全性与签名者作弊[J]. 通信学报, 2008, 29(10): 101-107.