RSA加密算法
周五在上c语言课的时候，有幸接触了著名的rsa加密算法。rsa算法作为目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。回寝室后我感觉这种算法很有趣并且以我们目前的学习进度可以进行编写，便进行了尝试。在开始前我也找到了一些资料，下面和大家分享一下。
RSA
rsa算法的由来
1976年以前，所有的加密方法都是同一种模式：
- 甲方选择某一种加密规则，对信息进行加密；
- 乙方使用同一种规则，对信息进行解密。
由于加密和解密使用同样规则（简称”密钥”），这被称为”对称加密算法”（Symmetric-key algorithm）。
这种加密模式有一个最大弱点：甲方必须把加密规则告诉乙方，否则无法解密。保存和传递密钥，就成了最头疼的问题。
1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为”Diffie-Hellman密钥交换算法”。这个算法启发了其他科学家。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。
这种新的加密模式被称为非对称加密算法：
- 乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
- 甲方获取乙方的公钥，然后用它对信息加密。
- 乙方得到加密后的信息，用私钥解密。
如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。
1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的”非对称加密算法”。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。
rsa算法的步骤
- 随机选择两个不相等的质数p和q。（实际应用中，这两个质数越大，就越难破解。）
- 计算p和q的乘积n。n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12 位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。
- 计算n的欧拉函数φ(n)。根据公式：φ(n) = (p-1)(q-1)
- 随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
- 计算e对于φ(n)的模反元素d。
- 将n和e封装成公钥，n和d封装成私钥。
实际应用中，公钥和私钥的数据都采用ASN.1格式表达（实例）。
加密和解密
有了公钥和密钥，就能进行加密和解密了。
- 加密要用公钥 (n,e) 所谓”加密”，就是算出下式的c：m^e ≡ c (mod n)。c就是密文
- 解密要用私钥(n,d) 可以证明，下面的等式一定成立：c^d ≡ m (mod n) 也就是说，c的d次方除以n的余数为m。m就是明文
至此，”加密–解密”的整个过程全部完成。
后续
这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。 由于rsa的公钥(n,e) 只能加密小于n的整数m，那么如果要加密大于n的整数，就要采用这么两种解决方法：一种是把长信息分割成若干段短消息，每段分别加密；另一种是先选择一种”对称性加密算法”（比如DES），用这种算法的密钥加密信息，再用RSA公钥加密DES密钥。
代码
由于时间与水平有限，目前编写的rsa还比较简陋，而且素数也不够大，只编写了的一个加密解密和在一起的程序，和单独加密的程序，还有单独随机公钥的程序，后续将会在时间充裕的时候补上有关明文字母分开的代码，以便于编写单独解密的程序。下面是我写的代码，欢迎大家的讨论。
RSA集合
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163 | #include <stdlib.h>#include <string.h>#include <time.h>#include <math.h>
int (int e,int fn);
int fun_2(int e,int fn);
int zhuan_huan(int b,int a[],int k);
int js_mod(int a,int b,int n);* 主函数 **************/void main()
{ int p,q,e,d,n,fn; long m[10000],c[100000];//c[10000]存放加密后的数字密文，m[1000]存放解密后的数字明文，即英文明文在zimu_biao[69]中的下标。
int i,j; //i,j用于循环遍历数组
int mi_yue; //用户输入的密钥
int count=1; //统计输入密钥的次数，count>3时将不允许用户再输入。
char min_wen[大专栏 RSA加密算法ass="number">10000],re_min_wen[10000];//分别为用户输入的明文、密文，解密后的明文。
//密钥生成 char zimu_biao[69]="abcdefghijklmnopqrstuvwxyz,ABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789'.?!"; printf("请输入您要发送的明文文件（小写英文表示）:n"); printf("******************************************************n"); gets(min_wen); printf("******************************************************n"); srand((unsigned) time(NULL)); printf("n加密开始nn"); do
{ p=rand()%201+101; for(i=2;i<=sqrt(p);i++) { if(p%i==0) break; } }while(i<=sqrt(p)); do
{ q=rand()%201+101; for(i=2;i<=sqrt(q);i++) { if(q%i==0) break; } }while(i<=sqrt(q)||q==p); n=p*q; fn=(p-1)*(q-1); do
{ e=rand()%(fn)+1; }while(fun_1(e,fn)); d=fun_2(e,fn); //求解密指数d
printf("******************************************************n"); printf("n明文长度:%dn",strlen(min_wen)); printf("n您的两个大素数分别为p=%d(保密),q=%d(保密)n模数n=%d(公开),欧拉函数fn=%d(保密)n",p,q,n,fn); printf("Public Key:%10d %10d(公钥,公开)n",n,e); printf("Private Key:%10d %10d(私钥,保密)nn",n,d);//明文转换过程 for(i=0;i<strlen(min_wen);i++) for(j=0;j<68;j++) if(min_wen[i]==zimu_biao[j]) m[i]=j;//将字符串明文换成数字，并存到整型数组m里面，即明文的另一种表示方法
//加密过程 for(i=0;i<strlen(min_wen);i++) c[i]=js_mod(m[i],e,n); printf("输出密文：n"); printf("******************************************************n"); for(i=0;i<strlen(min_wen);i++) printf("%d",c[i]); printf("n******************************************************n");//提示用户解密 printf("nn您有3次输入密钥（只需要输入私钥的d）的机会，3次输入错误将无法解密nn"); while(1) { scanf("%d",&mi_yue); if(mi_yue==d) { printf("密钥输入正确，您得到的明文为：nn"); for(i=0;i<strlen(min_wen);i++) m[i]=js_mod(c[i],d,n); for(i=0;i<strlen(min_wen);i++) re_min_wen[i]=zimu_biao[m[i]]; for(i=0;i<strlen(min_wen);i++) printf("%c",re_min_wen[i]); printf("nn"); break; } else
{ printf("您第%d次输入的密钥错误，请重新输入。。。n",count); count++; if(count>3) { printf("n您已%d次输入的密钥错误，将不允许继续输入n",count-1); break; } } }}//判断fn和e是否互素int (int e,int fn)
{ int i,null=0; for(i=2;i<=fn;i++) { if(e%i==0&&fn%i==0) null=1; } return null;}//扩展欧几里得算法求乘法逆元，即求解密指数dint fun_2(int e,int fn)
{ int d=1; while((e*d)%fn!=1) { d++; } return d;}//将十进制数转换成二进制int zhuan_huan(int b,int a[],int k)
{ int t,temp=-1; while(b>0){ t=b%2; temp++; a[temp]=t; b=b/2; } return temp;}//快速计算模指数int js_mod(int a,int b,int n)
{ int x=0,y=1,k,i,s[1000]; k=zhuan_huan(b,s,1000); for(i=k;i>=0;i--){ x=2*x; y=(y*y)%n; if(s[i]==1){ x++; y=(y*a)%n; } } return y;} |