RSA加密解密網絡課程設計

PAGE22PAGE23計算機與信息學院《計算機網絡系統(tǒng)實踐》報告設計題目：設計題目：RSA加密解密學生姓名：學號： 專業(yè)班級：計算機科學與技術一、設計要求隨機搜索大素數(shù)，隨機生成公鑰和私鑰。用公鑰對任意長度的明文（字符）加密。用私鑰對密文解密。界面簡潔、友好便于操作。二、開發(fā)環(huán)境與工具硬件環(huán)境：PC機一臺軟件環(huán)境：Windos2000/XP,VC++6.0三、設計原理（一）RSA算法原理首先，找出兩個大素數(shù)key_P,key_Q,令key_N=key_P*key_Q。根據歐拉（Euler）數(shù)(key_N)的定義為小于key_N且與key_N互素的正整數(shù)個數(shù)，如果key_P和key_Q的最大公約數(shù)GCD(key_P,key_Q)＝1，則(key_N)＝(key_P)*(key_Q)，特別地，如果若key_P!=key_Q且都是素數(shù)，則(key_N)＝(key_P-1)*(key_Q-1)。這時，我們令key_Z=(key_N)=(key_P-1)*(key_Q-1)。并且，key_N公開，key_Z要保密。然后，選擇一個與key_Z互素的整數(shù)key_D，作為解密密鑰。Key_D公開。解同余方程key_E*key_Dmodkey_Z=1。得到的key_E就是加密密鑰。Key_E需要保密。這個時候key_E一定存在。因為key_D和key_Z互素，根據歐幾里德算法，GCD(key_D,key_Z)＝1，而擴展歐幾里德算法key_D存在模key_Z乘法逆元的充分必要條件是GCD(key_D,key_Z)＝1。至于key_E怎么得到，用輾轉相除法即可得到，下面還會就模key_Z的擴展歐幾里德算法予以祥述。接著做加密和解密信息處理。發(fā)送端將要發(fā)送信息為key_P,通過key_C=key_P^key_Emodkey_N進行處理，然后將密文key_C發(fā)到接受端。這時即使中途有人竊取信息，也只能得到密文，而且，竊取者很難通過公鑰(key_N,key_E)對密文進行解密。這時接受端接受到密文。并通過密鑰(key_N,key_D)進行解密處理：key_P=key_C^key_Dmodkey_N。（二）大數(shù)儲存及運算原理1．RSA

依賴大數(shù)運算，目前主流RSA

算法都建立在1024位的大數(shù)運算之上。

而大多數(shù)的編譯器只能支持到64位的整數(shù)運算，即我們在運算中所使用的整數(shù)必須小于等于64位，即：0xffffffffffffffff，也就是18446744073709551615，這遠遠達不到RSA

的需要，于是需要專門建立大數(shù)運算庫來解決這一問題。最簡單的辦法是將大數(shù)當作數(shù)組進行處理，也就是將大數(shù)用0—9這十個數(shù)字組成的數(shù)組進行表示，然后模擬人們手工進行“豎式計算”的過程編寫其加減乘除函數(shù)。但是這樣做效率很低，因為二進制為1024位的大數(shù)其十進制也有三百多位，對于任何一種運算，都需要在兩個有數(shù)百個元素的數(shù)組空間上做多重循環(huán)，還需要許多額外的空間存放計算的進退位標志及中間結果。另外，對于某些特殊的運算而言，采用二進制會使計算過程大大簡化，這種大數(shù)表示方法轉化成二進制顯然非常麻煩，所以在某些實例中則干脆采用了二進制數(shù)組的方法來記錄大數(shù)，這樣效率就更低了。一個有效的改進方法是將大數(shù)表示為一個n

進制數(shù)組，n

可以取值為2

的16次方，即0x1000，假如將一個二進制為1024位的大數(shù)轉化成0x1000進制，它就變成了64位，而每一位的取值范圍就不是二進制的0—1或十進制的0—9，而是0-0xffff，我們正好可以用一個無符號整數(shù)來表示這一數(shù)值。所以1024位的大數(shù)就是一個有64個元素的unsigned

