RSA算法實(shí)驗(yàn)報(bào)告

1、word RSA算法的實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康?、理解公鑰密碼體制根本原理。2、理解并能夠編寫(xiě)RSA算法。3、熟練應(yīng)用C+編程實(shí)現(xiàn)算法。二、實(shí)驗(yàn)內(nèi)容利用C+編程實(shí)現(xiàn)RSA算法密碼體制，算法描述參考課本P191-204。3、 實(shí)驗(yàn)原理1、 算法原理步驟如下這里設(shè)B為是實(shí)現(xiàn)著（1） B尋找出兩個(gè)大素?cái)?shù)p和q。（2） B計(jì)算出n=p*q和n=p-1*q-1。（3） B選擇一個(gè)隨機(jī)數(shù)e0<e<(n),滿足e,(n)=1 (即e與歐拉函數(shù)互素n)。（4） B使用歐幾里得算法計(jì)算e的模余n的乘法逆元素d。（5） B在目錄中公開(kāi)n和e作為他的公開(kāi)密鑰，保密p、q和d。加密時(shí)，對(duì)每一明文m計(jì)算密文 cmm

2、odn解密時(shí)，對(duì)每一密文c計(jì)算明文 mcmodn2、 主要函數(shù)說(shuō)明1判斷一個(gè)數(shù)是否為素?cái)?shù)函數(shù)bool prime(int n) int m=sqrt(n);for(int i=2;i<m;i+)if(n%i=0)break;if(i>=m)return 1;else return 0;2模冪算法 (這里以明文m為一個(gè)為例)令f=1；用for循環(huán)遍歷從i=1到i=b，令f=(f*a)%n輸出f，f的值即為模冪的結(jié)果。int multiplication(int a,int b,int n) int f=1;for(int i=1;i<=b;i+)f=(f*a)%n;return

3、 f;3擴(kuò)展歐幾里得算法由擴(kuò)展歐幾里得算法可以計(jì)算整數(shù)s和t ，使得s*e+t*N=e,N=1,那么e的乘法逆元等價(jià)于s mod N。定義變量 x1,x2,x3,y1,y2,y3,t1,t2,t3,q;令 x1 = y2 = 1; x2 = y1 = 0; 計(jì)算q = x3/y3; t1 = x1 - q*y1; t2 = x2 - q*y2; t3 = x3 - q*y3; x1 = y1; x2 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3;當(dāng) y3 =1時(shí)，*result = y2; result 的結(jié)果即為所求乘法逆元；如果y3 ！=1，那么返回順序

4、執(zhí)行、步直到滿足 y3 =1int ExtendedEuclid( int f,int d ,int *result) int x1,x2,x3,y1,y2,y3,t1,t2,t3,q;x1 = y2 = 1;x2 = y1 = 0;if(f>=d)x3=f;y3=d;else x3=d;y3=f;while( 1 )if ( y3 = 1 )*result = y2; /* 兩個(gè)數(shù)互素那么resutl為其乘法逆元，此時(shí)返回值為1 */ return 1; q = x3/y3; t1 = x1 - q*y1;t2 = x2 - q*y2; t3 = x3 - q*y3; x1 = y1;

5、x2 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3; 4主函數(shù)輸入兩個(gè)數(shù)字判斷是否為素?cái)?shù)，當(dāng)不為素?cái)?shù)時(shí)重新輸入。如輸入 17 11輸入e，得到公鑰。如輸入e為7調(diào)用ExtendedEuclid(e,N,&d)函數(shù)，得到d，和私鑰。如d=23輸入明文長(zhǎng)度。如輸入 5 如輸入明文為 56 88 78 12 23開(kāi)始加密，調(diào)用加密函數(shù) Encryption()。 那么輸入密文為 78 11 56 177 133開(kāi)始解密，調(diào)用解密函數(shù) Decipher()。 那么解密后明文為 56 88 78 12 23四、算法流程圖 開(kāi)始輸入兩個(gè)素?cái)?shù)p和q N調(diào)用Prim

6、eY 找出N=(p-1)*(q-1)的所有公約數(shù)輸入不等于N公約數(shù)的e輸入明文長(zhǎng)度len及明文i=0調(diào)用ExtendEuclide，N，&dNi <len開(kāi)始加密調(diào)用EncryptionY調(diào)用multiplication(m1i,e,n)i+輸出密文i=0Ni <len開(kāi)始解密調(diào)用Decipher()Y調(diào)用multiplication(m1i,e,n)i+輸出明文，結(jié)束5、 實(shí)驗(yàn)心得和總結(jié) 我是這次試驗(yàn)主要負(fù)責(zé)人， 因?yàn)閷?shí)驗(yàn)要分組做，每個(gè)人都要負(fù)責(zé)一個(gè)工程，在我們組前兩次實(shí)驗(yàn)中，我主要負(fù)責(zé)編寫(xiě)代碼，像寫(xiě)報(bào)告、做PPT我?guī)缀鯖](méi)有參與。但這次不一樣了，所以的工作自己都要操起心來(lái)

