1、 安全學(xué)實驗報告RSA加密解密的簡單實現(xiàn) 華南師范大學(xué) 趙教授RSA介紹：當(dāng)前最著名、應(yīng)用最廣泛的公鑰系統(tǒng)RSA是在1978年，由美國麻省理工學(xué)院(MIT)的Rivest、Shamir和Adleman在題為獲得數(shù)字簽名和公開鑰密碼系統(tǒng)的方法的論文中提出的。RSA算法是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法，因此它為公用網(wǎng)絡(luò)上信息的加密和鑒別提供了一種基本的方法。它通常是先生成一對RSA 密鑰，其中之一是保密密鑰，由用戶保存；另一個為公開密鑰，可對外公開，甚至可在網(wǎng)絡(luò)服務(wù)器中注冊，人們用公鑰加密文件發(fā)送給個人，個人就可以用私鑰解密接受。為提高保密強(qiáng)度，RSA密鑰至少為500位長，一般推薦使

2、用1024位。公鑰加密算法中使用最廣的是RSA。RSA算法研制的最初理念與目標(biāo)是努力使互聯(lián)網(wǎng)安全可靠，旨在解決DES算法秘密密鑰的利用公開信道傳輸分發(fā)的難題。而實際結(jié)果不但很好地解決了這個難題；還可利用RSA來完成對電文的數(shù)字簽名以抗對電文的否認(rèn)與抵賴；同時還可以利用數(shù)字簽名較容易地發(fā)現(xiàn)攻擊者對電文的非法篡改，以保護(hù)數(shù)據(jù)信息的完整性。此外，RSA加密系統(tǒng)還可應(yīng)用于智能IC卡和網(wǎng)絡(luò)安全產(chǎn)品。 一系統(tǒng)總體方案：1.要求：編寫RSA加密解密演示程序，用戶自己輸入兩個素數(shù)P，Q以及公鑰E，程序判斷P，Q為素數(shù)后計算得到公鑰（e，n），私鑰（d，n）并顯示。 輸入明文密文并可以進(jìn)行加密解密。2.數(shù)學(xué)原理

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

4、(n) 3.輸出公鑰為（e，n）私鑰為（d，n） 4.輸入明文（數(shù)字）M計算密文C=M e(mod n) 5.輸入密文C計算明文M=C d(mod n)二.設(shè)計思路： 1.關(guān)鍵問題： （1）素數(shù)的判斷：首先在輸入p，q之后應(yīng)該有一個函數(shù)int sushu（）可以判斷p，q是否為素數(shù)，并返回 1（是）或0（否）?？紤]到程序中數(shù)據(jù)類型為long型，依次用2n之間的數(shù)去除n，如果能整除則不為素數(shù)。該算法時間復(fù)雜度為O（n）。int sushu(long m)int i; for(i=2;i*i=d )?f:d;y3 = ( f=d )?d:f;while( 1 ) if ( y3 = 0 ) *re

5、sult = 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 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3;（4）快速冪模算法：在加密解密時都要用到類似A B（mod C）的計算，當(dāng)指數(shù)B較大時，如果先計算A B的值時間較慢，且結(jié)果過大會溢出。依據(jù)模運算的性質(zhì)（a*b）mod n=（a mod n）*（b mod n）mod n 可以將A B分解為較小幾個數(shù)的乘積

6、分別進(jìn)行模運算例如（3 999）可以分解為(3 512) * (3 256) * (3 128) * (3 64) * (3 32) * (3 4) * (3 2) * 3 這樣只要做16次乘法。把999轉(zhuǎn)為2進(jìn)制數(shù)：1111100111，其各位就是要乘的數(shù)。所以程序中要有函數(shù)int a_b_Mod_c（long a, long b, long c）計算a b mod c的值并返回結(jié)果。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