int數(shù)組，針對unsigned

int數(shù)組進行各種運算所需的循環(huán)規(guī)模至多64次而已。而且0x10000

進制與二進制，對于計算機來說，幾乎是一回事，轉換非常容易。加法A=Sum[i=0

to

p](A[i]*0x10000**i)；B=Sum[i=0

to

q](B[i]*0x10000**i)，p>=q；C=Sum[i=0

to

n](C[i]*0x10000**i)=A+B。如果用carry[i]記錄每次的進位則有：C[i]=A[i]+B[i]+carry[i-1]-carry[i]*0x10000，其中carry[-1]=0。若A[i]+B[i]+carry[i-1]>0xffffffff，則carry[i]=1；反之則carry[i]=0，若carry[p]=0，則n=p；反之則n=p+1。減法與加法同理。乘法

A=Sum[i=0

to

p](A[i]*0x10000**i)；

B=Sum[i=0

to

q](B[i]*0x10000**i)，p>=q；C=Sum[i=0

to

n](C[i]*0x10000**i)=A*B。顯然，C=Sum[i=0

to

n](C[i]*0x10000**i)=A*B而(A*B[i]*100000000**i)=Sum[j=0

to

p](A[j]*B[i]*0x10000**(i+j))，所以C=Sum[i=0

to

q](Sum[j=0

to

p](A[j]*B[i]*0x10000**(i+j)))。因此，因此：

C[i]=Sum[j=0

to

q](A[i-j]*B[j])+carry[i-1]-carry[i]*0x10000，其中carry[-1]=0，carry[i]=(Sum[j=0

to

q](A[i-j]*B[j])+carry[i-1])/0x10000，n=p+q-1，若carry[n]>0，則n=n+1，C[n]=carry除法設A=Sum[i=0

to

p](A[i]*0x10000**i)，B=Sum[i=0

to

q](B[i]*0x10000**i)，p>=q，

C=Sum[i=0

to

n](C[i]*0x10000**i)=A/B。由于無法將B

對A

“試商”，我們只能轉換成B[q]對A[p]的試商來得到一個近似值，所以我們不能夠直接計算C。但是，我們可以一步一步地逼近C。顯然，(A[p]/B[q]-1)*0x10000**(p-q)<C，令X=0，重復A=A-X*B，X=X+(A[p]/B[q]-1)*0x10000**(p-q)，直到A<B。則有

X=C。取模設A=Sum[i=0

to

p](A[i]*0x10000**i)；

