網(wǎng)絡安全實驗-RSA算法

1、 網(wǎng)絡安全作業(yè)1 RSA算法流程如下：（1）密鑰生成算法流程：1）隨機地選擇兩個大素數(shù)p和q（需保密）； 2）計算乘積n=p×q； 3）計算歐拉函數(shù)z=j(n)=(p-1)(q-1)。其數(shù)值等于小 于n并且與n互質(zhì)的整數(shù)的個數(shù)。4）選擇一個隨機數(shù)e，使e與z互質(zhì)，且1<e<z。5）計算d，使d*e=1 mod z。6）其中，公鑰KP=e,n，私鑰KS=d,n。（2）RSA 加密、解密的過程首先將明文分塊并數(shù)字化，每個數(shù)字化明文塊的長度小于或等于log2n。然后對每個明文塊M依次進行加、解密：加密：使用公鑰 e 和加密密文 m，即C=mod n；解密：使用私鑰 d 將密文

2、c 解密，獲得明文 m，即 M=mod n。2. 具體的數(shù)據(jù)結(jié)構(gòu)與算法：（1）存儲大整數(shù)的數(shù)據(jù)結(jié)構(gòu)：typedef struct intlength; unsigned int nMAX; Lint;這里大整數(shù)用65536進制表示并使用結(jié)構(gòu)體Lint存儲大整數(shù)。Lint由一個整型變量length和一個無符號整型數(shù)組nMAX構(gòu)成, length存儲大整數(shù)的位數(shù)，nMAX具體存儲每一位的值。（2）具體的算法：具體的算法主要參考了此書：趙振江等譯密碼編碼學加密方法的C與C十十實現(xiàn)(第二版)北京：電子工業(yè)出版社，2003具體的算法包括：基于上述數(shù)據(jù)結(jié)構(gòu)的大整數(shù)的加、減、乘、除、模冪運算，求逆元運算，以

3、及大素數(shù)的判定等。這些算法的具體內(nèi)容都在原程序與其注釋中。 3. 源程序 此程序的開發(fā)環(huán)境是Microsoft Visual studio 2008。 （1） RSA生成密鑰源程序及運行結(jié)果#include<iostream>#include<cmath>using namespace std;void main() int p,q; cout<<"*RSA生成密鑰算法*"<<endl<<endl; cout<<"請輸入兩個較大的素數(shù)："<<endl; cin>&g

4、t;p>>q; cout<<"p="<<p<<",q="<<q<<endl; int n,o; n=p*q; o=(p-1)*(q-1); cout<<"n="<<n<<",o="<<o<<endl; cout<<"請從(0，"<<o-1<<")中選擇一個與"<<o<<"互素的

5、數(shù)e："<<endl; int e,i; float d; cin>>e; for(i=1;i+) d=(float)(o*i+1)/e; if(d-(int)d=0) break; cout<<"e="<<e<<",d="<<d<<endl; cout<<"公開密鑰Pk=e,n="<<e<<","<<n<<""<<endl; co

6、ut<<"秘密密鑰Sk=d,n="<<d<<","<<n<<""<<endl; cout<<endl; cout<<"請輸入要加密的正整數(shù)（以-1結(jié)束）："<<endl; int m1500,m3500,m4500; double m2500; int j; for(j=0;j<500;j+) cin>>m1j; if(m1j=-1) break; m2j=pow(m1j,e); m4j=m

7、2j/n; m3j=m2j-m4j*n; cout<<"密文為："<<endl; int k; for(k=0;k<j;k+) cout<<m3k<<" " cout<<endl;程序運行結(jié)果及分析：算法按照要求進行，生成的密鑰也符合要求。（2）RSA加密及解密算法實現(xiàn)源程序及運行結(jié)果#include "stdafx.h"#include <stdio.h>#include <stdlib.h>#include <string.h>#

8、include <time.h> #define MAX 200 /定義大整數(shù)的最大位數(shù)，200完全可以滿足p與q達到768bit位的要求，可以選擇更大的數(shù)。#define GREAT 1 /定義大整數(shù)比較時的返回值#define EQUAL 0#define LOW -1#define PL 33 /如果重新生成p與q，則PL定義了p與q的最大位數(shù)。這里定義為33保證p與q達到512bit長度。typedef struct intlength; unsigned int nMAX; Lint;Lint ZERO,ONE,TWO; /定義常用大整數(shù)0、1、2。/ Init_Lint

