一种改进的Montgomery模乘快速算法

利用Karatsuba-Ofman算法的思想,改进了Montgomery模乘的CIOS实现算法:一方面,改进后的CIOS算法在时间效率上有较大提高,减少的乘法次数比率接近25%;另一方面,改进后的算法具有更好的并行性,能够实现两个乘法器的并行结构,适合于设计高速的RSA密码专用芯片。

基于改进Montgomery模乘算法的RSA加密处理器的实现

在Montgomery模乘算法改进的基础上,提出了一种实现Montgomery模乘算法的结构,该结构只需使用一个CSA(carrysaveadder)加法器.与目前使用两个CSA加法器的模乘算法相比,所提出的算法加快了RSA加密处理器的实现,并提高了整个加密系统的时间效率.

Montgomery模乘算法的改进及其应用

Montgomery算法是目前最适合于通用处理器软件实现的大整数模乘算法。1996年,Koc总结了该算法的五种实现方法:SOS、CIOS、FIOS、FIPS和CIHS,并指出CIOS方法综合性能较优。首先深入分析了FIOS实现方法,并通过消除进位传递和减少循环控制等手段,提出了一种改进方法IFIOS。然后将该方法应用于模幂计算,给出了基于滑动窗口技术的Montgomery模幂算法。最后理论分析和实验结果表明,该改进将FIOS的执行速度提高了约54%,与目前常用的CIOS方法相比,亦有较大的优势。

Montgomery算法在大数模幂运算中的改进

针对Montgomery算法中模乘模块的FIPS模式进行改进,将平方的简化算法与FIPS模式的算法相结合,在运用Montgomery算法计算模平方时降低了乘法运算次数,有效地提高了大数模幂运算的效率.

面向嵌入式处理器的优化Montgomery模乘算法

针对嵌入式系统中频繁的内存存取影响Montgomery模乘算法效率的问题,提出了一种优化的分离连续操作数缓存算法。该算法基于连续操作数缓存算法并进行优化,应用于计算多精度乘法和约减两部分,将整个计算分块使得每块内操作数只被加载一次;为了不破坏操作数加载的连续性,在多精度乘法和约减之间采用分离集成的方式;通过动态地使用寄存器和有效的缓存操作数来减少嵌入式系统中算法使用内存存取操作的总量,实现提高模乘算法效率的目的。实验结果表明:在使用MIPS64架构的处理器上,当模数为1 024bit时,与应用广泛的粗粒度集成操作数扫描算法相比,该算法的效率提高了4.17%。在嵌入式系统中,可将该算法应用于公钥密码体系中的模乘运算,在提高模乘效率的同时提高公钥密码算法的运算效率。

Montgomery模平方算法及其应用

分析Montgomery模乘算法的设计思想和模平方中乘法的计算过程，通过引入两种新的平方计算方法以及对Montgomery算法的优化，提出适合于通用32位处理器实现的Montgomery模平方算法。将该方法应用于模幂计算，给出基于滑动窗口技术的Montgomery模幂算法。实验结果表明，该算法能将模幂的计算速度提高9％～12％。

一种Montgomery模幂乘硬件流水线实现算法

文章提出了一种基于Montgomery算法的模幂乘硬件流水线实现算法,该算法的核心是把模N乘上一个系数,使倍增后的模之低若干位(二进制)全为1,然后用倍增后的模进行Montgomery算法模幂乘运算。采用该算法,可以设计出用于实现RSA的高频流水线运算部件。

针对Montgomery模幂算法的选择明文SPA攻击

