实验四：RSA加密算法.doc

1、实验四：RSA加、解密算法实现姓名班级11信息安全学号实验目的通过上机操作，使同学生对公钥加密算法RSA密码体制的加、解过程有一个更加清晰地认识。通过本次实验，加深学生对公钥密码体制的认识，为后面的学习打下基础。实验内容及要求 1、在RSA密码体制中，有，其中、均为素数，现给定p=1874113084280153735306658132040384611093897935132757017046995662677351096773572253280762088015535511593，q=60191029407054636927655161587756444761379072535783988

2、2704111695696928780728208299489784763935240286491，以及公钥=58997，试求出私钥，使得.2、使用上述密钥，选取消息m=“学号+班级+姓名”，例如：11350023中山大学信息科学与技术学院2011级信息安全班张三，分别对其进行加密和解密操作（利用平方-乘算法）。实验结果（可续页）（包括实验代码、实验结果）结果如下：（注：消息的汉字为“11350026中山大学信息科学与技术学院2011级信息安全班叶宏彪”对应的拼音为”11350026zhongshandaxuexinxikexueyujishuxueyuan2011jixinxianquanb

3、anyehongbiao”）代码如下：#include#include #include#includeusing namespace std;/函数声明#define MAXINT 10000 /整数最大位数int compare(int a,int b);vector bigplus(vector ivec1,vector ivec2); /大整数加法vector bigsub(vector ivec1,vector ivec2); /大整数减法vector bigmult(vector ivec1,vector ivec2); /大整数乘法vector bigdiv(vector ive

4、c1,vector ivec2); /大整数除法vector bigmod(vector ivec1,vector ivec2); /大整数模运算int compares(vector ivec1,vector ivec2); /大整数比较vector ExtendEcuild(vector ivec1,vector ivec2); /扩展欧几里得算法求乘法逆int power(int m,int n); /幂级数vector decToBin(vector v); /大整数十进制转二进制?vector squAndMult(vector ivec1,vector ivec2,vector i

5、vec3); /平方-乘算法vector trans(string str); / 字符转换为整数/主函数int main() coutRSAendl; vector p; vector q; vector p1; vector q1; vector n; vector fin; vector e; vector d; vector m; vector s; vector s1; string str1; string str2; string str3; string str4; cout输入大素数：str1; cout输入大素数：str2; for(int i=0;istr1.size()

6、;+i) p.push_back(str1i-0); for(int i=0;istr2.size();+i) q.push_back(str2i-0); vector w; w.push_back(1); q1=bigsub(q,w); p1=bigsub(p,w); n=bigmult(p,q); fin=bigmult(p1,q1); cout输入公钥:str3; for(int i=0;istr3.size();+i) e.push_back(str3i-0); d=ExtendEcuild(fin,e); cout输入明文:str4; coutendl; coutendl; cout

7、p*q的乘积n为:endl; for(int i=0;in.size();i+) coutni; coutendl; cout(p-1)*(q-1)的乘积Fi(n)为:endl; for(int i=0;ifin.size();i+) coutfini; coutendl; cout由公钥计算得私钥d为：endl; for(int i=0;id.size();i+) coutdi; coutendl; cout公钥与私钥d的乘积为:endl; vector pro=bigmod(bigmult(e,d),fin); for(int i=0;ipro.size();i+) coutproi; c

8、outendl; m=trans(str4); cout明文翻译如下：endl; /将消息转换为整数 for(int i=0;im.size();i+) coutmi; coutendl; s=squAndMult(m,decToBin(e),n); s1=squAndMult(s,decToBin(d),n); cout明文加密如下：endl; for(int i=0;is.size();i+) coutsi; coutendl; cout密文解密如下：endl; int temp=0; O0qsdd44z for(int i =0;is1.size();i+) /逐位比较原文和解密后的消息

