第6卷第12期 2006年6月科學(xué)技術(shù)與工程Vol. 6 No. 12 Jun. 20061671 -1815 (2006)12 -1628 -04Science Technology and Engineering@ 2006 Sei. Tech. Engng,Montgomery算法分析與研究李明久季曉勇劉鞭箭(南京大學(xué)電子科學(xué)與工程系,南京210093)摘要Mongomery算法作為- - 種快速大數(shù)模乘算法,常被應(yīng)用于RSA、EIGamal等公鑰密碼算法的基本運算。對Montgomery算法進行了深人的剖析,系統(tǒng)地進行了理論推導(dǎo),通過實驗應(yīng)用分析比較了兩種有代表性的優(yōu)化方案,并針對性地給出了其他方面的一些改進建議。關(guān)鍵詞RSA Montgomery算法 模乘中圖法分類號TP309; 文獻標(biāo)識碼 A隨著信息技術(shù)的飛速發(fā)展,網(wǎng)絡(luò)通信中的身份.上述定理中T+MN=T+(TN'-kR)N=T(1+N'N)-認(rèn)證和信息安全傳輸問題正逐漸受到人們的關(guān)注kRN=TR-'R- kRN為R的倍數(shù)，所以(T+MN)/R為整和重視。數(shù)字簽名、驗證和密鑰交換都離不開RSA、數(shù)。 又因為T+MN=T mod N,所以可以很容易推導(dǎo)出ElGamal等公鑰密碼體制算法。RSA等算法最基本最(T+MN)/R=TR+ mod N。耗時的計算工作就是大數(shù)模乘運算。Montgomery算Montgomery 在算法中選取0N,則可直(3)m,=ino' mod 2*,接利用Montgomery算法計算Mon(A ,BN)=A BR' modN,(4)T=T+m,N2*,然后再做適當(dāng)調(diào)整。(5)U=T/R ,在進行模乘運算C=ABmodN時,常采取將大數(shù)(6)if U≥N return U-N,else return U。改進算法利用n'代替了N' ,只需預(yù)計算N'最低轉(zhuǎn)換到模N的剩余系中，用|A=AR mod N分別代替w bits,借助在文獻[3]中給出的一種二進制快速EuclidB=BR mod N擴展算法可以很便捷地計算出來。由于這個改進,算A、B,然后計算C=Mon(A ,B ,N)=ABR mod N=A BR法重新構(gòu)造了M= 2 m2",其中m,=Ino' mod 2",這樣.mod N=CR mod N。=0M=T.N'modR的大數(shù)乘法變成了s次的wxwbits字最后再轉(zhuǎn)換回普通數(shù)域,C=Mon(C,l ,N)。由此可見,Montgomery模乘算法會帶來一定的乘法,運算量和存儲空間都大大減少。附加計算。該算法對于單次模乘如ABmodN并不適下面給出改進算法的簡單證明推導(dǎo)。合,只有在RSA算法這樣的需要多次模乘的冪模運由改進算法可以看出U可表示為算中才能體現(xiàn)其優(yōu)勢。(7+i MAN2*/R=(T+MN)/R。2.2基于Dusse改進的模乘算法改進對于Montgomery模乘算法的很多改進都是在(1)證明T+MN能被R整除。Dusse改進思想基礎(chǔ)上進行的。Koc將 各種實現(xiàn)方法for i=0 tos-1,歸納為五大類sOS、CIOS .FOIS、FIPS、CIHS5),其中t:=(1+m.NV) mod 2*=最具代表性應(yīng)用最廣的是CIOS和FIPS法。下面分別(t+(tno' mod 2")N) mod 2°=對這兩種方法進行分析。(t+(t.N" mod 2")NV) mod 2"=2.2.1 CIOS法(.+(1+N'N)) mod 2"=由節(jié)1.2中算法步驟(3)、<4)可以看出m僅取決(t,R R) mod 2"=0。于i;T的求解是一個從低位到高位的過程;T最終結(jié)很明顯T+MN的低s個字(w bits )均為0,所以(T+MN/果的低s個字為0,可以直接舍棄。根據(jù)這些特點可以.R為整數(shù)。將T=A B和后面的計算結(jié)合起來,并將乘法和約化交替進行，改進后算法簡要步驟如下:(2)證明(T+MN)/R=TR" mod N。(T+MN)/R= [(T+MN)/R](1+N'N) mod N≈T←0,[(T+MN)IR]RR" mod N。T=T+aB,又::(T+MN)能被R整除,m=tpno' mod 2",.(T+MN)/R≈[(T+MN)/R]RR mod N=T=( T+mN)/2"。(T+MN)R+ mod N= (TR +MR "N) mod N=這里m用于臨時存放m,只需u bits的存放空間,TR~ mod N。同時可以看出T的大小從來沒有超過s+2個w bits。在由(T+MN)/R<(NR+RN)lR=2N?？梢钥闯龈倪M后的具體實現(xiàn)時將中間變量m用一個通用寄存器代替,算法與原算法效果相同。減少讀寫內(nèi)存的次數(shù)。對于7和N由于太大只能存放在內(nèi)存中國煤化工行1次Montgomery2 Montgomery 算法應(yīng)用于大數(shù)模乘算法共YHCN M H G字.加63+5s+2次2.1 Montgomery 模乘算法讀內(nèi)存和25*+4s+1次與內(nèi)仔。Montgomery算法給出了滿足04922834015.22.2.2 FIPS法1024>1 0001993 1 53123.2FIPS法依據(jù)從低位到高位求解的順序計算T+2048>2012 12181 8 55329.7MN。低s個字最終結(jié)果都為0,故直接舍棄,只保留進更為明顯。這與Koc在X86處理器上測得的結(jié)果正好位，同時計算出m。低s個字的計算方法如下:相反?？梢奆IPS法 更適合于ARM和DSP之類寄存器豐富的RISC處理芯片,而CIOS法適合于通用處理器S=S+ 2 abi+ 2 mn,的實現(xiàn)。j-02.3其 他方面的改進建議m=Sjn' mod 2",Montgomery模乘算法主要用于RSA算法這樣的S=(S+m,no)/2"。其中S用于保存計算的中間結(jié)果以及t向tu的進冪模運算,會大量出現(xiàn)Mon(A,A ,N)的模平方運位,始終小于3w bits,可用3個通用寄存器代替,這樣算。AA由于其對稱性存在aq,=qq;的冗余計算,所以移位只需要2條寄存器之間的move指令就能完成?？梢詫IOS和FIPS法作--些細(xì)微修改，就可以減少(s3-s )/2次字乘法。高s+1個字郎為(T+MN)/R,計算方法如下:另外Montgomery算法最后都需作-次條件減S=S+ 2 (ab.+mm),法。在RSA算法運算中最初時0j;i-a+14N則可以省略條件減法。因為S=(AB+MN)IR<2N,1=So,將s作為Montgomery算法輸人時同樣有(S3+MN)/R