非对称密码算法

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业实验4 非对称密码算法RSA（验证型）实验目的通过实际编程了解非对称密码算法RSA的加密和解密过程，加深对非对称密码算法的认识。实验原理对称密码算法要求通信双方通过交换密钥实现使用同一个密钥，这在密钥的管理、发布和安全性方面存在很多问题，而非对称密码算法解决了这个问题。加密密钥和解密密钥是不同的，其中加密密钥是可以公开的，解密密钥是要求保密的，并且不能用其中的一个推导出另一个。它的安全性是建立在“大数分解和素性检测”这个数论难题的基础上，即将两个大素数相乘在计算上容易实

2、现，而将该乘积分解为两个大素数因子的计算量相当大。虽然它的安全性还未能得到理论证明，但经过30年的密码分析和攻击，迄今仍然被实践证明是安全的。实验环境运行Windows或者Linux操作系统的PC机，具有gcc（Linux）、VC（Windows）等C语言编译环境。实验内容和步骤1、为了加深对算法的了解，根据已知参数：，手工计算公私钥，并对明文进行加密，然后对密文进行解密。2、编写程序，加密一段文字，了解算法原理。尝试加密一大段文字，记录程序的运行时间。使用DES算法加密相同的文字，比较两种算法加密的速度。3、编写一个程序，随机选择3个 较大的数 ，计算 ，记录 程序运行时间。查阅资料给出简单

3、说明大数在计算机上是如何表示，如何进行运算。4、查阅资料，找出目前实际可行的素数判定法则，并比较各自的优缺点。五、实验步骤1、p=3，q=11 则n=pq=33,f(n)=20，选择e=7,则d=3 那么加密得c=29 解密得m=22、打开VC+，编写程序如下：#include#include #include #include /using namespace std;typedef struct RSA_PARAM_Tag/64 位数 unsigned _int64 p, q; /两个素数，不参与加密解密运算 unsigned _int64 f; /f=(p-1)*(q-1)，不参与加密解

