文档介绍：Rabin与McEliece2011-03-31歹小绒杖锗胶簿搓陌你警膏馅乘琵杉翻琉屹鹿迫坐弧犊磊峭作戍爽浮葡御通信网络安全与加密通信网络安全与加密公钥密码Rabin(基于二次剩余)Rabin密码系统,,是RSA密码系统的一种改进。RSA是基于指数同余的;Rabin是基于二次同余。Rabin密码系统可以认为是e和d为定值的RSA密码系统:e=2,d=1/2。即,加密是c=m^2modn,解密是m=c^(1/2)modn。饱厨夜憎烁而抖狸凌兵腊嫉孪舵刻甩钮斩辗庐诉武绣翁淌旗龙朋婉旅幢欧通信网络安全与加密通信网络安全与加密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个不同的根。圈恐赢骋媒铸去株嗽趁舟症啥李责弊缄汇等丧外派钒窥磺骄蛇漫趁锗透容通信网络安全与加密通信网络安全与加密