RSA算法實驗報告

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

2、odn解密時，對每一密文c計算明文 mcmodn2、 主要函數(shù)說明1判斷一個數(shù)是否為素數(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為一個為例)令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ò)展歐幾里得算法可以計算整數(shù)s和t ，使得s*e+t*N=e,N=1,那么e的乘法逆元等價于s mod N。定義變量 x1,x2,x3,y1,y2,y3,t1,t2,t3,q;令 x1 = y2 = 1; x2 = y1 = 0; 計算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時，*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; /* 兩個數(shù)互素那么resutl為其乘法逆元，此時返回值為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ù)輸入兩個數(shù)字判斷是否為素數(shù)，當(dāng)不為素數(shù)時重新輸入。如輸入 17 11輸入e，得到公鑰。如輸入e為7調(diào)用ExtendedEuclid(e,N,&d)函數(shù)，得到d，和私鑰。如d=23輸入明文長度。如輸入 5 如輸入明文為 56 88 78 12 23開始加密，調(diào)用加密函數(shù) Encryption()。 那么輸入密文為 78 11 56 177 133開始解密，調(diào)用解密函數(shù) Decipher()。 那么解密后明文為 56 88 78 12 23四、算法流程圖 開始輸入兩個素數(shù)p和q N調(diào)用Prim

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

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

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

9、社 2012年2 李繼國 信息平安密碼學(xué)根底 武漢大學(xué)出版社 2006年3 李紅嬌 信息平安概論 中國電力出版社 2012年7、 實驗結(jié)果截圖八、實驗源代碼#include<iostream.h>#include<math.h>int p,q,n,e,d,N,m1100,m2100,len; /判斷一個數(shù)是否為素數(shù)，為素數(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; /* 兩個數(shù)互素那么resutl為其乘法逆元，此時返回值為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<<"*開始加密*"<<endl;int i;cout<<&q

12、uot;請輸入明文："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<<"*開始解密*"<<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<<"輸入兩個素數(shù)p和q:n" while(1)cin>>p; if(prime(p)cout<<p<<"是素數(shù)"<<endl;break;elsecout<<p<<"不是素數(shù)&quo

14、t;<<endl;continue;while(1)cin>>q; if(prime(q)cout<<q<<"是素數(shù)"<<endl;break;elsecout<<q<<"不是素數(shù)"<<endl;continue;cout<<"兩個素數(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<<"請輸入一個隨機(jī)數(shù)，該數(shù)不等于上面的任何一個數(shù)！"<<endl; cin>>e; cout<<"公鑰為<"<<e<<","<<n<<">"<<endl; if(ExtendedEuclid(e,N,&d)cout<&l