RSA加密的簡易實現(xiàn)

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

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

3、進行加密解密。2 . 數(shù)學原理 ：1 .密鑰的生成 選才I p,q為兩個大的互異素數(shù)計算n=p*q, 3（n）=（p-1）（q-1）選擇整數(shù)e使gcd（少（n）,e）=1（互質），（1<e<3）計算d,使d=e ?-1（mod少（n）（求乘法逆元）公鑰 Pk=e,n;私鑰 Sk=d,n。(定義若a?x 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)得到明文 M3.實現(xiàn)過程：1. 輸入p, q判斷為素數(shù)，計算 n=p*q ,少(n) = (p

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

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

6、的公約數(shù)因此(a,b)和(b,a mod b)的公約數(shù)是一樣的，其最大公約數(shù)也必然相等所以若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),所以有函數(shù)long ExtendedEuclid ()計算d并返回d的值，這里用到擴展歐幾里德算法。大體思路與歐幾里德算法一致：如果gcd(a , b)=d ,則存在m, n,使得d = ma+ nb,稱呼這種關系為 a、b組合整數(shù)d, m, n稱為組合系數(shù)。當 d=1時，有

7、ma + nb = 1,此時可以看出 m是a模b的乘法逆元，n是b模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

8、; t2 = x2 - q*y2; t3 = x3 - q*y3;x1 = y1; x2 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3;在加密解密時都要用到類似 A ?B (mod C)的計算，當指數(shù) B較大時，如果先計算 A ?B的值時間較慢，且結果過大會溢出。依據(jù)模運算的性質a a*b ) mod n= (a mod n) * (b mod n) mod n 可以將A ?的解 為較小幾個數(shù)的乘積分別進行模運算例如(3 A 999 )可以分解為(3 A 512) * (3 A 256) * (3 A 128) * (3 A 64) * (3 A32) *

9、(3 a 4) * (3 a 2) * 3這樣只要做16次乘法。把999轉為2進制數(shù)：1111100111,其各位就是要乘的數(shù)。所以程序中要有函數(shù) 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*re

10、sualt)%c;if(digitk=1) resualt=(resualt*a)%c; return resualt;2. 總操作界面:1. 輸入兩個素數(shù)P,Q2. 輸入公鑰 E3. 查看當前密鑰信息4. 加密5. 解密6. 幫助0. 退出三.程序實現(xiàn)流程圖:(1)流程圖:(2)各功能模塊:命令對應函數(shù)功能描述1input_P_Q輸入素數(shù)P,Q2input_E輸入公鑰E3print_miyao顯示密鑰信息4jiami加密5jiemi解密幫助print_help四.程序測試:1 輸入兩個素數(shù) p=47, q=71 則 n=47*71=3337；應為數(shù)字，請重新輸入, 急為素數(shù).請重新輸入: 輕

11、入第二個素數(shù)3 71 力鑰為r <0,333?> 私鑰為:<0.3337>2.輸入 e=79,計算得 d=e?-1 mod (p-1) (q-1 ) =79?-1 mod 3220=1019 因此公鑰為(79,3337)私鑰為(1019, 3337)私鑰為<0 33 3V>輸入一個小于3220的數(shù)怎：79隊鑰為：<79r3337>初鑰為：<1019,3337>3 .輸入明文688并加密4 .輸入密文1570并解密制|八支刖笆曲 明二二688密文為 15705輸入要解密的密文1570明文為：688L五.總結、改進思考：1 .大數(shù)類庫的建

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

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

14、。2 .大素數(shù)隨機生成，以及判斷：真正的RSA加密時密鑰的生成應該是自動完成的，而不是用戶手動制定 p, q, e。所以在使用大數(shù)類庫后隨之而來一個問題就是如何隨機的生成兩個大素數(shù)，以及大素數(shù)的判斷。 由于素數(shù)有無窮多個， 且沒有固定的生成方式， 所以大素數(shù)的生成基本是采用在一定范圍內 （比如奇數(shù)，且不會被小素數(shù)整除的） 隨機選取大數(shù)后再進行素數(shù)檢測，直到有通過檢測的數(shù)。因此大數(shù)的素數(shù)檢測算法就是關鍵了，如果按照之前的素數(shù)檢測算法需要依次除2到，n的數(shù)，時間復雜度 O（，n）太大。所以我們要用更為快速的算法。是目前公認米勒拉賓測試是一個不確定的算法，只能從概率意義上判定一個數(shù)可能是素數(shù)。的最高

15、效的素性測試之一。大體步驟如下：輸入奇數(shù)n,判斷n為素數(shù)或者合數(shù)。計算r和R,使得n _1 = 2r R, R奇。隨即選擇a, a zn 0。for i=0 to r2r R，計算b=a. R右a =br=1(modn),則輸入合數(shù)。 R右a =b。三1(modn),則輸入素數(shù)。設 j=maxi: bi # 1(mod n),則輸入素數(shù)。若bj三1(modn),則輸出素數(shù)，否則輸出合數(shù)。參考書目：1劉嘉勇等應用密碼學2胡道元閔京華網(wǎng)絡安全3張四蘭等可信賴的高效素數(shù)生成和檢驗算法附程序代碼：#include<iostream.h>#include <stdlib.h>#i

16、nclude<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 d,long n);void print_help();int sushu(long m);9int gcd(long a, long b);long ExtendedEuc

17、lid(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<<"=RS儆擬="<<endl;cout<<" 1.輸入兩個素數(shù) P,Qn"cout<<" 2.輸入公鑰 En"cout<<" 3.查看當前密鑰信息n”;cout<<"4.加密 n”;cout<<&qu

18、ot;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(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 :

19、print_help();break;case 0 : break;while(ch);int gcd(long a, long b)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 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 =

20、 ( 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_b_Mod_c(long a, long b, long c) int digit32;long i,k,resualt = 1; i = 0;while(b

21、) 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) cout<<" 輸入第一個素數(shù) p:n"while(1)11 if (cin>>P) break;else cout<<"P

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

23、k;else cout<<"Q 應為素數(shù)，請重新輸入：cin.clear(); cin.ignore(); cin>>Q;N=P*Q;N1=(P-1)*(Q-1);void input_E(long &E,long &D,long n1)"<<endl;"<<endl;"<<endl;"<<endl;if(n1=0)13cout<<"請先輸入兩個素數(shù)P, Q"<<endl;return;long z=0;cout&

24、lt;<"輸入一個小于"<<n1<<"的數(shù) e:n"while(1) if (cin>>E) break;else cout<<"E應為數(shù)字，請重新輸入： "<<endl;cin.clear(); cin.ignore(); while(1) if (gcd(E,n1)=1) break;"<<endl;else cout<<"E 應與"<<n1<<"互質"<<

25、",請重新輸入: 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<<"公鑰為：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<<"輸入