一种高速可伸缩的双域Montgomery模乘器架构

doi:10.19678/j.issn.1000-3428.0065018

摘要/Abstract

摘要：

为提高Montgomery模乘在硬件实现上的运算速度并保持较高的性能，提出一种适用于高速椭圆曲线密码处理器的高速可伸缩的双域Montgomery模乘算法及其硬件架构。通过迭代调用Karatsuba乘法，实现最大位宽为576 bit的Montgomery模乘，并利用Montgomery模乘相邻运算部分数据的无关性，通过提前计算部分数据，减少Montgomery模乘运算使用的时钟周期数。基于Karatsuba算法中多次使用大位宽加法运算带来资源消耗大和超长进位链的问题，设计基于双域4-2压缩变换的加法选择电路结构，将一个超大位宽的加法运算拆分成多个小位宽的加法，在一个时钟周期内同时得到所有加法运算的结果，并根据加法的进位输出进行最终输出结果的选择，有效缩短加法进位链的延时。实验结果表明，相比基于ASIC的Montgomery模乘实现方案，Montgomery模乘算法及硬件架构具有更高的灵活性，在65 nm的CMOS工艺下进行逻辑综合，最高时钟频率能够达到459 MHz，面积资源占用为480 254 µm²，完成0~145 bit、146~289 bit、290~435 bit和436~576 bit的Montgomery模乘分别仅需要8.72 ns、23.98 ns、58.86 ns和71.94 ns，且具有较低的面积时间积。

关键词: Montgomery模乘器, Karatsuba乘法, 可伸缩, 椭圆曲线密码, 双域4-2压缩变换

Abstract:

A high-speed scalable dual-field Montgomery Modular Multiplier(MMM) algorithm and its hardware architecture are proposed for an Elliptic Curve Cryptography(ECC) processor to improve its performance. The 576 bit scalable MMM is implemented in this study by iteratively calling the Karatsuba algorithm.The number of clock cycles is reduced by calculating some of the data in advance, utilizing the data irrelevance in the adjacent operations of the MMM. To avoid large resource consumption and a long carry chain in the implementation of the Karatsuba algorithm, a carry-select addition approach based on dual-field 4-2 compressors is proposed. It splits a large addition into several small additions, simultaneously obtains all the addition results, and selects the final result according to the addition carries, shortening the delay of the carry chain.The experimental results show that, compared with other MMM implementations in Application-Specific Integrated Circuits(ASIC), the proposed MMM hardware architecture has higher flexibility.Synthesized with a 65 nm Complementary Metal-Oxide-Semiconductor(CMOS) process, the maximum frequency is 459 MHz and the area is 480 254 µm². Completing MMMs of 0-145 bit, 146-289 bit, 290-435 bit, and 436-576 bit takes 8.72 ns, 23.98 ns, 58.86 ns, and 71.94 ns, respectively, with a low area-time product.

Key words: Montgomery Modular Multiplier(MMM), Karatsuba multiplication, scalable, Elliptic Curve Cryptography(ECC), dual-field 4-2 compression transformation

陈億, 杨萱, 曾涵, 李伟. 一种高速可伸缩的双域Montgomery模乘器架构[J]. 计算机工程, 2023, 49(8): 283-290.

Yi CHEN, Xuan YANG, Han ZENG, Wei LI. A High-Speed Scalable Dual-Field Montgomery Modular Multiplier Architecture[J]. Computer Engineering, 2023, 49(8): 283-290.

http://www.ecice06.com/CN/Y2023/V49/I8/283

图/表 13

图1 4n bit Karatsuba乘法

Fig.1 4n bit Karatsuba multiplication

图2 优化前的146~289 bit的Montgomery模乘算法流图

Fig.2 MMM algorithm flow diagram before optimization for 146-289 bit

图3 优化后的146~289位的Montgomery模乘算法流图

Fig.3 MMM algorithm flow diagram after optimization for 146-289 bit

图4 优化后的290~435 bit的Montgomery模乘算法流图

Fig.4 MMM algorithm flow diagram after optimization for 290-435 bit

图5 优化后的436~576 bit的Montgomery模乘算法流图

Fig.5 MMM algorithm flow diagram after optimization for 436-576 bit

图6 Montgomery模乘硬件架构

Fig.6 Hardware architecture of Montgomery modular

图7 双域乘法器结构

Fig.7 Structure of dual-field multiplication

图8 双域4-2压缩变换单元

Fig.8 Dual-field 4-2 compressor conversion unit

图9 素数域KO_Add数据流图

Fig.9 Prime number field KO_Add data flow diagram