9、 if(mi=s1i) temp+; if(temp=s1.size()&temp=m.size() /如果原文和解密后的消息一致 for(int i=0;istr4.size();i+) coutstr4i; else cout解密失败”; /如果不一致 coutb0) return 1; /比较的位数确定返回值 else if (a0bi) return 1; else return -1; vector bigplus(vector ivec1,vector ivec2) vector ivec3;int aMAXINT,bMAXINT,cMAXINT; memset(a,0,sizeo

10、f(a); memset(b,0,sizeof(b); a0=ivec1.size(); b0=ivec2.size(); for(int i=0;iivec1.size();i+)ai+1=ivec1ivec1.size()-1-i; for(int i=0;ib0?a0:b0); for(i=0;iMAXINT;i+) ci=0; for (i=1;i=10) ci-=10; ci+1+; if (ci+10) len+; c0=len; for (i=len;i=1;i-) ivec3.push_back(ci); return ivec3;vector bigsub(vector iv

11、ec1,vector ivec2) vector ivec3;int aMAXINT,bMAXINT,cMAXINT; memset(a,0,sizeof(a); memset(b,0,sizeof(b); a0=ivec1.size(); b0=ivec2.size(); for(int i=0;iivec1.size();i+)ai+1=ivec1ivec1.size()-1-i; for(int i=0;ib0?a0:b0); for(i=0;i=1;i-) ivec3.push_back(ci); return ivec3; else if (compare(a,b)0) for (i

12、=1;i=len;i+) ci+=(ai-bi); if (ci0) ci+=10; ci+1-; else for (i=1;i=len;i+) ci+=(bi-ai); if (ci1 & clen=0) len-; c0=len;if(compare(a,b)=1;i-) ivec3.push_back(ci); return ivec3;vector bigmult(vector ivec1,vector ivec2) vector ivec3;int aMAXINT,bMAXINT,cMAXINT; memset(a,0,sizeof(a); memset(b,0,sizeof(b)

13、; a0=ivec1.size(); b0=ivec2.size(); for(int i=0;iivec1.size();i+)ai+1=ivec1ivec1.size()-1-i; for(int i=0;iivec2.size();i+)bi+1=ivec2ivec2.size()-1-i; int i,j,len; for (i=0;iMAXINT;i+) ci=0; for (i=1;i=a0;i+) for (j=1;j1 & clen=0) len-; c0=len; for (i=len;i=1;i-) ivec3.push_back(ci); return ivec3; ve

14、ctor bigdiv(vector ivec1,vector ivec2) vector ivec3; vector ivec4; int aMAXINT,bMAXINT,cMAXINT,dMAXINT; memset(a,0,sizeof(a); memset(b,0,sizeof(b); a0=ivec1.size(); b0=ivec2.size(); for(int i=0;iivec1.size();i+)ai+1=ivec1ivec1.size()-1-i; for(int i=0;iivec2.size();i+)bi+1=ivec2ivec2.size()-1-i; int

15、i,j,len; if (compare(a,b)0) ivec4.push_back(0); return ivec4; for (i=0;i=1;i-) for (j=d0;j=1;j-) dj+1=dj; d1=ai; d0+; if(compare(d,b)=0&q=0) for (j=1;j=d0;j+) dj-=bj; if (dj0 & dj=0) j-; d0=j; ci+; c0=q; for (i=c0;i=1;i-) ivec3.push_back(ci); for (i=d0;i=1;i-) ivec4.push_back(di); return ivec3;vecto

16、r bigmod(vector ivec1,vector ivec2) vector ivec3; vector ivec4; int aMAXINT,bMAXINT,cMAXINT,dMAXINT; memset(a,0,sizeof(a); memset(b,0,sizeof(b); a0=ivec1.size(); b0=ivec2.size(); for(int i=0;iivec1.size();i+)ai+1=ivec1ivec1.size()-1-i; for(int i=0;iivec2.size();i+)bi+1=ivec2ivec2.size()-1-i; int i,j

17、,len; if (compare(a,b)=1;i-) ivec4.push_back(ai); return ivec4; for (i=0;i=1;i-) for (j=d0;j=1;j-) dj+1=dj; d1=ai; d0+; if(compare(d,b)=0&q=0) for (j=1;j=d0;j+) dj-=bj; if (dj0 & dj=0) j-; d0=j; ci+; c0=q; for (i=c0;i=1;i-) ivec3.push_back(ci); for (i=d0;i=1;i-) ivec4.push_back(di); return ivec4;int

18、 compares(vector ivec1,vector ivec2)int aMAXINT,bMAXINT; memset(a,0,sizeof(a); memset(b,0,sizeof(b); a0=ivec1.size(); b0=ivec2.size(); for(int i=0;iivec1.size();i+)ai+1=ivec1ivec1.size()-1-i; for(int i=0;ib0) return 1; else if (a0bi) return 1; else return -1; vector ExtendEcuild(vector ivec1,vector

19、ivec2)vector a0,b0,t0,t,q,r,temp,tqt;a0=ivec1;b0=ivec2;t0.push_back(0);t.push_back(1);q=bigdiv(a0,b0);r=bigsub(a0,bigmult(q,b0);while(r00)tqt=bigsub(t0,bigmult(q,t);if(tqt0=0)temp=bigsub(ivec1,tqt);else temp=bigsub(ivec1,bigmod(tqt,ivec1);elsetemp=bigmod(tqt,ivec1);t0=t;t=temp;a0=b0;b0=r;q=bigdiv(a0

20、,b0);r=bigsub(a0,bigmult(q,b0);return t;int power(int m,int n)int sum=1;if(n=0&m!=0) return 1;elsefor(int i=0;in;i+)sum*=m;return sum;vector decToBin(vector v)vector ivec1;int sum(0);string binary; char ch; int i, j;while(1) j = v.size() - 1; ch = vj % 2 + 0; binary.insert(binary.begin(), 1, ch); fo

21、r(sum = 0, i = 0; i = j; i+) if(i 1) = 1; sum += vi; if(sum = 0) break; for(int i =0;ibinary.size();i+)ivec1.push_back(binaryi-0);return ivec1;vector squAndMult(vector ivec1,vector ivec2,vector ivec3)vector ivec5;ivec5.push_back(1);for(int i=0;iivec2.size();i+)ivec5=bigmod(bigmult(ivec5,ivec5),ivec3);if(ivec2i=1)ivec5=bigmod(bigmult(ivec5,ivec1),ivec3);return ivec5;vector trans(string str)vector v;vector s;for(int i=0;istr.size();i+)if(stri=a)v.push_back(stri-a+1);coutendl;for(int i=0;iv.size();i+)if(vi10)s.push_back(vi);elses.push_back(vi/10);s.push_back(vi%10);return s;