一种新的快速模乘算法

1、一种新的快速模乘算法修稿日期：2005-06-07 唐 勇, 许金玲(燕山大学 信息科学与工程学院 河北 秦皇岛 066004)xjl摘要 大整数模幂乘运算一直是制约RSA广泛应用的瓶颈，在对传统算法剖析的基础上，提出了一种新的快速模乘算法，借鉴生成Wallace tree的思想，结合查找表和并行乘法运算进行RSA模幂运算。理论分析和试验证明新算法时间复杂度降低到O(logn)。关键词 RSA 模幂 模乘 Wallace tree 时间复杂度 A New Fast Modular Multiplication Algorithm Tang Yong, Xu Jinling (The colle

2、ge of Information Science and Engineering, Yanshan University, Qinhuangdao, 066004)Abstract: Modular exponentiation of large integers is the choke point for RSA. After analyzing traditional algorithms, a new fast modular exponentiation algorithm was presented. Wallace tree, lookup table and parallel

3、 multiplication were used in the algorithm. With theoretical analyzing and practical application, it was shown that the time complexity of the new algorithm was reduced to O(nlogn) . Key Words: RSA, Modular exponentiation, Modular multiplication, Wallace tree, Time complexity1. 引 言 RSA(Rivest,Shamir

4、&Adleman)1是一种国际公认的理想公钥密码体制。它表达方式简单、保密性强、没有密钥管理的麻烦，并且具有数字签名、认证和鉴别等功能，特别适合于现代保密通信的需要。这些优越性都归功于其核心大整数模幂乘计算。但是大整数幂剩余运算耗时太多，一直是它广泛应用的瓶颈问题，为此人们一直在寻找它的各种快速算法，如：SMM、RSR2、分块模幂算法3、Montgomery模乘算法4、滑动窗口模幂算法5等诸多算法6,7。这些算法虽然都在一定程度上提高了RSA的运算速度，但都没有突破O(n)的时间复杂度。本文提出的快速模乘算法时间复杂度降低到O(logn)，模幂算法时间复杂度降低到O(nlogn)，从而大大提高

5、了RSA算法的运算速度。2. 传统RSA算法的时间复杂性简述大整数模幂乘的计算速度决定了加密和解密的速度。传统的计算大整数模幂乘的算法是将指数m二进制化，即将指数m表示成二进制形式，其时间复杂性为O(ln2m)；之后再进行一系列迭代运算，从m的二进制的高位计算起，遇到为 l的位就用底数去乘上一步的迭代结果，先求乘同余再求平方剩余；遇到为0的位就直接对上一步的迭代结果求平方剩余。鉴于安全性m取值比较大，考虑到安全的要求，m的取值往往比较大，因而这种方法速度比较慢，时间复杂性为O(lnmln2n)。所以计算am mod n所需的时间复杂性为O(lnmln2n)+ O(ln2m)= O(lnmln2

6、n+ln2m)。3. 新算法描述及时间复杂性分析3.1 算法的基本思想模幂运算中所有的模乘运算都具有相同的模，新算法就是根据这一特性和已有的数论知识8提出的。在算法中，预先建立一个查找表，存放模乘运算中所需数据，然后执行包含模简化的并行乘法运算。常规模乘运算需对2n字节的整数约简，而并行模乘运算缩短了这种时耗，只需对n字节的整数进行约简，从而提高了RSA的加密和解密速度。所以，新的模乘算法主要由以下两部分组成：建立查找表存放整个模幂运算中所需数据，然后进行并行模乘运算。3.1.1 建立查找表（Precomputing of lookup table）在模幂乘运算中，需要获得20 mod M,

7、21 mod M, 2n-1 mod M, 22n-1 mod M。由于2n-1M2n且20,2n-1都小于M，根据费马小定理9，无需计算2i mod M (0in)。因此，查找表中存放的值为：2i mod M (ni2n)。查找表结构如表3-1所示：表3-1 查找表Table 3-1 Lookup table for precomputing values t2n-1 22n-1 mod M t2n-2 22n-2 mod M tn 2n mod M在新算法中为了确保对查找表中的值的计算的快速性，采用当前迭代步数最少的2k进制算法。设l为指数n被2k进制化后的序列长度，则n=nl-1(2k)

8、l-1+ nl-2(2k)l-2+ n1(2k)+n0，其中ni0,1,2,2k-1。3.1.2 并行模乘运算 (Parallel multiplication)阶段1 (1st multiplication)：并行乘法不妨设：借鉴生成Wallace tree10的思想，将该式中n个值相加。但当X, Y, M是1024位以上整数时，选择加法器等存在进位传送时延，为了避免这种时延，采用移位存储加法器。通过log n次相加，得到P。阶段2 (2nd multiplication)：模简化。根据以上分析得到：根据整除与同余特性有P = P mod M + k * M，所以其中Pi*2i mod M或

