RSA算法实验报告

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（0e(n)）,满足（e,(n))=1(即e与欧拉函数互素（n）)。（4）B使用欧几里得算法计算e的模余（n）的乘法逆元素d。（5）B在目录中公开n和e作为他的公开密钥，保密p、q和d。加密时，对每一明文m计算密文cΞme（modn）解密时，对每一密文c计算明文mΞcd（modn）2、主要函数说明（1）判断一个数是否为素数函数boolprime(intn){intm=sqrt(n);for(inti=2;im;i++){if(n%i==0)break;}if(i=m)return1;elsereturn0;}（2）模幂算法(这里以明文m为一个为例)①令f=1；②用for循环遍历从i=1到i=b，令f=(f*a)%n③输出f，f的值即为模幂的结果。intmultiplication(inta,intb,intn){intf=1;for(inti=1;i=b;i++){f=(f*a)%n;}returnf;}（3）扩展欧几里得算法由扩展欧几里得算法可以计算整数s和t，使得s*e+t*N=（e,N）=1,则e的乘法逆元等价于smodN。①定义变量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=1intExtendedEuclid(intf,intd,int*result){intx1,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*/return1;}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）主函数①输入两个数字判断是否为素数，当不为素数时重新输入。如输入1711②输入e，得到公钥。如输入e为7③调用ExtendedEuclid(e,N,&d)函数，得到d，和私钥。如d=23④输入明文长度。如输入5如输入明文为5688781223⑤开始加密，调用加密函数Encryption()。则输入密文为781156177133⑥开始解密，调用解密函数Decipher()。则解密后明文为5688781223四、算法流程图开始输入两个素数p和q调用Prime（）找出N=(p-1)*(q-1)的所有公约数输入不等于N公约数的eYN五、实验心得和总结我是这次试验主要负责人，因为实验要分组做，每个人都要负责一个项目，在我们组前两次实验中，我主要负责编写代码，像写报告、做PPT我几乎没有参与。但这次不一样了，所以的工作自己都要操起心来，比同组的同学多做一些工作，多分担一些，但是组员也很给力，实验的时候给了我很多建议与指导，制作PPT时给了我很多建议和帮助，有了团队精神所以效率提高了很多。所以这次试验下来感觉自己比以前做实验多学了好多东西，因为什么都要动手做，不懂得东西要查询清楚。我感觉做实验对学生真正掌握知识很重要。上课的时候只是听老师讲RSA算法顶多就是学会理论知识，而真正实践动手做的时候就会发现自己漏洞百出，因为考虑问题不周全，编写代码的时候总是出错，编写的不完善，算法的功能没有全部体现，最后又翻看了课本、大一的时候学的C++课本、大二学的密码学基础课本和信息安全概论课本。巩固了一些已经忘记了的基础知识，有不太理解的算法实现方法就通过上网查询以及与同学讨论来解决。这次调用ExtendEuclid（e，N，&d）开始加密调用Encryption（）输入明文长度len及明文ilen调用multiplication(m1[i],e,n)i++输出密文开始解密调用Decipher()i=0ileni++调用multiplication(m1[i],e,n)输出明文，结束YNYNi=0写代码是我参与编写过的比较长的代码，RSA算法的算法原理我理解的比较清楚，所以对算法如何实现有一定的认识，编写起来也比较轻松一点。RSA算法用到了数论的知识，这次实验对我来说最难理解的就是扩展欧几里得算法，虽然在大二时学过了理论但实际编写还是有点难度的，通过查阅书籍及网上搜寻资料最终写出来扩展欧几里得算法实现函数。实在不容易啊。。。经过这次试验，我认识到了我编写代码的能力确实需要提升，需要平时更多的努力，相信以后在与组员以及其他同学的合作下，我能够学到更多知识。六、参考资料[1]WilliamStallings《密码编码学与网络安全》电子工业出版社2012年[2]李继国《信息安全密码学基础》武汉大学出版社2006年[3]李红娇《信息安全概论》中国电力出版社2012年七、实验结果截图八、实验源代码#includeiostream.h#includemath.hintp,q,n,e,d,N,m1[100],m2[100],len;//判断一个数是否为素数，为素数返回1，否则返回0boolprime(intn){intm=sqrt(n);for(inti=2;im;i++){if(n%i==0)break;}if(i=m)return1;elsereturn0;}//扩展欧几里得算法求乘法逆元,两数互素返回1intExtendedEuclid(intf,intd,int*result){intx1,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*/return1;}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;}}//将十进制数据转化为二进制数组voidto_bit(intb,intbit[32]){intn=0;while(b0){bit[n]=b%2;n++;b/=2;}}//模幂算法intmultiplication(inta,intb,intn){intf=1;for(inti=1;i=b;i++){f=(f*a)%n;}returnf;}//加密函数voidEncryption(){cout******************开始加密*****************endl;inti;cout请输入明文：;for(i=0;ilen;i++)cinm1[i];for(i=0;ilen;i++)m2[i]=multiplication(m1[i],e,n);cout加密后的密文为：;for(i=0;ilen;i++)coutm2[i];coutendl;}//解密函数voidDecipher(){inti;cout*************开始解密*************endl;for(i=0;ilen;i++)m2[i]=multiplication(m2[i],d,n);cout解密后的明文为：;for(i=0;ilen;i++)coutm2[i];coutendl;}voidmain(){cout输入两个素数p和q:\n;while(1){cinp;if(prime(p)){coutp是素数endl;break;}else{coutp不是素数endl;continue;}}while(1){cinq;if(prime(q)){coutq是素数endl;break;}else{coutq不是素数endl;continue;}}cout两个素数为：p,qendl;n=p*q;N=(p-1)*(q-1);for(inti=2;iN;i++){if(N%i==0){couti;}}coutendl;cout请输入一个随机数，该数不等于上面的任何一个数！endl;cine;cout公钥为e,nendl;if(ExtendedEuclid(e,N,&d))coute的乘法逆元是：dendl;cout私钥为d,nendl;cout请输入明文长度:;cinlen;Encryption();Decipher();}