RSA算法简述.doc

《RSA算法简述.doc》由会员分享，可在线阅读，更多相关《RSA算法简述.doc（2页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、RSA算法简述1. 算法原理RSA体制用户i的公开加密变换Ei与保密的解密变换Di的生成:(1) 随机选取两个一百位(十进制)以上的素数pi和qi 。(2) 计算ni=piqi,(ni)=( pi-1)( qi-1)。(3) 随机选取整数ei ,满足(ei ,(ni)=1。(4) 利用欧几里得算法计算di ,满足eidi 1(mod (ni)。(5) 公布ni ei作为Ei ,记为Ei =。保密 pi qi di (ni)作为Di ,记为Di=。加密算法:c=Ei(m)=me (mod ni)。解密算法:m=Di(c)=cd(mod ni)。要证明加密解密过程是正确的,只需证明解密运算Di能恢

2、复明文,即Di(c)=c exp(di)=(m exp(ei)exp(di)m(mod ni)下面证明对任何k及任何m ni 均有m exp(k(ni)+1) m (mod ni)证明:若(m, ni )=1,成立。 若(m,ni) 1,因为ni=piqi ,所以(m,ni)必含pi和qi 之一,假设是pi 。令(m, ni )= pi ,则m=cpi ,1cqi 。有：m exp(qi),m exp(k(qi)(pi-1)1(mod qi),m exp(k(ni)=1+aqi ,m exp(k(ni)+1)=m+aqi cpi ,故 m exp(k(ni)+1)m(mod ni)。 2. 加

3、密解密过程RSA体制为分组密码体制,利用RSA加密第一步需将明文数字化,相对于用户i并取长度小于ni长度的数字作明文块,即相对用户j实施下列各步：(1) 在公开钥数据库中查得用户i的公开钥Ei =。(2) 将m分组为m=m1 m2 m3 . mr,maZn ,a=1,2,.,r。 (3) 对每一分组作加密变换,即对a=1,.,r作ca =Ei(ma)me (mod ni)。(4) 将密文c=c1 c2 .cr传给用户i。 解密过程:用户i收到密文c=c1 c2 .cr 后,先对每一分组密文解密变换,即对a=1.r作ma =Di(ca)cd(mod ni),接着合并分组得m=m1 m2 m3 .

4、 mr,这就是用户j传来的明文。3. RSA算法示例假设用户i选择了pi=43,qi=59,那么ni=4359=2537。(ni)=4258=2436,取ei =13。利用欧几里得算法将产生di ,eidi1(mod 2436)。因为2436=18713+5,13=25+3,3=2+1,所以1=3-2=3-(5-3)=23-5=2(13-25)-5=213-55=213-5(2436-18713)=-52436+93713,937131 (mod 2436),di =937.用户i将Ei =公开,将Di=保密。若用户j有明文public key encryptions,将明文数字化得:1520 0111 0803 1004 2404 1302 1724 1519 0814 1318加密得密文:0095 1648 1410 1299 1365 1379 2333 2132 1751 1324PleaseiSolist