Montgomery模乘法器的实现与优化

科学技术与工程６卷２００６年２月２２日收到南京市软件发展资金（２００４软资１１６号）资助第一作者简介：李明久（１９８１—），男，江苏泰州人，硕士研究生，研究方向：网络信息安全。

Ｅ－ｍａｉｌ：ｌｉｍｉｎｇｊｉｕ＠ｈｏｔｍａｉｌ．ｃｏｍ。

第６卷第１２期２００６年６月１６７１－１８１５（２００６）１２－１６２８－０４科学技术与工程ＳｃｉｅｎｃｅＴｅｃｈｎｏｌｏｇｙａｎｄＥｎｇｉｎｅｅｒｉｎｇＶｏｌ．６Ｎｏ．１２Ｊｕｎ．２００６２００６Ｓｃｉ．Ｔｅｃｈ．Ｅｎｇｎｇ．ｃMontgomery 算法分析与研究李明久季晓勇刘鞭箭（南京大学电子科学与工程系，南京２１００９３）摘要Ｍｏｎｔｇｏｍｅｒｙ算法作为一种快速大数模乘算法，常被应用于ＲＳＡ、ＥｌＧａｍａｌ等公钥密码算法的基本运算。

对Ｍｏｎｔｇｏｍｅｒｙ算法进行了深入的剖析，系统地进行了理论推导，通过实验应用分析比较了两种有代表性的优化方案，并针对性地给出了其他方面的一些改进建议。

关键词ＲＳＡＭｏｎｔｇｏｍｅｒｙ算法模乘中图法分类号ＴＰ３０９；文献标识码Ａ随着信息技术的飞速发展，网络通信中的身份认证和信息安全传输问题正逐渐受到人们的关注和重视。

数字签名、验证和密钥交换都离不开ＲＳＡ、ＥｌＧａｍａｌ等公钥密码体制算法。

ＲＳＡ等算法最基本最耗时的计算工作就是大数模乘运算。

Ｍｏｎｔｇｏｍｅｒｙ算法作为一种快速且有效的大数模乘算法，得到了广泛的研究和应用。

目前的一些文章主要是从具体应用的角度对其进行一些改进分析，并没有对算法本身及其基本改进方法进行系统的理论分析。

本文对Ｍｏｎｔｇｏｍｅｒｙ算法进行了深入的剖析和系统的理论推导；分析比较了有代表性的两种优化实现方案，在实际应用中进行了性能比较；并给出了其他方面的一些改进建议。

１Ｍｏｎｔｇｏｍｅｒｙ算法１．１算法描述及证明该算法由Ｐ．Ｌ．Ｍｏｎｔｇｏｍｅｒｙ在１９８５年提出［１］，用于ＴＲ－１ｍｏｄＮ的快速计算。

Ｍｏｎｔｇｏｍｅｒｙ算法基于下面的定理：［定理］设Ｎ和Ｒ是互素的两个整数，且ＲＲ－１－ＮＮ′＝１（即Ｎ′＝－Ｎ－１ｍｏｄＲ），则对于任意整数Ｔ，当Ｍ＝ＴＮ′ｍｏｄＲ时，（Ｔ＋ＭＮ）／Ｒ为整数，且满足（Ｔ＋ＭＮ）／Ｒ≡ＴＲ－１ｍｏｄＮ。

Montgomery模乘算法一、介绍Montgomery模乘算法是一种高效的模乘算法，可以在不使用除法的情况下进行模乘运算，适用于计算机硬件实现。

该算法最初由彼得L蒙哥马利（Peter L.Montgomery）在1985年提出，被广泛应用于密码学领域，特别是在RSA加密算法中。

二、算法原理在介绍Montgomery模乘算法之前，我们先来了解一下模乘运算的定义。

模乘运算是指对两个数a和b进行乘法运算后，再对结果进行模运算，即(a*b)%n。

在RSA加密算法中，n通常是一个大素数，a和b是两个大整数。

传统的模乘运算需要进行除法运算，这是一种比较耗时的运算。

Montgomery模乘算法的核心思想是将模运算转化为一系列的加法和移位运算，从而避免了除法运算，提高了运算效率。

具体来说，Montgomery模乘算法的运算过程如下：1. 预处理：首先，我们需要将模数n转换为一个特殊的数R，使得R是2的k次幂，且R>n。

这里k是一个正整数，通常取值为32或64。

然后，我们计算出一个数T，使得T*R-1是n的倍数，即(T*R-1)%n=0。

这个T的值可以使用扩展欧几里得算法来计算。

预处理的结果是R和T这两个数。

