Design of High Area Efficiency Elliptic Curve Scalar Multiplier Based on Fast Modulo Reduction of Bit Reorganization

LIU Zhiwei; ZHANG Qi; HUANG Hai; YANG Xiaoqiu; CHEN Guanbai; ZHAO Shilei; YU Bin

doi:10.11999/JEIT221446

Volume 46 Issue 1

Jan. 2024

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2024 > 46(1): 344-352

LIU Zhiwei, ZHANG Qi, HUANG Hai, YANG Xiaoqiu, CHEN Guanbai, ZHAO Shilei, YU Bin. Design of High Area Efficiency Elliptic Curve Scalar Multiplier Based on Fast Modulo Reduction of Bit Reorganization[J]. Journal of Electronics & Information Technology, 2024, 46(1): 344-352. doi: 10.11999/JEIT221446

Citation:

LIU Zhiwei, ZHANG Qi, HUANG Hai, YANG Xiaoqiu, CHEN Guanbai, ZHAO Shilei, YU Bin. Design of High Area Efficiency Elliptic Curve Scalar Multiplier Based on Fast Modulo Reduction of Bit Reorganization[J]. Journal of Electronics & Information Technology, 2024, 46(1): 344-352. doi: 10.11999/JEIT221446

Citation:

LIU Zhiwei, ZHANG Qi, HUANG Hai, YANG Xiaoqiu, CHEN Guanbai, ZHAO Shilei, YU Bin. Design of High Area Efficiency Elliptic Curve Scalar Multiplier Based on Fast Modulo Reduction of Bit Reorganization[J]. Journal of Electronics & Information Technology, 2024, 46(1): 344-352. doi: 10.11999/JEIT221446

PDF( 2362 KB)

Design of High Area Efficiency Elliptic Curve Scalar Multiplier Based on Fast Modulo Reduction of Bit Reorganization

doi: 10.11999/JEIT221446

College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China

Funds: The National Key R&D Program of China (2018YFB2202101), Special Projects for the Central Government to Guide the Development of Local Science and Technology (ZY20B11), Fundamental Research Foundation for of Heilongjiang Province (2019KYYWF0214)

Received Date: 2022-11-17
Rev Recd Date: 2023-06-15

Available Online: 2023-06-22

Publish Date: 2024-01-17

Abstract

Abstract

To solve the problem that existing elliptic curve cryptography scalar multipliers are difficult to balance flexibility and area efficiency, a scalar multiplier with high area efficiency based on bit reorganization fast modular reduction is designed. Firstly, according to the operation characteristics of elliptic curve scalar multiplication, a hardware multiplexing operation unit that can realize two operations of multiplication and modular inversion is designed to improve the utilization rate of hardware resources, and the Karatsuba-Ofman algorithm is used to improve the calculation performance. Secondly, a fast modular reduction algorithm based on bit reorganization is designed, and a hardware architecture supporting secp256k1, secp256r1 and SCA-256 (SM2 standard recommended curve) fast modular reduction calculation is implemented. Finally, the scheduling of modular operations for point addition and point doubling is optimized to improve the utilization of multiplication and fast modular reduction, and reduce the number of cycles required for scalar multiplication calculations. The designed scalar multiplier requires 275 k equivalent gates in 55 nm CMOS technology, the scalar multiplication operation speed is 48309 times/s, and the area-time product reaches 5.7.
- Elliptic curve cryptography,
- Hardware implementation,
- Secp256k1,
- Scalar multiplication,
- Fast modular reduction

FullText(HTML)

References(25)

References