9、函數(shù)功能：初始化大整數(shù)。首先清零，然后把前n位設置為 valueint Init_Lint(Lint *a, int n,unsigned int value) int i;if (a=NULL) return (0);else a->length=0; for (i=0;i<MAX;i+) a->ni=0; for (i=0;i<n;i+) a->ni=value; a->length=n; return (1); / Set _Lint函數(shù)功能：把大整數(shù)a的第n位設置為valuevoid Set_Lint(Lint* a,int n,unsigned i

10、nt value) if (a->length < n) a->length =n; a->nn-1=value; / Cpy_Lint函數(shù)功能：把大整數(shù)a復制給bint Cpy_Lint(Lint * a,Lint* b) int i; if (a=NULL|b=NULL) return 0;if(b->length=0) Init_Lint(a,0,0); return 1; for(i=0;i<MAX;i+)a->ni=b->ni;a->length=b->length;return 1; /Split_Lint函數(shù)功能：提取大

11、整數(shù)b從n1開始的n2位的數(shù)據(jù)組成大整數(shù)aint Split_Lint(Lint * a,Lint* b,int n1,int n2) int i; if(n1<1|n2>b->length) return 0; for (i=n1-1;i<n2;i+)a->ni-n1+1=b->ni; a->length=n2-n1+1; return 1; / Cmp_Lint函數(shù)功能：比較兩個大整數(shù)的大小，若a>b返回1，若a=b返回0，若a<b返回-1int Cmp_Lint(Lint a,Lint b) int i;i=a.length; whi

12、le(1) if (a.ni-1=0 )&&(a.length>1) a.length-=1; else break; i-; i=b.length;while(1) if (b.ni-1=0 )&&(b.length>1) b.length-=1; else break; i-; if (a.length > b.length ) return GREAT; if (a.length < b.length ) return LOW; i=a.length-1; while(i>=0) if(a.ni>b.ni) return

13、 GREAT; if(a.ni<b.ni) return LOW; i-; if (i<0) return EQUAL; / Lint_Add函數(shù)功能：實現(xiàn)大整數(shù)加法，a+b=cvoid Lint_Add(Lint *a,Lint *b,Lint *c) unsigned long temp=0; int i=0,carry=0; Init_Lint(c,0,0); while(i<a->length)&&(i<b->length) temp=a->ni+b->ni+carry; c->ni=temp%65536; carr

14、y=temp/65536; i+; c->length=i; while (i<a->length) temp=a->ni+carry; c->ni=temp%65536; carry=temp/65536; i+; c->length=i; while (i<b->length) temp=b->ni+carry; c->ni=temp%65536; carry=temp/65536; i+; c->length=i; if(carry>0) c->ni=carry; c->length=i+1; / Lin

15、t_Sub函數(shù)功能：實現(xiàn)大整數(shù)的減法，a-b=cint Lint_Sub(Lint *a,Lint *b,Lint *c) unsigned long temp=0; int i=0,carry=1; Init_Lint(c,0,0); if (Cmp_Lint(*a,*b)=LOW) return 0; while(i<b->length) if(carry=1) temp=a->ni-b->ni+65536; else temp=a->ni-b->ni+65535; c->ni=temp%65536; carry=temp/65536; i+; c

16、->length=i; while (i<a->length) if(carry=1) temp=a->ni+65536; else temp=a->ni+65535; c->ni=temp%65536; carry=temp/65536; i+; c->length=i; while(1) if (c->ni-1=0 )&&(c->length>1) c->length-=1; else break; i-; return 1;/* Lint_Mul函數(shù)功能：實現(xiàn)大整數(shù)的乘法，a*b=c。兩個數(shù)a和b的乘法,按

17、照在學校所學過的方法,當a和b的位數(shù)都為3時，乘積a*b的計算如下圖：(a2 a1 a0)B×(b2 b1 b0)BC20 P20 P10 P00+ C21 P21 P11 P01+ C22 P22 P12 P02(P5 P4 P3 P2 P1 P0) BLint_Mul函數(shù)使用的算法完全遵從上面圖解。*/void Lint_Mul(Lint *a,Lint *b,Lint *c) int i,j; unsigned long temp1=0,temp2=0,carry=0; Init_Lint(c,0,0); for(i=0;i<a->length;i+) for(j=

18、0,carry=0;j<b->length;j+) temp1=a->ni*b->nj+c->ni+j+carry; c->ni+j=temp1%65536; carry=temp1/65536; if(carry>0) c->ni+b->length=carry; c->length=a->length+b->length; i=c->length; while(1) if (c->ni-1=0 )&&(c->length>1) c->length-=1; else brea