7、= 1; for(k = i-1; k = 0; k-) resualt=(resualt*resualt)%c; if(digitk=1) resualt=(resualt*a)%c; return resualt;2.總操作界面:1. 輸入兩個素數(shù)P,Q 2. 輸入公鑰E 3. 查看當(dāng)前密鑰信息 4. 加密 5. 解密 6. 幫助 0. 退出三程序?qū)崿F(xiàn)流程圖：（1）流程圖： 輸入兩個素數(shù)p，q計算n=p*q （n）=（p-1）*（q-1）輸入一個大于2小于（n）的數(shù)e計算d= e -1(mod(n)得到公鑰（e，n）私鑰（d，n）加密或者解密根據(jù)輸入的明文M計算密文C= M e(mod n

8、)根據(jù)輸入的密文C計算明文M= C d(mod n)（2）各功能模塊：命令對應(yīng)函數(shù)功能描述1input_P_Q輸入素數(shù)P,Q2input_E輸入公鑰E3print_miyao顯示密鑰信息4jiami加密5jiemi解密6print_help幫助四.程序測試：1輸入兩個素數(shù)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 并解密五.總結(jié)、改進(jìn)思考：1.大數(shù)類庫的建立：本程序作為RSA加密解密過

9、程演示程序，變量均為long型，因此密鑰長度較小，而RSA的安全性建立在密鑰長度很長，大素數(shù)難以分解的前提上。所以為了能夠提高安全性，應(yīng)該建立一個大數(shù)類庫，對512位或1024位大數(shù)進(jìn)行存取，及簡單運算。一個最容易理解的方法就是將大數(shù)用十進(jìn)制表示，并將每一位（0 9）都做為一個單獨的數(shù)用數(shù)組進(jìn)行管理。做加減乘除等運算時，人工的對其進(jìn)行進(jìn)、借位。然而計算機(jī)對于10進(jìn)制數(shù)的處理并不在行，而且表示非2n進(jìn)制的數(shù)會浪費很多空間，所以應(yīng)該采用8進(jìn)制、16進(jìn)制、32進(jìn)制、64進(jìn)制的表示法，使得每一位數(shù)字都能占據(jù)一個完整的內(nèi)存空間。目前絕大多數(shù)PC機(jī)都是基于32位運算的，所以采用2 32進(jìn)制表示大數(shù)將會很大

10、提高計算機(jī)的處理效率?，F(xiàn)實中，就使用32位的整數(shù)數(shù)組進(jìn)行存儲每一位數(shù)，另設(shè)一個布爾值表示正負(fù)。進(jìn)行計算時常會遇到進(jìn)位借位的情況，而且常常會超過2 32次方，幸好目前的編譯器都支持64位整數(shù)，可以滿足( 232 - 1 ) * ( 232 - 1 )以內(nèi)的運算，所以使用64位整數(shù)作為運算中間量將會是很好的選擇。 大數(shù)除了加減乘除等基本運算以外，還有一些如賦值、比較、左右移位、或、與等，為了方便使用，我們可以利用面向?qū)ο蟮姆椒ò汛髷?shù)進(jìn)行封裝，并利用C+的特性進(jìn)行運算符重載，使它成為一個整體對象來進(jìn)行操作。這樣我們就可像使用int一樣來使用它了。2.大素數(shù)隨機(jī)生成，以及判斷： 真正的RSA加密時密鑰

11、的生成應(yīng)該是自動完成的，而不是用戶手動制定p，q，e。所以在使用大數(shù)類庫后隨之而來一個問題就是如何隨機(jī)的生成兩個大素數(shù)，以及大素數(shù)的判斷。由于素數(shù)有無窮多個，且沒有固定的生成方式，所以大素數(shù)的生成基本是采用在一定范圍內(nèi)（比如奇數(shù)，且不會被小素數(shù)整除的）隨機(jī)選取大數(shù)后再進(jìn)行素數(shù)檢測，直到有通過檢測的數(shù)。 因此大數(shù)的素數(shù)檢測算法就是關(guān)鍵了，如果按照之前的素數(shù)檢測算法需要依次除2到n的數(shù)，時間復(fù)雜度O（n）太大。所以我們要用更為快速的算法。米勒拉賓測試是一個不確定的算法，只能從概率意義上判定一個數(shù)可能是素數(shù)。是目前公認(rèn)的最高效的素性測試之一。大體步驟如下：輸入奇數(shù)n，判斷n為素數(shù)或者合數(shù)。計算r和R

12、,使得，R奇。隨即選擇a,。for i=0 to r，計算。若，則輸入合數(shù)。若，則輸入素數(shù)。設(shè)j=maxi:,則輸入素數(shù)。若，則輸出素數(shù)，否則輸出合數(shù)。參考書目：1 劉嘉勇等 應(yīng)用密碼學(xué)2 胡道元 閔京華網(wǎng)絡(luò)安全3張四蘭等 可信賴的高效素數(shù)生成和檢驗算法附 程序代碼：#include#include #includevoid 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

13、 e,long n);void jiemi(long 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. 輸入兩個素數(shù)P,Qn;cout 2. 輸入公鑰En;cout 3. 查看當(dāng)前密鑰信息n;cout 4

14、. 加密n;cout 5. 解密n;cout 6. 幫助n;cout 0. 退出n;coutch; switch(ch) case 1 : input_P_Q(P,Q,N,N1);break; case 2 : input_E(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

15、= 0)return a;return gcd(b, a % b);int sushu(long m) int i; for(i=2;i*i=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 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3;int a

16、_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 &Q,long &N,long &N1) coutP) break; else coutP應(yīng)為數(shù)字，請重新輸入：endl; c

17、in.clear(); cin.ignore(); while(1) if (sushu(P) break; else coutP應(yīng)為素數(shù)，請重新輸入：P;coutQ) break; else coutQ應(yīng)為數(shù)字，請重新輸入：endl; cin.clear(); cin.ignore(); while(1) if (sushu(Q) break; else coutQ應(yīng)為素數(shù)，請重新輸入：Q;N=P*Q;N1=(P-1)*(Q-1);void input_E(long &E,long &D,long n1)if(n1=0)cout請先輸入兩個素數(shù)P，Qendl;return;long z=0;

18、cout輸入一個小于n1E) break; else coutE應(yīng)為數(shù)字，請重新輸入：endl; cin.clear(); cin.ignore(); while(1) if (gcd(E,n1)=1) break; else coutE應(yīng)與n1互質(zhì)，請重新輸入：E;if(ExtendedEuclid(E,n1,&z) D=z; else cout錯誤endl;void print_miyao(long e,long n,long d)cout公鑰為：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;coutm) break; else cout明文應(yīng)為數(shù)字，請重新輸入：endl; cin.clear(); cin.ignore(); while(1) if (mn) break; else cout明文應(yīng)小于n，請重新輸入：endl; cin.clear(); cin.ignore(); c=a_b_Mod_c(m,e,n);cout密文為：