4、密运算 unsigned _int64 n, e; /公匙，n=p*q，gcd(e,f)=1 unsigned _int64 d; /私匙，e*d=1 (mod f)，gcd(n,d)=1 unsigned _int64 s; /块长，满足2s=1; /a=a * a % n; /函数看起来可以处理64位的整数，但由于这里a*a在a=232时已经造成了溢出，因此实际处理范围没有64位 a=MulMod(a, a, n); b-; /c=a * c % n; /这里也会溢出，若把64位整数拆为两个32位整数不知是否可以解决这个问题。 c=MulMod(a, c, n); return c;/*R

5、abin-Miller素数测试，通过测试返回1，否则返回0。n是待测素数。注意：通过测试并不一定就是素数，非素数通过测试的概率是1/4*/long RabinMillerKnl(unsigned _int64 &n) unsigned _int64 b, m, s, z, r; m=n - 1; s=0; /0、先计算出m、s，使得n-1=m*2s，其中m是正奇数，s是非负整数 while(!(m & 1) +s; m=1; /1、随机取一个b，2=bn-1 b=2 + g_Rnd.Random(n - 3); /2、计算z=bm mod n z=PowMod(b, m, n); /3、如果z

6、=1，通过测试 if(z = 1) return 1; /4、令r=0 r=0; /5、如果z=n-1，通过测试 while(z != n - 1) /6、如果i=l，非素数，结束 if(r = (s-1) return 0; /7、z=z2 mod n，i=i+1 z=PowMod(z,2,n); +r; /8、循环到5 return 1;/*Rabin-Miller素数测试，循环调用核心loop次全部通过返回1，否则返回0*/long RabinMiller(unsigned _int64 &n, long loop) /先用小素数筛选一次，提高效率 for(long k=0; k g_P

7、rimeCount; k+) if(n%g_PrimeTablek = 0) return 0; /循环调用Rabin-Miller测试loop次，使得非素数通过测试的概率降为(1/4)loop for(long i=0; i loop; i+) if(!RabinMillerKnl(n) return 0; return 1;/*随机生成一个bits位(二进制位)的大素数，最多32位*/unsigned _int64 RandomPrime(char bits) unsigned _int64 base; do base= (unsigned long)1 q ? p : q; unsign

8、ed _int64 b=p y) 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; return x;/*随机产生一个RSA加密参数*/RSA_PARAM RsaGetParam(void) RSA_PARAM Rsa= 0 ; unsigned _int64 t; Rsa.p=RandomPrime(16); /随机生成两个素数/Rsa.p=11;Rsa.q=23; Rsa.q=RandomPrime(16); Rsa.n=Rsa.p * Rsa.q; Rsa.f=(Rsa.

9、p - 1) * (Rsa.q - 1); do Rsa.e=g_Rnd.Random(65536); /小于216，65536=216 Rsa.e|=1; /保证最低位是1，即保证是奇数，因f一定是偶数，要互素，只能是奇数 while(EuclidGcd(Rsa.e, Rsa.f) != 1); /由de=1 mod f来求d;Rsa.d=Euclid(Rsa.e, Rsa.f); Rsa.s=0; t=Rsa.n 1; while(t) Rsa.s+; /s=log2(n) t=1; return Rsa;/*拉宾米勒测试,素性检测测试程序.非主要程序.*/RSA加密解密/*/void T

10、estRSA(void) RSA_PARAM r;/ 明文 /char pSrc=abcdefghijklmnopqrstuvwxyz;int pSrc2=165,31; /const unsigned long Len=sizeof(pSrc);const unsigned long Len=2;/密文信息unsigned _int64 pEncLen;/unsigned char *q, pDecn; unsigned _int64 pDecLen; r=RsaGetParam(); printf( p= %I64u n,r.p);printf( q= %I64u n,r.q);print

11、f( 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(unsigned long j=0; j Len; j+) pEncj=PowMod(pSrcj, r.e, r.n);printf( %I64u n,pEncj); coutDecode:en

12、dl; for(unsigned long i=0; i Len; i+) pDeci=PowMod(pEnci, r.d, r.n); /couthex(unsigned long)pDeci ;printf( %I64u n,pDeci); coutendl; /cout(char *)pDecendl;/* */int main(void)clock_t start,end;start=clock();long times; TestRSA();end=clock();times=1000*(end-start);cout花费的时间为:timesendl; return 0;调试程序，程

13、序运行如下：3、打开VC+，编写程序如下：#include#include #include#include#include#include#include /using namespace std;int main()clock_t start,end;long times;long x,e,n;cout随机产生3个大数:endl;/x=1000*(rand()%11)+100*(rand()%11)+10*(rand()%11)+rand()%11;x=*(rand()%11)+*(rand()%11)+10000*(rand()%11)+1000*(rand()%11)+100*(ran

14、d()%11)+10*(rand()%11)+rand()%11;e=*(rand()%11)+*(rand()%11)+10000*(rand()%11)+1000*(rand()%11)+100*(rand()%11)+10*(rand()%11)+rand()%11;n=*(rand()%11)+*(rand()%11)+10000*(rand()%11)+1000*(rand()%11)+100*(rand()%11)+10*(rand()%11)+rand()%11;coutx=x e=e n=nendl;start=clock();coutpow(x,e)endl;long ans

15、wer=(int)pow(x,e)%n;/指数运算end=clock();times=1000*(end-start);cout花费的时间为:timesendl;return 0;调试运行如下：计算机上大数表示方法：将大数看作一个n进制数组,对于目前的32位系统而言,n可以取值为2的32次方,即0 x,假如将一个1024位的大数转化成0 x进制,它就变成了32位,而每一位的取值范围就不是0-1或0-9,而是0-0 xfffffff.我们正好可以用一个无符号长整数来表示这一数值.所以1024位的大整数就是一个有32个元素的unsigned long数组.而且0 x进制的数组排列与2进制流对于计算

16、机来说,实际上是一回事,但是我们完全可以针对unsighed long数组进行”竖式计算”,而循环规模被降低到了32次之内,并且算法很容易理解.4、素性测试方法：所谓素数，是指除了能补1和它本身整除而不能被其他任何数整除的数。据此，只需用2到N-1去除N，如果都除不尽，则为素数 （1）flag=1,i=2(2)If n mod i=0 then flag=1 else i=i+1(3)If flag=0 and in-1 then(2) else (4)(4)If flag=0 then write yes else no在最坏的情况下，即N为素数，算法需要执行N-2次，时间复杂性太大。只需用2到根下N去除N，即可，于是上述算法改为（3）If flag=0 and i=int(根N) then(