RSA算法实验报告

1、word RSA算法的实现一、实验目的1、理解公钥密码体制根本原理。2、理解并能够编写RSA算法。3、熟练应用C+编程实现算法。二、实验内容利用C+编程实现RSA算法密码体制，算法描述参考课本P191-204。3、 实验原理1、 算法原理步骤如下这里设B为是实现着（1） B寻找出两个大素数p和q。（2） B计算出n=p*q和n=p-1*q-1。（3） B选择一个随机数e0<e<(n),满足e,(n)=1 (即e与欧拉函数互素n)。（4） B使用欧几里得算法计算e的模余n的乘法逆元素d。（5） B在目录中公开n和e作为他的公开密钥，保密p、q和d。加密时，对每一明文m计算密文 cmm

2、odn解密时，对每一密文c计算明文 mcmodn2、 主要函数说明1判断一个数是否为素数函数bool prime(int n) int m=sqrt(n);for(int i=2;i<m;i+)if(n%i=0)break;if(i>=m)return 1;else return 0;2模幂算法 (这里以明文m为一个为例)令f=1；用for循环遍历从i=1到i=b，令f=(f*a)%n输出f，f的值即为模幂的结果。int multiplication(int a,int b,int n) int f=1;for(int i=1;i<=b;i+)f=(f*a)%n;return

3、 f;3扩展欧几里得算法由扩展欧几里得算法可以计算整数s和t ，使得s*e+t*N=e,N=1,那么e的乘法逆元等价于s mod N。定义变量 x1,x2,x3,y1,y2,y3,t1,t2,t3,q;令 x1 = y2 = 1; x2 = y1 = 0; 计算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;当 y3 =1时，*result = y2; result 的结果即为所求乘法逆元；如果y3 ！=1，那么返回顺序

4、执行、步直到满足 y3 =1int ExtendedEuclid( int f,int d ,int *result) int x1,x2,x3,y1,y2,y3,t1,t2,t3,q;x1 = y2 = 1;x2 = y1 = 0;if(f>=d)x3=f;y3=d;else x3=d;y3=f;while( 1 )if ( y3 = 1 )*result = y2; /* 两个数互素那么resutl为其乘法逆元，此时返回值为1 */ return 1; q = x3/y3; t1 = x1 - q*y1;t2 = x2 - q*y2; t3 = x3 - q*y3; x1 = y1;

5、x2 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3; 4主函数输入两个数字判断是否为素数，当不为素数时重新输入。如输入 17 11输入e，得到公钥。如输入e为7调用ExtendedEuclid(e,N,&d)函数，得到d，和私钥。如d=23输入明文长度。如输入 5 如输入明文为 56 88 78 12 23开始加密，调用加密函数 Encryption()。 那么输入密文为 78 11 56 177 133开始解密，调用解密函数 Decipher()。 那么解密后明文为 56 88 78 12 23四、算法流程图 开始输入两个素数p和q N调用Prim

6、eY 找出N=(p-1)*(q-1)的所有公约数输入不等于N公约数的e输入明文长度len及明文i=0调用ExtendEuclide，N，&dNi <len开始加密调用EncryptionY调用multiplication(m1i,e,n)i+输出密文i=0Ni <len开始解密调用Decipher()Y调用multiplication(m1i,e,n)i+输出明文，结束5、 实验心得和总结 我是这次试验主要负责人， 因为实验要分组做，每个人都要负责一个工程，在我们组前两次实验中，我主要负责编写代码，像写报告、做PPT我几乎没有参与。但这次不一样了，所以的工作自己都要操起心来

7、，比同组的同学多做一些工作，多分担一些，但是组员也很给力，实验的时候给了我很多建议与指导，制作PPT时给了我很多建议和帮助，有了团队精神所以效率提高了很多。所以这次试验下来感觉自己比以前做实验多学了好多东西，因为什么都要动手做，不懂得东西要查询清楚。 我感觉做实验对学生真正掌握知识很重要。上课的时候只是听老师讲RSA算法顶多就是学会理论知识，而真正实践动手做的时候就会发现自己漏洞百出，因为考虑问题不周全，编写代码的时候总是出错，编写的不完善，算法的功能没有全部表达，最后又翻看了课本、大一的时候学的C+课本、大二学的密码学根底课本和信息平安概论课本。稳固了一些已经忘记了的根底知识，有不太理解的算

