Rabin加密解密算法

取两个大素数p和q,n=pq
选择这样的pq可以方便简化计算

加密:
为明文空间,选择 为某一明文,加密公式为 .
例子:p=7,q=11,n=77,P={0,...,76},当m=20时,密文c=400 % 77 = 15


解密:
当n无法分解时,我们是无法计算的,还是刚才的例子,我们假设已经用某种方法得到了n=pq,即77=7*11
已知n=77,77=7*11,明文c=15,求密文m

先计算在同余意义下的平方根
时,更方便计算,公式为:
.
计算得到: .

然后,根据扩展欧几里得算法,求得: and ,使得其满足:
算得:  , .

根据中国剩余定理,最后的明文空间为:

代入计算得到: .
小性质:  = p 或者   = q

全部评论

相关推荐

06-10 23:36
已编辑
首都经济贸易大学 C++
点赞 评论 收藏
分享
05-14 20:34
门头沟学院 Java
窝补药贝八股:管他们,乱说,反正又不去,直接说680
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务