擴(kuò)展euclid算法在rsa中的應(yīng)用

擴(kuò)展euclid算法在rsa中的應(yīng)用

eoclid算法也被稱為過程補(bǔ)償法，是根據(jù)等式計(jì)算的兩個(gè)最大值a和b的最常見算法。在那之后，人們進(jìn)行了變換，提出了擴(kuò)展eoclid算法的建議，用于解決ax=a.b的x和y問題。這些算法對(duì)研究密碼和數(shù)學(xué)學(xué)科具有極其重要的意義。RSA密碼體制是目前最著名、應(yīng)用最廣泛的公鑰密碼體制.RSA中關(guān)鍵的一環(huán)就是利用Euclid算法和擴(kuò)展Euclid算法來求公鑰和私鑰.隨著電子信息技術(shù)的飛速發(fā)展,RSA密碼體制廣泛應(yīng)用于計(jì)算能力和集成電路受限(如PC卡、SIM卡)且要求高速實(shí)現(xiàn)的系統(tǒng)中.筆者在IEEEP1363中擴(kuò)展Euclid算法的基礎(chǔ)上作了改進(jìn),得出一種新的算法,該算法消除了擴(kuò)展Euclid算法中負(fù)數(shù)的運(yùn)算,從而在一定程度上減少了RSA占用的計(jì)算資源,減少了實(shí)現(xiàn)RSA程序的復(fù)雜度.1ap-勞動(dòng)b-gcda,p定義1設(shè)a,b是任意2個(gè)整數(shù),b≠0.若存在整數(shù)c,使得a=bc,則稱b是a的約數(shù),a是b的倍數(shù).b可整除a,表示為b|a.定義2設(shè)a和b是整數(shù),若存在整數(shù)d,使得d|a,又d|b,則稱d為a和b的公約數(shù).公約數(shù)中最大者稱為最大公約數(shù),用gcd(a,b)表示.定理1a,b為2個(gè)整數(shù),若a=qb+r,即用b去除a,得商q,余數(shù)r,r<b,則gcd(a,b)=gcd(b,r).證明設(shè)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若整數(shù)a和b,用m除所得的最小非負(fù)余數(shù)相同,則稱a和b模m同余,用a≡bmodm來表示.定義4對(duì)于整數(shù)a,p,若存在整數(shù)b,滿足abmodp=1,則稱b是a的模p乘法逆元.定理2對(duì)于整數(shù)a和p,a存在模p的乘法逆元的充要條件是gcd(a,p)=1.證明充分性.若gcd(a,p)=1,根據(jù)歐拉定理,aφ(p)≡1modp,顯然aφ(p)-1modp是a的模p乘法逆元.必要性.假設(shè)存在a模p的乘法逆元為b,ab≡1modp,則ab=kp+1,故ab-kp=1.設(shè)gcd(a,p)=d,所以d|1,故d=1.推論1若gcd(a,b)=d,則存在x和y,使得xa+yb=d,當(dāng)d=1時(shí),有xa+yb=1,此時(shí)稱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運(yùn)行保護(hù)m保護(hù)a安全RSA公鑰密碼體制步驟如下:(1)用戶A任選大素?cái)?shù)p,q(保密),計(jì)算n=pq(公開),φ(n)=(p-1)(q-1)(保密).(2)任選e滿足gcd(φ(n),e)=1,令e為A的加密密鑰(公開),計(jì)算d使得ed≡1mod?(n)(d保密),e的公開不影響d的安全.(3)用戶B欲將信息m保密發(fā)送給A,查看A的公鑰e,n,計(jì)算C=memodn,將C發(fā)送給A.(4)A收到C后用只有他自己掌握的解密密鑰d,作m=Cdmodn解密出m.3eoclid算法的擴(kuò)展和改進(jìn)3.1gcdp,q的計(jì)算Euclid算法是求最大公因子的最普遍的算法,又稱輾轉(zhuǎn)相除法.設(shè)p,q(p>q),可得出如下遞推關(guān)系: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不宜導(dǎo)致p擴(kuò)展Euclid算法是Euclid算法的推廣,不僅能計(jì)算出2個(gè)正整數(shù)p和q的最大公因子gcd(p,q),還能計(jì)算出滿足gcd(p,q)=xp+yq的整系數(shù)x和y.已知正整數(shù)p,q(p>q),計(jì)算整數(shù)x,y,使得xp+yq=r,r=gcd(p,q).由Euclid算法可得出如下關(guān)系p=b0q+r0,q=b1r0+r1,r0=b2r1+r2,…rk-2=b2rk-1+rk,rk-1=bk+1rk+rk+1.(1)在上述關(guān)系中:若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)).同理可以計(jì)算出x3=x1-b3x2,y3=y1-b3y2,…xk=xk-2-bkxk-1,yk=yk-2-bkyk-1.當(dāng)rk+1=0時(shí),rk=gcd(p,q),且pxk+qyk=rk,得x=xk,y=yk.上述推導(dǎo)過程即為擴(kuò)展Euclid算法的主要流程.3.3擴(kuò)展euclid算法推導(dǎo)定理3設(shè)正整數(shù)p,q(p>q),由擴(kuò)展Euclid算法px+qy=gcd(p,q),則|x|<q,|y|<p.證明若pmodq=0,則gcd(p,q)=q,x=0,y=1,所以上述結(jié)論成立.若pmodq≠0,可得rk=gcd(p,q),且pxk+qyk=rk,則只需證明|xk|<q,|yk|<p.下面用數(shù)學(xué)歸納法證明.(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,設(shè)r2=qx′+r0y′.因?yàn)閞2=r0-b2(q-b1r0)=q(-b2)+r0(1+b2b1),所以|x′|=b2<r0,|y′|=1+b2b1<q.又因?yàn)閞2=qx′+r0y′=qx′+(p-b0q)y′=py′+q(x′-b0y′),所以|x2|=|y′|<q,|y2|=|x′-b0y′|<|x′|+|b0y′|<r0+b0q=p.(4)由歸納假設(shè),rk=qx′+r0y′,且|x′|<r0,|y′|<q成立.因?yàn)閞0=p-b0q,所以qx′+r0y′=qx′+(p-b0q)y′=py′+q(x′-b0y′).又因?yàn)閜xk+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節(jié)的擴(kuò)展Euclid算法,xk的符號(hào)為(-1)k,yk的符號(hào)為(-1)k+1.由于xk和yk均正負(fù)交替變化,如果只考慮xk和yk的絕對(duì)值,同時(shí)計(jì)數(shù)k解決符號(hào)問題,即pxk(-1)k+qyk(-1)k+1=rk,那么可以使其遞推關(guān)系更簡(jiǎn)單,從而改進(jìn)擴(kuò)展Euclid算法.若pmodq≠0,在擴(kuò)展Euclid算法推導(dǎo)中,令x0=1,y0=b0,x1=b1,y1=1+b1b0,可推導(dǎo)出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.當(dāng)rk+1=0時(shí),rk=gcd(p,q),且pxk(-1)k+qyk(-1)k+1=rk.當(dāng)kmod2=1時(shí),q的系數(shù)為正數(shù);而當(dāng)kmod2=0時(shí),通過(pxk(-1)k-pq)+(pq+qyk(-1)k+1)=rk,將q的系數(shù)轉(zhuǎn)為p-yk.根據(jù)定理3,該式為正數(shù).在RSA體制中,e滿足gcd(φ(n),e)=1,且需求e的模φ(n)乘法逆元d.由此可得下面的算法1.由于在RSA中不需要x的值,因此這里忽略x的計(jì)算.算法1判斷e是否滿足gcd(φ(n),e)=1,若滿足則計(jì)算出e的模φ(n)乘法逆元d=y.(ⅰ)p=φ(n),q=e,k=1,y0=0,y1=1,r0=p,r1=q,轉(zhuǎn)向(ⅱ);(ⅱ)若r1≠1,則k++,t=r1,b=r0/t,r1=r0modt,轉(zhuǎn)向(ⅲ),否則轉(zhuǎn)向(ⅳ);(ⅲ)若r1=0,則結(jié)束返回false,否則r0=t,y=by1,t=y1,y1=y0+y,y0=t,轉(zhuǎn)向(ⅱ);(ⅳ)若kmod2=0,則y=p-y1,否則y=y1,結(jié)束并返回true.通過上述改進(jìn),消除了擴(kuò)展Euclid算法中負(fù)數(shù)的運(yùn)算,從而消除了RSA程序?qū)崿F(xiàn)中負(fù)數(shù)的運(yùn)算,減少了RSA程序的復(fù)雜度,有利于RSA在資源有限系統(tǒng)中的應(yīng)用.張麗媛用到了類似的算法,但該算法并沒有考慮符號(hào)問題.該文中使用例子p=5,q=17,e=19求d,迭代的次數(shù)是奇數(shù)次,求出d=27,27×19mod(p-1)(q-1)=1.若用p=7,q=17,e=23求d,迭代的次數(shù)是偶數(shù)次,求出d=25,但25×23mod(p-1)(q-1)≠1.所以該算法是錯(cuò)誤的.4基于gcd的e從算法1得知,若其返回true,則說明選擇的e滿足gcd(φ(n),e)=1,且計(jì)算出e的模φ(