19、k; i-; / Lint_Div函數(shù)功能：實現(xiàn)大整數(shù)的帶余除法法，a/b=q余r。帶余除法的算法和乘法一樣也是遵從在學校所學過的方法的圖解。int Lint_Div(Lint *a,Lint *b,Lint *q,Lint* r) Lint R1,R2,B1,B2,temp_Lint0,temp_Lint1,temp_Lint2,Q1,Q_Lint,SubB,SubR,d; unsigned int i,j,n,Q,k; int flag1,flag2; unsigned long temp ; Init_Lint(&d,0,0); Init_Lint(&R1,0,0); I

20、nit_Lint(&R2,0,0); Init_Lint(&Q1,0,0); Init_Lint(&B1,0,0); Init_Lint(&B2,0,0); Init_Lint(&temp_Lint0,0,0); Init_Lint(&temp_Lint1,0,0); Init_Lint(&temp_Lint2,0,0); Init_Lint(&Q_Lint,0,0); Init_Lint(&SubB,0,0); Init_Lint(&SubR,0,0); Init_Lint(q,0,0); Init_Lint(r

21、,0,0); j=a->length-b->length; Cpy_Lint(&R1,a); Set_Lint(&R1,a->length+1,0); Cpy_Lint(&B1,b); Cpy_Lint(&B2,b); Set_Lint(&d,1,1); Set_Lint(&d,1,1); i=R1.length-1; n=B1.length; flag1=Cmp_Lint(*b,ZERO); if(a=NULL|b=NULL|flag1=0) return 0; if(Cmp_Lint(B1,ZERO)=0) return 0

22、; if(Cmp_Lint(R1,B1)<0) Cpy_Lint(q,&ZERO); Cpy_Lint(r,a); return 1; if(Cmp_Lint(R1,B1)=0) Cpy_Lint(q,&ONE); Cpy_Lint(r,&ZERO); return 1; while (i>=n) if(Cmp_Lint(R1,B1)<=0) Q=0; else temp=(R1.ni*65536+R1.ni-1)/B1.nn-1; temp=(temp<65535)?temp:65535; Split_Lint(&SubR,&R

23、1,i-n+1,i+1); do Set_Lint( &Q_Lint,1,temp); Lint_Mul(&B1,&Q_Lint,&temp_Lint1); flag1=Cmp_Lint(SubR,temp_Lint1); Set_Lint( &Q_Lint,1,temp+1); Lint_Mul(&B1,&Q_Lint,&temp_Lint1); flag2=Cmp_Lint(SubR,temp_Lint1); if(flag1=0) Q=temp;break; if(flag2=0) Q=temp+1;break; if(fl

24、ag1<0&&flag2<0) temp-; if(flag1>0&&flag2<0) Q=temp;break; if(flag1>0&&flag2>0) temp+; while(1); Set_Lint( &Q_Lint,1,Q); Lint_Mul(&B1,&Q_Lint,&temp_Lint2); Lint_Sub(&SubR,&temp_Lint2,&temp_Lint0); for(k=0;k<=n;k+)R1.ni-n+k=temp_

25、Lint0.nk; Set_Lint(&Q1,j+1,Q); i-; j-; i=R1.length; while(1) if (R1.ni-1=0 )&&(R1.length>1) R1.length-=1; else break; i-; i=Q1.length;while(1) if (Q1.ni-1=0 )&&(Q1.length>1) Q1.length-=1; else break; i-; Cpy_Lint(r,&R1); Cpy_Lint(q,&Q1); return 1;/ Mod_Sub函數(shù)功能：實現(xiàn)大整數(shù)

