《RSA算法的实现》由会员分享，可在线阅读，更多相关《RSA算法的实现（8页珍藏版）》请在金锄头文库上搜索。
1、 密码学实验报告 实验八、RSA算法的实现一、 实验目的与意义掌握并实现RSA算法。二、 实验环境 Windows xp sp2 Microsoft visual c+6.0三、 实验原理1）非对称加密算法需要两个密钥：公开密钥（publickey）和私有密钥（privatekey）。公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。 非对称加密算法实现机密信息交换的基本过程是：甲方生成一对密钥并将其中的一把作为公用密钥向其它
2、方公开；得到该公用密钥的乙方使用该密钥对机密信息进行加密后再发送给甲方；甲方再用自己保存的另一把专用密钥对加密后的信息进行解密。非对称加密算法另一方面，甲方可以使用乙方的公钥对机密信息进行签名后再发送给乙方；乙方再用自己的私匙对数据进行验签。1甲方只能用其专用密钥解密由其公用密钥加密后的任何信息。 非对称加密算法的保密性比较好，它消除了最终用户交换密钥的需要。非对称密码体制的特点：算法强度复杂、安全性依赖于算法与密钥但是由于其算法复杂，而使得加密解密速度没有对称加密解密的速度快。对称密码体制中只有一种密钥，并且是非公开的，如果要解密就得让对方知道密钥。所以保证其安全性就是保证密钥的安全，而非对
3、称密钥体制有两种密钥，其中一个是公开的，这样就可以不需要像对称密码那样传输对方的密钥了。这样安全性就大了很多。2 ） 利用CC+实现RSA算法的加、解密运算。具体包括：1) 利用扩展的EUCLID计算 a mod n 的乘法逆元；2) Miller-Rabin素性测试算法对一个给定的大数进行测试；3) 实现的运算，并计算；4) 利用Fermat定理手工计算，并与3）计算的结果对比；5) 实现RSA算法。并对I LOVE THE PEOPLES REPUBLIC OF CHINA加解密。说明：为了方便实现，分组可以小一点，比如两个字母一组。字母及其数字编码字母及其数字编码空格 00N 14A 0
4、1O 15B 02P 16C 03Q 17D 04R 18E 05S 19F 06T 20G 07U 21H 08V 22I 09W 23J 10X 24K 11Y 25L 12Z 26M 13四、 实验代码：#include #include #include using namespace std;int Euclid(int a,int n)/n大于aint x,y,r;x=n;y=a;for(int i=0;)if(y=0)return x;if(y=1)return y; r=x%y;x=y;y=r;double extenEuclid(double a,double n)/利用扩展
5、的EUCLID计算 a mod n 的乘法逆元double x1=1,x2=0,x3=n,y1=0,y2=1,y3=a,Q;double t1,t2,t3;for(int i=0;) if(y3=0) return x3; coutno reverseendl; if(y3=1) return y2; Q=int(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;bool Rabin(int a,int n)/Miller-Rabin素性测试算法对一个给定的大数进行测试vector
6、b;unsigned int N=n-1;for(int i=0,j=1; i+)if(jN)break;if( (N i) & (unsigned int)1 ) b.push_back(1);elseb.push_back(0);j*=2;/将n-1表示成二进制形式for(int k=0;kb.size();k+)coutbk;cout=0;ii-)x=d;d=(d*d)%n;if(d=1&x!=1&x!=n-1)return false;if(bii=1)d=(d*a)%n;if(d!=1)return false;return true;double quickindex1(doubl
7、e a,double m,double n)/实现am mod n 的运算vector b;unsigned double N=m;for(int ii=0,j=1;ii+)if(jN)break;if(Nii)& (unsigned double) 1)b.push_back(1);elseb.push_back(0);j*=2;double c=0,d=1;for(int i=b.size()-1;i=0;i-)c*=2;d=(d*d)-int(d*d)/n)*n;if(bi=1)c+=1;d=(d*a)-int(d*a)/n)*n;return d;void transfer(char
8、cypher,double c)int m100=0;for(int i=0,j=0;cypherj!=0;i+=2)if(cypherj= )mi=0;mi+1=0;elsemi=cypherj-64;if(mi10)mi+1=mi;mi=0;elsemi+1=mi%10;mi=mi/10;j+;for(int k2=0;k22*strlen(cypher);k2+)coutmk2;coutendl;/int c100=0;for(int k=0,n=0;k2*strlen(cypher);k+=4)cn=mk*1000+mk+1*100+mk+2*10+mk+3;n+;for(;cn-11
9、000;)/最后一个数填充零,不过此例可要可不要cn-1*=10;void main()double c100=0;double a100=0;double b100=0;char cypher=I LOVE THE PEOPLES REPUBLIC OF CHINA;/对“我爱中华人民共和国”加解密 transfer(cypher,c);/字母变数字的过程for(int k1=0;ck1!=0;k1+)coutck1 ;/选取两个素数p=563，q=823double n=0, fn=0, p=563,q=823,d=0;n=p*q;fn=(q-1)*(p-1);/选e与fn互素for(do
10、uble e=2;efn;e+=3)if(Euclid(e,fn)=1)break;d=extenEuclid(e,fn); coutendl密码和密钥e d and n:;coute d nendl;/加密过程coutendl加密：;for(int i=0;ci!=0;i+)ai=quickindex1(ci,e,n);coutai ;coutendl解密：;/解密过程for(int j=0;aj!=0;j+)bj=quickindex1(aj,d,n);coutbj ; coutendl;五、 实验结果截图：六、 实验心得：本次实验做得是RSA加密算法。RSA加密算法是一种非对称加密算法，
11、其实这个算法本身的原理等都是很容易理解的，但是对于这个算法有几个细节的处理是需要注意的。这也是我在开始考虑这个代码时遇到问题。这几个问题主要是：1 两个大素数的产生。首先我们就得想出一个判断素数的算法。以前我们一般做素数的判断的时候一般都是用的试除法，及将该数与所有比他小的数都试除一遍，如果除1之外没有其他的数能够被他整除的话，那么这个数就是素数。但是在这个算法里面，我们要寻找的是两个大素数，所以如果对于一个大数，如果我们用试除法的话，那么可以预见的是这个算法的效率是非常非常低的。所以我们就应该寻找其他的算法。经过在网络上搜索资料及参考老师给定的代码，我发现了对于大素数的判定可以使用罗宾测试。这种算法可以有效地提高整个算法的效率。2 求一个数在mod n下的逆元。这个问题是我之前不知道怎么处理的。后来看了老师给定的代码之后明白了。通过这次的实验，我对密码学中相关的RSA知识有了更进一步的了解。当然，时间是检验真理的唯一标准，在学习生活中我们应该多加动手，勤思考，多编程，从而提升自己的能力。