图10 二元域KO_Add数据流图

Fig.10 Binary field KO_Add data flow diagram

图11 进位加法选择电路

Fig.11 Carry-select addition circuit

表1 不同位宽Montgomery模乘运算时间

Table 1 Montgomery modular multiplier operation time with different length

位宽/bit	时钟周期数/个	运算时间/ns
0~145	4	8.72
146~289	11	23.98
290~435	27	58.86
436~576	33	71.94

表2 模乘性能对比

Table 2 Performance comparison of modular multiplier

方法	工艺制程/nm	位宽/bit	面积/µm²	等效门/KGates	最高时钟频率/MHz	运算时间/ns	AT/(ms·Gate^-1)
文献[23]方法	65	256	1 638 647	—	144	6.94	21.866
文献[24]方法	65	256	169 390	—	497	44.22	14.403
文献[6]方法	65	256	—	13.26	549	468.00	9.235
文献[16]方法	55	256	—	236.00	588	73.10	56.461
本文方法	65	128 256 384 576	480 254	333.51	459	8.72 23.98 58.86 71.94	8.053 22.148 54.360 66.442

参考文献 24

1	HAMMI B, FAYAD A, KHATOUN R, et al. A lightweight ECC-based authentication scheme for Internet of Things(IoT). IEEE Systems Journal, 2020, 14(3): 3440- 3450. doi: 10.1109/JSYST.2020.2970167
2	RIVEST R L, SHAMIR A, ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 1978, 21(2): 120- 126. doi: 10.1145/359340.359342
3	KOBLITZ N. Elliptic curve cryptosystems. Mathematics of Computation, 1987, 48(177): 203- 209. doi: 10.1090/S0025-5718-1987-0866109-5
4	MILLER V S. Use of elliptic curves in cryptography[C]//Proceedings of Theory and Application of Crypto-graphic Techniques Conference. Berlin, Germany: Springer, 2007: 417-426.
5	LAUTER K. The advantages of elliptic curve cryptography for wireless security. IEEE Wireless Communications, 2004, 11(1): 62- 67. doi: 10.1109/MWC.2004.1269719
6	HOSSAIN M S, KONG Y N, SAEEDI E, et al. High-performance elliptic curve cryptography processor over NIST prime fields. IET Computers & Digital Techniques, 2017, 11(1): 33- 42.
7	YEH L Y, CHEN P J, PAI C C, et al. An energy-efficient dual-field elliptic curve cryptography processor for Internet of things applications. IEEE Transactions on Circuits and Systems, 2020, 67(9): 1614- 1618.
8	BASU ROY D, MUKHOPADHYAY D. High-speed implementation of ECC scalar multiplication in GF(p) for generic Montgomery curves. IEEE Transactions on Very Large Scale Integration Systems, 2019, 27(7): 1587- 1600. doi: 10.1109/TVLSI.2019.2905899
9	MONTGOMERY P L. Modular multiplication without trial division. Mathematics of Computation, 1985, 44(170): 519- 521. doi: 10.1090/S0025-5718-1985-0777282-X
10	WALTER C D. Montgomery exponentiation needs no final subtractions. Electronics Letters, 1999, 35(21): 1831. doi: 10.1049/el:19991230
11	MANOCHEHRI K, POURMOZAFARI S. Modified radix-2 Montgomery modular multiplication to make it faster and simpler[C]//Proceedings of International Conference on Information Technology: Coding and Computing. Washington D. C., USA: IEEE Press, 2005: 598-602.
12	KUANG S R, WANG J P, CHANG K C, et al. Energy-efficient high-throughput Montgomery modular multipliers for RSA cryptosystems. IEEE Transactions on Very Large Scale Integration Systems, 2013, 21(11): 1999- 2009. doi: 10.1109/TVLSI.2012.2227846
13	KUANG S R, WU K Y, LU R Y. Low-cost high-performance VLSI architecture for Montgomery modular multiplication. IEEE Transactions on Very Large Scale Integration Systems, 2016, 24(2): 434- 443. doi: 10.1109/TVLSI.2015.2409113
14	ZHANG B, CHENG Z M, PEDRAM M. An iterative Montgomery modular multiplication algorithm with low area-time product. IEEE Transactions on Computers, 2023, 72(1): 236- 249. doi: 10.1109/TC.2022.3154164
15	ZHANG B, CHENG Z M, PEDRAM M. High-radix design of a scalable Montgomery modular multiplier with low latency. IEEE Transactions on Computers, 2022, 71(2): 436- 449. doi: 10.1109/TC.2021.3052999
16	BIE M N, LI W, CHEN T, et al. An energy-efficient reconfigurable asymmetric modular cryptographic operation unit for RSA and ECC. Frontiers of Information Technology & Electronic Engineering, 2022, 23(1): 134- 144.
17	KARATSUBA A A, OFMAN Y P. Multiplication of many-digital numbers by automatic computers. Doklady Akademii Nauk SSSR, 1962, 145(2): 293- 294.
18	CHOW G C T, EGURO K, LUK W, et al. A karatsuba-based Montgomery multiplier[C]//Proceedings of International Conference on Field Programmable Logic and Applications. Washington D. C., USA: IEEE Press, 2011: 434-437.
19	FENG X A, LI S G. A high performance FPGA implementation of 256-bit elliptic curve cryptography processor over GF(p). IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2015, 98(3): 863- 869.
20	DING J N, LI S G. Broken-Karatsuba multiplication and its application to Montgomery modular multiplication[C]//Proceedings of the 27th International Conference on Field Programmable Logic and Applications. Washington D. C., USA: IEEE Press, 2017: 1-4.
21	DING J N, LI S G. A low-latency and low-cost Montgomery modular multiplier based on NLP multiplication. IEEE Transactions on Circuits and Systems, 2020, 67(7): 1319- 1323.
22	LEE M M O, CHO B L. Ultra-high speed parallel multiplier with new first partial product addition algorithm[C]//Proceedings of the 4th International Conference on ASIC. Washington D. C., USA: IEEE Press, 2002: 592-595.
23	GU Z, LI S G. An implementation of karatsuba-based Montgomery modular multiplication with only half-size additions[C]//Proceedings of IEEE International Symposium on Circuits and Systems. Washington D. C., USA: IEEE Press, 2018: 1-5.
24	GU Z, LI S G. A division-free toom-cook multiplication-based Montgomery modular multiplication. IEEE Transactions on Circuits and Systems II: Express Briefs, 2019, 66(8): 1401- 1405. doi: 10.1109/TCSII.2018.2886962

