可重构的素域SM2算法优化方法

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

Abstract

Abstract:

Aiming at the problems of inefficient of software, low utilization of hardware resources and poor scalability of SM2 algorithm, a reconfigurable optimization method of SM2 algorithm over prime filed was proposed.Through in-depth analysis of the SM2 algorithm, starting from different computation stages and characteristics, respectively using KOA fast multiplication, fast modular reduction and Barrett algorithm to achieve recommended or arbitrary parameters of the modular multiplication operation, and the radix-4 extended Euclidean algorithm was optimized and improved to accelerate the modular inverse operation.Then, in the standard projective coordinate system, the Montgomery method was used to improve the efficiency of point multiplication, and the data flow of point addition and double point was optimized to shorten the operation cycle to 12 clocks.At the same time, fast coordinate system conversion was realized inside the FPGA.Finally, the parallel scheduling management of multi-SM2 was designed and implemented to meet the computational requirements of multiple applications.The experimental results show that the optimized SM2 makes full use of FPGA resources and shortens the cycle of point multiplication.The maximum number of calculations per second is 352.48 times higher than the CPU (Intel i5-8300), which improves the performance and scalability.

Key words: reconfigurable, SM2, FPGA, Montgomery point multiplication, fast modular multiplication

CLC Number:

TP309

Bin LI, Qinglei ZHOU, Xiaojie CHEN, Feng FENG. Optimization of reconfigurable SM2 algorithm over prime filed[J]. Journal on Communications, 2022, 43(3): 30-41.

Figures/Tables 12

References 28

[1]	JAVEED K , WANG X J . Radix-4 and radix-8 booth encoded interleaved modular multipliers over general Fp[C]// Proceedings of 2014 24th International Conference on Field Programmable Logic and Applications (FPL). Piscataway:IEEE Press, 2014: 1-6.
[2]	AMIET D , CURIGER A , ZBINDEN P . Flexible FPGA-based architectures for curve point multiplication over GF(p)[C]// Proceedings of 2016 Euromicro Conference on Digital System Design (DSD). Piscataway:IEEE Press, 2016: 107-114.
[3]	FENG X , LI S G . A high-speed and SPA-resistant implementation of ECC point multiplication over GF(p)[C]// Proceedings of 2017 IEEE Trustcom/BigDataSE/ICESS. Piscataway:IEEE Press, 2017: 255-260.
[4]	ZHAO Z W , BAI G Q . Ultra high-speed SM2 ASIC implementation[C]// Proceedings of 2014 IEEE 13th International Conference on Trust,Security and Privacy in Computing and Communications. Piscataway:IEEE Press, 2014: 182-188.
[5]	ZHANG D , BAI G Q . Ultra high-performance ASIC implementation of SM2 with power-analysis resistance[C]// Proceedings of 2015 IEEE International Conference on Electron Devices and Solid-State Circuits. Piscataway:IEEE Press, 2015: 523-526.
[6]	HOSSAIN M S , KONG Y N , SAEEDI E ,et al. High-performance elliptic curve cryptography processor over NIST prime fields[J]. IET Computers ＆ Digital Techniques, 2017,11(1): 33-42.
[7]	韩晓薇, 乌力吉, 王蓓蓓 ,等. 抗简单功耗攻击的SM2原子算法[J]. 计算机研究与发展, 2016,53(8): 1850-1856.
	HAN X W , WU L J , WANG B B ,et al. Atomic algorithm against simple power attack of SM2[J]. Journal of Computer Research and Development, 2016,53(8): 1850-1856.