9、者为0或者是查找表中的第i项。对P中n+1项仍然借鉴生成Wallace tree的思想进行操作，则总和S长度满足：length(S)log(n+1)*2n)=n+log(n+1)。具体操作如下例所示：Example: P=1101*1011 mod 1111按照查找表3-2得到：P=10001111S=1111+0*0001+0*0010+0*0100+1*1000=10111表3-2 查找表实例Table 3-2 An example of lookup tablet727mod11111000t626 mod 11110100t525 mod 11110010t424 mod 111100

10、01由于n的确定性，重复上述操作直至length(S)n，这样就实现了模简化的目的。然后借助比较和减法运算来完成P =S mod M。3.2 主要算法描述Precomputing of lookup table:Input：M (M2n)R(0)=1; A=1; j=1;while(j=0;i-) A=mod M;A=A*R(ni) mod M;for (i=n;i=M) A=A-M; Algorithm NEW_MOD_MULT：Input: X, Y, lookup_table(M); (X, Y=2n) l=length(S);S=parallel_binary_addition(sl-

11、1*lookup_tablel-1,sl-2*lookup_tablel-2,sl-1*lookup_tablen,(sn-1sn-2s0) if S=M then P=S-M else P=S; Algorithm Exponentiation:Input: A, B, M (A,B,M=0;i-) S= NEW_MOD_MULT (S, S, lookup_table);if (b1=1) then NEW_MOD_MULT(S,A,lookup_table);4. 新算法时间复杂度分析本算法的时间复杂度应从Precomputing、1st multiplication和2nd multi

12、plication三方面加以分析。(1) 显而易见，本算法中Precomputing阶段时间复杂度为O (2k+n+n)。因为2k n，所以该阶段时间复杂度为O (n)。(2) 在1st multiplication由于采纳了生成Wallace tree的思想，只需进行log n次加法便可求得P，因此该步时间复杂度为O(logn)。(3) 对2nd multiplication的运算，不妨先求出缩短S长度时重复进行约简操作直至满足要求所需时间。在最好的情况下仅需一次约简操作，所需时间复杂度为O(logn)。然而在最坏的情况下需进行n+1次约简操作，则TReduction=log (n+1)+l

13、og (log(n+1)+1)+log (log(log(n+1)+ 1)+1)+logn+1+2log(log(n+1)+1) logn+1+2log (logn+2)logn+1+2loglogn+4=logn+2loglogn+5然后需进行1次比较运算和1次减法运算，因而，本阶段所需时间T2为:T2= TReduction+2= logn+2loglogn+5+2= logn+2loglogn+7综上所述，即使在最坏的情况下，模乘运算所需时间复杂度为：O(logn+T2)= O(2logn+2loglogn+7)= O(logn)在模幂运算中需要n2n次模乘运算，于是模幂运算的时间复杂度

14、为O(n+2nlogn)=O(nlogn)。5. 实 例随机选取若干个大整数进行实例试验，与几个典型算法的比较结果如表5-1所示：表5-1 模乘算法时间复杂度比较Table 5-3 Comparison of time complexity of different modular multiplication algorithmsAlgorithmsIterationsTime complexityKim2n4nKocn3nTakagin3nSchmidt1n2nSchmidt2nnThe newnlogn实践证明，较典型的RSA算法，新算法的时间复杂度降低，运算效率有一定的改善。6. 结束

15、语RSA公钥密码体制的快速算法研究一直受到密码学界的高度重视，RSA的效率问题不解决就难以实际应用。本文提出的快速模幂乘算法，结合查找表和并行模乘运算进行RSA模幂运算，在时间复杂度上降低到O(nlogn)，这种改善是十分可观的。它所付出的代价是需预先建立查找表，增加了长度为n的线性存储空间。通过理论分析与实际应用表明，这种代价是微不足道的，因而是可行的。本算法具有重要的实际应用价值。参考文献1 Rivest R, Shamir A and Adleman L. A method for obtaining digital signatures and public-key cryptosys

16、temJ.Communications of the ACM, 1978, 21(2):120-1262 陈运，龚耀寰. 基于二进制冗余数的递归余数和算法. 电子科技大学学报. 2000, 29(1):1-43 倪谷炎.分块模幂算法.小型微型计算机系统. 2002,24(5):53-564 Ananda Mohan.Fast algorithms for implementation of montgomerys modular multiplication technique Circuis, Systems and Signal Processing. 2004, 23(6): 463-4

17、785 丁宏,郭艳华. 快速大数模乘算法及其应用. 小型微型计算机系统. 2003,24(7):1367-13706 V. Bunimov, M. Schimmler. Area and Time Efficient Modular Multiplication of Large Integers. IEEE 14th International Conference on Application specific Systems, Architectures and Processors. 2003, 6:400-4097 Manfred Schimmler, Viktor Bunimov.

18、 Fast Modular Multiplication by Operand Changing. International on Information Technology: Coding and Computing. 2004,2:518-5248 William Stallings. 密码编码学与网络安全：原理与实践(第二版). 北京:电子工业出版, 2001:167-1869 Granville A. Some conjectures in analytic number theory and their connection with Fermats last theorem. Proceedings of the Conference on Analytic Number Theory. 1990:31110 Carpinelli, John D, Dokachev, Michael. The w