大整数模幂运算的核心是大整数模乘运算,一般采用Montgomery模乘算法实现。针对Montgomery模乘算法实现方式中大整数拆分成多个字节或字相乘存在功耗泄露问题,提出一种选择能产生Montgomery模乘算法的某操作数由多个字节或字为零组成的大整数的特定明文,简单功耗分析(simple power analysis,SPA)的方法。通过输入特定明文,一条功耗曲线就能将模幂算法中平方和乘运算位置区分出来,私钥攻击难度下降。在搭建真实的8051智能卡芯片攻击环境下,输入特定明文进行SPA攻击,1024比特私幂指数私钥攻击准确率可达99%。实验结果表明可选特定明文数量多,用单一的屏蔽特殊明文的方法无法有效防范文中提出的SPA攻击,最后给出防范此选择明文SPA攻击的建议。

一种Montgomery模乘算法硬件结构

基于二进制多字Montgomery模乘算法,提出了一种参数可灵活配置的规则的脉动阵列硬件结构,并使用此结构在FPGA上实现了不同位宽的Montgomery模乘算法.该结构成功地在不增加额外电路或运行周期的情况下,将脉动阵列的关键路径限制在运算单元内部的加法器中.硬件实现结果表明,该结构具有更高的电路频率、更少的电路面积消耗及算法运算时间.

分割式Montgomery模乘运算的线性高基心动阵列新结构

本文基于提高并行性、加速模乘的思想，利用分割操作数的方法，提出了分割式Montgomery模乘算法（PMMM），并且基于C．D.Walter发明的心动阵列结构，提出了新的线性高基心动阵列模乘结构，较好地实现了PMMM。对于基r（r=2^w）的n位模乘运算，Walter使用（n＋1）（n＋2）个PF来实现Montgomery模乘，我们用n＋2个PE实现Montgomery模乘，最大并行性为Walter的2倍。将此结构应用于模幂运算，仅需一次预计算便可使得非平方模乘的输入输出延迟为walter中的1/2，且平方模乘延迟与其相当，从而提高了模幂的运算速度。当然，考虑到对速度和硬件资源的不同需求，我们也给出了使用n/2＋1个PE来计算模乘、模幂的实现算法，并做出了相应的数据分析。

一种Montgomery模乘的硬件算法及其实现

采用大数的高基表示方法对原 Montgomery算法进行了改进 ,提出了一种高效的面向硬件的计算 Montgomery积的算法 ,按照该算法实现的硬件具有较低的复杂度和较高的处理速度 ,并且利用 CSMC的 0 .6 μm CMOS标准单元库实现了 5 1 2位的 Montgomery模乘器。该模乘器约含480 0 0等效门 ,面积约为 3 mm× 3 mm,最高工作时钟频率可达 40 MHz,完成 5 1 2位 Montgomery模乘需要 3 4

一种基于CSA加法器的Montgomery模幂乘硬件实现算法

提出了一种改进的Montgomery模乘和模幂算法,该算法采用5-to-2 CSA加法器来实现Montgomery模乘算法中的超长大数加法。目前使用CSA加法器的其他模乘算法在模乘结果输出时均需要用CPA加法器来处理CSA加法器的输出结果,而本文提出的算法使得模乘运算的输入输出操作数均可采用保留进位形式,避免了进行超长操作数的CPA加法这一耗时的操作,因此显著减少了模乘运算所需时钟周期,提高了数据处理的时间效率,并加快了RSA模幂运算的速度。

Montgomery算法及其快速实现

基于传统的Montgomery算法，提出了对其加速的3种方案。分别对求逆元、模乘以及大整数平方运算构造了相应的快速算法，大大降低了传统Montgomery算法的时间复杂度,从而提高了RSA算法的加解密速度。

SM2高速双域Montgomery模乘的硬件设计

作为由国家密码管理局公布的SM2椭圆曲线公钥密码算法的核心运算,模乘的实现好坏直接决定着整个密码芯片性能的优劣.Montgomery模乘算法是目前最高效也是应用最为广泛的一种模乘算法.本文基于Montgomery模乘算法,设计了一种高速,且支持双域(GF(p)素数域和GF(2m)二进制域)的Montgomery模乘器.提出了新的实现结构,以及一种新型的Wallace树乘法单元.通过对模块合理的安排和复用,本设计极大的缩小了时间消耗与硬件需求,节省了大量的资源.实现256位双域模乘仅需0.34μs.