26、的模減運算,(a-b)mod m=cint Mod_Sub(Lint a, Lint b,Lint *c, Lint *m) Lint temp0,temp1; if (Cmp_Lint(a,b)>=0) Lint_Sub(&a,&b,&temp0); Lint_Div(&temp0,m,&a,c); else Lint_Sub(&b,&a,&temp0); Lint_Div(&temp0,m,&a,&temp1); if (Cmp_Lint(temp1,ZERO)>0) Lint_Sub(m,

27、&temp1,c); else Cpy_Lint(c,&ZERO); return 1; / Euclid函數(shù)功能：用擴展歐幾里德算法求a模n的乘法逆元v，和a與n的最大公約數(shù)。其中v 是返回的逆元，gcd是返回的最大公約數(shù)。若gcd返回的不是1，則a,n不互素,逆元不存在,即：所求逆元v無效。int Euclid(Lint n,Lint a,Lint *v,Lint *gcd) Lint u,g,v1,v3,q,t1,t3,temp1,temp2,temp3; int i; Cpy_Lint(&u,&ONE); Cpy_Lint(&t1,&ON

28、E); Cpy_Lint(&v1,&ZERO); Cpy_Lint(&g,&a); Cpy_Lint(&v3,&n); i=Cmp_Lint(v3,ZERO); if (i=0) return 0; while (i>0) Lint_Div(&g,&v3,&q,&t3); Lint_Mul(&q,&v1,&temp1); Lint_Div(&temp1,&n,&temp3,&temp2); Mod_Sub(u,temp2, &t1, &n

29、); Cpy_Lint(&u,&v1); Cpy_Lint(&v1,&t1); Cpy_Lint(&g,&v3); Cpy_Lint(&v3,&t3); i=Cmp_Lint(v3,ZERO); Cpy_Lint(v,&u); Cpy_Lint(gcd,&g); return 1;/ Mexp_Lint函數(shù)功能：用二進制算法進行模冪運算，p=mod mint Mexp_Lint(Lint a,Lint e,Lint* p,Lint m)/和下面這個數(shù)組中的數(shù)進行與運算可以提取出015位的二進制值。unsigned

30、int r,bit=1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768; int i,n,s,t;Lint temp0,temp1,temp2;Init_Lint(&temp0,0,0); Init_Lint(&temp1,0,0); Init_Lint(&temp2,0,0);if(Cmp_Lint(m,ZERO)=0) return 0; if(Cmp_Lint(m,ONE)=0) Cpy_Lint(p,&ZERO); return 1; else if (Cmp_Lint(a,ZERO)

31、=0) if(Cmp_Lint(e,ZERO)=0) Cpy_Lint(p,&ONE); return 1; if(Cmp_Lint(e,ZERO)>0) Cpy_Lint(p,&ZERO); return 1; n=e.length*16;r=e.ne.length-1&bit15;if (r>0) Cpy_Lint(p,&a);else Cpy_Lint(p,&ONE);i=n-2;while(i>=0) Lint_Mul(p,p,&temp1); Lint_Div(&temp1,&m,&temp0,

32、p); s=(i)/16; t=(i)%16; r=e.ns&bitt; if(r>0) Lint_Mul(p,&a,&temp0); Lint_Div(&temp0,&m,&temp1,p); i-; return 1;/ Rand_Lint函數(shù)功能：偽隨機生成n位大整數(shù)p。具體用線性乘同余方法隨機生成大整數(shù)的每一位（小于65536），然后組合成大整數(shù)。這里使用的是改進的線性乘同余方法。int Rand_Lint(Lint *p , int n) int i; unsigned long a = 65539,b = 65539,seed1

33、,seed0; unsigned long temp; unsigned long m = 65536; seed1=rand(); seed0=rand(); for(i=0;i<n;i+) temp= (a * seed1 + b * seed0 ) % m;Set_Lint(p,i+1,(unsigned short)temp); seed1 = rand(); seed0 = temp; return 1; / Isprime函數(shù)功能：利用費馬定理判斷大整數(shù)是否是素數(shù)，是返回1，不是返回0。int Isprime(Lint n) int x4=2,3,4,5,i; Lint te

