RSA算法分析與編程實(shí)現(xiàn)

實(shí)驗(yàn)二RSA算法實(shí)驗(yàn)?zāi)康模荷钊肓私釸SA加密算法的加密原理通過(guò)編程模擬RSA算法的加密過(guò)程實(shí)驗(yàn)內(nèi)容：RSA概述RSA加密算法是一種最常用的非對(duì)稱加密算法，CFCA在證書服務(wù)中離不了它。在公鑰加密標(biāo)準(zhǔn)和電子商業(yè)中，RSA被廣泛使用。公鑰和私鑰隨意選擇兩個(gè)大的質(zhì)數(shù)P和q,p不等于q,計(jì)算N=pq。根據(jù)歐拉函數(shù)，不大于N且與N互質(zhì)的整數(shù)個(gè)數(shù)為(p-1)(q-1)選擇一個(gè)整數(shù)。與(p-1)(q-1)互質(zhì)，并且e小于(p-1)(q-1)用以下這個(gè)公式計(jì)算d：dXe三1(mod(p-1)(q-1))將p和q的記錄銷毀。(N,e)是公鑰，(N,d)是私鑰。(N,d)是秘密的。Alice將她的公鑰(N,e)傳給Bob，而將她的私鑰(N,d)藏起來(lái)。RSA算法的編程實(shí)現(xiàn)#include<iostream>#include<cmath>usingnamespacestd;voidmain(){intp,q;//定義存放兩個(gè)質(zhì)數(shù)的變量cout〈〈"請(qǐng)輸入兩個(gè)較大的素?cái)?shù)："〈〈endl;cin>>p>>q;cout〈〈"p="〈〈p〈〈",q="〈〈q〈〈endl;intn,o;n=p*q;o=(p-1)*(q-1);cout〈〈"n="〈〈n〈〈",o="〈〈o〈〈endl;cout〈〈"請(qǐng)從【0,"〈〈oT〈〈"】中選擇一個(gè)與"〈〈o〈〈"互素的數(shù)e："〈〈endl;inte,i;floatd;cin〉〉e;//輸入e值for(i=1;;i++)//計(jì)算d值{d=(float)(o*i+1)/e;if(d-(int)d==0)break;}cout〈〈"e="〈〈e〈〈",d="〈〈d〈〈endl;cout〈〈"公開密鑰Pk二{e,n}二{"〈〈e〈〈"，"〈〈n〈〈"}"〈〈endl;//輸出公開密鑰cout〈〈〃秘密密鑰Sk={d,n}={〃〈〈d〈〈〃，〃〈〈n〈〈〃}〃〈〈endl;//輸出私密密鑰cout<<endl;cout〈〈"請(qǐng)輸入要加密的正整數(shù)(以-1結(jié)束)："〈〈endl;intm1[500],m3[500],m4[500];doublem2[500];intj;for(j=0;j〈500;j++)//對(duì)明文進(jìn)行加密{cin>>m1[j];if(m1[j]==-1)break;m2[j]=pow(m1[j],e);m4[j]=m2[j]/n;m3[j]=m2[j]-m4[j]*n;}cout〈〈"密文為："〈〈endl;intk;for(k=0;k〈j;k++)//輸出密文cout〈〈m3[k]〈〈"";cout〈〈endl;}實(shí)例描述在以下實(shí)例中只選取小數(shù)值的素?cái)?shù)p,q,以及e,假設(shè)用戶A需要將明文“key”通過(guò)RSA加密后傳遞給用戶B過(guò)程如下：設(shè)計(jì)公私密鑰(e,n)和(d,n)。令p=3,q=ll,得出n二pXq=3Xll=33；f(n)=(p-l)(q-l)=2X10=20；取e=3,(3與20互質(zhì))則eXd三1modf(n),即3Xd三1mod20。d怎樣取值呢？可以用試算的辦法來(lái)尋找。試算結(jié)果見下表：通過(guò)試算我們找到，當(dāng)d=7時(shí)，eXd三1modf(n)同余等式成立。因此，可令d=7。從而我們可以設(shè)計(jì)出一對(duì)公私密鑰，加密密鑰(公鑰)為:KU=(e,n)=(3,33),解密密鑰(私鑰)為：KR=(d,n)=(7,33)。英文數(shù)字化。將明文信息數(shù)字化，并將每塊兩個(gè)數(shù)字分組。假定明文英文字母編碼表為按字母順序排列數(shù)值，即：則得到分組后的key的明文信息為：11,05,25。明文加密用戶加密密鑰(3,33)將數(shù)字化明文分組信息加密成密文。由C三Me(modn)得：因此，得到相應(yīng)的密文信息為：11，26，16。密文解密。用戶B收到密文，若將其解密，只需要計(jì)算M=Cd(modn),即：用戶B得到明文信息為：11,05,25。根據(jù)上面的編碼表將其轉(zhuǎn)換為英文，我們又得到了恢復(fù)后的原文“key”。當(dāng)然，實(shí)際運(yùn)用要比這復(fù)雜得多，由于RSA算法的公鑰私鑰的長(zhǎng)度(模長(zhǎng)度)要到1024位甚至2048位才能保證安全，因此，p、q、e的選取、公鑰私鑰的生成，加密解密模指數(shù)運(yùn)算都有一定的計(jì)算程序，需要仰仗計(jì)算機(jī)高速完成。運(yùn)行結(jié)果RSA的安全性在RSA密碼應(yīng)用中，公鑰KU是被公開的，即e和n的數(shù)值可以被第三方竊聽者得到。破解RSA密碼的問(wèn)題就是從已知的e和n的數(shù)值(n等于pq)，想法求出d的數(shù)值，這樣就可以得到私鑰來(lái)破解密文。從上文中的公式： d三e-1(mod((p-l)(q-l)))或de三1(mod((p-l)(q-l)))我們可以看出。密碼破解的實(shí)質(zhì)問(wèn)題是：從pq的數(shù)值，去求出(p-1)和(qT)。換句話說(shuō)，只要求出p和q的值，我們就能求出d的值而得到私鑰。當(dāng)p和q是一個(gè)大素?cái)?shù)的時(shí)候，從它們的積pq去分解因子p和q,這是一個(gè)公認(rèn)的數(shù)學(xué)難題。比如當(dāng)pq大到1024位時(shí)，迄今為止還沒(méi)有人能夠利用任何計(jì)算工具去完成分解因子的任務(wù)。然而，雖然RSA的安全性依賴于大數(shù)的因子分解，但并沒(méi)有從理論上證明破譯RSA的難度與大數(shù)分解難度等價(jià)。即RSA的重大缺陷是無(wú)法從理論上把握它的保密性能如何。此外，RSA的缺點(diǎn)還有：A)產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。B)分組長(zhǎng)度太大，為保證安全性，n至少也要600bits以上，使運(yùn)算代價(jià)很高，尤其是速度較慢，較對(duì)稱密碼算法慢幾個(gè)數(shù)量級(jí)；且隨著大數(shù)分解技術(shù)的發(fā)展