RSA加密的简易实现要点.doc

《RSA加密的简易实现要点.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、安全学实验报告—RSA加密解密的简单实现华南师范大学赵教授RSA介绍：当前最著名、应用最广泛的公钥系统RSA是在1978年，由美国麻省理工学院(MIT)的Rivest、Shamir和Adleman在题为《获得数字签名和公开钥密码系统的方法》的论文中提出的。RSA算法是第一个既能用于数据加密也能用于数字签名的算法，因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文件发送给个人，个人就可以用私钥解密接受

2、。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。  公钥加密算法中使用最广的是RSA。RSA算法研制的最初理念与目标是努力使互联网安全可靠，旨在解决DES算法秘密密钥的利用公开信道传输分发的难题。而实际结果不但很好地解决了这个难题；还可利用RSA来完成对电文的数字签名以抗对电文的否认与抵赖；同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完整性。此外，RSA加密系统还可应用于智能IC卡和网络安全产品。一．系统总体方案：1.要求：编写RSA加密解密演示程序，用户自己输入两个素数P，Q以及公钥

3、E，程序判断P，Q为素数后计算得到公钥（e，n），私钥（d，n）并显示。输入明文密文并可以进行加密解密。2.数学原理：1.密钥的生成选择p,q为两个大的互异素数计算n=p*q,ψ(n)=(p-1)(q-1)选择整数e使gcd(ψ(n),e)=1（互质）,（1

4、modn)得到明文M。3.实现过程：1.输入p，q判断为素数，计算n=p*q，ψ（n）=（p-1）（q-1）2．输入e判断是否与ψ（n）互质，计算d=eˆ-1(modψ(n))3.输出公钥为（e，n）私钥为（d，n）4.输入明文（数字）M计算密文C=Mˆe(modn)5.输入密文C计算明文M=Cˆd(modn)二.设计思路：1.关键问题：（1）素数的判断：首先在输入p，q之后应该有一个函数intsushu（）可以判断p，q是否为素数，并返回1（是）或0（否）。考虑到程序中数据类型为long型，依次用2~√n之间的数去除n，如果能整除则不

5、为素数。该算法时间复杂度为O（√n）。intsushu(longm){inti;for(i=2;i*i<=m;i++)if(m%i==0)return0;return1;}（2）互质的判断：在输入e之后需要判断e与ψ（n）是否互质，所以用该有判断互质的函数intgcd（）返回1（是），其他（否）。根据欧几里德算法gcd(a,b)=gcd(b,amodb)证明：a可以表示成a=kb+r，则r=amodb假设d是a,b的一个公约数，则有14d

6、a,d

7、b，而r=a-kb，因此d

8、r因此d是(b,amodb)的公约数假设d是(b,amodb)

9、的公约数，则d

10、b,d

11、r，但是a=kb+r因此d也是(a,b)的公约数因此(a,b)和(b,amodb)的公约数是一样的，其最大公约数也必然相等所以若gcd（a，b）=1则a与b互质。intgcd(longa,longb){if(b==0)returna;returngcd(b,a%b);}（3）求乘法逆元：因为需要计算私钥d=eˆ-1(modψ(n))，所以有函数longExtendedEuclid（）计算d并返回d的值，这里用到扩展欧几里德算法。大体思路与欧几里德算法一致：如果gcd(a，b)=d，则存在m，n，使得d=ma+nb

12、，称呼这种关系为a、b组合整数d，m，n称为组合系数。当d=1时，有ma+nb=1，此时可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。longExtendedEuclid(longf,longd,long*result){intx1,x2,x3,y1,y2,y3,t1,t2,t3,q;x1=y2=1;x2=y1=0;x3=(f>=d)?f:d;y3=(f>=d)?d:f;while(1){if(y3==0){*result=x3;return0;}if(y3==1){*result=y2;return1;}q=x3/y3;t1=x

13、1-q*y1;t2=x2-q*y2;t3=x3-q*y3;x1=y1;x2=y2;x3=y3;y1=t1;y2=t2;y3=t3;}}（4）快速幂模算法：14在加密解密时都要用到类似AˆB（modC）的计算