爱华网RSA加密算法的破解
1. 什么是RSA加密算法 RSA加密算法是在1977年开发的，是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
在RSA算法中，我们先要获得两个不同的质数P和Q做为算法因子，再找出一个正整数E，使得E与 ( P - 1 ) * ( Q - 1 ) 的值互质，这个E就是私钥。找到一个整数D，使得( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立，D就是公钥1。设N为P和Q的乘积，N则为公钥2。加密时先将明文转换为一个或一组小于N的整数I，并计算ID mod N的值M，M就密文。解密时将密文ME mod N，也就是M的E次方再除以N所得的余数就是明文。
因为私钥E与( P - 1 ) * ( Q - 1 )互质，而公钥D使( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立。破解者可以得到D和N，如果想要得到E，必须得出( P - 1 ) * ( Q - 1 )，因而必须先对N进行因数分解。如果N很大那么因数分解就会非常困难，所以要提高加密强度P和Q的数值大小起着决定性的因素。一般来讲当P和Q都大于2128时，按照目前的机算机处理速度破解基本已经不大可能了。
2. RSA算法的原理
（1） 费马小定理：有N为任意正整数，P为素数，且N不能被P整除，则有
NP mod P = N
（2） 积模分解公式有X、Y和Z三个正整数，且X * Y大于Z，则有：( X * Y )
mod Z = ( ( X mod Z ) * ( Y mod Z ) ) mod Z
（3）有P和Q两个互质数，如果有X mod P = 0，X mod Q = 0，则有：X mod PQ
= 0
（4）有P和Q两个互质数，设有整数X和Y满足Y mod P = X，Y mod
Q = X，则有：Y mod PQ = X
1
（5）有P和Q两个互质数，设有整数X和Y满足Y mod PQ = X ，
则有：Y mod P = X，Y mod Q = X
（6） RSA定理：:若P和Q是两个相异质数，另有正整数R和M，其中M的
值与( P - 1 )( Q - 1 )的值互质，并使得( RM ) mod ( P - 1 )( Q - 1 ) = 1。有正整数A，且A < PQ，设C = AR mod PQ，B = CM mod PQ则有：A = B
3. RSA加密算法的缺点
1)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。
2)分组长度太大，为保证安全性，n 至少也要 600 bits 以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。
3)安全性, RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，而且密码学界多数人士倾向于因子分解不是NPC问题。
4．RSA算法的C语言实现
一、RSA 算法的描述
1、选取长度相等的两个大素数p 和q，计算其乘积：
n = pq
然后随机选取加密密钥e，使e 和(p–1)(q–1)互素。
最后用欧几里德扩展算法计算解密密钥d，以满足
ed = 1(mod(p–1) ( q–1))
即d = e–1 mod((p–1)(q–1))
2
e 和n 是公钥，d 是私钥
2、加密公式如下：
ci = mi^e（mod n）
3、解密时，取每一密文分组ci 并计算：
mi = ci^d（mod n）
Ci^d =（mi^e）^d = mi^(ed) = mi^[k（p–1）（q–1）+1 ] = mi mi^[k（p–1）（q–1）] = mi *1 = mi
4、消息也可以用d 加密用e 解密
C 源程序
#include <stdio.h>
intcandp(inta,intb,int c) //数据处理函数，实现幂的取余运算 { int r=1;
b=b+1;
while(b!=1)
{
r=r*a;
r=r%c;
b--;
}
printf("%dn",r);
return r;
}
int fun(intx,int y) //公钥e 与t 的互素判断
{
int t;
while(y)
{
t=x;
x=y;
y=t%y;
}
if(x == 1)
return 0; //x 与y 互素时返回0
else
return 1; //x 与y 不互素时返回1
3
}
void main()
{
intp,q,e,d,m,n,t,c,r;
printf("请输入两个素数p,q: ");
scanf("%d%d",&p,&q);
n=p*q;
printf("计算得n 为%3dn",n);
t=(p-1)*(q-1); //求n 的欧拉数
printf("计算得t 为%3dn",t);
printf("请输入公钥e: ");
scanf("%d",&e);
if(e<1||e>t||fun(e,t))
{
printf("e 不合要求，请重新输入: "); //e<1 或e>t 或e 与t 不互素时，重新输入
scanf("%d",&e);
}
d=1;
while(((e*d)%t)!=1) d++; //由公钥e 求出私钥d
printf("经计算d 为%dn",d);
printf("加密请输入1n"); //加密或解密选择
printf("解密请输入2n");
scanf("%d",&r);
switch(r)
{
case 1: printf("请输入明文m: "); //输入要加密的明文数字
scanf("%d",&m);
c=candp(m,e,n);
printf("密文为%dn",c);break;
case 2: printf("请输入密文c: "); //输入要解密的密文数字
scanf("%d",&c);
m=candp(c,d,n);
printf("明文为%dn",m);break;
}
}
4
百度搜索“爱华网”,专业资料,生活学习,尽在爱华网