一种适用于多种公钥密码算法的模运算处理器

文章设计了一种能够实现多种公钥密码算法(如RSA、ECC、DSA等)的协处理器。通过分析几种常用的公钥密码算法,归纳了一组最常用的基本模运算指令。基于基本指令,设计优化了处理器硬件结构。用微代码循环调用执行这些基本指令,实现其他各种模运算指令。基于这些模运算指令,处理器可实现多种公钥密码算法的运算。该处理器支持从106位到2 048位多种长度的模运算。采用流水线结构设计,处理速度较快。处理器占用芯片面积小,核心电路等效门数约为26 000门,适用于智能卡等对芯片面积有严格限制的应用。

基于FIOS类型的Montgomery双域模乘器设计

针对FIOS类型的Montgomery模乘扩展算法的比特级-字级和字级-字级的两种实现形式进行研究,设计多处理单元的流水线组织结构实现算法,并对模乘器进行双有限域统一结构设计,使之能够同时支持两个有限域GF(p)和GF(2n)上的运算。最后对设计的两种模乘器用Verilog硬件描述语言进行代码描述,采用Synopsys公司的Design Compiler在Artisan SIMC 0.18μm typical工艺库下综合。实验结果表明,该模乘器不仅在运算速度和电路面积方面各具有优势,而且具有运算长度可变的灵活性。

大数快速模幂算法的硬件设计

将快速模幂算法、快速模乘算法和快速加法组合,提出了一种大数快速RSA算法,并利用该算法给出了一个RSA公开密钥的加解密硬件实现方案.首先采用m ary方法,减少模乘运算次数;其次采用Montgomery改进算法,减少模加运算次数;最后,采用高速加法器并调整加法与乘法的结构使其同时运行,以节约资源.对于1024位操作数,在100MHz时钟频率下,加密速率约为390kbit/s.

一种新型的基于Montgomery的模幂器结构

大数模乘是许多公钥密码体制的核心运算,也是运算效率提高的瓶颈。基于Montgomery模乘算法,该文提出了一种改进的快速模乘及其模幂算法,由于采用了新的booth编码,算法的循环次数减少近一半,因此性能提高近一倍。模幂器采用新型的保留进位加法器(CSA)树,此结构无须对每次模乘的结果求和。实验表明,在97MHz时钟频率下,1 024-bit模幂器的波特率为184Kb/s,适合于设计高速的公钥密码协处理器。

基于高基阵列乘法器的高速模乘单元设计与实现

蒙哥马利模乘算法是最适合硬件实现的模乘算法,被应用在RSA密码和ECC密码的协处理器设计中。目前性能最高的是高基蒙哥马利模乘算法,分析了高基蒙哥马利算法的实现,提出了一种新的基于高基阵列乘法器的Montgomery模乘高速硬件实现结构,基于这种结构位长为n的比特模乘仅需要约n/w+6个时钟周期,该结构设计的电路只与最小单元有关,在硬件实现时可以大大提高频率,并提高设计的性能,可以设计高速的RSA和椭圆曲线密码大规模集成电路。

基于FPGA的Montgomery模乘器的高效实现

为了提高椭圆曲线密码处理器的模乘速度,提出了一种更有效且更适合硬件实现的Montgomery算法。改进的算法分析了基于CSA加法器的Montgomery模乘算法,提出了多步CSA加法器的Montgomery算法,该算法能够在一个时钟内做多次CSA迭代运算,可以有效地降低时钟个数,进而提高模乘速度。通过ModelSim仿真工具仿真,正确完成一次256位的Montgomery模乘运算只需要16个时钟周期。在Altera EP3SL200F1517C2 FPGA中的运行结果表明,71.5 MHz的时钟频率下,完成一次256位的模乘运算仅需要0.22μs。