文档介绍：公钥密码Rabin(基于二次剩余)
Rabin密码系统,是由M. Rabin设计的,是RSA密码系统的一种改进。
RSA是基于指数同余的;Rabin是基于二次同余。
Rabin密码系统可以认为是e和d为定值的RSA密码系统:e = 2 ,d = 1/2。
即,加密是 c = m^2 mod n, 解密是 m = c^(1/2) mod n。
Rabin的密钥生成
选择两个大的素数p和q,要求p和q都是4的倍数加3。
计算n=pq。
Bob的公钥是n,对外公布。
Bob的私钥是(p,q),自己私藏。
Rabin的加密过程
Alice欲发送明文m给Bob,其中 0<m<n 。
Alice用Bob的公钥n,计算: c=m2(modn)。
c为密文。
Rabin的解密过程
Bob 收到密文c后, 用自己的私钥(p,q)计算:
计算:m1, m2, m3, m4,
满足: 0<m1<n;0<m3<n; 0<m2<n; 0<m4<n;
m1(modp)=mp; m1(modq)=mq; m2(modp)=mp; m2(modq)=q-mq; m3(modp)=p-mp; m3(modq)=mq; m4(modp)=p-mp; m4(modq)=q-mq 。 (4个数的计算使用孙子定理(中国剩余定理)。)
于是,真正的明文m一定就是4个数 m1, m2, m3, m4 之中的一个。
观察4个数,排除那些没有意义的“乱码课文”。 哪个是有意义的课文,哪个就是真正的明文m。
解密完毕。
Rabin的解密正确性
因为n=pq是两个不同的素数的乘积,所以,关于未知数x的二次方程
x2= c (modn)
恰好有4个不同的根x,分别有以下形状:
一个根的(modp)、(modq)值是mp、mq;
一个根的(modp)、(modq)值是mp、q-mq;
一个根的(modp)、(modq)值是p-mp、mq;
一个根的(modp)、(modq)值是p-mp、q-mq 。
4个根中有一个是明文m。
如果把(modp)、(modq)值为mp、mq的根叫做m’,则(modp)、(modq)值为p-mp、q-mq的根就是n-m’。
另外两个根的和也等于n。即如果把一个叫做m’’,则另一个就是n-m’’。
那么, 4个不同的根怎样计算呢? 如果仅仅知道n,而不知道分解式n=pq,则无法计算mp和mq,因而无法计算这4个不同的根。
如果知道了n的分解式n=pq,则能够计算mp和mq。再由mp和mq计算4个根,使用的是著名的孙子定理(中国剩余定理)。
最后,要判断哪一个根是真正的明文。 一般,真正的明文都具有语言含义,而其它的根则是没有语言含义的“乱码课文”。当然也有例外,比如当明文是一副图象的编码时,明文也是没有语言含义的“乱码课文”。