2. 转换：对于要进行模乘运算的两个数a和b，我们需要将它们分别乘以R，然后对结果进行模T，得到两个新的数a'和b'。

这个过程称为转换。

3. 乘法：接下来，我们对a'和b'进行乘法运算，得到一个新的数c'。

这个数可能大于T，因此我们需要对它进行一定的处理。

4. 归约：最后，我们对c'进行归约运算，得到最终的结果c。

归约运算的过程是将c'乘以T的逆元，然后对R取模，即c=(c'*T^(-1))%R。

三、算法优点Montgomery模乘算法的优点在于它可以在不使用除法的情况下进行模乘运算，从而提高了运算效率。

此外，该算法还可以避免一些安全漏洞，例如侧信道攻击和冒险计算攻击。

上海交通大学工学硕士学位论文摘要基于心动阵列的RSA算法的VLSI实现摘要RSA公钥密码算法是目前信息安全领域最成熟，使用最广泛的一种算法。

然而由于RSA加解密运算中使用的大数模幂运算运算量很大，制约了RSA算法的更广泛的应用。

因此，研究一种RSA运算的协处理器具有重要的现实意义。

在本文中我们介绍了一种基于可伸展的Montgomery模乘结构的1024位RSA加解密芯片实现。

文中首先研究了Montgomery模乘算法，并针对模幂运算的特点对算法进行改进，提高了模乘的运算速度。

由本算法设计的模乘单元采用的新型心动阵列结构，可以在有效控制芯片面积的前提下，极大的提高运算频率，从而提高运算速度。

文中还介绍了多种模幂算法，并选取了其中2进制算法的R-L形式作为我们实现模型。

同时，我们对本模幂算法进行改进，使之适合运用于Montgomery模乘算法。

我们还研究了L-R形式的模幂单元作为对照。

经过ModelSim仿真和Design Compiler综合，我们实现的模幂单元在最差条件下能运行于100MHz频率。

在相同的频率下，运算速度是L-R模幂单元的1.5倍，是另一项目组w=2的2w进制算法的模幂单元的1.38倍，适合应用于对运算速度要求较高的场合。

