RSA算法的实现
一、实验目的
1、理解公钥密码体制基本原理。 2、理解并能够编写RSA算法。 3、熟练应用C++编程实现算法。
二、实验内容
利用C++编程实现RSA算法密码体制，算法描述参考课本P191-204。
三、实验原理 1、算法原理
步骤如下（这里设B为是实现着）
（1）B寻找出两个大素数p和q。 （2）B计算出n=p*q和?（n）=）（p-1）*（q-1）。
（3）B选择一个随机数e（0 （4）B使用欧几里得算法计算e的模余?（n）的乘法逆元素d。 （5）B在目录中公开n和e作为他的公开密钥，保密p、q和d。 加密时，对每一明文m计算密文 cΞme（modn） 解密时，对每一密文c计算明文 mΞcd（modn） 2、主要函数说明 （1）判断一个数是否为素数函数 bool prime(int n) { int m=sqrt(n); for(int i=2;i （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 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，则返回顺序执行③、④步直到满足 y3 =1 int 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 = 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 调用Prime（） Y 找出N=(p-1)*(q-1)的所有公约数 输入不等于N公约数的e 输入明文长度len及明文 N 调用ExtendEuclid（e，N，&d） i=0 i 五、实验心得和总结 我是这次试验主要负责人， 因为实验要分组做，每个人都要负责一个项目，在我们组 前两次实验中，我主要负责编写代码，像写报告、做PPT我几乎没有参与。但这次不一样了，所以的工作自己都要操起心来，比同组的同学多做一些工作，多分担一些，但是组员也很给力，实验的时候给了我很多建议与指导，制作PPT时给了我很多建议和帮助，有了团队精神所以效率提高了很多。所以这次试验下来感觉自己比以前做实验多学了好多东西，因为什么都要动手做，不懂得东西要查询清楚。 我感觉做实验对学生真正掌握知识很重要。上课的时候只是听老师讲RSA算法顶多就是学会理论知识，而真正实践动手做的时候就会发现自己漏洞百出，因为考虑问题不周全，编写代码的时候总是出错，编写的不完善，算法的功能没有全部体现，最后又翻看了课本、大一的时候学的C++课本、大二学的密码学基础课本和信息安全概论课本。巩固了一些已经忘记了的基础知识，有不太理解的算法实现方法就通过上网查询以及与同学讨论来解决。这次 写代码是我参与编写过的比较长的代码，RSA算法的算法原理我理解的比较清楚，所以对算法如何实现有一定的认识，编写起来也比较轻松一点。RSA算法用到了数论的知识，这次实验对我来说最难理解的就是扩展欧几里得算法，虽然在大二时学过了理论但实际编写还是有点难度的，通过查阅书籍及网上搜寻资料最终写出来扩展欧几里得算法实现函数。实在不容易啊。。。经过这次试验，我认识到了我编写代码的能力确实需要提升，需要平时更多的努力，相信以后在与组员以及其他同学的合作下，我能够学到更多知识。 六、参考资料 [1] William Stallings 《密码编码学与网络安全》 电子工业出版社 2012年 [2] 李继国 《信息安全密码学基础》 武汉大学出版社 2006年 [3] 李红娇 《信息安全概论》 中国电力出版社 2012年 七、实验结果截图