1.前言
RSA密碼是1978年美國(guó)麻省理工學(xué)院三位密碼學(xué)者、和提出的一種基于大合數(shù)因子分解困難性的公開(kāi)密鑰密碼。由于RSA密碼既可用于加密，又可用于數(shù)字簽名，通俗易懂，因此RSA密碼已成為目前應(yīng)用最廣泛的公開(kāi)密鑰密碼。
2.RSA的密鑰生成過(guò)程1.隨機(jī)地選擇兩個(gè)大素?cái)?shù)p和q，而且保密；
2.計(jì)算n=pq，將n公開(kāi)；
3.計(jì)算φ(n)=(p-1)(q-1)，對(duì)φ(n)保密；
4.隨機(jī)地選取一個(gè)正整數(shù)e，1eφ(n)且(e,φ(n))=1，將e公開(kāi)；
5.根據(jù)ed=1(modφ(n))，求出d，并對(duì)d保密；
6.加密運(yùn)算：c=p^e(modn)；
7.解密運(yùn)算：p=c^d(modn)。
注意：在加密運(yùn)算和解密運(yùn)算中，M和C的值都必須小于n，也就是說(shuō)，如果明文（或密文）太大，必須進(jìn)行分組加密（或解密）。
比如愛(ài)麗絲選擇了61和53。（實(shí)際應(yīng)用中，這兩個(gè)質(zhì)數(shù)越大，就越難破解。）
愛(ài)麗絲就把61和53相乘:n=61×53=3233；n的長(zhǎng)度就是密鑰長(zhǎng)度。3233寫(xiě)成二進(jìn)制是110010100001，一共有12位，所以這個(gè)密鑰就是12位。實(shí)際應(yīng)用中，RSA密鑰一般是1024位，重要場(chǎng)合則為2048位。
根據(jù)公式：φ(n)=(p-1)(q-1)，愛(ài)麗絲算出φ(3233)等于60×52，即3120。
愛(ài)麗絲就在1到3120之間，隨機(jī)選擇了17。（實(shí)際應(yīng)用中，常常選擇65537。）
計(jì)算ed≡1(modφ(n))帶入e=17，求解方程組：17x+3120y=1,這個(gè)方程可以用"擴(kuò)展歐幾里得算法"求解，得到(x,y)=(2753,-15)其中私鑰d=2753
3.RSA解密正確性證明命題:解密者使用自己的私鑰d可以恢復(fù)正確的明文m。
證明:由加密過(guò)程c=m^emodn，所以存在某整數(shù)k，滿足c^dmodn=(m^e)^dmodn=m^kφ(n)modn
分兩種情況:
(m,n)=1，由Euler定理m^φ(n)modn=1，因此m^kφ(n)modn=1，于是m^kφ(n)+1modn=m，即c^dmodn=m
(m,n)≠1，設(shè)m=tp,0tq。
因?yàn)?tp,q)=1，由Euler定理得m^φ(n)modq=1。所以存在整數(shù)r，滿足m^φ(n)=1+rq。等式兩邊同乘以m，得m^kφ(n)+1=m+rtpq因此，c^dmodn=m^φ(n)+1modn=(m+rtpq)modn=m
4.RSA算法細(xì)節(jié)實(shí)現(xiàn)RSA算法，主要需要實(shí)現(xiàn)以下幾個(gè)部分：
1.對(duì)大數(shù)的素?cái)?shù)判定；
2.模逆運(yùn)算；
3.模指運(yùn)算。
4.1對(duì)大數(shù)的素?cái)?shù)判定
一個(gè)較小的數(shù)是否為素?cái)?shù)，可以用試除法來(lái)判定，而如果這個(gè)數(shù)很大的話，試除法的效率就會(huì)變得很低下。也就是說(shuō)，試除法不適用于對(duì)大數(shù)進(jìn)行素?cái)?shù)判定，所以對(duì)大數(shù)的素?cái)?shù)判定一般采用素?cái)?shù)的概率性檢驗(yàn)算法，其中又以Miller算法最為常見(jiàn)。
使用素?cái)?shù)的概率性檢驗(yàn)算法判定一個(gè)數(shù)是否為素?cái)?shù)，雖然相比試除法而言效率非常之高，但是對(duì)該數(shù)的判定結(jié)果并不準(zhǔn)確。該算法通過(guò)循環(huán)使用Miller算法來(lái)提高判定結(jié)果的正確性。
素?cái)?shù)的概率性檢驗(yàn)算法的流程：對(duì)于奇整數(shù)n，在2~n-2之間隨機(jī)地選取k個(gè)互不相同的整數(shù)，循環(huán)使用Miller算法來(lái)檢驗(yàn)n是否為素?cái)?shù)。若結(jié)果為true，則認(rèn)為n可能為素?cái)?shù)，否則肯定n為合數(shù)。
一輪Miller算法判定大整數(shù)n不是素?cái)?shù)的概率≤4^-1，所以，素?cái)?shù)的概率性檢驗(yàn)算法判定大整數(shù)n不是素?cái)?shù)的概率≤4^-k（k為Miller算法的循環(huán)次數(shù)）。
#4.1.1Miller算法
若n為奇素?cái)?shù)，則對(duì)?a∈[2,n-2]，由于a與n互素，根據(jù)歐拉定理可得a^φ(n)=a^(n-1)=1(modn)。
若n是奇素?cái)?shù)，則不存在1(modn)的非平凡平方根，即對(duì)于x^2=1(modn)的解有且僅有±1。
若n是奇素?cái)?shù)，則n-1是偶數(shù)。不妨令n=2^t*m+1（t≥1），則m為n-1的最大奇因子。根據(jù)上述兩點(diǎn)，不難得出，對(duì)?a∈[2,n-2]，?τ∈[1,t]使得
Miller算法正是通過(guò)上述的逆否命題而設(shè)計(jì)出來(lái)的，其原理是：對(duì)?a∈[2,n-2]，n是一個(gè)合數(shù)的充要條件是對(duì)?τ∈[1,t]使得
Miller算法的設(shè)計(jì)思路：令b=a^m(modn)，如果b=±1(modn)則n可能是一個(gè)素?cái)?shù)；否則，b=b^2(modn)，并判斷是否滿足b=-1(modn)（滿足則n可能是一個(gè)素?cái)?shù)），由此循環(huán)t-1次。如果都滿足b≠-1(modn)，則n一定是一個(gè)合數(shù)。
判定221是否為素?cái)?shù)
n=221=2^2*55+1,所以m=55，t=2,取a=174，則174^55(mod221)=47,174^110(mod221)=220,所以n要么是一個(gè)素?cái)?shù)，要么a=174是一個(gè)“強(qiáng)偽證”,再取a=137，則137^55(mod221)=188,137^110(mod221)=205。所以n是一個(gè)合數(shù)。
4.2模逆運(yùn)算
模逆運(yùn)算就是求滿足方程ax=1(modm)的解x，而ab=1(modm)有解的前提條件是(a,m)=1，即a和m互素。
對(duì)方程ax=1(modm)的求解可以轉(zhuǎn)換為求解ax+my=1=(a,m)，即轉(zhuǎn)換為擴(kuò)展歐幾里德算法。
求243^-1(mod325)
325=1325+0243
243=0325+1243
82=325-243=1325+(-1)243
79=243-282=(-2)325+3*243
3=82-79=3325+(-4)243
1=79-263=(-80)325+107*243
所以243^-1(mod325)=107
4.3模指運(yùn)算
模指運(yùn)算就是對(duì)a^n(modm)的計(jì)算。當(dāng)指數(shù)n的值較大時(shí)，如果先求出b^n再去模m的話，效率會(huì)很低下。所以，對(duì)于指數(shù)n較大的情況一般采用反復(fù)平方乘算法。
反復(fù)平方乘算法
所以，反復(fù)平方乘算法的原理是將指數(shù)n轉(zhuǎn)化為2的冪之和的形式，即n=2^kek+2^(k-1)ek-1+…+2e1+e0，然后根據(jù)l1=a^2(modm)，l2=a^4(modm)=l1^2(modm)，，
最后根據(jù)a^n(modm)=e0a·e1l1··eklk(modm)求解。
求23^35(mod101)
35=32+2+1
23^1(mod101)=23
23^2(mod101)=24
23^4(mod101)=24^2(mod101)=71
23^8(mod101)=71^2(mod101)=92
23^16(mod101)=92^2(mod101)=81
23^32(mod101)=81^2(mod101)=97
所以2335(mod101)=97×24×23(mod101)=14
5.實(shí)際編程中存在的缺陷5.1缺陷1：使用相同的N。
多人共用同一模數(shù)n，各自選擇不同的e和d，這樣實(shí)現(xiàn)當(dāng)然簡(jiǎn)單，但是不安全。消息以?xún)蓚€(gè)不同的密鑰加密，在共用同一個(gè)模下，若兩個(gè)密鑰互素(一般如此)，則可以恢復(fù)明文。
在實(shí)現(xiàn)過(guò)程中，部分程序員使用相同的N，更改e來(lái)達(dá)到生成新的公私鑰對(duì)的目的。比如，一開(kāi)始選擇e=3，由于過(guò)于簡(jiǎn)單更改其e=65537，但是N不變，可能導(dǎo)致該問(wèn)題。
實(shí)驗(yàn)?zāi)M：
?一、準(zhǔn)備
?攻擊者擁有公鑰n，e1私鑰d1
?被攻擊者擁有公鑰n，e2私鑰d2
?二、攻擊
?攻擊者通過(guò)e1d1≡1(modφ(n))枚舉φ(n)
?通過(guò)φ(n)以及e2生成私鑰d2（類(lèi)似私鑰生成過(guò)程）
設(shè)e1和e2是兩個(gè)互素的不同密鑰，共用模為n，對(duì)同一消息m加密得c1=m^e1modn,c2=m^e2modn。分析者知道n,e1,e2,c1和c2。因?yàn)?e1,e2,)=1，由擴(kuò)展Euclid算法可以求得整數(shù)r,s滿足re1+se2=1。從而可得c1^rc2^s=mmodn。
5.2缺陷2：e和d的值設(shè)置的過(guò)小。
采用小的e可以加快加密和驗(yàn)證簽字的速度，且所需的存儲(chǔ)密鑰空間小，但若加密鑰e選擇得太小，則容易受到攻擊。
實(shí)驗(yàn)場(chǎng)景：
假設(shè)在一個(gè)網(wǎng)域中，有四個(gè)以上的用戶。（假設(shè)4個(gè)）其中一個(gè)用戶用三個(gè)不用用戶的公鑰(e,n1),(e,n2)和(e,n3)加密同一段明文消息P，得到三個(gè)不同的密文C1，C2，C3。攻擊者可以由C1，C2，C3反推明文。
實(shí)驗(yàn)?zāi)M：
一、獲得C1，C2，C3
?分別使用不同的RSA公私鑰對(duì)同一段明文P進(jìn)行加密，公私鑰對(duì)中選擇e=3.并且將加密結(jié)果（C1，C2，C3）發(fā)送給攻擊者，攻擊者得到秘文后開(kāi)始反推明文。
二、還原明文
?C1=P3modn1
?C2=P3modn2
?C3=P3modn3
由中國(guó)剩余定理可求出P3從而可以求出明文P
中國(guó)剩余定理：令m=n1·n2·n3,
M1=n2·n3,M2=n1·n3,M3=n1·n2
Mi'·Mi≡1(modmi)i=1,2,3
P3=M1'·M1·C1+M2'·M2·C2+M3'·M3·C3從而求出P。
5.3缺陷3：選擇密文攻擊
實(shí)驗(yàn)?zāi)M：
?一、被攻擊者擁有公私鑰e,n,d，并且加密了一個(gè)消息m，加密后的消息c=m^e(modn)
?二、攻擊者選擇隨機(jī)數(shù)s，計(jì)算m'=c*s^e(modn)
?三、攻擊者將m'交給被攻擊者，要求被攻擊者解密
?四、攻擊者計(jì)算c’=m'^d(modn)
?代入得c’=medsed(modn)=ms(modn)
?五、攻擊者拿到c'后計(jì)算m=c's-1(modn)得到了原明文
所以，e不能太小，最常用的e值為3，17，65537(2^16+1),解密指數(shù)d需要滿足dn^1/4
6.基于java實(shí)現(xiàn)RSA的加解密過(guò)程
;;/***1.隨機(jī)選擇兩個(gè)質(zhì)數(shù)p和q（比如61和53），這兩個(gè)數(shù)不相等，且應(yīng)該是同一個(gè)量級(jí)。*（實(shí)際應(yīng)用中，這兩個(gè)質(zhì)數(shù)越大，就越難破解。）*2.計(jì)算n的值（n=3233），n的長(zhǎng)度即是密鑰的長(zhǎng)度。*3233寫(xiě)成二進(jìn)制是110010100001，一共有12位，所以這個(gè)密鑰就是12位.*實(shí)際應(yīng)用中，RSA密鑰一般是1024位，重要場(chǎng)合則為2048位。*3.計(jì)算n的歐拉函數(shù)φ(n)。*根據(jù)公式：φ(n)=(p-1)(q-1)，愛(ài)麗絲算出φ(3233)等于60×52，即3120。*4.隨機(jī)選擇一個(gè)整數(shù)e，條件是1eφ(n)，且e與φ(n)互質(zhì)。*愛(ài)麗絲就在1到3120之間，隨機(jī)選擇了17。（實(shí)際應(yīng)用中，常常選擇65537。）*5.計(jì)算e對(duì)于φ(n)的模反元素d。*計(jì)算ed≡1(modφ(n))帶入e=17，求解方程組：17x+3120y=1*6.將n和e封裝成公鑰，n和d封裝成私鑰。*/publicclassRSA{privatestaticBigIntegern;//largeprimeprivatestaticBigIntegere;//publickeyprivatestaticBigIntegerd;//privatekeyprivatestaticBigIntegerp;//primeprivatestaticBigIntegerq;//primeprivatestaticBigIntegero;//meansφ(n)publicstaticvoidmain(String[]args){Stringplaintext="rsaencryptdecrypttest";RSArsa=newRSA();();BigInteger[]encrypt=(plaintext);("\nplaintext:"+plaintext+"\n\nencrpyt:");for(inti=0;;++i){(encrypt[i]);}Stringdecrypt=(encrypt);("\ndecrypt:"+decrypt);}//RSAencryption,逐位進(jìn)行加密//RSA加密過(guò)程：加密后的消息p=m^e（modn)；publicBigInteger[]encrypt(Stringplaintext){BigInteger[]encrypt=newBigInteger[()];BigIntegerm,p;for(inti=0;();++i){m=((i));p=(e,n);encrypt[i]=p;}returnencrypt;}//RSAdecryption//RSA解密過(guò)程：還原消息m=p^d（modn)；publicStringdecrypt(BigInteger[]encrypt){StringBufferplaintext=newStringBuffer();BigIntegerm,p;for(inti=0;;++i){p=encrypt[i];m=(d,n);((char)());}();}//givepublickeyandprivatekeypublicvoidgiveKey(){//getp,q,n,e,bproducePQ();n=(q);o=(newBigInteger("1")).multiply((newBigInteger("1")));produceEB(o);("n:"+n+"\np:"+p+"\nq:"+q+"\ne:"+e+"\nd:"+d);}//largeprimepandqgenerationpublicvoidproducePQ(){p=(32,newRandom());q=(32,newRandom());while((q)){p=(32,newRandom());q=(32,newRandom());}}//producepublickeye,privatekeybpublicvoidproduceEB(BigIntegereulerN){e=((int)(()*63+2),newRandom());while((eulerN)!=-1|(e).equals(0)){e=((int)(()*63+2),newRandom());}//e=(65537);//defaultd=(eulerN);}}代碼執(zhí)行結(jié)果如下所示：
更多密碼學(xué)源碼請(qǐng)參考：