RSA加密的简易实现.docVIP

安全学实验报告 —RSA加密解密的简单实现 华南师范大学 赵教授 RSA介绍： 当前最著名、应用最广泛的公钥系统RSA是在1978年，由美国麻省理工学院(MIT)的Rivest、Shamir和Adleman在题为《获得数字签名和公开钥密码系统的方法》的论文中提出的RSA算法是第一个既能用于数据加密也能用于数字签名的算法，因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA 密钥，其中之一是必威体育官网网址密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文件发送给个人，个人就可以用私钥解密接受。为提高必威体育官网网址强度，RSA密钥至少为500位长，一般推荐使用1024位。??公钥加密算法中使用最广的是RSA。RSA算法研制的最初理念与目标是努力使互联网安全可靠，旨在解决DES算法秘密密钥的利用公开信道传输分发的难题。而实际结果不但很好地解决了这个难题；还可利用RSA来完成对电文的数字签名以抗对电文的否认与抵赖；同时还可以利用数字签名较容易地发现攻击者对电文的非法篡改，以保护数据信息的完整性。此外，RSA加密系统还可应用于智能IC卡和网络安全产品。用2~之间的数去除int sushu(long m) {int i; for(i=2;i*i=m;i++) if(m%i==0)return 0; return 1;} （2）互质的判断： 在输入e之后需要判断e与ψ（n）是否互质，所以用该有判断互质的函数int gcd（）返回1（是），其他（否）。根据欧几里德算法 gcd(a,b)=gcd(b,a mod b) 证明：a可以表示成a = kb + r，则r = a mod b 假设d是a,b的一个公约数，则有 d|a, d|b，而r = a - kb，因此d|r 因此d是(b,a mod b)的公约数 假设d 是(b,a mod b)的公约数，则 d | b , d |r ，但是a = kb + r 因此d也是(a,b)的公约数 因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等int gcd(long a, long b) {if(b == 0)return a; return gcd(b, a % b);} （3）求乘法逆元： 因为需要计算私钥d= e ?-1(modψ(n))，所以有函数long ExtendedEuclid（）计算d并返回d的值，这里用到扩展欧几里德算法。大体思路与欧几里德算法一致： 如果gcd(a，b)=d，则存在m，n，使得d = ma + nb，称呼这种关系为a、b组合整数d，m，n称为组合系数。当d=1时，有 ma + nb = 1 ，此时可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。long ExtendedEuclid(long f,long d ,long *result) { int x1,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; return 0; } if ( y3 == 1 ) { *result = y2; return 1; } 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）快速幂模算法： 在加密解密时都要用到类似A ?B（mod C）的计算，当指数B较大时，如果先计算A ?B的值时间较慢，且结果过大会溢出。 依据模运算的性质（a*b）mod n=（（a mod n）*（b mod n））mod n 可以将A ?B分解为较小几个数的乘积分别进行模运算 例如（3 ^ 999）可以分解为(3 ^ 512) * (3 ^ 256) * (3 ^ 128) * (3 ^ 64) * (3 ^ 32) * (3 ^ 4) * (3 ^ 2) * 3? 这样只要做16次乘法把999转为2进制数：1111100111，其各位就是要乘的数。int a_b_Mod_c（long a, long b, long c）计算a ?b mod c的值并返回结果。 int a_b_Mod_c(long a, long b, long c) { int digit