[8]	JAVEED K , WANG X J . Low latency flexible FPGA implementation of point multiplication on elliptic curves over GF(p)[J]. International Journal of Circuit Theory and Applications, 2017,45(2): 214-228.
[9]	RAHMAN M S , HOSSAIN M S , RAHAT E H ,et al. Efficient hardware implementation of 256-bit ECC processor over prime field[C]// Proceedings of 2019 International Conference on Electrical,Computer and Communication Engineering (ECCE). Piscataway:IEEE Press, 2019: 1-6.
[10]	J?RVINEN K , MIELE A , AZARDERAKHSH R ,et al. FourQ on FPGA:new hardware speed records for elliptic curve cryptography over large prime characteristic fields[C]// International Conference on Cryptographic Hardware and Embedded Systems. Berlin:Springer, 2016: 517-537.
[11]	LI W , LIU J H , BAI G Q . High-speed implementation of SM2 based on fast modulus inverse algorithm[C]// Proceedings of 2018 China Semiconductor Technology International Conference (CSTIC). Piscataway:IEEE Press, 2018: 1-3.
[12]	DING J N , LI S G . A reconfigurable high-speed ECC processor over NIST primes[C]// Proceedings of 2017 IEEE Trustcom/ BigDataSE/ICESS. Piscataway:IEEE Press, 2017: 1064-1069.
[13]	YANG D Y , DAI Z B , LI W ,et al. An efficient ASIC implementation of public key cryptography algorithm SM2 based on module arithmetic logic unit[C]// Proceedings of 2019 IEEE 13th International Conference on ASIC. Piscataway:IEEE Press, 2019: 1-4.
[14]	HOSSAIN M R , HOSSAIN M S . Efficient FPGA implementation of modular arithmetic for elliptic curve cryptography[C]// Proceedings of 2019 International Conference on Electrical,Computer and Communication Engineering (ECCE). Piscataway:IEEE Press, 2019: 1-6.
[15]	DING J N , LI S G , GU Z . High-speed ECC processor over NIST prime fields applied with toom-cook multiplication[J]. IEEE Transactions on Circuits and Systems I:Regular Papers, 2019,66(3): 1003-1016.
[16]	ROY D B , MUKHOPADHYAY D . High-speed implementation of ECC scalar multiplication in GF(p) for generic Montgomery curves[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2019,27(7): 1587-1600.
[17]	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.
[18]	KHAN S , JAVEED K , SHAH Y A . High-speed FPGA implementation of full-word Montgomery multiplier for ECC applications[J]. Microprocessors and Microsystems, 2018,62: 91-101.
[19]	ZHANG D , BAI G Q . High-performance implementation of SM2 based on FPGA[C]// Proceedings of 2016 8th IEEE International Conference on Communication Software and Networks. Piscataway:IEEE Press, 2016: 718-722.
[20]	GARG H K , XIAO H S . New residue arithmetic based barrett algorithms:modular integer computations[J]. IEEE Access, 2016,4: 4882-4890.
[21]	BRIER E , JOYE M . Weierstra? elliptic curves and side-channel attacks[C]// International Workshop on Public Key Cryptography. Berlin:Springer, 2002: 335-345.
[22]	JAVEED K , WANG X J . FPGA based high speed SPA resistant elliptic curve scalar multiplier architecture[J]. International Journal of Reconfigurable Computing,2016, 2016:6371403.
[23]	YU W , WANG K P , LI B ,et al. Montgomery algorithm over a prime field[J]. Chinese Journal of Electronics, 2019,28(1): 39-44.
[24]	HU X H , ZHENG X , ZHANG S S ,et al. A high-performance elliptic curve cryptographic processor of SM2 over GF(p)[J]. Electronics, 2019,8(4): 431.
[25]	WU T , YE J H , LU J . Hardware implementation of SM2 ECC protocols on FPGAs[C]// Proceedings of 2021 IEEE 5th Information Technology,Networking,Electronic and Automation Control Conference. Piscataway:IEEE Press, 2021: 33-37.
[26]	王腾飞, 张海峰, 许森 . SM2 专用指令协处理器设计与实现[J]. 计算机工程与应用, 2022,58(2): 102-109.
	WANG T F , ZHANG H F , XU S . Design and implementation of SM2 co-processor with specific instructions[J]. Computer Engineering and Applications, 2022,58(2): 102-109.
[27]	XIAO Y , LIN W B , ZHAO Y ,et al. A high-speed elliptic curve cryptography processor for teleoperated systems security[J]. Mathematical Problems in Engineering,2021, 2021:6633925.
[28]	杨国强, 丁杭超, 邹静 ,等. 基于高性能密码实现的大数据安全方案[J]. 计算机研究与发展, 2019,56(10): 2207-2215.
	YANG G Q , DING H C , ZOU J ,et al. A big data security scheme based on high-performance cryptography implementation[J]. Journal of Computer Research and Development, 2019,56(10): 2207-2215.

Metrics

Recommended 0

No Suggested Reading articles found!

时钟	KOA乘法	快速模约减	中间变量	计算结果
1	T₁=X₁Z₂	—	T₆=2b	—
2	T₂=X₂Z₁	T ₁ Mod P_SM2	T₆=4b	—
3	T₃=Z₁Z₂	T ₂ Mod P_SM2	—	X₁Z₂
4	T₄=X₁X₂	T ₃ Mod P_SM2	T₁=T₁–T₂	X₂Z₁
5	T₅=aT₃	T ₄ Mod P_SM2	T₂=T₁+T₂	Z₁Z₂, X₁Z₂–X₂Z₁
6	T₆=T₆T₃	T ₅ Mod P_SM2	—	X₁X₂, X₁Z₂+X₂Z₁
7	T₁=T₁2	T ₆ Mod P_SM2	T₄=T₄–T₅	aZ₁Z₂
8	T₂=T₆T₂	T ₁ Mod P_SM2	—	4bZ₁Z₂,X₁X₂–aZ₁Z₂
9	T₄=T₄2	T ₂ Mod P_SM2	—	(X₁Z₂–X₂Z₁) ²
10	T₁=x_GT₁	T ₄ Mod P_SM2	—	4bZ₁Z₂(X₁Z₂+X₂Z₁)
11	—	T₁ Mod P_SM2	T₄=T₄–T₂	(X₁X₂–aZ₁Z₂)²
12	—	—	—	x_G(X₁Z₂–X₂Z₁)²,
				(X₁X₂–aZ₁Z₂)²–
				4bZ₁Z₂(X₁Z₂+X₂Z₁)

时钟	KOA乘法	快速模约减	中间变量	计算结果
1	T₁=Z₁2	—	T₄=2b	—
2	T₂=X₁2	T ₁ Mod P_SM2	T₄=4b	—
3	T₃=aT₁	T ₂ Mod P_SM2	—	Z₁2
4	T₄=T₄T₁	T ₃ Mod P_SM2	—	X₁2
5	T₅=X₁Z₁	T ₄ Mod P_SM2	T₂=T₂–T₃	aZ ₁2
6	T₁=T₁T₄	T ₅ Mod P_SM2	T₃=T₂+T₃	4 bZ₁2,X₁2–aZ₁2
7	T₄=T₅T₄	T ₁ Mod P_SM2	T₃=2T₃	X₁ Z ₁,X₁2+aZ₁2
8	T₂=T₂2	T ₄ Mod P_SM2	T₃=2T₃	4 bZ₁4,2(X₁2+aZ₁2)
9	T₃=T₅T₃	T ₂ Mod P_SM2	T₄=2T₄	4 bX₁ Z₁3,4(X₁2+aZ₁2)
10	—	T₃ Mod P_SM2	T₂=T₂–T₄	(X₁2–aZ₁2)²,8 bX₁Z ₁3
11	—	—	T₁=T₁+T₃	4 X₁ Z ₁(X₁2+aZ₁2),
				(X₁2–aZ₁2)²–8 bX₁Z ₁3
12	—	—	—	4 X₁ Z ₁(X₁2+aZ₁2)+4 bZ ₁4

模块	频率/MHz	LUT	REG	DSP	计算周期
模加减	27	3 185	0	0	1
KOA快速乘法	27	1 993	0	144	1
快速模约减	27	2 609	0	0	1
Barrett模乘	27	5 131	2 323	144	6
基4模逆	27	8 625	1 524	0	212
点加	27	8 583	4 380	144	12
倍点	27	9 627	3 620	144	12
点乘	27	19 087	12 906	288	3 064
坐标转换	27	25 486	5 925	144	225
主控状态机	50	9 999	22 943	0	—

运算	坐标系
运算	仿射坐标	标准射影坐标	Jacobian加重射影坐标	蒙哥马利(标准射影坐标)
点加	I+2M+S	13M+2S	12M+4S	8M+2S
倍点	I+2M+2S	8M+5S	4M+6S	6M+3S

器件	速度/（次·秒^-1）	提升倍数
CPU（Intel i5-8300）	800	—
FPGA（任意参数）	31 936	39.92
FPGA（推荐参数）	281 984	352.48

Optimization of reconfigurable SM2 algorithm over prime filed

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 28

Related Articles 15

Metrics

Recommended 0

方案	器件	参数类型	时钟频率/MHz	点乘性能（次·秒^-1）	运算时钟周期数
文献[2]	Virtex-7	任意	225.0	671	335 360
文献[6]	ASIC 65 nm	任意	546.5	1 375	397 300
文献[9]	Virtex-7	任意	90.7	1 378	65 783
文献[17]	Virtex-7	任意	177.7	676	262 650
文献[4]	ASIC 0.13 μm	推荐	163.7	49 105	3 333
文献[5]	ASIC 0.13 μm	推荐	214.0	45 147	4 740
文献[12]	Virtex-6	推荐	166.0	10 807	15 360
文献[16]	XC7Z020	推荐	268.1	2 173	123 187
本文方案	Xcku-060	任意推荐	27.027.0	9988 812	27 0283 064

方案	器件	抵抗SPA	时钟频率/MHz	性能/（次·秒^-1）	面积/ kslice	时间/ms	AT	本文性能提高倍数	本文AT提高倍数
文献[19]	StratixII	是	62.3	1 298	4.74	0.77	3.65	6.79	6.91
文献[24]	xc6vlx760	否	38.0	2 703	6.91	0.37	2.56	3.26	4.84
文献[25]	XC7V585-3	是	244.0	1 645	5.35	0.61	3.26	5.36	6.18
文献[26]	ZYNQ ZC706	是	110.0	444	7.15	2.25	16.09	19.85	30.47
文献[27]	xc6vlx760	否	38.4	2 703	10.06	0.37	3.72	3.26	7.05
本文方案	Xcku-060	是	27.0	8 812	4.80	0.11	0.53	—	—

功能	LUT	REG	DSP	计算周期
SM3	2 677	1 712	0	182
共享模块	29 531	13 001	144	519
签名	30 823	22 981	288	3 768
验签	32 543	22 586	288	7 591

[1]	Rong ZENG, Xiao HANG. Reconfigurable intelligent surface assist wireless channel estimation algorithm in Internet of vehicles environment [J]. Journal on Communications, 2022, 43(8): 142-150.
[2]	Haiyan GUO, Zhen YANG, Yulong ZOU, Bin LYU, Yuntian FENG, Yujuan ZHAO. Double-RIS assisted anti-jamming communication method based on joint active and passive beamforming optimization [J]. Journal on Communications, 2022, 43(7): 21-30.
[3]	Zhengyu ZHU, Gengwang HOU, Chongwen HUANG, Gangcan SUN, Wanming HAO, Jing LIANG. Systems resource allocation algorithm for RIS-assisted D2D secure communication based on parallel CNN [J]. Journal on Communications, 2022, 43(3): 172-179.
[4]	Bin LI, Xiaojie CHEN, Feng FENG, Qinglei ZHOU. FPGA multi-unit parallel optimization and implementation of post-quantum cryptography CRYSTALS-Kyber [J]. Journal on Communications, 2022, 43(2): 196-207.
[5]	Songlin ZHOU, Junwen TANG, Luohao LIU, You WU, Changhao LIU, Yifei JIN, Fan YANG, Shenheng XU, Maokun LI. Review of array antenna and its application based on electromagnetic surface [J]. Journal on Communications, 2022, 43(12): 13-23.
[6]	Kui TANG, Qi HU, Junming ZHAO, Ke CHEN, Yijun FENG. RIS-based indoor wireless communication signal enhancement system [J]. Journal on Communications, 2022, 43(12): 24-31.
[7]	Haixia LIU, Hao YI, Xiangjin MA, Shuyao YUE, Xudong KONG, Pei MA, Yuxin ZENG, Long LI. Indoor wireless signal coverage and enhancement based on passive reconfigurable intelligent metasurface [J]. Journal on Communications, 2022, 43(12): 32-44.
[8]	Xianhao SHEN, Ziling ZENG, Shaohua NIU. Reconfigurable intelligent surface assisted resource optimization method for heterogeneous network [J]. Journal on Communications, 2022, 43(11): 171-182.
[9]	Bin LI, Wenshuai LIU, Wancheng XIE, Zesong FEI. Computation offloading scheme for RIS-empowered UAV edge network [J]. Journal on Communications, 2022, 43(10): 223-233.
[10]	Sai LI, Liang YANG, Qimei CUI, Siyuan YU. Performance analysis of RIS-assisted mixed RF/THz system [J]. Journal on Communications, 2022, 43(1): 49-58.
[11]	Rongna XIE,Hui LI,Guozhen SHI,Yunchuan GUO. Attribute-based lightweight reconfigurable access control policy [J]. Journal on Communications, 2020, 41(2): 112-122.
[12]	Xiaodong FU,Yongcheng LI,Gangxiang SHEN. Novel node upgradation strategy for migration to elastic optical networks [J]. Journal on Communications, 2018, 39(9): 76-83.
[13]	Chao WANG,Xiao-dong HAN,Rui WANG,Xi ZHOU,Lin-lu YANG,Ya-ping LIU. Study of key technology for reconfigurable satellite platform supporting network interconnection [J]. Journal on Communications, 2017, 38(Z1): 83-87.
[14]	Mian DAI,Guang CHENG. Sketch-based data plane hardware model for software-defined measurement [J]. Journal on Communications, 2017, 38(10): 113-121.
[15]	Dan ZHAO,Feng WEN,Xin XU,Peng WANG,Bo CHEN. Construction mechanism for service path over reconfigurable service-centric network [J]. Journal on Communications, 2016, 37(Z1): 147-155.