实验4非对称密码算法RSA实验目的通过实际编程了解非对称密码算法RSA的加密和解密过程，加深对非对称密码算法的认识。实验原理算法原理步骤如下（这里设B为是实现者）B寻找出两个大素数p和q。B计算出n=p*q和（n）=）（p-1）*（q-1）。B选择一个随机数e（0<e<(n)）,满足（e,(n))=1(即e与欧拉函数互素（n）)。B使用欧几里得算法计算e的模余（n）的乘法逆元素d。B在目录中公开n和e作为他的公开密钥，保密p、q和d。加密时，对每一明文m计算密文cΞm（modn）解密时，对每一密文c计算明文mΞc（modn）实验环境运行Windows或者Linux操作系统的PC机，具有gcc（Linux）、VC（Windows）等C语言编译环境。实验内容1、为了加深对算法的了解，根据输入的参数p，q，M，手工计算公私钥，并对明文进行加密，然后对密文进行解密。2、编写程序，加密一段文字，了解算法原理。尝试加密一大段文字，记录程序的运行时间。使用DES算法加密相同的文字，比较两种算法加密的速度。3、编写一个程序，随机选择3个较大的数，计算，记录程序运行时间。查阅资料给出简单说明大数在计算机上是如何表示，如何进行运算。4、查阅资料，找出目前实际可行的素数判定法则，并比较各自的优缺点。五、实验步骤1、主要函数说明（1）判断一个数是否为素数函数boolprime(intn){intm=sqrt(n);for(inti=2;i<m;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()。则解密后明文为56887812232、打开VC++，编写程序如下：#include<iostream.h>#include<math.h>intp,q,n,e,d,N,m1[100],m2[100],len;//判断一个数是否为素数，为素数返回1，否则返回0boolprime(intn){intm=sqrt(n);for(inti=2;i<m;i++){if(n%i==0)break;}if(i>=m)return1;elsereturn0;}