一種新的快速模乘算法

1、一種新的快速模乘算法修稿日期：2005-06-07 唐 勇, 許金玲(燕山大學(xué) 信息科學(xué)與工程學(xué)院 河北 秦皇島 066004)xjl摘要 大整數(shù)模冪乘運(yùn)算一直是制約RSA廣泛應(yīng)用的瓶頸，在對(duì)傳統(tǒng)算法剖析的基礎(chǔ)上，提出了一種新的快速模乘算法，借鑒生成Wallace tree的思想，結(jié)合查找表和并行乘法運(yùn)算進(jìn)行RSA模冪運(yùn)算。理論分析和試驗(yàn)證明新算法時(shí)間復(fù)雜度降低到O(logn)。關(guān)鍵詞 RSA 模冪 模乘 Wallace tree 時(shí)間復(fù)雜度 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是一種國(guó)際公認(rèn)的理想公鑰密碼體制。它表達(dá)方式簡(jiǎn)單、保密性強(qiáng)、沒(méi)有密鑰管理的麻煩，并且具有數(shù)字簽名、認(rèn)證和鑒別等功能，特別適合于現(xiàn)代保密通信的需要。這些優(yōu)越性都?xì)w功于其核心大整數(shù)模冪乘計(jì)算。但是大整數(shù)冪剩余運(yùn)算耗時(shí)太多，一直是它廣泛應(yīng)用的瓶頸問(wèn)題，為此人們一直在尋找它的各種快速算法，如：SMM、RSR2、分塊模冪算法3、Montgomery模乘算法4、滑動(dòng)窗口模冪算法5等諸多算法6,7。這些算法雖然都在一定程度上提高了RSA的運(yùn)算速度，但都沒(méi)有突破O(n)的時(shí)間復(fù)雜度。本文提出的快速模乘算法時(shí)間復(fù)雜度降低到O(logn)，模冪算法時(shí)間復(fù)雜度降低到O(nlogn)，從而大大提高

5、了RSA算法的運(yùn)算速度。2. 傳統(tǒng)RSA算法的時(shí)間復(fù)雜性簡(jiǎn)述大整數(shù)模冪乘的計(jì)算速度決定了加密和解密的速度。傳統(tǒng)的計(jì)算大整數(shù)模冪乘的算法是將指數(shù)m二進(jìn)制化，即將指數(shù)m表示成二進(jìn)制形式，其時(shí)間復(fù)雜性為O(ln2m)；之后再進(jìn)行一系列迭代運(yùn)算，從m的二進(jìn)制的高位計(jì)算起，遇到為 l的位就用底數(shù)去乘上一步的迭代結(jié)果，先求乘同余再求平方剩余；遇到為0的位就直接對(duì)上一步的迭代結(jié)果求平方剩余。鑒于安全性m取值比較大，考慮到安全的要求，m的取值往往比較大，因而這種方法速度比較慢，時(shí)間復(fù)雜性為O(lnmln2n)。所以計(jì)算am mod n所需的時(shí)間復(fù)雜性為O(lnmln2n)+ O(ln2m)= O(lnmln2

6、n+ln2m)。3. 新算法描述及時(shí)間復(fù)雜性分析3.1 算法的基本思想模冪運(yùn)算中所有的模乘運(yùn)算都具有相同的模，新算法就是根據(jù)這一特性和已有的數(shù)論知識(shí)8提出的。在算法中，預(yù)先建立一個(gè)查找表，存放模乘運(yùn)算中所需數(shù)據(jù)，然后執(zhí)行包含模簡(jiǎn)化的并行乘法運(yùn)算。常規(guī)模乘運(yùn)算需對(duì)2n字節(jié)的整數(shù)約簡(jiǎn)，而并行模乘運(yùn)算縮短了這種時(shí)耗，只需對(duì)n字節(jié)的整數(shù)進(jìn)行約簡(jiǎn)，從而提高了RSA的加密和解密速度。所以，新的模乘算法主要由以下兩部分組成：建立查找表存放整個(gè)模冪運(yùn)算中所需數(shù)據(jù)，然后進(jìn)行并行模乘運(yùn)算。3.1.1 建立查找表（Precomputing of lookup table）在模冪乘運(yùn)算中，需要獲得20 mod M,

7、21 mod M, 2n-1 mod M, 22n-1 mod M。由于2n-1M2n且20,2n-1都小于M，根據(jù)費(fèi)馬小定理9，無(wú)需計(jì)算2i mod M (0in)。因此，查找表中存放的值為：2i mod M (ni2n)。查找表結(jié)構(gòu)如表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在新算法中為了確保對(duì)查找表中的值的計(jì)算的快速性，采用當(dāng)前迭代步數(shù)最少的2k進(jìn)制算法。設(shè)l為指數(shù)n被2k進(jìn)制化后的序列長(zhǎng)度，則n=nl-1(2k)

