蒙哥马利模乘算法改进及硬件实现.pdf

蒙哥马利模乘算法改进及硬件实现任仕伟，王华阳，郝越，薛丞博（北京理工大学 集成电路与电子学院，北京100081）摘 要：在嵌入式和物联网等领域的加密应用场景中，需要在加密实现的性能和资源消耗之间找到综合效率最佳的平衡点.模乘法器是 Rivest-Shamir-Adleman 算法（RSA）和椭圆曲线密码（ECC）等公钥密码算法的核心运算模块，其资源占用和运算速度直接影响上层密码算法的整体性能.本文提出高效低延迟的蒙哥马利模乘算法可以有效降低运算量，减少硬件设计的复杂度，结合使用提出的 5-2 低延迟加法器进一步降低模乘法器的关键路径长度，从而提高算法的运行效率.在 Xilinx-K7 系列平台上实现的 1 024 位模乘运算模块系统主频可达 278 MHz，同时面积时间积（ATP）比已有同类算法提高了 15%以上，综合效率表现最优.结果表明，改进后的蒙哥马利模乘算法硬件资源消耗低，适用于物联网等轻量级密码系统.关键词：加密算法；模乘；蒙哥马利；保留进位加法器中图分类号：TN402 文献标志码：A 文章编号：1001-0645(2024)03-0306-06DOI：10.15918/j.tbit1001-0645.2023.082An Improved Montgomery Modular Multiplication Algorithm andIts Hardware ImplementationREN Shiwei，WANG Huayang，HAO Yue，XUE Chengbo（School of Integrated Circuits and Electronics,Beijing Institute of Technology,Beijing 100081,China）Abstract：In cryptographic application scenarios such as embedded and IoT,it is necessary to balance the per-formance and resource consumption of cryptographic implementation to find the best balance of comprehensiveefficiency.As the core computing module of public key cryptographic algorithms such as Rivest-Shamir-Adle-man algorithm(RSA)and elliptic curve cryptography(ECC),the resource consumption and computing speed ofthe modulo multiplier directly determine the overall performance of the upper layer cryptographic algorithms.The proposed efficient low-latency Montgomery modulo multiplication was designed to effectively reduce theamount of operations and the complexity of hardware design.On this basis,the length of the critical path in themodulo multiplier was arranged to be further reduced by using the proposed 5-2 low-latency adder in combina-tion to improve the algorithm operation efficiency.The system main frequency of the 1024-bit modulo moduleimplemented on the Xilinx-K7 series platform can reach 278 MHz,while the area-time-product（ATP）is im-proved by more than 15%compared with the existing similar algorithms,and the overall efficiency is optimal.The results show that the improved Montgomery modulo multiplication algorithm can give a low hardware re-source consumption,being suitable for lightweight cryptosystems such as IoT.Key words：encryption algorithm；modulo multiplier；Montgomery；carry save adder 数字通信技术的发展在提高信息传输的便利性和效率的同时，也加剧了信息泄漏和窃听的风险.为了加强信息安全，许多加密算法被提出1.目前，作为现代公钥密码学两个主要标准的 Rivest-Shamir-Adle-man 算法（RSA）和椭圆曲线密码（elliptic curve crypto-graphy,ECC）是密码系统研究的焦点之一2 4.收稿日期：2023 04 06基金项目：国家自然科学基金资助项目（62201039）；重庆自然科学基金资助项目（cstc2021jcyj-msxmX1096）作者简介：任仕伟（1985），女，博士，副教授，E-mail：.通信作者：薛丞博（1988），男，博士，实验师，E-mail：.第 44 卷第 3 期北 京 理 工 大 学 学 报Vol.44No.32024 年 3 月Transactions of Beijing Institute of TechnologyMar.2024MdeAC=AemodMA=CdmodMAemodM以 RSA 为例，该算法使用一个模数（modulus）和两个密钥 和，其中至少有一个密钥是私钥.要传递的信息通过模幂运算被加密为，解密阶段同样通过模幂运算解密.的计算过程主要由模乘和幂运算组成.ABNS=ABNSSN从前述可以看出，RSA 算法在加解密的过程中都会进行重复的模乘运算.类似地，ECC 算法中的点乘操作基于模乘操作实现5.对于模乘运算，以 RSA常用的 1 024 位大数为例，设有乘数，被乘数，模数，需要先计算两个 1 024 位大数的积，再将结果积对模数取余数，在此计算过程中将会产生 2 048 位的中间结果.对中间结果的模约减步骤通常需要将与模进行比较，在最坏的情况下，意味着需要依次检查两个长数的每一位.因此模乘运算是 RSA 和 ECC 算法中主要的耗时操作，提高模乘操作的效率对提高公钥密码系统的性能起着关键作用.在现有模乘算法中，蒙哥马利算法6是最有效的方案.该算法提出基于加法及除以 2n（nZ）的替代方法，以避免除法操作7，而除以 2n（nZ）可通过简单的移位操作在硬件上实现，从而达到节省硬件资源的效果.该算法在很多密码学应用中都得到了广泛的应用，如用于抗侧信道攻击、密钥管理和其他依赖安全性的应用8 10，其高效性和安全性得到了广泛认可，成为现代密码学领域中不可或缺的重要工具.然而在物联网等轻量级的应用场景下，由于要兼顾设备资源敏感、低功耗和速度，该算法的性能表现较为有限11 12.为解决前述问题，本文提出使用高效低延迟蒙哥马利模乘及 5-2 低延迟加法器相结合的方法优化基-2 的蒙哥马利模乘的结构，以减少资源消耗并提高计算速度.在 Xilinx-K7 平台上的实现结果表明，与已有同类算法相比，所提出的方法可降低 15%以上的面积时间积（area-time-product,ATP），在资源和速度上达到了很好的平衡，更加适用于物联网安全等轻量型应用场景.1 算法理论基础 1.1 蒙哥马利模乘算法NABR2k1 A,B 2kR=2kgcd(N,R)=1R1给定模数、两个整数和以及大整数，满足，且13.此时存在自然数满足：RR1mod N=1（1）A N蒙哥马利算法首先将操作数转换为蒙哥马利表示形式，然后进行蒙哥马利乘运算.对于，其蒙哥马利表示定义为A:=AR mod N（2）AB和的蒙哥马利乘积定义为C:=ABR1(mod N)（3）C故而可以通过蒙哥马利约减算法计算得到C:=C+(CNmod R)NR（4）R1N其中和满足RR1NN=1(mod N)（5）R1NMonpro(A,B)和均通过扩展的欧几里得算法预先计算6.综合上述可知，蒙哥马利模乘算法（）主要有以下 3 个步骤：AB（1）求出大数 和 的蒙哥马利乘积为T:=ABR1(mod N),（2）将结果进行蒙哥马利约减U:=(T+(T Nmod R)N)/R,U NU NN（3）判断是否成立，若判断结果为成立，则返回，否则返回.1.2 基-2 的蒙哥马利算法基-2 的蒙哥马利模乘算法按位进行交错循环计算，算法伪代码如算法 1 所示.算法 1：基-2 的蒙哥马利算法A B；N输入：操作数，模数AB mod N输出：结果的蒙哥马利表示 S1 function Radix-2s Monpro(A,B)2 S0=0;3 for i=0 upto k-1 do4 qi=(Si0+AiB0)mod 2;5 Si+1=(Si+AiB+qiN)/2;6 end for7 return Sk8 end function基-2 的蒙哥马利模乘算法具备实现简单、资源消耗少、系统主频高的特点，更适用于硬件实现14 15.观察算法 1 可知，基-2 的蒙哥马利算法的延迟主要来自于循环迭代的大数加和的运算.本文致力于对该部分运算的优化从而实现对基-2 的蒙哥马利算法的改进.1.3 保留进位加法器传统的进位传播加法器在进行加法计算时，需要等待每一位的进位信号从低位到高位逐个传递，第 3 期任仕伟等：蒙哥马利模乘算法改进及硬件实现307最终才能得到整个加法结果.这种逐位传递的方式，虽然可以确保计算的正确性，但在计算速度上存在瓶颈.相比之下，保留进位加法器（carry save adder,CSA）会同时计算出所有位的结果，并将进位信号暂时保留，以备后续的加法计算使用.待所有位计算完成后，保留的进位信号会一次性地进行处理，最终得到整个加法结果.这种方式可以大大提升加法器的计算速度，特别是在对长数字进行计算时，其优势更为显著.所以，相对于传统的进位传播加法器，保留进位加法器在计算速度和效率上具有明显的优势.SUMCARRY保留进位加法器将操作数表示为保留进位格式（carry save representation,CSR）进行计算，在加法器链中，每个操作数的和（）与进位（）被计算并存储在两个独立的链路中，即：SUM=X1 xor X2 xorX3，CARRY=(X1 and X2)or(X1 and X3)or(X2 and X3)，在加法器链路末端，和与进位相加得出最终结果.2 算法改进 2.1 高效低延迟蒙哥马利模乘qiNqiBB0ASi0B0AiB0qi如前所述，在基-2 的蒙哥马利模乘法器中，计算求和的过程是其中关键的一环.该过程需要计算值并将其乘以，然后将结果与另外两个参数的求和结果相加.然而，在计算的过程中，需要将的最低位（）和进行逻辑与运算，然后将其与上一轮次结果的最低位（）相加.为了避免这种情况的发生，本文提出了一种改进方案，即将 B 乘以 2（左移1 位）后作为算法的输入，以使得=0.通过这种方式，可以省略掉的计算，从而减小计算的复杂度.使用改进后的蒙哥马利模乘无需额外计算，即qi=(Si0+AiB0)mod 2=(Si0+Ai0)mod 2=Si0mod 2=Si0（6）由于将 B 左移后，新的操作数比原操作数多了一个二进制位，算法的计算时间也相应地增加了一个时钟周期.qiSi0qiSi+1硬件实现的计算速度取决于计算所需周期数和系统主频.公钥密码系统中的模幂运算实际上是模乘算法进行一定次数的迭代，所以单次迭代延时直接影响了算法整体延时.改进后的蒙哥马利模乘相比原算法减少一个乘加计算，并且由于与位数均为 1，所以改进后的算法并不增加电路面积.且由于原算法中与的计算存在固定的前后串行关系，因此改进后的算法单次迭代用时减半，从而在减小计算复杂度的情况下直接缩减了整体计算用时.为了验证改进算法的效率提升，将原算法与高效低延迟蒙哥马利模乘分别使用 MATLAB 实现并计时进行对比.实验采用 64 位无符号整数操作数循环计算 16 次来模拟 1 024 位大数的计算，并在此基础上计算 100 次以得到足够的样本并减小误差，结果表明，本算法的计算时间为 39.575 ms，而原算法的计算时间为 80.487 ms，本文提出的改进算法具有更高的效率和更低的时间延迟，同时由前述分析可知，改进后的算法硬件资源占用方面也具有优势.2.2 5-2 低延迟加法器S i+1=(S i+AiB+Si0N)/2由 2.1 节可知，使用了高效低延迟蒙哥马利模乘后，基-2 的模乘在单次迭代中仅含一次乘加运算，即.在 实 际 应 用 中，公钥密码方法通常选取位宽较大的操作数以满足安全性需求，而在大位宽数的加法中，常规的进位传播加法器会引起长进位链问题，导致整体电路时序紧张、系统主频降低，从而影响模乘运算的吞吐率，降低电路的性能与稳定性，保留进位加法器是在减少进位传播延迟的同时添加多个操作数的最常用方法之一，可用于解决这个问题，本节以此为出发点对该计算进行改进.S i+1=S i+AiB+Si0S1i+1,S2i+1=CSRS1i+S2i+Ai(B1+B2)+Si0N/2S1、S2、AiB1、AiB2Si0N基于上述思想，将式转换为保留进位格式可得式.观察可知，新的算式操作数增加为 5 个，即和.针对此情况，本文提出了将 3 级 CSA级联构建为 5-2 低延迟加法器的结构，将 5 个操作数加和为 2 个输出，最大限度地减小关键延迟，更好地平衡资源占用与运算速度.5-2 低延迟加法器的结构框图如图 1 所示.CSA0CSA1CSA2RegisterCLOCKRESETCARRYSUMSUMCARRYCSAX1X1X2X2X3X3X4X5图 1 5-2 低延迟加法器结构框图Fig.1 Structure block diagram of 5-2 low latency adder X1X2X3由图 1 可知，5-2 低延迟加法器具有 5 个输入、2个输出.前 3 个操作数、和作为第一级 CSA的输入在第一个时钟周期参与运算，运算结果以308北 京 理 工 大 学 学 报第 44 卷X4SUMCARRYCSR 表示与第 4 个操作数共同作为第二级 CSA 的输入参与第二个时钟周期的计算，依次类推输出最终计算结果.其中 CSA 的电路组成表示在虚线框内，3 个输入经过 3 输入异或门得到，两两相与后经过 3 输入或门得到.结合 2.1 中提出的高效低延迟蒙哥马利模乘，将新的操作数代入 5-2 低延迟加法器中可得.S1、S2AiAiB1AiB2S10S20N由图 2 可知，代入高效低延迟蒙哥马利模乘的 5-2 低延迟加法器输入和输出全部使用 CSR 表示，以及即第 位和相与的结果作为第一级CSA 的输入参与第一个时钟周期的运算，和相与作为第二级的输入之一参与第二个时钟周期的计算，将与异或后的结果和模数相与作为第 3级 CSA 的输入之一参与第 3 个时钟周期的计算.对应的算法伪代码如下.算法 2：代入高效低延迟蒙哥马利模乘的 5-2 低延迟加法器A1，A2，B1，B2N输入：操作数；模数AB mod N输出：蒙哥马利表示的 CSR1 function new-5:2-compressor(A,B)2 S10=0,S20=0;3 for i=0 upto k-1 do4 S1i+1,S2i+1=CSRS1i+S2i+Ai(B1+B2)+Si0N/2;5 end for6 return S1k,S2k7 end function S1CSA0CSA1CSA2RegisterCLOCKRESETS1AiB1NCARRYSUMS2AiB2S200图 2 改进算法的 5-2 低延迟加法器结构框图Fig.2 Structure block diagram of improved algorithm using 5-2 low latencyadder 3 硬件实现基于上述改进后算法进行硬件实现，将 FPAG 设计分为 2 个子功能模块：基于 CSA 的 5-2 低延迟加法器和桶形移位全加器（barrel shifter adder,BSA）.FPGA 系统的电路结构框图如图 3 所示.S1S2BSA1A1B1B2A2NAiBSA2RESULTAiB1AiB2S1k1S2k1S2k2S1k2.S11S10S20S21.Full AdderSi(SUM)CARRYCSA1CSA2CSA3图 3 整体系统电路结构框图Fig.3 Circuit block diagram of the overall system 5-2 低延迟加法器模块是算法的核心模块，也是改进后的算法速度得以提升的关键，即图 3 中 3 个级联的 CSA.AB mod NABA1,A2B1,B2A1A2对于运算，操作数和以进位保留格式作为输入，即表示为和的形式.与作为第一个桶形移位全加器的输入，在 k 轮循环第 3 期任仕伟等：蒙哥马利模乘算法改进及硬件实现309iAiB1B2Aii中生成第一级与第二级 CSA 在第 轮次中所需的操作数，与分别与相乘生成第一级与第二级在第 轮次中所需操作数.N(S10 xor S20)S1+S2+Ai(B1+B2)本设计将置于第 3 级 CSA 输入端，在输入端计算时，可以同时得到的结果，从而最大限度地缩小了关键路径长度，系统最终关键路径长度包含 2 个 BSA 与 3 层 CSA.CARRYSUMCARRYAiAiB1,B2,S1,S2RESULTS10S20B2k+512+2由图 3 可看出，桶形移位全加器由 2 组移位寄存器和全加器组成，桶形移位寄存器随时钟完成数据的移位操作，全加器将移位寄存器与上一轮次的进位（）作为输入相加，输出本轮次的与.桶形移位全加器的作用：1）是将保留进位格式的输入通过移位相加得到作为 5-2 低延迟加法器的输入之一，5-2 低延迟加法器将接收到的连同保留进位表示下的作为输入进行计算，经过多轮循环得到 CSR 形式下的结果；2）是以 5-2低延迟加法器的输出作为输入，将其从 CSR 形式转回直接表示得到最终结果.图中所示输出最终结果（）的BSA 输入位宽设计为2 位，操作数为1 024位的情况下需 512 个时钟周期即可完成运算；在改进后的算法结构中，需要一个时钟周期将和复位，同时由于采用了以作为输入，会导致循环计算过程中增加一个时钟周期，因此改进后的算法共需个时钟周期.4 实验结果与分析为了对改进后的算法予以验证，本文使用 Viva-do 2017.4 软件对其功能进行了实验仿真.设计在 Xil-inx Kintex7 FPGA 上实现，芯片型号为 XC7K325T.在1 024 位的模乘运算场景下，系统消耗 8 219 个查找表（look up table,LUT），系统主频可达 278 MHz，单次模乘运算耗时 5.53 s.本设计与其他算法的对比如表 1 所示，表中所有算法指标均在 1 024 位计算场景下得出，其中面积时间积指标综合考量算法的资源占用与计算速度，计算方法为 LUT 数量时间103，等效 ATP 计算方法为等效 LUT 数量（LUT 数+DSP 等效 LUT 数）时间103.由表 1 可知，本文算法与文献 16 17 所提算法均使用纯逻辑实现.相比文献 16 所提算法，本文算法提升了 164%的系统主频，节省了 45%的运算时间.虽然本文算法使用了更多的 LUT 资源，但是通过比较 ATP 可知，本文算法具备更小的面积时间积，在计算时间和资源消耗上达到了更好的平衡.与文献17 所提算法相比，本文算法节省 73%LUT 数，同样实现了更小的 ATP.与文献 18 所提算法相比，本文算法提升了17%的系统主频.文献 18 所提算法消耗 LUT 数量低于本文算法，由表 1 可知原因是其使用了 DSP 资源，而本算法未使用.采用文献 19 中的等效方法计算，即一个 DSP 可等效为 619 个 slices（Xilinx FPGA 中最小可编程逻辑单元之一），每个 slice 内部包含 4 个LUT），从而文献 18 提出算法所用 LUT 等效数量为 131 6194+2 317=326 673 个，远超本文算法消耗的7 191 个 LUT 资源，从而可知其等效 ATP 为 1 176.02，远大于本文算法的 45.45.进一步地，由于本文提出的算法采用的是纯逻辑实现，从而更适合在嵌入式设备等资源敏感性的设备中实现，也更适合 ASIC实现.5 结论本文通过分析目前已有文献中对经典蒙哥马利模乘算法的硬件实现，在算法与电路设计两个方面提出改进方案，改进的方案采用针对性的硬件结构设计，减少计算量，进一步提高经典蒙哥马利模乘算法的执行效率.改进后的设计在大数模乘计算的场景取得更好的 ATP 表现，相比已有同类算法等效 ATP提升了 15%以上，在保障性能的前提下，节省了硬件资源，在小型设备和嵌入式设备中更加具有优势.参考文献：IQBAL W,ABBAS H,DANESHMAND M,et al.An in-Depth analysis of iot security requirements,challenges,andtheir countermeasures via software-defined securityJ.IEEEInternet of Things Journal,2020,7(10):10250 10276.1 RIVEST R L,SHAMIR A,ADLEMAN L.A method forobtaining digital signatures and public-key cryptosystemsJ.2 表 1 资源消耗对比Tab.1 Resource consumption comparison资源本文文献16文献17文献18LUT/个8 2195 31030 4672 317DSP/个000131频率/MHz278105/237计算时间/s5.5310.092.163.6ATP45.4553.5865.088.34等效ATP45.4553.5865.801 176.02等效提升/%153096310北 京 理 工 大 学 学 报第 44 卷Communications of the ACM,1978,21(2):120126.MENEZES A J,VANSTONE S A,OORSCHOT P.Handbook of applied cryptographyM.Florida:CRC Press,2018.3 高巍,骆宜萱,李佳琨,等.素数域椭圆曲线密码点乘的高性能硬件实现 J.北京理工大学学报,2021,41(9):977 984.GAO Wei,LUO Yixuan,LI Jiakun,et al.High performancehardware implementation of elliptic curve cryptography pointmultiplication over GF(p)J.Transactions of Beijing Instituteof Technology,2021,41(9):977 984.(in Chinese)4 李佳琨,李喆,张靖奇,等.基于改进 x(2n)次方器的二进制域快速模逆 J.北京理工大学学报,2020,40(7):765 770.LI Jiakun,LI Zhe,ZHANG Jingqi,et al.A fast modularinversion architecture over GF(2m)based modified x(2n)units J.Transactions of Beijing Institute of Technology,2020,40(7):765 770.(in Chinese)5 MONTGOMERY P L.Modular multilication without trialdivisionJ.Math of Computation,1985,44(170):519 521.6 ZHANG B,CHENG Z,PEDRAM M.High-radix design of ascalable montgomery modular multiplier with low latencyJ.IEEE Transactions on Computers,2022,71(2):436 449.7 KOLAGATLA V R,DARBAR M J S,SELVAKUMAR D,etal.A randomized montgomery powering ladderexponentiation for side-channel attack resilient RSA andleakage assessmentC/2021 25th International Symposiumon VLSI Design and Test(VDAT).S.l.:IEEE,2021:1 5.8 JANANI V S,MANIKANDAN M S K.A secured keymanagement scheme for mobile ad hoc networks withmodified montgomery modular arithmeticC/2022 IEEEInternational Conference on Signal Processing,Informatics,Communication and Energy Systems(SPICES).S.l.:IEEE,2022:1 4.9 SRINITHA S,NIVEDA S,RANGEETHA S,et al.A highspeed montgomery multiplier used in security applicationsC/2021 3rd International Conference on Signal Processingand Communication(ICPSC).Coimbatore,India:IEEE,2021:299 303.10 赵云正.基于 RSA/SHA-256 加解密协处理器的研究与设计 D.成都:电子科技大学,2022.ZHAO Yunzheng.Research and design of RSA/SHA-256based encryption and decryption coprocessorD.Chengdu:University of Electronic Science and Technology,2022.(inChinese)11 蒲誉文.物联网安全与隐私保护关键技术研究 D.重庆:重庆大学,2021.PU Yuwen.Research on key technologies for security andprivacy protection of internet of thingsD.Chongqing:Chongqing University,2021.(in Chinese)12 KOC C,ACAR T,JR B.Analyzing and comparingmontgomery multiplication algorithmsJ.Micro IEEE,1996,16(3):26 33.13 IBRAHIM A,GEBALI F,EL-SIMARY H,et al.High-performance,low-power architecture for scalable radix 2montgomery modular multiplication algorithmJ.CanadianJournal of Electrical and Computer Engineering,2009,34(4):152157.14 WALTER C D.Still faster modular multiplicationJ.Electronics Letters,2002,31(4):263264.15 CHEN D D,YAO G X,CHEUNG R C C,et al.Parameterspace for the architecture of FFT-based montgomery modularmultiplicationJ.IEEE Transactions on Computers,2016,65(1):147 160.16 DAI W,CHEN D D,CHEUNG R C C,et al.Area-timeefficient architecture of FFT-based montgomery multiplicationJ.IEEE Transactions on Computers,2017,66(3):375388.17 程碧倩,刘光柱,肖昊.改进的蒙哥马利模乘算法及 FPGA实现 J.电子科技,2022,35(7):5863.CHENG B Q,LIU G Z,XIAO H.Improved Montgomerymodulo multiplication algorithm and FPGAimplementationJ.Electronic Science and Technology,2022,35(7):58 63.(in Chinese)18 HAO Y,ZHONG S,MA M,et al.Lightweight architecture forelliptic curve scalar multiplication over prime fieldJ.Electronics,2022,11(14):2234.19（责任编辑：刘芳）第 3 期任仕伟等：蒙哥马利模乘算法改进及硬件实现311