扩展euclid算法在rsa中的应用

扩展euclid算法在rsa中的应用

eoclid算法也被称为过程补偿法，是根据等式计算的两个最大值a和b的最常见算法。在那之后，人们进行了变换，提出了扩展eoclid算法的建议，用于解决ax=a.b的x和y问题。这些算法对研究密码和数学学科具有极其重要的意义。RSA密码体制是目前最著名、应用最广泛的公钥密码体制.RSA中关键的一环就是利用Euclid算法和扩展Euclid算法来求公钥和私钥.随着电子信息技术的飞速发展,RSA密码体制广泛应用于计算能力和集成电路受限(如PC卡、SIM卡)且要求高速实现的系统中.笔者在IEEEP1363中扩展Euclid算法的基础上作了改进,得出一种新的算法,该算法消除了扩展Euclid算法中负数的运算,从而在一定程度上减少了RSA占用的计算资源,减少了实现RSA程序的复杂度.1ap-劳动b-gcda,p定义1设a,b是任意2个整数,b≠0.若存在整数c,使得a=bc,则称b是a的约数,a是b的倍数.b可整除a,表示为b|a.定义2设a和b是整数,若存在整数d,使得d|a,又d|b,则称d为a和b的公约数.公约数中最大者称为最大公约数,用gcd(a,b)表示.定理1a,b为2个整数,若a=qb+r,即用b去除a,得商q,余数r,r<b,则gcd(a,b)=gcd(b,r).证明设d=gcd(a,b),d1=gcd(b,r),由a=qb+r,a-qb=r,已知d|r,由d|b及d|r,故d|d1.反过来,d1=gcd(b,r),a=qb+r,故d1|a,由d1|a及d1|b,故d1|d.由d|d1和d1|d,即d=d1,故gcd(a,b)=gcd(b,r).定义3若整数a和b,用m除所得的最小非负余数相同,则称a和b模m同余,用a≡bmodm来表示.定义4对于整数a,p,若存在整数b,满足abmodp=1,则称b是a的模p乘法逆元.定理2对于整数a和p,a存在模p的乘法逆元的充要条件是gcd(a,p)=1.证明充分性.若gcd(a,p)=1,根据欧拉定理,aφ(p)≡1modp,显然aφ(p)-1modp是a的模p乘法逆元.必要性.假设存在a模p的乘法逆元为b,ab≡1modp,则ab=kp+1,故ab-kp=1.设gcd(a,p)=d,所以d|1,故d=1.推论1若gcd(a,b)=d,则存在x和y,使得xa+yb=d,当d=1时,有xa+yb=1,此时称x是a的模b的乘法逆元,y是b模a的乘法逆元.证明由gcd(a,b)=d得a=md,b=nd,且gcd(m,n)=1.xa+yb=xmd+ynd=(xm+yn)d,又gcd(m,n)=1,由定理2得存在x和y使得xm+yn=1,所以存在x和y使得xa+yb=d.2运行保护m保护a安全RSA公钥密码体制步骤如下:(1)用户A任选大素数p,q(保密),计算n=pq(公开),φ(n)=(p-1)(q-1)(保密).(2)任选e满足gcd(φ(n),e)=1,令e为A的加密密钥(公开),计算d使得ed≡1modϕ(n)(d保密),e的公开不影响d的安全.(3)用户B欲将信息m保密发送给A,查看A的公钥e,n,计算C=memodn,将C发送给A.(4)A收到C后用只有他自己掌握的解密密钥d,作m=Cdmodn解密出m.3eoclid算法的扩展和改进3.1gcdp,q的计算Euclid算法是求最大公因子的最普遍的算法,又称辗转相除法.设p,q(p>q),可得出如下递推关系:p=b0q+r00≤r0<q,q=b1r0+r10≤r1<r0,r0=b2r1+r20≤r2<r1,…rk-2=bkrk-1+rk0≤rk<rk-1,rk-1=bk+1rk.那么,gcd(p,q)=gcd(q,r0)=gcd(r0,r1)=…=gcd(rk-2,rk-1)=gcd(rk-1,rk)=gcd(rk,0)=rk.3.2gcdp,q不宜导致p扩展Euclid算法是Euclid算法的推广,不仅能计算出2个正整数p和q的最大公因子gcd(p,q),还能计算出满足gcd(p,q)=xp+yq的整系数x和y.已知正整数p,q(p>q),计算整数x,y,使得xp+yq=r,r=gcd(p,q).由Euclid算法可得出如下关系p=b0q+r0,q=b1r0+r1,r0=b2r1+r2,…rk-2=b2rk-1+rk,rk-1=bk+1rk+rk+1.(1)在上述关系中:若r0=0,则gcd(p,q)=q,x0=0,y0=1,得x=x0,y=y0;若r0≠0,令x0=1,y0=-b0,x1=-b1,y1=1+b1b0,则px0+qy0=r0,(2)px1+qy1=r1.(3)将(2)和(3)代入(1)式得px0+qy0-b2(px1+qy1)=r2.又由于px2+qy2=r2,因此x2=x0-b2x1=1+b2b1,y2=y0-b2y1=-(b0+b2(1+b1b0)).同理可以计算出x3=x1-b3x2,y3=y1-b3y2,…xk=xk-2-bkxk-1,yk=yk-2-bkyk-1.当rk+1=0时,rk=gcd(p,q),且pxk+qyk=rk,得x=xk,y=yk.上述推导过程即为扩展Euclid算法的主要流程.3.3扩展euclid算法推导定理3设正整数p,q(p>q),由扩展Euclid算法px+qy=gcd(p,q),则|x|<q,|y|<p.证明若pmodq=0,则gcd(p,q)=q,x=0,y=1,所以上述结论成立.若pmodq≠0,可得rk=gcd(p,q),且pxk+qyk=rk,则只需证明|xk|<q,|yk|<p.下面用数学归纳法证明.(1)k=0,p=b0q+r0,|x0|=1<q,|y0|=b0<p.(2)k=1,q=b1r0+r1,p=(1+b1b0)r0+b0r1,|x1|=b1<q,|y1|=1+b1b0<p.(3)k=2,r0=b2r1+r2,设r2=qx′+r0y′.因为r2=r0-b2(q-b1r0)=q(-b2)+r0(1+b2b1),所以|x′|=b2<r0,|y′|=1+b2b1<q.又因为r2=qx′+r0y′=qx′+(p-b0q)y′=py′+q(x′-b0y′),所以|x2|=|y′|<q,|y2|=|x′-b0y′|<|x′|+|b0y′|<r0+b0q=p.(4)由归纳假设,rk=qx′+r0y′,且|x′|<r0,|y′|<q成立.因为r0=p-b0q,所以qx′+r0y′=qx′+(p-b0q)y′=py′+q(x′-b0y′).又因为pxk+qyk=rk,所以|xk|=|y′|,|yk|=|x′-b0y′|.由|x′|<r0,|y′|<q得|xk|=|y′|<q,|yk|=|x′-b0y′|≤|x′|+b0|y′|<r0+b0q=p.由3.2节的扩展Euclid算法,xk的符号为(-1)k,yk的符号为(-1)k+1.由于xk和yk均正负交替变化,如果只考虑xk和yk的绝对值,同时计数k解决符号问题,即pxk(-1)k+qyk(-1)k+1=rk,那么可以使其递推关系更简单,从而改进扩展Euclid算法.若pmodq≠0,在扩展Euclid算法推导中,令x0=1,y0=b0,x1=b1,y1=1+b1b0,可推导出x2=x0+b2x1,y2=y0+b2y1,px2(-1)2+qy2(-1)2+1=r2,…xk=xk-2+bkxk-1,yk=yk-2+bkyk-1,pxk(-1)k+qyk(-1)k+1=rk.当rk+1=0时,rk=gcd(p,q),且pxk(-1)k+qyk(-1)k+1=rk.当kmod2=1时,q的系数为正数;而当kmod2=0时,通过(pxk(-1)k-pq)+(pq+qyk(-1)k+1)=rk,将q的系数转为p-yk.根据定理3,该式为正数.在RSA体制中,e满足gcd(φ(n),e)=1,且需求e的模φ(n)乘法逆元d.由此可得下面的算法1.由于在RSA中不需要x的值,因此这里忽略x的计算.算法1判断e是否满足gcd(φ(n),e)=1,若满足则计算出e的模φ(n)乘法逆元d=y.(ⅰ)p=φ(n),q=e,k=1,y0=0,y1=1,r0=p,r1=q,转向(ⅱ);(ⅱ)若r1≠1,则k++,t=r1,b=r0/t,r1=r0modt,转向(ⅲ),否则转向(ⅳ);(ⅲ)若r1=0,则结束返回false,否则r0=t,y=by1,t=y1,y1=y0+y,y0=t,转向(ⅱ);(ⅳ)若kmod2=0,则y=p-y1,否则y=y1,结束并返回true.通过上述改进,消除了扩展Euclid算法中负数的运算,从而消除了RSA程序实现中负数的运算,减少了RSA程序的复杂度,有利于RSA在资源有限系统中的应用.张丽媛用到了类似的算法,但该算法并没有考虑符号问题.该文中使用例子p=5,q=17,e=19求d,迭代的次数是奇数次,求出d=27,27×19mod(p-1)(q-1)=1.若用p=7,q=17,e=23求d,迭代的次数是偶数次,求出d=25,但25×23mod(p-1)(q-1)≠1.所以该算法是错误的.4基于gcd的e从算法1得知,若其返回true,则说明选择的e满足gcd(φ(n),e)=1,且计算出e的模φ(