7、，比同組的同學(xué)多做一些工作，多分擔(dān)一些，但是組員也很給力，實(shí)驗(yàn)的時(shí)候給了我很多建議與指導(dǎo)，制作PPT時(shí)給了我很多建議和幫助，有了團(tuán)隊(duì)精神所以效率提高了很多。所以這次試驗(yàn)下來(lái)感覺(jué)自己比以前做實(shí)驗(yàn)多學(xué)了好多東西，因?yàn)槭裁炊家獎(jiǎng)邮肿觯欢脰|西要查詢清楚。 我感覺(jué)做實(shí)驗(yàn)對(duì)學(xué)生真正掌握知識(shí)很重要。上課的時(shí)候只是聽(tīng)老師講RSA算法頂多就是學(xué)會(huì)理論知識(shí)，而真正實(shí)踐動(dòng)手做的時(shí)候就會(huì)發(fā)現(xiàn)自己漏洞百出，因?yàn)榭紤]問(wèn)題不周全，編寫(xiě)代碼的時(shí)候總是出錯(cuò)，編寫(xiě)的不完善，算法的功能沒(méi)有全部表達(dá)，最后又翻看了課本、大一的時(shí)候?qū)W的C+課本、大二學(xué)的密碼學(xué)根底課本和信息平安概論課本。穩(wěn)固了一些已經(jīng)忘記了的根底知識(shí)，有不太理解的算

8、法實(shí)現(xiàn)方法就通過(guò)上網(wǎng)查詢以及與同學(xué)討論來(lái)解決。這次寫(xiě)代碼是我參與編寫(xiě)過(guò)的比擬長(zhǎng)的代碼，RSA算法的算法原理我理解的比擬清楚，所以對(duì)算法如何實(shí)現(xiàn)有一定的認(rèn)識(shí)，編寫(xiě)起來(lái)也比擬輕松一點(diǎn)。RSA算法用到了數(shù)論的知識(shí)，這次實(shí)驗(yàn)對(duì)我來(lái)說(shuō)最難理解的就是擴(kuò)展歐幾里得算法，雖然在大二時(shí)學(xué)過(guò)了理論但實(shí)際編寫(xiě)還是有點(diǎn)難度的，通過(guò)查閱書(shū)籍及網(wǎng)上搜尋資料最終寫(xiě)出來(lái)擴(kuò)展歐幾里得算法實(shí)現(xiàn)函數(shù)。實(shí)在不容易啊。經(jīng)過(guò)這次試驗(yàn)，我認(rèn)識(shí)到了我編寫(xiě)代碼的能力確實(shí)需要提升，需要平時(shí)更多的努力，相信以后在與組員以及其他同學(xué)的合作下，我能夠?qū)W到更多知識(shí)。6、 參考資料1 William Stallings 密碼編碼學(xué)與網(wǎng)絡(luò)平安 電子工業(yè)出版

9、社 2012年2 李繼國(guó) 信息平安密碼學(xué)根底 武漢大學(xué)出版社 2006年3 李紅嬌 信息平安概論 中國(guó)電力出版社 2012年7、 實(shí)驗(yàn)結(jié)果截圖八、實(shí)驗(yàn)源代碼#include<iostream.h>#include<math.h>int p,q,n,e,d,N,m1100,m2100,len; /判斷一個(gè)數(shù)是否為素?cái)?shù)，為素?cái)?shù)返回1，否那么返回0bool prime(int n) int m=sqrt(n);for(int i=2;i<m;i+)if(n%i=0)break;if(i>=m)return 1;else return 0;/擴(kuò)展歐幾里得算法求乘法逆

10、元,兩數(shù)互素返回1int ExtendedEuclid( int f,int d ,int *result) int x1,x2,x3,y1,y2,y3,t1,t2,t3,q;x1 = y2 = 1;x2 = y1 = 0;if(f>=d)x3=f;y3=d;else x3=d;y3=f;while( 1 )if ( y3 = 1 )*result = y2; /* 兩個(gè)數(shù)互素那么resutl為其乘法逆元，此時(shí)返回值為1 */ return 1; q = x3/y3; t1 = x1 - q*y1;t2 = x2 - q*y2; t3 = x3 - q*y3; x1 = y1;x2 =

11、y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3; /將十進(jìn)制數(shù)據(jù)轉(zhuǎn)化為二進(jìn)制數(shù)組void to_bit(int b,int bit32) int n=0;while(b>0)bitn=b%2;n+;b/=2;/模冪算法int multiplication(int a,int b,int n) int f=1;for(int i=1;i<=b;i+)f=(f*a)%n;return f;/加密函數(shù)void Encryption()cout<<"*開(kāi)始加密*"<<endl;int i;cout<<&q

12、uot;請(qǐng)輸入明文："for(i=0;i<len;i+)cin>>m1i;for(i=0;i<len;i+)m2i=multiplication(m1i,e,n);cout<<"加密后的密文為："for(i=0;i<len;i+)cout<<m2i<<" "cout<<endl;/解密函數(shù)void Decipher()int i;cout<<"*開(kāi)始解密*"<<endl;for(i=0;i<len;i+)m2i=mul

13、tiplication(m2i,d,n);cout<<"解密后的明文為："for(i=0;i<len;i+)cout<<m2i<<" "cout<<endl;void main()cout<<"輸入兩個(gè)素?cái)?shù)p和q:n" while(1)cin>>p; if(prime(p)cout<<p<<"是素?cái)?shù)"<<endl;break;elsecout<<p<<"不是素?cái)?shù)&quo

14、t;<<endl;continue;while(1)cin>>q; if(prime(q)cout<<q<<"是素?cái)?shù)"<<endl;break;elsecout<<q<<"不是素?cái)?shù)"<<endl;continue;cout<<"兩個(gè)素?cái)?shù)為："<<p<<","<<q<<endl;n=p*q;N=(p-1)*(q-1); for(int i=2;i<N;i+) if(N%i=0) cout<<i<<" " cout<<endl;cout<<"請(qǐng)輸入一個(gè)隨機(jī)數(shù)，該數(shù)不等于上面的任何一個(gè)數(shù)！"<<endl; cin>>e; cout<<"公鑰為<"<<e<<","<<n<<">"<<endl; if(ExtendedEuclid(e,N,&d)cout<&l