8、l-1+ nl-2(2k)l-2+ n1(2k)+n0，其中ni0,1,2,2k-1。3.1.2 并行模乘運(yùn)算 (Parallel multiplication)階段1 (1st multiplication)：并行乘法不妨設(shè)：借鑒生成Wallace tree10的思想，將該式中n個(gè)值相加。但當(dāng)X, Y, M是1024位以上整數(shù)時(shí)，選擇加法器等存在進(jìn)位傳送時(shí)延，為了避免這種時(shí)延，采用移位存儲(chǔ)加法器。通過(guò)log n次相加，得到P。階段2 (2nd multiplication)：模簡(jiǎn)化。根據(jù)以上分析得到：根據(jù)整除與同余特性有P = P mod M + k * M，所以其中Pi*2i mod M或

9、者為0或者是查找表中的第i項(xiàng)。對(duì)P中n+1項(xiàng)仍然借鑒生成Wallace tree的思想進(jìn)行操作，則總和S長(zhǎng)度滿足：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 查找表實(shí)例Table 3-2 An example of lookup tablet727mod11111000t626 mod 11110100t525 mod 11110010t424 mod 111100

10、01由于n的確定性，重復(fù)上述操作直至length(S)n，這樣就實(shí)現(xiàn)了模簡(jiǎn)化的目的。然后借助比較和減法運(yùn)算來(lái)完成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. 新算法時(shí)間復(fù)雜度分析本算法的時(shí)間復(fù)雜度應(yīng)從Precomputing、1st multiplication和2nd multi

12、plication三方面加以分析。(1) 顯而易見，本算法中Precomputing階段時(shí)間復(fù)雜度為O (2k+n+n)。因?yàn)?k n，所以該階段時(shí)間復(fù)雜度為O (n)。(2) 在1st multiplication由于采納了生成Wallace tree的思想，只需進(jìn)行l(wèi)og n次加法便可求得P，因此該步時(shí)間復(fù)雜度為O(logn)。(3) 對(duì)2nd multiplication的運(yùn)算，不妨先求出縮短S長(zhǎng)度時(shí)重復(fù)進(jìn)行約簡(jiǎn)操作直至滿足要求所需時(shí)間。在最好的情況下僅需一次約簡(jiǎn)操作，所需時(shí)間復(fù)雜度為O(logn)。然而在最壞的情況下需進(jìn)行n+1次約簡(jiǎn)操作，則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然后需進(jìn)行1次比較運(yùn)算和1次減法運(yùn)算，因而，本階段所需時(shí)間T2為:T2= TReduction+2= logn+2loglogn+5+2= logn+2loglogn+7綜上所述，即使在最壞的情況下，模乘運(yùn)算所需時(shí)間復(fù)雜度為：O(logn+T2)= O(2logn+2loglogn+7)= O(logn)在模冪運(yùn)算中需要n2n次模乘運(yùn)算，于是模冪運(yùn)算的時(shí)間復(fù)雜度

14、為O(n+2nlogn)=O(nlogn)。5. 實(shí) 例隨機(jī)選取若干個(gè)大整數(shù)進(jìn)行實(shí)例試驗(yàn)，與幾個(gè)典型算法的比較結(jié)果如表5-1所示：表5-1 模乘算法時(shí)間復(fù)雜度比較Table 5-3 Comparison of time complexity of different modular multiplication algorithmsAlgorithmsIterationsTime complexityKim2n4nKocn3nTakagin3nSchmidt1n2nSchmidt2nnThe newnlogn實(shí)踐證明，較典型的RSA算法，新算法的時(shí)間復(fù)雜度降低，運(yùn)算效率有一定的改善。6. 結(jié)束

15、語(yǔ)RSA公鑰密碼體制的快速算法研究一直受到密碼學(xué)界的高度重視，RSA的效率問(wèn)題不解決就難以實(shí)際應(yīng)用。本文提出的快速模冪乘算法，結(jié)合查找表和并行模乘運(yùn)算進(jìn)行RSA模冪運(yùn)算，在時(shí)間復(fù)雜度上降低到O(nlogn)，這種改善是十分可觀的。它所付出的代價(jià)是需預(yù)先建立查找表，增加了長(zhǎng)度為n的線性存儲(chǔ)空間。通過(guò)理論分析與實(shí)際應(yīng)用表明，這種代價(jià)是微不足道的，因而是可行的。本算法具有重要的實(shí)際應(yīng)用價(jià)值。參考文獻(xià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 陳運(yùn)，龔耀寰. 基于二進(jìn)制冗余數(shù)的遞歸余數(shù)和算法. 電子科技大學(xué)學(xué)報(bào). 2000, 29(1):1-43 倪谷炎.分塊模冪算法.小型微型計(jì)算機(jī)系統(tǒng). 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 丁宏,郭艷華. 快速大數(shù)模乘算法及其應(yīng)用. 小型微型計(jì)算機(jī)系統(tǒng). 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. 密碼編碼學(xué)與網(wǎng)絡(luò)安全：原理與實(shí)踐(第二版). 北京:電子工業(yè)出版, 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