[1]	尤文珠, 葛海波. 利用多基数系统的高效椭圆曲线多标量乘算法[J]. 计算机工程, 2021, 47(2): 182-187.
[2]	吴昆, 魏国珩. 基于ECC的无证书WSN广播信息认证方案[J]. 计算机工程, 2020, 46(12): 157-162,200.
[3]	谷建光. 抗能量分析攻击的门限窗口NAF标量乘算法[J]. 计算机工程, 2019, 45(8): 296-299,308.
[4]	俞超杰,陈翔,姚振,杨坚. 软件定义无线Mesh网络中的可伸缩视频传输系统[J]. 计算机工程, 2019, 45(5): 232-236.
[5]	韩煦, 张国强, 高茜. 基于SVC与多网络接口的DASH调度算法[J]. 计算机工程, 2019, 45(12): 243-248.
[6]	王明青,杨博文,杨坚. LTE可伸缩视频组播的动态资源分配算法[J]. 计算机工程, 2018, 44(10): 274-280.
[7]	邬可可,李慧云,闫立军. 一种防御差分功耗分析的ECC同种映射模型[J]. 计算机工程, 2017, 43(10): 115-119,125.
[8]	刘博雅,刘年义,杨亚涛,李子臣. 基于椭圆曲线密码的无线射频识别双向认证协议[J]. 计算机工程, 2017, 43(1): 196-200.
[9]	沈海波,陈勇昌. 联邦物联网中的认证机制研究[J]. 计算机工程, 2016, 42(9): 110-115.
[10]	柳寻,杨恩众,曾祥迟,杨坚. OpenFlow网络下SVC视频的多路径传输[J]. 计算机工程, 2016, 42(7): 77-81.
[11]	完颜许哲,张洋洋,陈双武,杨坚. OpenFlow网络中可伸缩视频的自适应传输算法[J]. 计算机工程, 2016, 42(7): 100-103.
[12]	李宏宇，付东来. 一种改进的组签名平台配置远程证明机制[J]. 计算机工程, 2014, 40(5): 99-102.
[13]	王天成，张建中. 基于椭圆曲线的代理多重盲签名方案[J]. 计算机工程, 2013, 39(9): 189-191,205.
[14]	刘涛，熊焰，黄文超，陆琦玮，龚旭东. 基于信誉模型的WSN密钥管理方案[J]. 计算机工程, 2013, 39(11): 123-126.
[15]	康鸿雁. 基于ECC的RFID组证明协议分析及改进[J]. 计算机工程, 2013, 39(1): 153-156.

选择文件类型/文献管理软件名称

选择包含的内容