RSA加密算法的破解

《RSA加密算法的破解》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、RSA加密算法的破解1.什么是RSA加密算法RSA加密算法是在1977年开发的，是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。在RSA算法中，我们先要获得两个不同的质数P和Q做为算法因子，再找出一个正整数E，使得E与 (P-1)*(Q-1) 的值互质，这个E就是私钥。找到一个整数D，使得(E*D)mod((P-1)

2、*(Q-1))=1成立，D就是公钥1。设N为P和Q的乘积，N则为公钥2。加密时先将明文转换为一个或一组小于N的整数I，并计算ID modN的值M，M就密文。解密时将密文ME modN，也就是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的数值大小起着决定性的因素

3、。一般来讲当P和Q都大于2128时，按照目前的机算机处理速度破解基本已经不大可能了。2.RSA算法的原理（1）费马小定理：有N为任意正整数，P为素数，且N不能被P整除，则有NP modP=N（2）积模分解公式有X、Y和Z三个正整数，且X*Y大于Z，则有：(X*Y)modZ=((XmodZ)*(YmodZ))modZ（3）有P和Q两个互质数，如果有XmodP=0，XmodQ=0，则有：XmodPQ=0（4）有P和Q两个互质数，设有整数X和Y满足YmodP=X，YmodQ=X，则有：YmodPQ=X4（5）有P和

4、Q两个互质数，设有整数X和Y满足YmodPQ=X ，则有：YmodP=X，YmodQ=X（6） RSA定理：:若P和Q是两个相异质数，另有正整数R和M，其中M的值与(P-1)(Q-1)的值互质，并使得(RM)mod(P-1)(Q-1)=1。有正整数A，且A

5、算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(SecureElectronicTransaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。3)安全性,RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，而且密码学界多数人士倾向于因子分解不是NPC问题。4．RSA算法的C语言实现一、RSA算法的描述1、选取长度相等的两个大素数p和q，计算其乘积：n=pq然后随机选取加密密钥e，使e和

6、(p–1)(q–1)互素。最后用欧几里德扩展算法计算解密密钥d，以满足ed=1(mod(p–1)(q–1))即d=e–1mod((p–1)(q–1))4e和n是公钥，d是私钥2、加密公式如下：ci=mi^e（modn）3、解密时，取每一密文分组ci并计算：mi=ci^d（modn）Ci^d=（mi^e）^d=mi^(ed)=mi^[k（p–1）（q–1）+1]=mimi^[k（p–1）（q–1）]=mi*1=mi4、消息也可以用d加密用e解密C源程序#includeintcandp(inta

7、,intb,intc)//数据处理函数，实现幂的取余运算{intr=1;b=b+1;while(b!=1){r=r*a;r=r%c;b--;}printf("%d",r);returnr;}intfun(intx,inty)//公钥e与t的互素判断{intt;while(y){t=x;x=y;y=t%y;}if(x==1)return0;//x与y互素时返回0elsereturn1;//x与y不互素时返回14}voidmain(){intp,q,e,d,m,n,t,c,r;printf("请输入两个素数p

8、,q:");scanf("%d%d",&p,&q);n=p*q;printf("计算得n为%3d",n);t=(p-1)*(q-1);//求n的欧拉数printf("计算得t为%3d",t);printf("请输入公钥e:");scanf("%d",&e);if(e<1

9、

10、e>t

11、

12、fun(e,t)){printf("e不合要求，请重新输入:");//e<1或e>t或e与t不互素时，重新输入