Montgomery算法分析與研究

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