8、法实现方法就通过上网查询以及与同学讨论来解决。这次写代码是我参与编写过的比拟长的代码，RSA算法的算法原理我理解的比拟清楚，所以对算法如何实现有一定的认识，编写起来也比拟轻松一点。RSA算法用到了数论的知识，这次实验对我来说最难理解的就是扩展欧几里得算法，虽然在大二时学过了理论但实际编写还是有点难度的，通过查阅书籍及网上搜寻资料最终写出来扩展欧几里得算法实现函数。实在不容易啊。经过这次试验，我认识到了我编写代码的能力确实需要提升，需要平时更多的努力，相信以后在与组员以及其他同学的合作下，我能够学到更多知识。6、 参考资料1 William Stallings 密码编码学与网络平安 电子工业出版

9、社 2012年2 李继国 信息平安密码学根底 武汉大学出版社 2006年3 李红娇 信息平安概论 中国电力出版社 2012年7、 实验结果截图八、实验源代码#include<iostream.h>#include<math.h>int p,q,n,e,d,N,m1100,m2100,len; /判断一个数是否为素数，为素数返回1，否那么返回0bool prime(int n) int m=sqrt(n);for(int i=2;i<m;i+)if(n%i=0)break;if(i>=m)return 1;else return 0;/扩展欧几里得算法求乘法逆

10、元,两数互素返回1int ExtendedEuclid( int f,int d ,int *result) int x1,x2,x3,y1,y2,y3,t1,t2,t3,q;x1 = y2 = 1;x2 = y1 = 0;if(f>=d)x3=f;y3=d;else x3=d;y3=f;while( 1 )if ( y3 = 1 )*result = y2; /* 两个数互素那么resutl为其乘法逆元，此时返回值为1 */ return 1; q = x3/y3; t1 = x1 - q*y1;t2 = x2 - q*y2; t3 = x3 - q*y3; x1 = y1;x2 =

11、y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3; /将十进制数据转化为二进制数组void to_bit(int b,int bit32) int n=0;while(b>0)bitn=b%2;n+;b/=2;/模幂算法int multiplication(int a,int b,int n) int f=1;for(int i=1;i<=b;i+)f=(f*a)%n;return f;/加密函数void Encryption()cout<<"*开始加密*"<<endl;int i;cout<<&q

12、uot;请输入明文："for(i=0;i<len;i+)cin>>m1i;for(i=0;i<len;i+)m2i=multiplication(m1i,e,n);cout<<"加密后的密文为："for(i=0;i<len;i+)cout<<m2i<<" "cout<<endl;/解密函数void Decipher()int i;cout<<"*开始解密*"<<endl;for(i=0;i<len;i+)m2i=mul

13、tiplication(m2i,d,n);cout<<"解密后的明文为："for(i=0;i<len;i+)cout<<m2i<<" "cout<<endl;void main()cout<<"输入两个素数p和q:n" while(1)cin>>p; if(prime(p)cout<<p<<"是素数"<<endl;break;elsecout<<p<<"不是素数&quo

14、t;<<endl;continue;while(1)cin>>q; if(prime(q)cout<<q<<"是素数"<<endl;break;elsecout<<q<<"不是素数"<<endl;continue;cout<<"两个素数为："<<p<<","<<q<<endl;n=p*q;N=(p-1)*(q-1); for(int i=2;i<N;i+) if(N%i=0) cout<<i<<" " cout<<endl;cout<<"请输入一个随机数，该数不等于上面的任何一个数！"<<endl; cin>>e; cout<<"公钥为<"<<e<<","<<n<<">"<<endl; if(ExtendedEuclid(e,N,&d)cout<&l