大整数模幂的固定基窗口组合算法

模幂乘运算是实现公钥密码体制的一个很重要的运算,其运算速度从整体上决定了公钥密码体制的实现效率。通过采用预处理技术,将椭圆曲线的定点标量乘的固定基窗口方法应用在模幂运算中,与SMM算法进行组合得到一种新的求模幂乘算法——固定基窗口方法。对算法的原理与效率进行了分析,实验结果表明,算法的运算速度得到了有效提高。     

RSA算法的一种快速软件实现

RSA算法是基于数论的公开密钥密码体制。RSA算法已经成为现在最流行的公钥加密算法和数字签名算法之一。RSA算法的加密、解密操作要进行十进制位数达百位以上的大数运算，实现难度大，运算时间长。而影响其运算速度的主要因素是大数乘幂算法和取余算法。本文提出一种改进大数乘幂算法和取余算法，并加以实现，该算法可以提高RSA算法的运算速度。     

公开密钥算法芯片的设计与实现

以RSA算法为例,探讨公钥密码处理芯片的设计与优化。首先提出公钥密码芯片实现中的核心问题,即大整数模幂运算算法和大整数模乘运算算法的实现;然后针对RSA算法,提出Montgomery模乘算法的CIOS方法的一种新的快速硬件并行实现方法,其中采用加法与乘法并行运算以及多级流水线技术以提高性能,较大地减少乘法运算时间,显著提高模乘器的运算性能。     

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

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

并行窗口算法在防御RSA计时攻击中的研究

模幂运算是RSA公钥密码算法中最基本也是最耗时的运算。为了防御计时攻击,一般采用以“绑定法”为代表,影响运算性能的模幂算法。文章指出并行窗口算法在不牺牲性能的条件下,对于RSA计时攻击有内在的免疫能力,并在特定条件下可以有效提高RSA密码算法的运算速度,具有推广的价值。     

面向公钥密码体系的大数相除快速算法

模运算是公钥密码学的一种基本运算。做模运算前提需要做除法运算,因此除法运算也是密码学的基本运算。大整数除法的运算速度是影响公钥密码体系中效率的关键因素。针对大数相除问题,提出大数相除的快速改进算法,其基本思想是,以空间换取时间。首先,通过建立预处理表,减少试除法中大数乘法的次数,从而高效快速得出商值;然后,运用窗口滑动方法来提高大数减法的速度。实验结果表明,该算法可以提高密码学算法的运算效率。算法时间复杂度为O(n),空间复杂度为O(n)。     

高效加密预计算RSA算法实现方法

本文提出了一种随机预先计算RSA算法。实验结果表明,相比原始公钥密码算法RSA17次模n乘法运算复杂度,随机预先计算RSA算法计算复杂度只需4次模n乘法运算,揭示了预计算RSA算法的加密时间复杂度小,在很大程度上提高了加密速度,有利于实践应用。     

大数模乘算法的分析与研究

大数模乘在密码学领域有广泛的应用,它是RSA、ElGamal等公钥密码的基本运算。文章对目前具有典型代表性的各种大数模乘算法的设计思想进行了深入剖析,从基本设计原理和实现角度对这些模乘算法进行整理和分类,归纳并给出了各类算法的优缺点、实现方法、适用环境和研究现状。     

模n的大整数幂乘的一种快速算法

在RSA公钥密码体制中,要提高模n的大整数幂乘的运算效率,主要是解决两个方面的问题:⑴大整数的算术运算,特别是大整数的乘除法;⑵降低幂模运算的实际次数。文章从这两个方面进行研究,实现了大整数幂乘的一种快速计算,并给出了关键部分的算法,分析了算法的效率。     

一种高性能大数模运算单元及其应用

为了加速公钥密码系统的实现速度,设计支持大教模乘和模加减运算的模运算单元是关键.目前的方法多关注于这两种运算的分别实现,为了改善这种方式导致的硬件单元吞吐量低的问题,提出了一种流水线结构的高性能大数模运算单元.基于改进的Montgomery模乘算法,采用流水线技术,把模乘电路分成3个流水线阶段,并把模加减电路结合到第3阶段,得到一种能同时计算模乘和模加减的模运算单元.仿真结果显示,模运算单元以较少的资源占用率获得了较高的吞吐量,非常适合做高性能的公钥密码系统的基本硬件运算单元.     

大数模幂乘动态匹配快速算法及其应用

针对 RSA、Elgamal、DSA等算法在进行数据加密或数字签名时都要进行复杂的大数模幂乘运算 ,本文分析了目前常用的几种大数模幂乘算法 ,并在此基础上提出了一种动态匹配快速算法 .实验表明 ,将该算法用于实现 RSA算法 ,其实现速度较其他算法有明显提高 .     

