RSA加密的简易实现

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

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

3、进行加密解密。2 . 数学原理 ：1 .密钥的生成 选才I p,q为两个大的互异素数计算n=p*q, 3（n）=（p-1）（q-1）选择整数e使gcd（少（n）,e）=1（互质），（1<e<3）计算d,使d=e ?-1（mod少（n）（求乘法逆元）公钥 Pk=e,n;私钥 Sk=d,n。(定义若a?x mod n =1,则称a与x对于模n互为逆元)2 .加密(用e,n)明文M<n 由C=M ? e(mod n)得到密文 C。3 .解密(用d,n)对于密文C 由M=C?d(mod n)得到明文 M3.实现过程：1. 输入p, q判断为素数，计算 n=p*q ,少(n) = (p

4、-1) (q-1 )2. .输入e判断是否与 少(n)互质，计算d= e ?-1(mod少(n)3. 输出公钥为(e, n)私钥为(d, n)4. 输入明文(数字)M计算密文C=M ? e(mod n)5. 输入密文C计算明文 M=C ?d(mod n)二.设计思路：1.关键问题：(1)素数的判断：首先在输入p, q之后应该有一个函数int sushu ()可以判断p, q是否为素数，并 返回1 (是)或0 (否)。考虑到程序中数据类型为long型，依次用2，n之间的数去除n,如果能整除则不为素数。该算法时间复杂度为O(v/n)oint sushu(long m)int i;for(i=2;i

5、*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，贝U r = a mod b假设d是a,b的一个公约数，则有3d|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)的公

6、约数因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等所以若gcd (a, b) =1则a与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

7、 + 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;

8、t2 = x2 - q*y2; t3 = x3 - q*y3;x1 = y1; x2 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3;在加密解密时都要用到类似 A ?B (mod C)的计算，当指数 B较大时，如果先计算 A ?B的值时间较慢，且结果过大会溢出。依据模运算的性质a a*b ) mod n= (a mod n) * (b mod n) mod n 可以将A ?的解 为较小几个数的乘积分别进行模运算例如(3 A 999 )可以分解为(3 A 512) * (3 A 256) * (3 A 128) * (3 A 64) * (3 A32) * (3

9、 a 4) * (3 a 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 digit32;long i,k,resualt = 1;i = 0;while(b) digiti+ = b%2;b >>= 1; for(k = i-1; k >= 0; k-) resualt=(resualt*resu

10、alt)%c;if(digitk=1) resualt=(resualt*a)%c; return resualt;2. 总操作界面:1. 输入两个素数P,Q2. 输入公钥 E3. 查看当前密钥信息4. 加密5. 解密6. 帮助0. 退出三.程序实现流程图:(1)流程图:(2)各功能模块:命令对应函数功能描述1input_P_Q输入素数P,Q2input_E输入公钥E3print_miyao显示密钥信息4jiami加密5jiemi解密帮助print_help四.程序测试:1 输入两个素数 p=47, q=71 则 n=47*71=3337；应为数字，请重新输入, 急为素数.请重新输入: 轻入第

11、二个素数3 71 力钥为r <0,333?> 私钥为:<0.3337>2.输入 e=79,计算得 d=e?-1 mod (p-1) (q-1 ) =79?-1 mod 3220=1019 因此公钥为(79,3337)私钥为(1019, 3337)私钥为<0 33 3V>输入一个小于3220的数怎：79队钥为：<79r3337>初钥为：<1019,3337>3 .输入明文688并加密4 .输入密文1570并解密制|八支刖笆曲 明二二688密文为 15705输入要解密的密文1570明文为：688L五.总结、改进思考：1 .大数类库的建立：

12、本程序作为RSAm密解密过程演示程序， 变量均为10ng型，因此密钥长度较小， 而RSA 的安全性建立在密钥长度很长，大素数难以分解的前提上。所以为了能够提高安全性，应该建立一个大数类库，对 512位或1024位大数进行存取，及简单运算。一个最容易理解的方法就是将大数用十进制表示，并将每一位（0 - 9）都做为一个单独的数用数组进行管理。做加减乘除等运算时，人工的对其进行进、借位。然而计算机对于10进制数的处理并不在行， 而且表示非2n进制的数会浪费很多空间， 所以应该采用8进制、 16进制、32进制、64进制的表示法，使得每一位数字都能占据一个完整的内存空间。目前 绝大多数PC机都是基于32

13、位运算的，所以采用2 ?32进制表示大数将会很大提高计算机的 处理效率。现实中，就使用32位的整数数组进行存储每一位数，另设一个布尔值表示正负。进行计算时常会遇到进位借位的情况，而且常常会超过2 ?32次方，幸好目前的编译器都支持64位整数，可以满足（232 - 1 ） *（ 232 - 1 ）以内的运算，所以使用 64位整数作为运算中间量将会是很好的选择。大数除了加减乘除等基本运算以外，还有一些如赋值、比较、左右移位、或、与等，为 了方便使用，我们可以利用面向对象的方法把大数进行封装，并利用C+的特性进行运算符重载，使它成为一个整体对象来进行操作。这样我们就可像使用int 一样来使用它了。2

14、 .大素数随机生成，以及判断：真正的RSA加密时密钥的生成应该是自动完成的，而不是用户手动制定 p, q, e。所以在使用大数类库后随之而来一个问题就是如何随机的生成两个大素数，以及大素数的判断。 由于素数有无穷多个， 且没有固定的生成方式， 所以大素数的生成基本是采用在一定范围内 （比如奇数，且不会被小素数整除的） 随机选取大数后再进行素数检测，直到有通过检测的数。因此大数的素数检测算法就是关键了，如果按照之前的素数检测算法需要依次除2到，n的数，时间复杂度 O（，n）太大。所以我们要用更为快速的算法。是目前公认米勒拉宾测试是一个不确定的算法，只能从概率意义上判定一个数可能是素数。的最高效的

15、素性测试之一。大体步骤如下：输入奇数n,判断n为素数或者合数。计算r和R,使得n _1 = 2r R, R奇。随即选择a, a zn 0。for i=0 to r2r R，计算b=a. R右a =br=1(modn),则输入合数。 R右a =b。三1(modn),则输入素数。设 j=maxi: bi # 1(mod n),则输入素数。若bj三1(modn),则输出素数，否则输出合数。参考书目：1刘嘉勇等应用密码学2胡道元闵京华网络安全3张四兰等可信赖的高效素数生成和检验算法附程序代码：#include<iostream.h>#include <stdlib.h>#inc

16、lude<stdio.h>void input_P_Q(long &P,long &Q,long &N,long &N1);void input_E(long &E,long &D,long n1);void print_miyao(long e,long n,long d);void jiami(long e,long n);void jiemi(long d,long n);void print_help();int sushu(long m);9int gcd(long a, long b);long ExtendedEucli

17、d(long f,long d ,long *result);int a_b_Mod_c(long a, long b, long c);void main()long P=0,Q=0,E=0,N=0,N1=0,D=0;cout<<"=RS儆拟="<<endl;cout<<" 1.输入两个素数 P,Qn"cout<<" 2.输入公钥 En"cout<<" 3.查看当前密钥信息n”;cout<<"4.加密 n”;cout<<"

18、;5.解密 n”;cout<<"6.帮助 n"cout<<"0.退出 n"cout<<"n输入你的选择："；long ch;do cin>>ch;switch(ch)case 1 : input_P_Q(P,Q,N,N1);break;case 2 : input_E(E,D,N1);break;case 3 : print_miyao(E,N,D);break;case 4 : jiami(E,N);break;case 5 : jiemi(D,N);break;case 6 : pr

19、int_help();break;case 0 : break;while(ch);int gcd(long a, long b)return a;return gcd(b, a % b);int sushu(long m) int i;for(i=2;i*i<=m;i+)if(m%i=0) return 0;return 1;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 = (

20、 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;int a_b_Mod_c(long a, long b, long c) int digit32;long i,k,resualt = 1; i = 0;while(b)

21、digiti+ = b%2; b >>= 1; for(k = i-1; k >= 0; k-) resualt=(resualt*resualt)%c;if(digitk=1) resualt=(resualt*a)%c; return resualt;void input_P_Q(long &P,long &Q,long &N,long &N1) cout<<" 输入第一个素数 p:n"while(1)11 if (cin>>P) break;else cout<<"P 应为

22、数字，请重新输入：cin.clear(); cin.ignore(); while(1) if (sushu(P) break;else cout<<"P 应为素数，请重新输入：cin.clear(); cin.ignore(); cin>>P;cout<<" 输入第二个素数 Q:n"while(1) if (cin>>Q) break;else cout<<"Q 应为数字，请重新输入：cin.clear(); cin.ignore(); while(1) if (sushu(Q) break;

23、else cout<<"Q 应为素数，请重新输入：cin.clear(); cin.ignore(); cin>>Q;N=P*Q;N1=(P-1)*(Q-1);void input_E(long &E,long &D,long n1)"<<endl;"<<endl;"<<endl;"<<endl;if(n1=0)13cout<<"请先输入两个素数P, Q"<<endl;return;long z=0;cout<

24、;<"输入一个小于"<<n1<<"的数 e:n"while(1) if (cin>>E) break;else cout<<"E应为数字，请重新输入： "<<endl;cin.clear(); cin.ignore(); while(1) if (gcd(E,n1)=1) break;"<<endl;else cout<<"E 应与"<<n1<<"互质"<<&q

25、uot;,请重新输入: cin.clear(); cin.ignore(); cin>>E;if(ExtendedEuclid(E,n1,&z) D=z;else cout<<" 错误"<<endl;void print_miyao(long e,long n,long d) cout<<"公钥为：n" cout<<"("<<e<<","<<n<<")"<<endl; cout<<"公钥为：n" cout<<"("<<d<<","<<n<<")"<<endl;void jiami(long e,long n)if(e=0,n=0)cout<<"请先输入密钥"<<endl;return;long c,m; cout<<"输入