关键词：RSA，Montgomery，模乘，心动阵列，模幂第 III 页A SYSTOLIC ARRAY BASED VLSI IMPLEMENTATIONOF RSA ALGORITHMABSTRACTRSA public-key algorithm is one of the most widely used algorithms in the field of information security. However the intense calculation of modular exponentiation has prevented the algorithm from wider applications. So it has important value to do the research about RSA algorithm coprocessor. In this paper a 1024-bit RSA encryption and decryption chip based on scalable Montgomery Modular Multiplier is proposed.At the beginning of the paper, we introduce the Montgomery modular multiplication algorithm. We improve the algorithm to adapt to the modular exponentiation algorithm so the modular calculation can be speeded up. The modular multiplication unit which is design with the algorithm uses the new systolic array architecture, which can improve the speed by increase the frequency without size increased.We also introduce several modular exponentiation algorithms in the paper. We choice the R-L form of the binary method as the model of our implementation. The algorithm has been improved to adapt to Montgomery modular multiplication algorithm. We also implement the modular exponentiation unit of L-R form as a comparison.This design has been simulated by ModelSim and synthesized by Design Compiler. The module can work on the frequency of 100MHz even in the worst situation. At the frequency, our design is 1.5 times faster than the L-R modular exponentiation unit, and is 1.28 times faster than the 2w algorithm modular exponentiation unit of another project team. So our modular exponentiation module can be used in the application which第 IV 页requires a higher speed.KEY WORDS: RSA, Montgomery, modular multiplier, systolic array, modular exponentiation第 V 页图片目录图 2-1 加密和解密 (7)图 2-2 使用同一个密钥K的加解密 (9)图 2-3 使用不同密钥K1和K2的加解密 (9)图 3-1 2w进制模乘算法模乘次数优化比率和n的关系图 (33)图 4-1 一个7位模乘器(n = 4)的部分积项阵列 (38)图 4-2 PE模块框图 (40)图 4-3 PE模块内部设计图 (41)图 4-4 MM_N模块框图 (42)图 4-5 Qin信号产生示意图 (42)图 4-6 心动阵列结构示意图 (43)图 4-7 一个7位模乘器(n = 4)的各个时钟对应的部分积项阵列 (44)图 4-8 PE_N单元内部电路图 (46)图 4-9 PE_P单元内部电路图 (47)图 4-10 MMprl_N_P_Control模块控制时序 (49)图 4-11 MMprl_N_P_Transferer模块数据收集控制状态机 (50)图 4-12 MMprl_N模块框图 (50)图 4-13 MMprl_N模块内部设计图 (51)图 4-14 MMprl_N模块时序图 (52)图 4-15 MECore_Control状态机框图 (53)图 4-16 MECore_Control模幂运算控制状态机 (54)图 4-17 MECoreLR模块框图 (57)图 4-18 MECoreLR模块内部设计图 (58)图 4-19 MECoreLR模块时序图 (58)图 4-20 MECore_Control_RL状态机框图 (60)图 4-21 MECore_Control_RL模幂运算控制状态机 (61)图 4-22 MECoreRL模块框图 (64)图 4-23 MECoreRL模块内部设计图 (65)图 4-24 MECoreRL模块时序图 (66)图 4-25 RWData_In_N模块内部设计图 (68)图 4-26 RWData模块框图 (71)图 4-27 RWData模块内部设计图 (72)图 4-28 RWData模块运行仿真图 (72)图 4-29 RSA_RL模块框图 (73)图 4-30 RSA_RL模块内部设计图 (74)第 IX 页表格目录表格 4-1 PE模块端口说明 (40)表格 4-2 MM_N模块端口说明 (42)表格 4-3 心动阵列模乘其端口信号的bit图 (45)表格 4-4 PE_N单元的关键路径 (46)表格 4-5 PE_P单元的关键路径 (47)表格 4-6 PE_N和PE_P单元面积 (48)表格 4-7 ShiftReg模块端口说明 (48)表格 4-8 MMprl_N_P_Control模块端口说明 (48)表格 4-9 MMprl_N_P_Transferer模块端口说明 (49)表格 4-10 MMprl_N_P_Transferer有限状态机转移表 (49)表格 4-11 MMprl_N模块端口说明 (51)表格 4-12 MMprl_N模块及其子模块的面积 (52)表格 4-13 MECore_Control模块端口说明 (53)表格 4-14 MECore_Control模块State信号指示值含义说明 (53)表格 4-15 MECore_Control有限状态机转移表 (55)表格 4-16 MECore_Selecte模块端口说明 (55)表格 4-17 MECore_Selecter模块功能描述 (56)表格 4-18 MECore_Ready模块端口说明 (56)表格 4-19 MECore_Ready模块功能描述 (56)表格 4-20 MECoreLR模块端口说明 (57)表格 4-21 MECoreLR模块及其子模块的面积 (59)表格 4-22 MECore_Control_RL模块端口说明 (59)表格 4-23 MECore_Control_RL模块State信号指示值含义说明 (60)表格 4-24 MECore_Control_RL有限状态机转移表 (61)表格 4-25 MECore_Selecter _RL模块端口说明 (62)表格 4-26 MECore_Selecter模块功能描述 (62)表格 4-27 MECore_Ready_RL模块端口说明 (62)表格 4-28 MECore_Ready模块功能描述 (63)表格 4-29 MMprl_N_C模块端口说明 (63)表格 4-30 MECoreRL模块端口说明 (64)表格 4-31 MECoreRL模块及其子模块的面积 (66)表格 4-32 MECoreLR和MECoreRL模幂单元的面积和速度比较 (67)表格 4-33 RWData_In_N模块端口说明 (68)表格 4-34 RWData_Out_N模块端口说明 (69)表格 4-35 RWData_CMD模块端口说明 (69)第 X 页表格 4-36 RWData_CMD模块输出逻辑图 (70)表格 4-37 RWData模块端口说明 (71)表格 4-38 RWData模块CMD指令含义 (71)表格 4-39 RWData模块及其子模块的面积 (72)表格 4-40 RSA_RL模块端口说明 (73)表格 4-41 RSA_RL模块及其子模块的面积 (74)第 XI 页算法目录算法 3-1 Montgomery算法原型 (18)算法 3-2 高基的Montgomery算法 (20)算法 3-3 改进的高基的Montgomery算法 (21)算法 3-4 基-2的Montogomery快速算法 (22)算法 3-5 改进的基-2的Montgomery算法 (24)算法 3-6 基于Montgomery算法的模乘运算 (26)算法 3-7：L-R(从左到右)模幂算法[] (27)算法 3-8：R-L (从右到左)模幂算法 (29)算法 3-9：2w进制模幂算法 (31)算法 3-10基于Montgomery模乘的L-R模幂算法 (33)算法 3-11基于Montgomery模乘的R-L模幂算法 (34)第 XII 页上海交通大学工学硕士学位论文学位论文原创性声明上海交通大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。