实验4---非对称密码算法RSA

实验4非对称密码算法RSA（验证型）一、实验目的通过实际编程了解非对称密码算法RSA的加密和解密过程，加深对非对称密码算法的认识。二、实验原理对称密码算法要求通信双方通过交换密钥实现使用同一个密钥，这在密钥的管理、发布和安全性方面存在很多问题，而非对称密码算法解决了这个问题。加密密钥和解密密钥是不同的，其中加密密钥是可以公开的，解密密钥是要求保密的，并且不能用其中的一个推导出另一个。它的安全性是建立在“大数分解和素性检测”这个数论难题的基础上，即将两个大素数相乘在计算上容易实现，而将该乘积分解为两个大素数因子的计算量相当大。虽然它的安全性还未能得到理论证明，但经过30年的密码分析和攻击，迄今仍然被实践证明是安全的。三、实验环境运行Windows或者Linux操作系统的PC机，具有gcc（Linux）、VC（Windows）等C语言编译环境。四、实验内容和步骤1、为了加深对RSA算法的了解，根据已知参数：2,11,3Mqp，手工计算公私钥，并对明文进行加密，然后对密文进行解密。2、编写RSA程序，加密一段文字，了解RSA算法原理。尝试加密一大段文字，记录程序的运行时间。使用DES算法加密相同的文字，比较两种算法加密的速度。3、编写一个程序，随机选择3个较大的数nex,,，计算nxemod，记录程序运行时间。查阅资料给出简单说明大数在计算机上是如何表示，如何进行运算。4、查阅资料，找出目前实际可行的素数判定法则，并比较各自的优缺点。五、实验步骤1、p=3，q=11则n=pq=33,f(n)=20，选择e=7,则d=3那么加密得c=29解密得m=22、打开VC++，编写程序如下：#includestdio.h#includeiostream.h#includestdlib.h#includetime.h//usingnamespacestd;typedefstructRSA_PARAM_Tag{//64位数unsigned__int64p,q;//两个素数，不参与加密解密运算unsigned__int64f;//f=(p-1)*(q-1)，不参与加密解密运算unsigned__int64n,e;//公匙，n=p*q，gcd(e,f)=1unsigned__int64d;//私匙，e*d=1(modf)，gcd(n,d)=1unsigned__int64s;//块长，满足2^s=n的最大的s，即log2(n)}RSA_PARAM;//小素数表,用于素性测试前,用小素数来初步筛选素数.conststaticunsigned__int64g_PrimeTable[]={3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};conststaticlongg_PrimeCount=sizeof(g_PrimeTable)/sizeof(long);//乘数constunsigned__int64multiplier=12747293821;//加数constunsigned__int64adder=1343545677842234541;//随机数类classRandNumber{private:unsigned__int64randSeed;/**/public:RandNumber(unsigned__int64s=0);unsigned__int64Random(unsigned__int64n);};/**/RandNumber::RandNumber(unsigned__int64s){if(!s){randSeed=(unsigned__int64)time(NULL);}else{randSeed=s;}}/*一个简单的随机数产生算法*/unsigned__int64RandNumber::Random(unsigned__int64n){randSeed=multiplier*randSeed+adder;returnrandSeed%n;}//定义了一个静态的类对象staticRandNumberg_Rnd;/*模乘运算，返回值x=a*bmodn*/inlineunsigned__int64MulMod(unsigned__int64a,unsigned__int64b,unsigned__int64n){returna*b%n;}/*模幂运算，返回值x=base^powmodn*/unsigned__int64PowMod(unsigned__int64base,unsigned__int64pow,unsigned__int64n){unsigned__int64r=1;pow=pow+1;while(pow!=1)//循环结果为pow(a,b)%c{r=r*base;r=r%n;pow--;}returnr;}/*{unsigned__int64a=base,b=pow,c=1;while(b){while(!(b&1)){b=1;//a=a*a%n;//函数看起来可以处理64位的整数，但由于这里a*a在a=2^32时已经造成了溢出，因此实际处理范围没有64位a=MulMod(a,a,n);}b--;//c=a*c%n;//这里也会溢出，若把64位整数拆为两个32位整数不知是否可以解决这个问题。c=MulMod(a,c,n);}returnc;}/*Rabin-Miller素数测试，通过测试返回1，否则返回0。n是待测素数。注意：通过测试并不一定就是素数，非素数通过测试的概率是1/4*/longRabinMillerKnl(unsigned__int64&n){unsigned__int64b,m,s,z,r;m=n-1;s=0;//0、先计算出m、s，使得n-1=m*2^s，其中m是正奇数，s是非负整数while(!(m&1)){++s;m=1;}//1、随机取一个b，2=bn-1b=2+g_Rnd.Random(n-3);//2、计算z=b^mmodnz=PowMod(b,m,n);//3、如果z==1，通过测试if(z==1){return1;}//4、令r=0r=0;//5、如果z=n-1，通过测试while(z!=n-1){//6、如果i==l，非素数，结束if(r==(s-1)){return0;}//7、z=z^2modn，i=i+1z=PowMod(z,2,n);++r;//8、循环到5}return1;}/*Rabin-Miller素数测试，循环调用核心loop次全部通过返回1，否则返回0*/longRabinMiller(unsigned__int64&n,longloop){//先用小素数筛选一次，提高效率for(longk=0;kg_PrimeCount;k++){if(n%g_PrimeTable[k]==0){return0;}}//循环调用Rabin-Miller测试loop次，使得非素数通过测试的概率降为(1/4)^loopfor(longi=0;iloop;i++){if(!RabinMillerKnl(n)){return0;}}return1;}/*随机生成一个bits位(二进制位)的大素数，最多32位*/unsigned__int64RandomPrime(charbits){unsigned__int64base;do{base=(unsignedlong)1(bits-1);//保证最高位是1base+=g_Rnd.Random(base);//再加上一个随机数base|=1;//保证最低位是1，即保证是奇数}while(!RabinMiller(base,30));//进行拉宾－米勒测试30次returnbase;//全部通过认为是素数}/*欧几里得除法求最大公约数*/unsigned__int64EuclidGcd(unsigned__int64&p,unsigned__int64&q){unsigned__int64a=pq?p:q;unsigned__int64b=pq?p:q;unsigned__int64t;if(p==q){returnp;//两数相等，最大公约数就是本身}else{while(b)//辗转相除法，gcd(a,b)=gcd(b,a-qb){a=a%b;t=a;a=b;b=t;}returna;}}//已知a、b，求x，满足a*x=1(modb)///相当于求解a*x-b*y=1的最小整数解//*/unsigned__int64Euclid(unsigned__int64&a,unsigned__int64&b){unsigned__int64m,e,i,j,x,y;longxx,yy;m=b;e=a;x=0;y=1;xx=1;yy=1;while(e){i=m/e;j=m%e;m=e;e=j;j=y;y*=i;if(xx==yy){if(xy){y=x-y;}else{y-=x;yy=0;}}else{y+=x;xx=1-xx;yy=1-yy;}x=j;}if(xx==0){x=b-x;}returnx;}/*随机产生一个RSA加密参数*/RSA_PARAMRsaGetParam(void){RSA_PARAMRsa={0};unsigned__int64t;Rsa.p=RandomPrime(16);//随机生成两个素数//Rsa.p=11;Rsa.q=23;Rsa.q=RandomPrime(16);Rsa.n=Rsa.p*Rsa.q;Rsa.f=(Rsa.p-1)*(Rsa.q-1);do{Rsa.e=g_Rnd.Random(65536);//小于2^16，65536=2^16Rsa.e|=1;//保证最低位是1，即保证是奇数，因f一定是偶数，要互素，只能是奇数}while(EuclidGcd(Rsa.e,Rsa.f)!=1);//由de=1modf来求d;Rsa.d=Euclid(Rsa.e,Rsa.f);Rsa.s=0;t=Rsa.n1;while(t){Rsa.s++;//s=log2(n)t=1;}returnRsa;}/*拉宾－米勒测试,素性检测测试程序.非主要程序.*///RSA加密解密//*/voidTestRSA(void){RSA_PARAMr;//明文//charpSrc[]=abcdefghijklmnopqrstuvwxyz;intpSrc[2]={165,31};//constunsignedlongLen=sizeof(pSrc);constunsignedlongLen=2;//密文信息unsigned__int64pEnc[Len];//unsignedchar*q,pDec[n];unsigned__int64pDec[Len];r=RsaGetParam();printf(p=%I64u\n,r.p);printf(q=%I64u\n,r.q);printf(f=(p-1)(q-1)=%I64u\n,r.f);printf(n=p*q=%I64u\n,r.n);printf(e=%I64u\n,r.e);printf(d=%I64u\n,r.d);printf(s=%I64u\n,r.s);//coutSource:pSrcendl;//g=(unsigned__int64*)pSrc;coutEncode:endl;for(unsignedlongj=0;jLen;j++){pEnc[j]=PowMod(pSrc[j],r.e,r.n);printf(%I64u\n,pEnc[j]);}coutDecode:endl;for(unsignedlongi=0;iLen;i++){pDec[i]=PowMod(pEnc[i],r.d,r.n);//couthex(unsignedlong)pDec[i]