蒙哥马利算法简介.docx

文档介绍：该【蒙哥马利算法简介 】是由【niupai11】上传分享，文档一共【13】页，该文档可以免费在线阅读，需要了解更多关于【蒙哥马利算法简介 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。蒙哥马利(Montgomery)算法简介
最近在看一款芯片的DataSheet的时候,在加密处理部分集成了蒙哥马利协处理器。在我印象里,蒙哥马利不是个将军么,我又土了一回〜google后才知道是做RSA打算运算中用以快速计算模乘的,收集了一篇不错的文章,以供参考:
、八、'
刖言
俺曾经查阅了网上找得到的各种用于实现RSA的大数运算库,然而最终还是决定自己动手写一个。因为凡是效率高速度快的代码(crypto++、miracl、freelip、rsaref等),要么使用的数据结构过于复杂,要么编码风格杂乱无章,俺的水平和
耐心都实在是有限,以至于无法读懂这些东西。而俺读得懂的一些代码,其实现方
式却又过于幼稚,效率极低速度一塌糊涂。俺觉得像俺这样的人不在少数,于是决
心写一个清晰易懂,效率也过得去的东西奉献给大家。
这个函数库刚做好的时候,生成1024位的随机密钥耗时大约5分钟,俺认为是可以接受的。但后来找到一个叫tE!的老外用miracl库写的RsaTools,发现其生成
1024位的密钥耗时不超过三秒钟!于是俺针对俺的代码开始了艰苦的优化工作,希
望能达到甚至超过这一水平。一周之后1024位密钥的平均生成时间已经降至5秒左
右,但是单单依靠优化代码来进一步提高速度也非常困难了。于是俺开始借助金山
词霸来查阅能够通过google找到的一切与RSA算法相关的论文,但是网上关于RSA
算法的论述绝大多数都是用于硬件实现的,将其算法流程用软件设计语言来实现极
其繁琐。而且俺发现这样做下去俺只会离自己的初衷越来越远:俺的代码将不再清
晰易懂。所以俺一度准备放弃。
准备放弃之后,心态平静了许多,再回头去看那些原来不太能够理解的RSA算法原理,却发现其实也不是那么高深莫测,不急不躁地慢慢看,慢慢想,突然就
下子全明白了。一番改进之后,现在这个版本的函数库同样具有非常简单而清晰的
结构,速度也不算慢,生成1024位的密钥在俺PIII900的笔记本上平均耗时不超过
两秒。程序使用C++编写,,希望大家喜欢。如果发现
Bug或者有好的修改建议,俺将非常感谢您能够给俺一个Mail。
最后,感谢看雪论坛,感谢雪兄多次热心相助,俺在此学到了很多知识,当然还要乘机拍拍马屁,感谢俺家甜甜的支持!
******@
原理介绍
RSA原理:
选取两个不同的大素数P、q,并计算N=p*q选取小素数d,并计算e,使d*e%(p-l)(q-l)=l
对于任意A<N:
若B=A**d%N
则A=B**e%N
可见d、e形成了非对称秘钥关系,加密者用公钥d加密,解密者可用私钥e解密,第
三者即使拦截了密文B、公钥d和N,在不知道p、q的前提下,无法推算出e,从而无
法获得明文A。当N取非常大的值时,将其因式分解成p、q是非常困难的,例如当N
为1024bit时,据分析,需动用价值数千万美金的大型计算机系统并耗费一年的时
间。
RSA密钥的选取和加解密过程都非常简洁,在算法上主要要实现四个问题:
1、 如何处理大数运算
2、 如何求解同余方程XY%M=1
3、 如何快速进行模幕运算
4、 如何获取大素数
实际上,在实现RSA算法的过程中大家会发现后三个问题不是各自独立的,它们互
有关联,环环相套,相信届时你会意识到:RSA算法是一种“优美”的算法!
大数存储
RSA依赖大数运算,目前主流RSA算法都建立在1024位的大数运算之上。而大多数的编译器只能支持到64位的整数运算,即我们在运算中所使用的整数必须
小于
等于64位,即:Oxffffffffffffffff,也就是18446744073709551615,这远远达不
到RSA的需要,于是需要专门建立大数运算库来解决这一问题。
最简单的办法是将大数当作数组进行处理,数组的各元素也就是大数每一位上的数字,通常采用最容易理解的十进制数字0—9。然后对“数字数组”编写加减乘
除函数。但是这样做效率很低,因为二进制为1024位的大数在十进制下也有三百多
位,对于任何一种运算,都需要在两个有数百个元素的数组空间上多次重循环,还
需要许多额外的空间存放计算的进退位标志及中间结果。另外,对于某些特殊的运
算而言,采用二进制会使计算过程大大简化,而这种大数表示方法转化成二进制显
然非常麻烦,所以在某些实例中则干脆采用了二进制数组的方法来记录大数,当然
这样效率就更低了。
一个有效的改进方法是将大数表示为一个n进制数组,对于目前的32位系统而言n可以取值为2的32次方,即0x100000000,假如将一个二进制为1024位的大数
转化成0x10000000进制,就变成了32位,而每一位的取值范围不再是二进制的0—1
或十进制的0—9,而是0-0xffffffff,我们正好可以用一个32位的DWORD(如:无
符号长整数,unsignedlong)类型来表示该值。所以1024位的大数就变成一个含
有32个元素的DWORD数组,而针对DWORD数组进行各种运算所需的循环规模至多32
次而已。而且0x100000000进制与二进制,对于计算机来说,几乎是一回事,转换
非常容易。
例如大数18446744073709551615,等于0xffffffffffffffff,就相当于十进制的99:有两位,每位都是0xffffffff。而18446744073709551616等于0x00000001
0000000000000000,就相当于十进制的100:有三位,第一位是1,其它两位都是
0,如此等等。在实际应用中,“数字数组”的排列顺序采用低位在前高位在后的
方式,这样,大数A就可以方便地用数学表达式来表示其值:
A=Sum[i=0ton](A*r**i),r=0xl00000000,0<=A<r
其中Sum表示求和,A表示用以记录A的数组的第i个元素,**表示乘方。
任何整数运算最终都能分解成数字与数字之间的运算,在0x100000000进制下其“数字”最大达到0xffffffff,其数字与数字之间的运算,结果也必然超出了目
前32位系统的字长。在VC++中,存在一个—_int64类型可以处理64位的整数,所以
不用担心这一问题,而在其它编译系统中如果不存在64位整形,就需要采用更小的
进制方式来存储大数,例如16位的WORD类型可以用来表示0x10000进制。但效率更
高的办法还是采用32位的DWORD类型,只不过将0x100000000进制改成0x40000000
进制,这样两个数字进行四则运算的最大结果为0x3fffffff*0x3fffffff,小于
0xffffffffffffff,可以用一个双精度浮点类型(double,52位有效数字)来储存
这一中间结果,只是不能简单地用高位低位来将中间结果拆分成两个“数字”。
加减乘除
设有大数A、B和C,其中A>=B:
A=Sum[i=0top](A*r**i)
B=Sum[i=0toq](B*r**i)
C=Sum[i=0ton](C*r**i)r=0x100000000,0<=A,B,C<r,p>=q
则当C=A+B、C=A-B、C=A*B时,我们都可以通过计算出C来获得C:
C=A+B,显然C不总是等于A+B,因为A+B可能>0xffffffff,而C
必须<=0xffffffff,这时就需要进位,当然在计算C[i-1]时也可能产生了进位,所
以计算C时还要加上上次的进位值。如果用一个64位变量result来记录和,另个32位变量carry来记录进位,则有:
carry=0
FORiFROM0TOp
result二A+B+carry
C二result%0x100000000
carry二result/0x100000000
IFcarry=On=p
ELSEn=p+1
C=A-B,同理C不总是等于A-B,因为A-B可能<0,而C必须>=0,
这时就需要借位,同样在计算C[i-1]时也可能产生了借位,所以计算C时还要减
去上次的借位值:
carry=0
FORiFROM0TOp
IFA-B-carry>=0
C二A—B—carry
carry=0
ELSE
C=0x100000000+A-B-carry
carry=1
n=p
WHILEC[n]=0n=n-1
C=A*B,首先我们需要观察日常做乘法所用的“竖式计算”过程:
A3A2A1A0
*B2B1B0=A3B0A2B0A1B0A0B0
+A3B1A2B1A1B1A0B1
+A3B2A2B2A1B2A0B2=C5C4C3C2C1C0
可以归纳出:C=Sum[j=0toq](A[i-j]*B[j]),其中i-j必须>=0且〈二p。当然这
一结论没有考虑进位,虽然计算A[i-j]*B[j]和Sum的时候都可能发生进位,但显然
这两种原因产生的进位可以累加成一个进位值。最终可用如下算法完成乘法:
n二p+q_l
carry=0
ForiFROM0TOn
result二carry
ForjFROM0TOq
IF0<=i-j<=presult二result+A[i-j]*B[j]
C二result%OxlOOOOOOOO
carry二result/OxlOOOOOOOO
IFcarry!=0
n=n+1
C[n]二carry
对于C=A/B,由于无法将B对A“试商",我们只能转换成B[q]对A[p]的试商来得到
一个近似值,所以无法直接通过计算C来获得C,只能一步步逼近C。由于:
B*(A[p]/B[q]-1)*0x100000000**(p-q)<C
令:X=0,重复A=A-X*B,X=X+(A[p]/B[q]-1)*0x100000000**(p-q),直到A<B则:X=A/B,且此时的A=A%B
注意对于任意大数A*0x100000000**k,都等价于将A的数组中的各元素左移k位,
不必计算;同样,A/0x100000000**k则等价于右移。
欧几里得方程
在RSA算法中,往往要在已知A、N的情况下,求B,使得(A*B)%N=1。即相当于求解B、M都是未知数的二元一次不定方程A*B-N*M=1的最小整数解。
而针对不定方程ax-by=c的最小整数解,古今中外都进行过详尽的研究,西方有著名的欧几里德算法,即辗转相除法,中国有秦九韶的“大衍求一术”。事实上
二元一次不定方程有整数解的充要条件是c为a、b的最大公约数。即当c=1时,a、b
必须互质。而在RSA算法里由于公钥d为素数,素数与任何正整数互质,所以可以通
过欧几里德方程来求解私钥e。
欧几里德算法是一种递归算法,比较容易理解:
例如:11x-49y=1,求x
11x-49y=149%11=5->
11x-5y=111%5=1->
x-5y=1
令y=0代入(c)得x=1令x=1代入(b)得y=2令y=2代入(a)得x=9
同理可使用递归算法求得任意ax-by=l(a、b互质)的解。实际上通过分析归纳将递归算法转换成非递归算法就变成了大衍求一术:x=0,y=1
WHILEa!=0
i=y
y=x-y*a/b
x=i
i=a
a=b%a
b=i
IFx<0x=x+b
RETURNx
模幕运算
模幕运算是RSA的核心算法,最直接地决定了RSA算法的性能。针对快速模幕运算这一课题,西方现代数学家提出了大量的解决方案,通常都是先将幕模运算转
化为乘模运算。
例如求D=C**15%N,由于:a*b%n=(a%n)*(b%n)%n,所以:
Cl=C*C%N二C**2%N
C2=C1*C%N二C**3%N
C3=C2*C2%N二C**6%N
C4=C3*C%N二C**7%N
C5=C4*C4%N二C**14%N
C6=C5*C%N=C**15%N
即:对于E=15的幕模运算可分解为6个乘模运算,归纳分析以上方法可以发现对于任意E,都可采用以下算法计算D=C**E%N:
D=1
WHILEE>=0
IFE%2=0
C=C*C%N
E=E/2
ELSE
D=D*C%N
E=E-1
RETURND继续分析会发现,要知道E何时能整除2,并不需要反复进行减一或除二的操作,只需验证E的二进制各位是0还是1就可以了,从左至右或从右至左验证都可
以,从左至右会更简洁,设E=Sum[i=0ton](E*2**i),0<=E<=1,则:
D=1
FORi=nTO0
D=D*D%N
IFE=1D=D*C%N
RETURND
这样,模幕运算就转化成了一系列的模乘运算。
模乘运算
对于乘模运算A*B%N,如果A、B都是1024位的大数,先计算A*B,再%N,就会
产生2048位的中间结果,如果不采用动态内存分配技术就必须将大数定义中的数组
空间增加一倍,这样会造成大量的浪费,因为在绝大多数情况下不会用到那额外的
一倍空间,而采用动态内存分配技术会使大数存储失去连续性而使运算过程中的循
环操作变得非常繁琐。所以模乘运算的首要原则就是要避免直接计算A*B。
设A=Sum[i=0tok](A*r**i),r=0x10000000,0<=A<r,贝U:
C=A*B=Sum[i=0ton](A*B*r**i)%N
可以用一个循环来处理:
C=0;
FORi=nto0
C=C*r
C=C+A*B
RETURNC
这样将一个多位乘法转换成了一系列单位乘法和加法,由于:
a*b%n=(a%n*b%n)%n
a+b%n=(a%n+b%n)%n
所以,对于求C=A*B%N,我们完全可以在求C的过程中完成:
C=0;
FORi=nto0
C=C*r%N
C=C+A*B%N
RETURNC
这样产生的最大中间结果是A*B或C*r,都不超过1056位,空间代价会小得多,但是时间代价却加大了,因为求模的过程由一次变成了多次。对于孤立的乘模
运算而言这种时间换空间的交易还是值得的,但是对于反复循环的乘模运算,这种
代价就无法承受,必须另寻出路。
蒙哥马利模乘
由于RSA的核心算法是模幕运算,模幕运算又相当于模乘运算的循环,要提高RSA算法的效率,首要问题在于提高模乘运算的效率。不难发现,模乘过程中复杂
度最高的环节是求模运算,因为一次除法实际上包含了多次加法、减法和乘法,如
果在算法中能够尽量减少除法甚至避免除法,则算法的效率会大大提高。
设A=Sum[i=0tok](A*2**i),0<=A<=1,则:
C=A*B=Sum[i=0tok](A*B*2**i)
可用循环处理为:
C=0
FORiFROMkTO0
C=C*2
C=C+A*B
RETURNC
若令C'=A*B*2**(-k),则:
C'=Sum[i=0tok](A*B*2**(i-k))
用循环处理即:
C'=0
FORiFROM0TOk
C'=C'+A*B
C'=C'/2
RETURNC'通过这一算法求A*B*2**(-k)是不精确的,因为在循环中每次除以2都可能有余数被舍弃了,但是可以通过这一算法求A*B*2**(-k)%N的精确值,方法是在对C'除
2之前,让C'加上C'[0]*N。由于在RSA中N是两个素数的积,总是奇数,所以当C,是
奇数时,C,[0]=1,C,+C,[0]*N就是偶数,而当C,为偶数时C,[0]=0,C,+C,[0]*N还是偶数,这样C,/2就不会有余数被舍弃。又因为C,+N%N=C,%N,所以在计算
过程中加若干次N,并不会影响结果的正确性。可以将算法整理如下:
C,=0
FORiFROM0TOk
C,=C,+A*B
C,=C,+C,[0]*N
C,=C,/2
IFC,>=NC,=C,-N
RETURNC,
由于在RSA中A、B总是小于N,又0<=A,C,[0]<=1,所以:
C,=(C,+A*B+C,[O]*N)/2
C,<(C,+2N)/2
2C,<C,+2N
C,<2N
既然C,总是小于2N,所以求C,%N就可以很简单地在结束循环后用一次减法来完成,即在求A*B*2**(-k)%N的过程中不用反复求模,达到了我们避免做除法的目
的。当然,这一算法求得的是A*B*2**(-k)%N,而不是我们最初需要的A*B%N。但
是利用A*B*2**(-k)我们同样可以求得A**E%N。
设R=2**k%N,R,=2**(-k)%N,E=Sum[i=0ton](E*2**i):
A,=A*R%N
X=A,
FORiFROMnTO0
X=X*X*R,%N
IFE=1X=X*A,*R,%N
X=X*1*R,%N
RETURNX