Montgomery算法分析与研究

第6卷第12期 2006年6月科学技术与工程Vol. 6 No. 12 Jun. 20061671 -1815 (2006)12 -1628 -04Science Technology and Engineering@ 2006 Sei. Tech. Engng,Montgomery算法分析与研究李明久季晓勇刘鞭箭(南京大学电子科学与工程系,南京210093)摘要Mongomery算法作为- - 种快速大数模乘算法,常被应用于RSA、EIGamal等公钥密码算法的基本运算。对Montgomery算法进行了深人的剖析,系统地进行了理论推导,通过实验应用分析比较了两种有代表性的优化方案,并针对性地给出了其他方面的一些改进建议。关键词RSA Montgomery算法 模乘中图法分类号TP309; 文献标识码 A随着信息技术的飞速发展,网络通信中的身份.上述定理中T+MN=T+(TN'-kR)N=T(1+N'N)-认证和信息安全传输问题正逐渐受到人们的关注kRN=TR-'R- kRN为R的倍数，所以(T+MN)/R为整和重视。数字签名、验证和密钥交换都离不开RSA、数。 又因为T+MN=T mod N,所以可以很容易推导出ElGamal等公钥密码体制算法。RSA等算法最基本最(T+MN)/R=TR+ mod N。耗时的计算工作就是大数模乘运算。Montgomery算Montgomery 在算法中选取0N,则可直(3)m,=ino' mod 2*,接利用Montgomery算法计算Mon(A ,BN)=A BR' modN,(4)T=T+m,N2*,然后再做适当调整。(5)U=T/R ,在进行模乘运算C=ABmodN时,常采取将大数(6)if U≥N return U-N,else return U。改进算法利用n'代替了N' ,只需预计算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法重新构造了M= 2 m2",其中m,=Ino' mod 2",这样.mod N=CR mod N。=0M=T.N'modR的大数乘法变成了s次的wxwbits字最后再转换回普通数域,C=Mon(C,l ,N)。由此可见,Montgomery模乘算法会带来一定的乘法,运算量和存储空间都大大减少。附加计算。该算法对于单次模乘如ABmodN并不适下面给出改进算法的简单证明推导。合,只有在RSA算法这样的需要多次模乘的幂模运由改进算法可以看出U可表示为算中才能体现其优势。(7+i MAN2*/R=(T+MN)/R。2.2基于Dusse改进的模乘算法改进对于Montgomery模乘算法的很多改进都是在(1)证明T+MN能被R整除。Dusse改进思想基础上进行的。Koc将 各种实现方法for i=0 tos-1,归纳为五大类sOS、CIOS .FOIS、FIPS、CIHS5),其中t:=(1+m.NV) mod 2*=最具代表性应用最广的是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"=由节1.2中算法步骤(3)、<4)可以看出m仅取决(t,R R) mod 2"=0。于i;T的求解是一个从低位到高位的过程;T最终结很明显T+MN的低s个字(w bits )均为0,所以(T+MN/果的低s个字为0,可以直接舍弃。根据这些特点可以.R为整数。将T=A B和后面的计算结合起来,并将乘法和约化交替进行，改进后算法简要步骤如下:(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用一个通用寄存器代替,算法与原算法效果相同。减少读写内存的次数。对于7和N由于太大只能存放在内存中国煤化工行1次Montgomery2 Montgomery 算法应用于大数模乘算法共YHCN M H G字.加63+5s+2次2.1 Montgomery 模乘算法读内存和25*+4s+1次与内仔。Montgomery算法给出了满足04922834015.22.2.2 FIPS法1024>1 0001993 1 53123.2FIPS法依据从低位到高位求解的顺序计算T+2048>2012 12181 8 55329.7MN。低s个字最终结果都为0,故直接舍弃,只保留进更为明显。这与Koc在X86处理器上测得的结果正好位，同时计算出m。低s个字的计算方法如下:相反。可见FIPS法 更适合于ARM和DSP之类寄存器丰富的RISC处理芯片,而CIOS法适合于通用处理器S=S+ 2 abi+ 2 mn,的实现。j-02.3其 他方面的改进建议m=Sjn' mod 2",Montgomery模乘算法主要用于RSA算法这样的S=(S+m,no)/2"。其中S用于保存计算的中间结果以及t向tu的进幂模运算,会大量出现Mon(A,A ,N)的模平方运位,始终小于3w bits,可用3个通用寄存器代替,这样算。AA由于其对称性存在aq,=qq;的冗余计算,所以移位只需要2条寄存器之间的move指令就能完成。可以对CIOS和FIPS法作--些细微修改，就可以减少(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