1、精選優質文檔-傾情為你奉上 安全學實驗報告RSA加密解密的簡單實現 華南師范大學 趙教授RSA介紹：當前最著名、應用最廣泛的公鑰系統RSA是在1978年，由美國麻省理工學院(MIT)的Rivest、Shamir和Adleman在題為獲得數字簽名和公開鑰密碼系統的方法的論文中提出的。RSA算法是第一個既能用于數據加密也能用于數字簽名的算法，因此它為公用網絡上信息的加密和鑒別提供了一種基本的方法。它通常是先生成一對RSA 密鑰，其中之一是保密密鑰，由用戶保存；另一個為公開密鑰，可對外公開，甚至可在網絡服務器中注冊，人們用公鑰加密文件發送給個人，個人就可以用私鑰解密接受。為提高保密強度，RSA密鑰至

2、少為500位長，一般推薦使用1024位。  公鑰加密算法中使用最廣的是RSA。RSA算法研制的最初理念與目標是努力使互聯網安全可靠，旨在解決DES算法秘密密鑰的利用公開信道傳輸分發的難題。而實際結果不但很好地解決了這個難題；還可利用RSA來完成對電文的數字簽名以抗對電文的否認與抵賴；同時還可以利用數字簽名較容易地發現攻擊者對電文的非法篡改，以保護數據信息的完整性。此外，RSA加密系統還可應用于智能IC卡和網絡安全產品。 一系統總體方案：1.要求：編寫RSA加密解密演示程序，用戶自己輸入兩個素數P，Q以及公鑰E，程序判斷P，Q為素數后計算得到公鑰（e，n），私鑰（d，n）并顯