[1]	ANSI. ANSI X9.63 Public key cryptography for the financial services industry: Elliptic curve key agreement and key transport protocols[S]. 2000.
[2]	BARKER E. Digital signature standard[R]. Gaithersburg: National Institute of Standards and Technology, 2000.
[3]	Institute of Electrical and Electronic Engineers. 1363-2000 IEEE standard specifications for public-key cryptography[S]. IEEE, 2000.
[4]	JAVEED K, SAEED K, and GREGG D. High-speed parallel reconfigurable F_p multipliers for elliptic curve cryptography applications[J]. International Journal of Circuit Theory and Applications, 2022, 50(4): 1160–1173. doi: 10.1002/cta.3206
[5]	WANG Huaqun, HE Debiao, and JI Yimu. Designated-verifier proof of assets for bitcoin exchange using elliptic curve cryptography[J]. Future Generation Computer Systems, 2020, 107: 854–862. doi: 10.1016/j.future.2017.06.028
[6]	HU Xianghong, ZHENG Xin, ZHANG Shengshi, et al. A high-performance elliptic curve cryptographic processor of SM2 over GF(p)[J]. Electronics, 2019, 8(4): 431. doi: 10.3390/electronics8040431
[7]	HUANG Hai, NA Ning, XING Lin, et al. An improved wNAF Scalar-multiplication algorithm with low computational complexity by using prime precomputation[J]. IEEE Access, 2021, 9: 31546–31552. doi: 10.1109/ACCESS.2021.3061124
[8]	赵石磊, 杨晓秋, 刘志伟, 等. 一种低复杂度的改进wNAF标量乘算法[J]. 电子学报, 2022, 50(4): 977–983. doi: 10.12263/DZXB.20211016 ZHAO Shilei, YANG Xiaoqiu, LIU Zhiwei, et al. An Improved wNAF Scalar-Multiplication Algorithm With Low Computational Complexity[J]. Acta Electronica Sinica, 2022, 50(4): 977–983. doi: 10.12263/DZXB.20211016
[9]	LIU Zilong, LIU Dongsheng, and ZOU Xuecheng. An efficient and flexible hardware implementation of the dual-field elliptic curve cryptographic processor[J]. IEEE Transactions on Industrial Electronics, 2017, 64(3): 2353–2362. doi: 10.1109/TIE.2016.2625241
[10]	HOSSAIN M S, KONG Yinan, SAEEDI E, et al. High-performance elliptic curve cryptography processor over NIST prime fields[J]. IET Computers & Digital Techniques, 2017, 11(1): 33–42. doi: 10.1049/iet-cdt.2016.0033
[11]	LIU Jianwei, CHENG Dongxu, GUAN Zhenyu, et al. A high speed VLSI implementation of 256-bit scalar point multiplier for ECC over GF(p)[C]. Proceedings of 2018 IEEE International Conference on Intelligence and Safety for Robotics, Shenyang, China, 2018: 184–191.
[12]	HU Xianghong, ZHENG Xin, ZHANG Shengshi, et al. A low hardware consumption elliptic curve cryptographic architecture over GF(p) in embedded application[J]. Electronics, 2018, 7(7): 104. doi: 10.3390/electronics7070104
[13]	CHOI P, LEE M K, KIM J H, et al. Low-complexity elliptic curve cryptography processor based on configurable partial modular reduction over NIST prime fields[J]. IEEE Transactions on Circuits and Systems II:Express Briefs, 2018, 65(11): 1703–1707. doi: 10.1109/TCSII.2017.2756680
[14]	ZHANG Dan and BAI Guoqiang. 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 (EDSSC), Singapore, 2015: 523–526.
[15]	ISLAM M M, HOSSAIN M S, SHAHJALAL M, et al. Area-time efficient hardware implementation of modular multiplication for elliptic curve cryptography[J]. IEEE Access, 2020, 8: 73898–73906. doi: 10.1109/ACCESS.2020.2988379
[16]	HANKERSON D, VANSTONE S, and MENEZES A. Guide to Elliptic Curve Cryptography[M]. New York: Springer, 2004: 312.
[17]	LUCCA A V, SBORZ G A M, LEITHARDT V R Q, et al. A review of techniques for implementing elliptic curve point multiplication on hardware[J]. Journal of Sensor and Actuator Networks, 2021, 10(1): 3. doi: 10.3390/jsan10010003
[18]	王敏, 吴震. 抗SPA攻击的椭圆曲线NAF标量乘实现算法[J]. 通信学报, 2012, 33(S1): 228–232. WANG Min and WU Zhen. Algorithm of NAF scalar multiplication on ECC against SPA[J]. Journal on Communications, 2012, 33(S1): 228–232.
[19]	SOLINAS J A. Efficient arithmetic on Koblitz curves[J]. Designs, Codes and Cryptography, 2000, 19(2): 195–249. doi: 10.1023/A:1008306223194
[20]	KARATSUBA A. Multiplication of multidigit numbers on automata[J]. Soviet Physics Doklady, 1963, 7: 595–596.
[21]	CHOI P, LEE M K, KONG J T, et al. Efficient design and performance analysis of a hardware right-shift binary modular inversion algorithm in GF(p)[J]. Journal of Semiconductor Technology and Science, 2017, 17(3): 425–437. doi: 10.5573/JSTS.2017.17.3.425
[22]	HU Xianghong, LI Xueming, ZHENG Xin, et al. A high speed processor for elliptic curve cryptography over NIST prime field[J]. IET Circuits, Devices & Systems, 2022, 16(4): 350–359. doi: 10.1049/CDS2.12110
[23]	于斌, 黄海, 刘志伟, 等. 面向多椭圆曲线的高速标量乘法器设计与实现[J]. 通信学报, 2020, 41(12): 100–109. doi: 10.11959/j.issn.1000-463X.2020226 YU Bin, HUANG Hai, LIU Zhiwei, et al. Design and implementation of high-speed scalar multiplier for multi-elliptic curve[J]. Journal on Communications, 2020, 41(12): 100–109. doi: 10.11959/j.issn.1000-463X.2020226
[24]	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. doi: 10.1109/ACCESS.2019.2958491
[25]	ASIF S, HOSSAIN M S, and KONG Yinan. High-throughput multi-key elliptic curve cryptosystem based on residue number system[J]. IET Computers & Digital Techniques, 2017, 11(5): 165–172. doi: 10.1049/iet-cdt.2016.0141