B=Sum[i=0

to

q](B[i]*0x10000**i)，p>=q；C=Sum[i=0

to

n](C[i]*0x10000**i)=A%B。求模與求商的過程一致，只是由于不需要記錄商而更加簡單：重復A=A-(A[p]/B[q]-1)*0x10000**(p-q)*B，直到A<B。則有A=C。四、系統(tǒng)功能描述及軟件模塊劃分公鑰和私鑰的生成voidgenerate_key()（1）首先利用strongprime函數(shù)生成兩個素數(shù)key_P_Q[0],key_P_Q[1],然后利用multiply函數(shù)得到key_N=key_P_Q[0]*key_P_Q[1],用subtract函數(shù)和add函數(shù)實現(xiàn)key_Z=(key_P_Q[0]-1)*(key_P_Q[1]–1)=key_N–(key_P_Q[0]+key_P_Q[1])+1。（2）隨機生成一個密鑰key_D，然后利用extend_gcd函數(shù)求同余方程key_D*key_Emodkey_Z=1。得到key_E,作為公鑰。（3）至此將公鑰（key_N,key_E）寫入文件中，將私鑰（key_N,key_D）寫入文件中保存。加密信息voidencode_information()將加密的信息長度判斷是否大于key_N的長度，如果大于key_N的長度，應該將加密信息分成一小段一小段，各小段長度均小于key_N長度，然后利用讀取已經保存在文件中的公鑰和私鑰，對加密信息每小段每小段進行加密，并將加密信息密文存放到加密文件中。加密將用到的函數(shù)為powmod(key_P,key_E,key_N,key_C)。解密信息voiddecode_information()解密信息和加密信息采用同樣的道理，即利用保存好的密鑰對密文一段一段進行解密。解密將用到的函數(shù)為Powmod(key_C,key_D,key_N,key_P)五、設計核心代碼extern"C"{#include"miracl.h"}#include"big.h"#include"stdlib.h"#include"string.h"#include"stdio.h"#include"malloc.h"staticmiracl*mip;staticbigpd,pl,ph;#definePRIME_BITS512//===============================================================intabs(intx){ if(x>=0) returnx; elsereturn(-x);}//==================================================================//產生一個強素數(shù)//==================================================================voidstrongprime(bigp,intn,longseed1,longseed2){intr,r1,r2;irand(seed1);//產生一個隨機數(shù)，即初始化bigbits(2*n/3,pd);//生一個2*n/3位（bit）的pd隨機數(shù)nxprime(pd,pd);//nxprime(pd,x)找到一個x大于pd的素數(shù)，返回值為BOOLexpb2(n-1,ph);//ph=2^(n-1),即2的(n-1)次方divide(ph,pd,ph);//ph=ph/pdexpb2(n-2,pl);divide(pl,pd,pl);//pl=pl/pdsubtract(ph,pl,ph);//ph=ph-plirand(seed2);bigrand(ph,ph);add(ph,pl,ph);r1=subdiv(pd,12,pl);//pl=pd/12r2=subdiv(ph,12,pl);//pl=ph/12r=0;while((r1*(r2+r))%12!=5) r++;incr(ph,r,ph);//ph=ph+rdo{//findp=2*r*pd+1=11mod12multiply(ph,pd,p);//p=ph*pdpremult(p,2,p);//p=p*2incr(p,1,p);//p=p+1incr(ph,12,ph);//ph=ph+12}while(!isprime(p));}//===============================================================//同余extend_gcd//===============================================================voidextend_gcd(bigkey_D,bigkey_Z,bigkey_E){ bigs0,s1,s2,zero,z1; s0=mirvar(1);//初始化為1 s1=mirvar(0); s2=mirvar(0); zero=mirvar(0); z1=mirvar(0); copy(key_Z,z1); bigq,t; q=mirvar(0); t=mirvar(0); while(compare(key_Z,zero)>0) { copy(key_Z,t);//t=key_Z divide(key_D,key_Z,q);//q=key_D/key_Z copy(key_D,key_Z);//key_Z=key_D copy(t,key_D);//key_D=t multiply(q,s1,t);//t=q*s1 subtract(s0,t,s2);//s2=s0-q*s1 copy(s1,s0);//s0=s1 copy(s2,s1);//s1=s2 } convert(1,t);//t=1 if(compare(t,key_D)!=0) convert(0,key_E); else { if(compare(s0,zero)>0) copy(s0,key_E); else add(s0,z1,key_E); } return;}//===============================================================//生成公鑰和私鑰generate_key()//===============================================================voidgenerate_key(){inti;longseed[4];bigone,key_P_Q[2],key_N,key_Z,key_D,key_E/*,key_ZR*/;FILE*outfile;mip=mirsys(100,0);//初始化操作pd=mirvar(0);pl=mirvar(0);ph=mirvar(0); one=mirvar(0); key_P_Q[0]=mirvar(0); key_P_Q[1]=mirvar(0);key_N=mirvar(0); key_Z=mirvar(0); key_D=mirvar(0); key_E=mirvar(0);for(i=0;i<4;i++) seed[i]=abs(brand()); printf("\t\t\n正在產生公鑰和私鑰，請等候……\n"); //產生兩個素數(shù) strongprime(key_P_Q[0],PRIME_BITS,seed[0],seed[1]); strongprime(key_P_Q[1],PRIME_BITS,seed[2],seed[3]);multiply(key_P_Q[0],key_P_Q[1],key_N);//key_N=key_P_Q[0]*key_P_Q[1] mip->IOBASE=16; //寫到key_P_Q.dat文件中outfile=fopen("key_P_Q.dat","wt");cotnum(key_P_Q[0],outfile); cotnum(key_P_Q[1],outfile);fclose(outfile);printf("\t\t\n公鑰長度key_N=key_P_Q[0]*key_P_Q[1]有%d位!\n",logb2(key_N));printf("\n\t===========輸出公鑰key_N================\n");cotnum(key_N,stdout); mip->IOBASE=16; //寫到key_N.dat文件中 outfile=fopen("key_N.dat","wt");cotnum(key_N,outfile);fclose(outfile); //key_Z=key_N-key_P_Q[0]-key_P_Q[1]+1; convert(1,one); subtract(key_N,key_P_Q[0],key_Z); subtract(key_Z,key_P_Q[1],key_Z); add(key_Z,one,key_Z); mip->IOBASE=16; //寫到key_Z.dat文件中 outfile=fopen("key_Z.dat","w+");cotnum(key_Z,outfile);fclose(outfile); printf("\n\t===========輸出解密密鑰key_D===============\n"); do { bigrand(key_P_Q[0],key_D); subtract(key_D,one,key_D); }while(!isprime(key_D)); cotnum(key_D,stdout); mip->IOBASE=16; //寫到key_D.dat文件中 outfile=fopen("key_D.dat","w+");cotnum(key_D,outfile);fclose(outfile); printf("\n\t==========-輸出加密密鑰key_E===============\n"); extend_gcd(key_D,key_Z,key_E); cotnum(key_E,stdout); mip->IOBASE=16; //寫到key_E.dat文件中 outfile=fopen("key_E.dat","w+");cotnum(key_E,outfile);fclose(outfile); }//===============================================================//加密encode_information()//===============================================================voidencode_information(){ bigkey_N,key_E,key_P,key_C; charbuffer[130],ifname[32]; intbuffer_length,i=0; FILE*infile,*outfile; BOOLflag; key_N=mirvar(0); key_E=mirvar(0); key_P=mirvar(0); key_C=mirvar(0); if((infile=fopen("key_N.dat","rt"))==NULL){printf("\n不能打開文件key_N.dat"); return;} mip->IOBASE=16; cinnum(key_N,infile); fclose(infile); if((infile=fopen("key_E.dat","rt"))==NULL){printf("\n不能打開文件key_E.dat"); return;} mip->IOBASE=16; cinnum(key_E,infile); fclose(infile); printf("\t要加密的文件為="); getchar();gets(ifname);if((infile=fopen(ifname,"rt"))==NULL){printf("\n不能打開文件%s\n",ifname); return;} else { printf("\n正在加密信息……\n"); outfile=fopen("key_C.dat","w+"); if(fgets(buffer,128,infile)==NULL) flag=true; else flag=false; while(!flag) { buffer_length=strlen(buffer); buffer[buffer_length]='\0'; mip->IOBASE=128; cinstr(key_P,buffer); cotnum(key_P,stdout); powmod(key_P,key_E,key_N,key_C); mip->IOBASE=16; cotnum(key_C,outfile); if(fgets(buffer,128,infile)==NULL) flag=true; } printf("\n"); fclose(infile); fclose(outfile); }}//===============================================================//解密decode_information()//===============================================================voiddecode_information(){ bigkey_N,key_D,key_C,key_P; charifname[32]; FILE*infile,*outfile; key_N=mirvar(0); key_D=mirvar(0); key_C=mirvar(0); key_P=mirvar(0); //打開key_N.dat文件，寫入key_N if((outfile=fopen("key_N.dat","rt"))==NULL) { printf("不能打開key_N.dat文件\n"); return; } mip->IOBASE=16; cinnum(key_N,outfile); fclose(outfile); //打開key_D.dat文件，寫入key_D if((outfile=fopen("key_D.dat","rt"))==NULL) { printf("不能打開key_D.dat文件\n"); return; } mip->IOBASE=16; cinnum(key_D,outfile); fclose(outfile); printf("\t要解密出的文件存儲在="); getchar(); gets(ifname); infile=fopen(ifname,"wt"); printf("\t============解密出的明文信息===============\n"); //打開key_C.dat文件，一段一段寫入key_C if((outfile=fopen("key_C.dat","rt"))==NULL) { printf("不能打開key_C.dat文件\n"); return; } while(1) { mip->IOBASE=16; cinnum(key_C,outfile); if(size(key_C)==0)break; powmod(key_C,key_D,key_N,key_P); mip->IOBASE=128; cotnum(key_P,infile); cotnum(key_P,stdout); } printf("\t===========解密信息結束====================\n"); fclose(outfile); fclose(infile);}//===============================================================//主程序//===============================================================intmain(){ charch; do{ system("cls"); printf("\t\t==============請選擇菜單!==============\n"); printf("\t\t*1:生成公鑰和私鑰*\n"); printf("\t\t*2:加密信息*\n"); printf("\t\t*3:解密信息*\n"); printf("\t\t*=============4:退出===================\n"); printf("\n\t\t請輸入你要選擇的菜單項="); ch=getchar(); if(ch=='1') { generate_key(); system("pause"); } elseif(ch=='2') { encode_information(); system("pause"); } elseif(ch=='3') { decode_information(); system("pause"); } }while(ch!='4'); return0;}//===============================================================六、關鍵問題及其解決方法

（1）流程圖開始開始選擇產生公鑰和私鑰，請按1選擇產生公鑰和私鑰，請按1選擇加密信息，請按2選擇解密信息，請按3選擇退出程序，請按4產生公鑰和密鑰產生兩個素數(shù)key_P_Q[0],key_P_Q[1]得到key_N=key_P_Q[0]*key_P_Q[1]和key_Z=key_N-key_P_Q[0]-key_P_Q[1]+1。產生一個密鑰key_D,解同余方程key_D*key_Emodkey_Z=1,得到key_E將公鑰公鑰(key_N,key_E)和密鑰(key_N,key_D)存入文件加密信息讀進公鑰(key_N,key_E)讀進明文key_P,并進行加密key_P^key_Emodkey_N。將密文存入文件解密信息讀進密鑰(key_N,key_D)讀進密文key_C,并進行解密key_C^key_Domdkey_N。將解密信息在屏幕上顯示，并存入指定文件程序流程圖(2)關鍵環(huán)節(jié)1．求模逆元的擴展歐幾里德算法原理：正整數(shù)a和b滿足sn*a+tn*b=(a,b),當(a,b)=1時，sn=a^-1modb其中s0=1,s1=0,sj=(sj-2)–(qj-1)*s(j-1；t0=0,tj=(tj-2)–(qj-1)*t(j-1)輸入大數(shù)a和b輸出：a^-1modb或0（不存在逆元）s0=1,s1=0whileb>0doq=a/b;s2=s0-q*s1;s0=s1;s1=s2;t=b;b=a%b;a=t;ifa=1returns0;elsereturn0;2.明文（數(shù)值）長度要小于key_N，才符合RSA算法，否則很容易出錯，我選擇了一個大于key_N的明文，發(fā)現(xiàn)經過驗證并不符合RSA算法。那么，處理那些明文（數(shù)值）很大的辦法就是將明文分成一小段一小段，否則，解密的信息必然是一堆亂碼（除非原明文數(shù)值并不大）。分成一小段之后，然后利用加密公式和解密公式對其進行處理，這樣得到的結果就是準確結果了。七、設計結果及驗證（1）公鑰長度為1024位進行驗證：圖（1）生成公鑰和私鑰圖（2）加密文件e:\20042432\1.txt，并顯示加密文件中信息圖（3）解密文件，并顯示解密文件中信息圖（4）選擇鍵?？梢赃x擇4程序結束圖（5）e:\20042432\1.txt加密后的密文（2）公鑰長度為2048位進行驗證：圖（6）生成公鑰和私鑰圖（7）對e:\20042432\2.txt文本文件進行加密圖（8）對加密密文e:\20042432\key_C.dat進行解密，