RSA加密的簡(jiǎn)易實(shí)現(xiàn)要點(diǎn)(共14頁(yè))

1、 安全學(xué)實(shí)驗(yàn)報(bào)告RSA加密解密的簡(jiǎn)單實(shí)現(xiàn) 華南師范大學(xué) 趙教授RSA介紹：當(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）并顯示。 輸入明文密文并可以進(jìn)行加密解密。2.數(shù)學(xué)原理

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

4、(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)鍵問(wèn)題： （1）素?cái)?shù)的判斷：首先在輸入p，q之后應(yīng)該有一個(gè)函數(shù)int sushu（）可以判斷p，q是否為素?cái)?shù)，并返回 1（是）或0（否）?？紤]到程序中數(shù)據(jù)類型為long型，依次用2n之間的數(shù)去除n，如果能整除則不為素?cái)?shù)。該算法時(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）快速冪模算法：在加密解密時(shí)都要用到類似A B（mod C）的計(jì)算，當(dāng)指數(shù)B較大時(shí)，如果先計(jì)算A B的值時(shí)間較慢，且結(jié)果過(guò)大會(huì)溢出。依據(jù)模運(yùn)算的性質(zhì)（a*b）mod n=（a mod n）*（b mod n）mod n 可以將A B分解為較小幾個(gè)數(shù)的乘積

6、分別進(jìn)行模運(yù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）計(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

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

8、)根據(jù)輸入的密文C計(jì)算明文M= C d(mod n)（2）各功能模塊：命令對(duì)應(yīng)函數(shù)功能描述1input_P_Q輸入素?cái)?shù)P,Q2input_E輸入公鑰E3print_miyao顯示密鑰信息4jiami加密5jiemi解密6print_help幫助四.程序測(cè)試：1輸入兩個(gè)素?cái)?shù)p=47，q=71 則n=47*71=33372.輸入e=79，計(jì)算得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ù)類庫(kù)的建立：本程序作為RSA加密解密過(guò)

9、程演示程序，變量均為long型，因此密鑰長(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位運(yùn)算的，所以采用2 32進(jìn)制表示大數(shù)將會(huì)很大

10、提高計(jì)算機(jī)的處理效率?，F(xiàn)實(shí)中，就使用32位的整數(shù)數(shù)組進(jìn)行存儲(chǔ)每一位數(shù)，另設(shè)一個(gè)布爾值表示正負(fù)。進(jìn)行計(jì)算時(shí)常會(huì)遇到進(jìn)位借位的情況，而且常常會(huì)超過(guò)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.大素?cái)?shù)隨機(jī)生成，以及判斷： 真正的RSA加密時(shí)密鑰

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

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

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

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