34、mp0,temp1,temp2; Init_Lint(&temp0,0,0); Init_Lint(&temp1,0,0); Init_Lint(&temp2,0,0); for(i=0;i<4;i+) Lint_Sub(&n,&ONE, &temp0); Set_Lint(&temp2,1,xi); Mexp_Lint( temp2,temp0, &temp1,n); if(Cmp_Lint(temp1,ONE)!=0)return 0; return 1; / genprime函數(shù)功能：仿照PGP中確定大質(zhì)數(shù)的方法生成n

35、位大素數(shù)p。int genprime(Lint *p , int n) int i,flage; unsigned int primelist64=2 ,3,5,7,11,13,17,19,23,29,31,37,41,43, 47,53,59,61,67,71,73,79,83,89,97,101, 103,107,109,113,127,131,137,139,149,151, 157,163,167,173,179,181,191,193,197,199, 211,223,227,229,233,239,241,251,257,263, 269,271,277,281,283,293,3

36、07,311; /質(zhì)數(shù)篩選表 Lint temp0,temp1,temp2,temp3; Init_Lint(&temp0,0,0); Init_Lint(&temp1,0,0); Init_Lint(&temp2,0,0); Init_Lint(&temp3,0,0); Rand_Lint(&temp0 , n); temp0.n0=temp0.n0|1; /把隨機生成的大整數(shù)的最后一個比特位通過或運算置1，保證它是奇數(shù)。 while(1) do flage =0; for(i=0;i<64;i+) /for循環(huán)利用篩選表進行篩選。Set_Lin

37、t(&temp1,1,primelisti);Lint_Div(&temp0,&temp1,&temp2,&temp3); if(Cmp_Lint(temp3,ZERO)=0) flage=1;break; if(flage=1) Lint_Add(&temp0,&TWO,&temp1); 如果所選的大整數(shù)沒有通過篩選，則加2，重新篩選。 Cpy_Lint(&temp0,&temp1); while(flage=1); if (Isprime(temp0)=1) /判斷是否是素數(shù)，若是返回大整數(shù)。 Cpy_Lint

38、(p,&temp0); return 1; else Lint_Add(&temp0,&TWO,&temp1); /如果所選的大整數(shù)不是素數(shù)，則加2，重新篩選 Cpy_Lint(&temp0,&temp1); / genKey函數(shù)功能：產(chǎn)生密鑰。具體使用Euclid函數(shù)生成e的逆元d。int genKey(Lint p,Lint q,Lint e,Lint *d,Lint *n) Lint z,temp; Init_Lint(&z,0,0); Init_Lint(&temp,0,0); Lint_Mul(&p,&q

39、,n); Lint_Sub(&p,&ONE,&temp); Cpy_Lint(&p,&temp); Lint_Sub(&q,&ONE,&temp); Cpy_Lint(&q,&temp); Lint_Mul(&p,&q,&z); Euclid( z, e,d,&temp); if (temp.n0!=1) return 0; return 1; / Encrypt函數(shù)功能：實現(xiàn)對M加密,即：C=mod nint Encrypt(Lint M,Lint e,Lint n,Lint *C

40、) Mexp_Lint(M,e,C,n); /對明文模冪運算，求出密文 return 1; / Decrypt函數(shù)功能：實現(xiàn)對C解密,即：M=(mod n)int Decrypt(Lint C,Lint d,Lint n,Lint *M) Mexp_Lint(C,d,M,n); /對密文模冪運算，求出明文文 return 1; / reset函數(shù)功能：實現(xiàn)加解密之前的初始化，主要是設置ZERO,ONE,TWO變量int reset() Init_Lint(&ZERO,1,0); Init_Lint(&ONE,1,1); Init_Lint(&TWO,1,2); sran

