实验四：RSA算法

《实验四：RSA算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、RSA算法一、RSA有关知识1978年就出现了这种算法，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：RonRivest,AdiShamir和LeonardAdlemano但RSA的安全性一直未能得到理论上的证明。RSA的安全性依赖于大数难于分解这一特点。公钥和私钥都是两个大索数(大于100个十进制位)的函数。据猜测，从-个密钥和密文推断出明文的难度等同于分解两个人索数的积。密钥对的产生。选择两个大素数，p和q。计算：n=p*q然后随机选择加密密钥e,要求c和(p-1)*(q-1)互

2、质。最后，利用Euclid算法计算解密密钥d,满足e*d=1(mod(p-1)*(q-1))其中n和d也要互质。数c和n是公仞，d是私仞。两个素数p和q不再需要，应该丢弃，不要让任何人知道。加密信息m(二进制表示)时，首先把m分成等长数据块mlmi,块长s,其中2As<=n,s尽可能的人。对应的密文是：ci=miAe(modn)(a)解密时作如卜计算：mi=ciAd(modn)(b)RSA可用于数字签名，方案是用(a)式签名，(b)式验证。具体操作时考虑到安全性和m信息虽较大等因索，一燉是先作HASH运算。RSA的安全性。RSA的安全性依赖于大

3、数分解，但是否等同于大数分解-直未能得到理论上的证明，因为没有证明破解RSA就一定需要作人数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为人数分解算法。冃前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是授显然的攻击方法。现在，人们已能分解14()多个十进制位的大素数。I大I此，模数n必须选大一些，因具体适用情况而定。由于进行的都是人数计算，使得RSA最快的情况也比DES慢上100倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少最数据加密。二、实例：令P二3,q=ll,得出n=pXq=3X11=3

4、3；f(n)=(p-l)(q-l)=2X10=20；取e二3,(3与20互质)则eXd=lmodf(n),即3Xd=lmod20。d怎样取值呢？可以用试算的办法来寻找。试算结果见下表：deXd=3Xd(eXd)mod(p-1)(q-1)=(3Xd)mod20133266399412125151561818721182439276通过试算我们找到，当*7时,eXd三lmodf(n)同余等式成立。因此,可令d=7。从而我们可以设计出一•对公私密钥,加密密钥(公钥)为：KU=(e,n)=(3,33),解密密钥(私钥)为:KR=(d,n)=(7,33)

5、o(2)英文数字化。将明文信息数字化,并将每块两个数字分纟fh假定明文英文字母编码表为按字母顺序排列数值,B

6、J：字母Abcdefgh±jk1m玛侑01020304050607080910111213宇母n0Pq1:3tuVXyz码值14151617181920212223242526则得到分组后的key的明文信息为:11,05,25。(3)明文加密用八加密密钥(3,33)将数字化明文分组倔加蜜成密文。山C三Me(modn)Cl=llmod33=11C2=5mod33二26C3=25'mod33=16因此,得到相应的密文信息为：11,26,16

7、。(4)密文解密。用户B收到密文，若将其解密，只需要计算，BIJ：Pl=llmod33=11P2=26mod33=5P3=16mod33=25用户B得到明文信息为：11,05,25。根据上面的编码表将其转换为英文，我们又得到了恢复后的原文“key”0二、调试过的程序：#includcintcandp(intajntb.intc)/*数据处理函数，实现幕的取余运算*/{intr=l;b=b+l;while(b!=l)r=r*a;r=r%c;b-SprindT%d=);returnr;intfun(intx,inty)/*公钥

8、e与t的互素判断*/{intt;while(y){t=x;x=y;y=t%y;}if(x==1)return0;/*x与y互素时返回()*/elsereturn1;/*x与y不互素时返回1*/voidmain(){intp,q,c,d,m,n,t,c,F；printf(“请输入两个素数p,q:“)；scanf(”％d%d”,&p,&q);n=p*q;printfV计算得n为%3dH,n);t=(p-l)*(q-l);/*求n的欧拉数*/printfC计算得t为％3d”,t);printf(“请输入公钥e:”);scanf(”％d”,&e

9、);if(etllfun(e,t)){printfC'e不合要求，请重新输入/*et或e与t不互索时，重新输入*/scanf(“