An efficient common-multiplicand-multiplication method to the Montgomery algorithm for speeding up exponentiation

The modular exponentiation is a common operation for scrambling secret data and is used by several public-key cryptosystems, such as the RSA scheme and DSS digital signature scheme. However, the calculations involved in modular exponentiation are time-consuming especially when performed in software. In this paper, we propose an efficient CMM-MSD Montgomery algorithm by utilizing the Montgomery modular reduction method, common-multiplicand-multiplication (CMM) method, and minimal-signed-digit (MSD) recoding technique for fast modular exponentiation. By using the technique of recording the common signed-digit representations in the grouped substrings of exponent, our algorithm can improve the efficiency of both the original CMM exponentiation algorithm and the Montgomery multiplication algorithm. The fast modular exponentiation algorithm developed in this paper can be easily implemented in general signed-digit computing machine, and is therefore well suited for parallel implementation to fast evaluating modular exponentiation. Moreover, by using the proposed CMM-MSD Montgomery algorithm, on average the total number of single-precision multiplications can be reduced by about 38.9% and 26.68% as compared with Dusse-Kaliski’s Montgomery algorithm and Ha-Moon’s Montgomery algorithm, respectively.     

改进的RSA算法在无线传感器网络中的应用

针对公钥密码体制在无线传感器网络密钥管理中存在计算速度慢、能量消耗大等问题,提出将一种改进的公钥算法应用其中。新算法利用蒙哥马利算法把大数的幂模运算转换成模幂运算,并使用中国剩余定理把模幂运算转换成求解同余方程组。算法安全性分析与实验结果表明,新算法能减少55%的运算开销,减少67%的存储空间占用,并增加21%的节点生命周期。新算法在保证密钥安全性的同时减少了运算量和存储空间,更加适合节点运算能力较低且能量有限的无线传感器网络。     

Parallel exponentiation using common-multiplicand-multiplication and signed-digit-folding techniques

An efficient computation of the modular exponentiations C?=?M^E mod N is very useful for public-key cryptosystems. In this paper, an efficient parallel modular exponentiation algorithm is proposed based on both the common-multiplicand-multiplication (CMM) and signed-digit-folding (SDF) techniques. The ‘minimal-signed-digit (SD) recoding algorithm’ has less occurrence probability of the nonzero digit than the binary number representation. Taking this advantage, we can effectively decrease the amount of modular multiplications. By dividing the bit string of the minimal-SD recoding exponent E into three equal-length parts and by using the technique of recording the common parts in the folded substrings, the ‘folding-exponent algorithm’ can improve the efficiency of the binary algorithm, thus it can further decrease the computational complexity of modular exponentiation. As the modular squaring operation in GF(2 ⁿ ) over the normal basis can be done by a simple shift operation, the modular multiplications and the modular squaring operations in our proposed CMM–SDF algorithm can be executed in parallel. By using our proposed parallel CMM–SDF algorithm, we can obtain the optimal overall computational complexity as 0.689k?+?11 multiplications by folding the minimal-SD recoding exponent E exactly one-time in SD radix-2 recoding system, where k denotes the digit-length of the exponent and n denotes the folding time of the exponent.     

RSA算法的一种高效软件实现方法

分析了RSA算法的软件实现难点为大数的幂模运算,提出了将大数的幂模运算转换为小数幂模运算乘积的高效方法,并实现了RSA算法,该方法在理论分析和试验方面都具有较好的效果。     

一种适于硬件实现的快速模乘算法

RSA算法是目前应用最广泛的一种公钥加密算法,随着人们对加密安全性和加密速度要求的提高,硬件实现加密算法成了密码学应用的一个趋势。模乘算法是模幂算法的核心,基于Montgomery算法,结合Booth2算法的思想,文章给出了一种改进的高效算法,并且通过FPGA实现。对该算法和参考文献中算法的性能进行了比较,可以看出这一改进算法在速度和面积上优于现有的算法。     

秦九韶算法思想在RSA密码算法中的应用研究

介绍了用于快速计算高次多项式值的“秦九韶算法”,并用类似思路分析了RSA算法中方幂模快速实现算法,最后给出了该算法的具体实现。算法分析和实验结果证明,该算法的计算量不会随着指数的快速增大而增大,通过精心选择指数,还可以减少运算量。RSA算法中明文分组和密文分组都较大,方幂模运算消耗大量的运算时间。因此,简化方幂模计算减少计算次数对设计RSA快速算法和选择密钥具有重要的指导意义。