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)=m(mod ni)。解密算法:m=Di(c)=cd(mod ni)。

要证明加密解密过程是正确的,只需证明解密运算Di能恢复明文,即

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 ,1?c

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. 加密解密过程

RSA体制为分组密码体制,利用RSA加密第一步需将明文数字化,相对于用户i并取长度小于ni长度的数字作明文块,即相对用户j实施下列各步：

(1)在公开钥数据库中查得用户i的公开钥Ei =。 (2)将m分组为m=m1 m2 m3 ... mr,ma∈Zn ,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 ... mr,这就是用户j传来的明文。

3. RSA算法示例

假设用户i选择了pi=43,qi=59,那么ni=43×59=2537。Φ(ni)=42×58=2436,取ei =13。利用欧几里得算法将产生di ,eidi≡1(mod 2436)。因为2436=187×13+5,

13=2×5+3, 3=2+1, 所以

1=3-2=3-(5-3)=2×3-5

=2×(13-2×5)-5=2×13-5×5 =2×13-5×(2436-187×13) =-5×2436+937×13, 937×13≡1 (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 1324

Please@iSolist