RSA加密的簡(jiǎn)易實(shí)現(xiàn)

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

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

3、進(jìn)行加密解密。2 . 數(shù)學(xué)原理 ：1 .密鑰的生成 選才I p,q為兩個(gè)大的互異素?cái)?shù)計(jì)算n=p*q, 3（n）=（p-1）（q-1）選擇整數(shù)e使gcd（少（n）,e）=1（互質(zhì)），（1<e<3）計(jì)算d,使d=e ?-1（mod少（n）（求乘法逆元）公鑰 Pk=e,n;私鑰 Sk=d,n。(定義若a?x mod n =1,則稱a與x對(duì)于模n互為逆元)2 .加密(用e,n)明文M<n 由C=M ? e(mod n)得到密文 C。3 .解密(用d,n)對(duì)于密文C 由M=C?d(mod n)得到明文 M3.實(shí)現(xiàn)過程：1. 輸入p, q判斷為素?cái)?shù)，計(jì)算 n=p*q ,少(n) = (p

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

5、*i<=m;i+)if(m%i=0)return 0;return 1;(2)互質(zhì)的判斷：在輸入e之后需要判斷e與少(n)是否互質(zhì)，所以用該有判斷互質(zhì)的函數(shù) int gcd () 返回1 (是)，其他(否)。根據(jù)歐幾里德算法gcd(a,b)=gcd(b,a mod b)證明：a可以表示成 a = kb + r，貝U r = a mod b假設(shè)d是a,b的一個(gè)公約數(shù)，則有3d|a, d|b ，而 r = a - kb ,因此 d|r因此d是(b,a mod b) 的公約數(shù)假設(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互質(zhì)。int gcd(long a, long b)if(b = 0)return a;return gcd(b, a % b);(3)求乘法逆元：因?yàn)樾枰?jì)算私鑰d= e ?-1(mod少(n),所以有函數(shù)long ExtendedEuclid ()計(jì)算d并返回d的值，這里用到擴(kuò)展歐幾里德算法。大體思路與歐幾里德算法一致：如果gcd(a , b)=d ,則存在m, n,使得d = ma+ nb,稱呼這種關(guān)系為 a、b組合整數(shù)d, m, n稱為組合系數(shù)。當(dāng) d=1時(shí)，有ma

7、 + nb = 1,此時(shí)可以看出 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;在加密解密時(shí)都要用到類似 A ?B (mod C)的計(jì)算，當(dāng)指數(shù) B較大時(shí)，如果先計(jì)算 A ?B的值時(shí)間較慢，且結(jié)果過大會(huì)溢出。依據(jù)模運(yùn)算的性質(zhì)a a*b ) mod n= (a mod n) * (b mod n) mod n 可以將A ?的解 為較小幾個(gè)數(shù)的乘積分別進(jìn)行模運(yùn)算例如(3 A 999 )可以分解為(3 A 512) * (3 A 256) * (3 A 128) * (3 A 64) * (3 A32) * (3

9、 a 4) * (3 a 2) * 3這樣只要做16次乘法。把999轉(zhuǎn)為2進(jìn)制數(shù)：1111100111,其各位就是要乘的數(shù)。所以程序中要有函數(shù) int a_b_Mod_c ( long a, long b, long c ) 計(jì)算 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 >>= 1; for(k = i-1; k >= 0; k-) resualt=(resualt*resu

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

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

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

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

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

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

16、lude<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 ExtendedEucli

17、d(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.輸入兩個(gè)素?cái)?shù) P,Qn"cout<<" 2.輸入公鑰 En"cout<<" 3.查看當(dāng)前密鑰信息n”;cout<<"4.加密 n”;cout<<"

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

19、int_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<<" 輸入第一個(gè)素?cái)?shù) p:n"while(1)11 if (cin>>P) break;else cout<<"P 應(yīng)為

22、數(shù)字，請(qǐng)重新輸入：cin.clear(); cin.ignore(); while(1) if (sushu(P) break;else cout<<"P 應(yīng)為素?cái)?shù)，請(qǐng)重新輸入：cin.clear(); cin.ignore(); cin>>P;cout<<" 輸入第二個(gè)素?cái)?shù) Q:n"while(1) if (cin>>Q) break;else cout<<"Q 應(yīng)為數(shù)字，請(qǐng)重新輸入：cin.clear(); cin.ignore(); while(1) if (sushu(Q) break;

23、else cout<<"Q 應(yīng)為素?cái)?shù)，請(qǐng)重新輸入：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<<"請(qǐng)先輸入兩個(gè)素?cái)?shù)P, Q"<<endl;return;long z=0;cout<

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

25、uot;,請(qǐng)重新輸入: cin.clear(); cin.ignore(); cin>>E;if(ExtendedEuclid(E,n1,&z) D=z;else cout<<" 錯(cuò)誤"<<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<<"請(qǐng)先輸入密鑰"<<endl;return;long c,m; cout<<"輸入