41、d(time(NULL) ); return 1;/ outLint函數(shù)功能：在屏幕上輸出大整數(shù)a。int outLint(Lint a,char *ch) int i;printf("%s(",ch);for(i=a.length-1;i>0;i-)printf("%d,",a.ni); printf("%d)nn",a.n0);return 1; /_tmain是主函數(shù)。int _tmain(int argc, _TCHAR* argv)int i,j,k,fp1,fp2,fp3，block;/*以下定義的三個數(shù)組，存儲了已

42、經(jīng)生成的密鑰。num1存儲n, num2存儲e ,num3存儲d。 它們是由兩個大整數(shù)根據(jù)密鑰生成算法生成的，這兩個大整數(shù)的65536進制表示為：p=( 56341,44128,10452,31766,16477,6106,47982,25837,47849,42703,57844,33660,29050,15094,35675,47275,13929,47484,26103,63353,48462,46390,27222,12514,44259,43507,11299,55688,42703,40789,20607,5014,41207)q=( 22533,39752,53065,58105

43、,65008,6749,52002,20802,62369,11661,19298,35012,61519,24993,23723,32165,41488,54952,15816,45227,56713,30042,880,16242,53127,45253,18120,58298,36822,45169,16108,40565)這兩個大整數(shù)的乘積可以使模數(shù)n達到1024bit的長度*/unsigned int num165=10567,14761,1372,53568,17379,21756,52376, 62126,16750,27846,724,46574,12476,30055, 21

44、998,65355,188,19064,36274,60129,64576, 15721,44628,24949,53734,15213,6416,10161, 61156,60925,3632,15352,44198,40893,23342, 35721,51218,65260,6212,61225,326,57391, 38933,17076,61370,59632,50211,50157,54511, 8424,50839,3718,43798,43777,21693,34438, 14977,48272,2572,31888,48550,59918,58054, 17046,12275

45、, num24=33571,43045,33337,57736, num365=39083,47493,30050,23813,30775,16293,19261, 12608,10511,33180,11082,54551,64087,27213, 35271,411,55754,54307,4495,57550,43288, 39208,819,61700,15672,6186,18920,64599, 38621,44584,15479,6173,29554,17641,53319, 36489,2631,57732,20907,29597,55538,56620, 17278,4683

46、,10179,18900,12024,24151,60164, 30044,48123,44771,21923,35859,42548,3998, 14550,240,56061,34664,60976,53075,12301,42780,3877,;Lint C,M,temp; Lint e,z,d,p,q,n; char select; /*下面定義的共用體，用來把字符數(shù)字化。首先把明文中的偶數(shù)個字符讀入共用體的成員char ch中，再從共用體成員unsigned short l中依次讀出，這樣就把兩個字符組成一個兩字節(jié)的short型數(shù)據(jù)。 union char ch2*MAX; unsi

47、gned short lMAX; num,buffer;char *filename1="M:Example.txt",*filename2="M: cryptograph",*filename3="M: Decrypt.txt" Init_Lint(&C,0,0); Init_Lint(&M,0,0); Init_Lint(&temp,0,0); Init_Lint(&e,0,0); Init_Lint(&z,0,0); Init_Lint(&d,0,0); Init_Lint(&am

48、p;p,0,0); Init_Lint(&q,0,0); Init_Lint(&n,0,0);reset(); /初始化if(fp1=open( filename1,0)=-1) printf("不能打開文件n"); return 0; if(fp2=open( filename2,2)=-1) printf("不能打開文件n"); return 0; if(fp3=open( filename3,2)=-1) printf("不能打開文件n"); return 0; /以上語句用來打開文件/以下的多個printf語句

49、，用來輸出選擇信息。printf("n*n"); printf("* *n"); printf("* 1.使用已經(jīng)生成的密鑰進行加解密 *n"); printf("* 2.重新生成密鑰進行加解密 *n"); printf("* 3.退出該程序 *n"); printf("*n"); printf("請選擇（1、2或3）：");/以下程序根據(jù)用戶的不同選擇，進行相應的操作。如果選擇“1.使用已經(jīng)生成的密鑰進行加解密”那么就使用已經(jīng)生成的密鑰進行加解密。如果選

50、擇“2.重新生成密鑰進行加解密“那么就重新生成密鑰，包括生成：p,q,e 并且計算出 n與d，然后進行加解密。 while(1) select=getch(); printf("%cn",select); if(select='1') for(i=0;i<65;i+) Set_Lint(&n,i+1,num1i); for(i=0;i<4;i+) Set_Lint(&e,i+1,num2i); for(i=0;i<65;i+) Set_Lint(&d,i+1,num3i); Block=64;goto ll; else if (select='2') genprime(&p ,PL); /生成p genprime(&a