3、示。 輸入明文密文并可以進行加密解密。2.數學原理： 1.密鑰的生成 選擇p,q為兩個大的互異素數 計算n=p*q, (n)=(p-1)(q-1)選擇整數e使gcd(n),e)=1（互質）,（1<e<(n)）計算d,使d=e -1(mod(n)（求乘法逆元）公鑰Pk=e,n;私鑰Sk=d,n。 (定義若ax mod n =1,則稱a與x對于模n互為逆元) 2.加密 (用e,n) 明文 M<n 由C=M e(mod n)得到密文C。 3.解密 (用d,n) 對于密文C 由M=C d(mod n)得到明文M。 3.實現過程： 1.輸入p，q判斷為素數，計算n=p*q，（n）=（p

4、-1）（q-1） 2輸入e判斷是否與（n）互質，計算d= e -1(mod(n) 3.輸出公鑰為（e，n）私鑰為（d，n） 4.輸入明文（數字）M計算密文C=M e(mod n) 5.輸入密文C計算明文M=C d(mod n)二.設計思路： 1.關鍵問題： （1）素數的判斷：首先在輸入p，q之后應該有一個函數int sushu（）可以判斷p，q是否為素數，并返回 1（是）或0（否）。考慮到程序中數據類型為long型，依次用2n之間的數去除n，如果能整除則不為素數。該算法時間復雜度為O（n）。int sushu(long m)int i; for(i=2;i*i<=m;i+) if(m%i

5、=0)return 0; return 1; （2）互質的判斷：在輸入e之后需要判斷e與（n）是否互質，所以用該有判斷互質的函數int gcd（）返回1（是），其他（否）。根據歐幾里德算法gcd(a,b)=gcd(b,a mod b) 證明：a可以表示成a = kb + r，則r = a mod b 假設d是a,b的一個公約數，則有 d|a, d|b，而r = a - kb，因此d|r 因此d是(b,a mod b)的公約數 假設d 是(b,a mod b)的公約數，則 d | b , d |r ，但是a = kb + r 因此d也是(a,b)的公約數 因此(a,b)和(b,a mod b)的

6、公約數是一樣的，其最大公約數也必然相等所以若gcd（a，b）=1 則a與b互質。int gcd(long a, long b)if(b = 0)return a;return gcd(b, a % b); （3）求乘法逆元：因為需要計算私鑰d= e -1(mod(n)，所以有函數long ExtendedEuclid（）計算d并返回d的值，這里用到擴展歐幾里德算法。大體思路與歐幾里德算法一致：如果gcd(a，b)=d，則存在m，n，使得d = ma + nb，稱呼這種關系為a、b組合整數d，m，n稱為組合系數。當d=1時，有 ma + nb = 1 ，此時可以看出m是a模b的乘法逆元，n是b模

7、a的乘法逆元。long ExtendedEuclid(long f,long d ,long *result) int x1,x2,x3,y1,y2,y3,t1,t2,t3,q;x1 = y2 = 1;x2 = y1 = 0;x3 = ( f>=d )?f:d;y3 = ( f>=d )?d:f;while( 1 ) if ( y3 = 0 ) *result = x3; return 0; if ( y3 = 1 ) *result = y2; return 1; q = x3/y3; t1 = x1 - q*y1; t2 = x2 - q*y2; t3 = x3 - q*y3;

8、 x1 = y1; x2 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3;（4）快速冪模算法：在加密解密時都要用到類似A B（mod C）的計算，當指數B較大時，如果先計算A B的值時間較慢，且結果過大會溢出。依據模運算的性質（a*b）mod n=（a mod n）*（b mod n）mod n 可以將A B分解為較小幾個數的乘積分別進行模運算例如（3 999）可以分解為(3 512) * (3 256) * (3 128) * (3 64) * (3 32) * (3 4) * (3 2) * 3  這樣只要做16次乘法。把999轉為2進制數：11

9、11100111，其各位就是要乘的數。所以程序中要有函數int a_b_Mod_c（long a, long b, long c）計算a b mod c的值并返回結果。int a_b_Mod_c(long a, long b, long c) int digit32;long i,k,resualt = 1; i = 0; while(b) digiti+ = b%2; b >>= 1; for(k = i-1; k >= 0; k-) resualt=(resualt*resualt)%c; if(digitk=1) resualt=(resualt*a)%c; retur

10、n resualt;2.總操作界面:1. 輸入兩個素數P,Q 2. 輸入公鑰E 3. 查看當前密鑰信息 4. 加密 5. 解密 6. 幫助 0. 退出三程序實現流程圖：（1）流程圖： 輸入兩個素數p，q計算n=p*q （n）=（p-1）*（q-1）輸入一個大于2小于（n）的數e計算d= e -1(mod(n)得到公鑰（e，n）私鑰（d，n）加密或者解密根據輸入的明文M計算密文C= M e(mod n)根據輸入的密文C計算明文M= C d(mod n)（2）各功能模塊：命令對應函數功能描述1input_P_Q輸入素數P,Q2input_E輸入公鑰E3print_miyao顯示密鑰信息4jiami

11、加密5jiemi解密6print_help幫助四.程序測試：1輸入兩個素數p=47，q=71 則n=47*71=33372.輸入e=79，計算得d=e-1 mod （p-1）（q-1）=79-1 mod 3220=1019 因此公鑰為（79，3337）私鑰為（1019，3337）3.輸入明文 688 并加密4.輸入密文1570 并解密五.總結、改進思考：1.大數類庫的建立：本程序作為RSA加密解密過程演示程序，變量均為long型，因此密鑰長度較小，而RSA的安全性建立在密鑰長度很長，大素數難以分解的前提上。所以為了能夠提高安全性，應該建立一個大數類庫，對512位或1024位大數進行存取，及簡單

12、運算。一個最容易理解的方法就是將大數用十進制表示，并將每一位（0 9）都做為一個單獨的數用數組進行管理。做加減乘除等運算時，人工的對其進行進、借位。然而計算機對于10進制數的處理并不在行，而且表示非2n進制的數會浪費很多空間，所以應該采用8進制、16進制、32進制、64進制的表示法，使得每一位數字都能占據一個完整的內存空間。目前絕大多數PC機都是基于32位運算的，所以采用2 32進制表示大數將會很大提高計算機的處理效率。現實中，就使用32位的整數數組進行存儲每一位數，另設一個布爾值表示正負。進行計算時常會遇到進位借位的情況，而且常常會超過2 32次方，幸好目前的編譯器都支持64位整數，可以滿足

13、( 232 - 1 ) * ( 232 - 1 )以內的運算，所以使用64位整數作為運算中間量將會是很好的選擇。 大數除了加減乘除等基本運算以外，還有一些如賦值、比較、左右移位、或、與等，為了方便使用，我們可以利用面向對象的方法把大數進行封裝，并利用C+的特性進行運算符重載，使它成為一個整體對象來進行操作。這樣我們就可像使用int一樣來使用它了。2.大素數隨機生成，以及判斷： 真正的RSA加密時密鑰的生成應該是自動完成的，而不是用戶手動制定p，q，e。所以在使用大數類庫后隨之而來一個問題就是如何隨機的生成兩個大素數，以及大素數的判斷。由于素數有無窮多個，且沒有固定的生成方式，所以大素數的生成基

14、本是采用在一定范圍內（比如奇數，且不會被小素數整除的）隨機選取大數后再進行素數檢測，直到有通過檢測的數。 因此大數的素數檢測算法就是關鍵了，如果按照之前的素數檢測算法需要依次除2到n的數，時間復雜度O（n）太大。所以我們要用更為快速的算法。米勒拉賓測試是一個不確定的算法，只能從概率意義上判定一個數可能是素數。是目前公認的最高效的素性測試之一。大體步驟如下：輸入奇數n，判斷n為素數或者合數。計算r和R,使得，R奇。隨即選擇a,。for i=0 to r，計算。若，則輸入合數。若，則輸入素數。設j=maxi:,則輸入素數。若，則輸出素數，否則輸出合數。參考書目：1 劉嘉勇等 應用密碼學2 胡道元

15、閔京華網絡安全3張四蘭等 可信賴的高效素數生成和檢驗算法附 程序代碼：#include<iostream.h>#include <stdlib.h>#include<stdio.h>void input_P_Q(long &P,long &Q,long &N,long &N1);void input_E(long &E,long &D,long n1);void print_miyao(long e,long n,long d);void jiami(long e,long n);void jiemi(long

16、 d,long n);void print_help();int sushu(long m);int gcd(long a, long b);long ExtendedEuclid(long f,long d ,long *result);int a_b_Mod_c(long a, long b, long c);void main()long P=0,Q=0,E=0,N=0,N1=0,D=0;cout<<"=RSA模擬="<<endl; cout<<" 1. 輸入兩個素數P,Qn"cout<<"

17、 2. 輸入公鑰En"cout<<" 3. 查看當前密鑰信息n"cout<<" 4. 加密n"cout<<" 5. 解密n"cout<<" 6. 幫助n"cout<<" 0. 退出n"cout<<"n 輸入你的選擇:"long ch;do cin>>ch; switch(ch) case 1 : input_P_Q(P,Q,N,N1);break; case 2 : input_E(

18、E,D,N1);break; case 3 : print_miyao(E,N,D);break; case 4 : jiami(E,N);break; case 5 : jiemi(D,N);break; case 6 : print_help();break; case 0 : break;while(ch);int gcd(long a, long b)if(b = 0)return a;return gcd(b, a % b);int sushu(long m) int i; for(i=2;i*i<=m;i+) if(m%i=0) return 0; return 1;long

19、 ExtendedEuclid(long f,long d ,long *result)int x1,x2,x3,y1,y2,y3,t1,t2,t3,q;x1 = y2 = 1;x2 = y1 = 0;x3 = ( f>=d )?f:d;y3 = ( f>=d )?d:f;while( 1 ) if ( y3 = 0 ) *result = x3; return 0; if ( y3 = 1 ) *result = y2; return 1; q = x3/y3; t1 = x1 - q*y1; t2 = x2 - q*y2; t3 = x3 - q*y3; x1 = y1; x2

20、 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3;int a_b_Mod_c(long a, long b, long c) int digit32;long i,k,resualt = 1; i = 0; while(b) digiti+ = b%2; b >>= 1; for(k = i-1; k >= 0; k-) resualt=(resualt*resualt)%c; if(digitk=1) resualt=(resualt*a)%c; return resualt;void input_P_Q(long &P,long

21、&Q,long &N,long &N1) cout<<"輸入第一個素數p:n"while(1) if (cin>>P) break; else cout<<"P應為數字，請重新輸入："<<endl; cin.clear(); cin.ignore(); while(1) if (sushu(P) break; else cout<<"P應為素數，請重新輸入："<<endl; cin.clear(); cin.ignore(); cin>

22、;>P;cout<<"輸入第二個素數Q:n"while(1) if (cin>>Q) break; else cout<<"Q應為數字，請重新輸入："<<endl; cin.clear(); cin.ignore(); while(1) if (sushu(Q) break; else cout<<"Q應為素數，請重新輸入："<<endl; cin.clear(); cin.ignore(); cin>>Q;N=P*Q;N1=(P-1)*(Q-1

23、);void input_E(long &E,long &D,long n1)if(n1=0)cout<<"請先輸入兩個素數P，Q"<<endl;return;long z=0;cout<<"輸入一個小于"<<n1<<"的數e:n"while(1) if (cin>>E) break; else cout<<"E應為數字，請重新輸入："<<endl; cin.clear(); cin.ignore();

24、while(1) if (gcd(E,n1)=1) break; else cout<<"E應與"<<n1<<"互質"<<"，請重新輸入："<<endl; cin.clear(); cin.ignore(); cin>>E;if(ExtendedEuclid(E,n1,&z) D=z; else cout<<"錯誤"<<endl;void print_miyao(long e,long n,long d)cout

25、<<"公鑰為：n" cout<<"("<<e<<","<<n<<")"<<endl;cout<<"公鑰為：n" cout<<"("<<d<<","<<n<<")"<<endl;void jiami(long e,long n)if(e=0,n=0)cout<<"請先輸入密鑰"<<endl;return;long c,m;cout<<"輸入要加密的明文:n"while(1) if (cin>>m) break; else cout<<