Rabin密码体制

1.RSA密码体制

1.1算法描述

 RSA算法的具体描述如下:

(1)任意选取两个不同的大素数p和q计算乘积n = pq,φ(n) = (p-1)(q-1);

(2)任意选取一个大整数e,满足gcd(e,φ(n))=1,整数e用做加密钥(注意:e的选取是很容易的,例如,所有大于p和q的素数都可用) ;
(3)确定的解密钥d,满足(de) mod φ(n)=1,即de=kφ(n)+1(k≥1)是一个任意的整数;所以,若知道e和φ(n),则很容易计算出d;
(4)公开整数n和e,秘密保存d;

(5)将明文m(m<n是一个整数)加密成密文c,加密算法为

(6)将密文c解密为明文m,解密算法为

然而只根据n和e(注意:不是p和q)要计算出d是不可能的。因此,任何人都可对明文进行加密,但只有授权用户(知道d)才可对密文解密。 

1.2安全性

    RSA的安全性依赖于大数分解,但是否等同于大数分解一直未能得到理论上的证明,也并没有从理论上证明破译。RSA的难度与大数分解难度等价。因为没有证明破解RSA就一定需要做大数分解。假设存在一种无须分解大数的算法,那它肯定可以修改成为大数分解算法,即RSA的重大缺陷是无法从理论上把握它的保密性能如何,而且密码学界多数人士倾向于因子分解不是NPC问题。

    目前,RSA的一些变种算法已被证明等价于大数分解。不管怎样,分解n是最显然的攻击方法。现在,人们已能分解140多个十进制位的大素数。因此,模数n必须选大些,视具体适用情况而定。

    RSA算法的保密强度随其密钥的长度增加而增强。但是,密钥越长,其加解密所耗用的时间也越长。因此,要根据所保护信息的敏感程度与攻击者破解所要花费的代价值不值得以及系统所要求的反应时间来综合考虑,尤其对于商业信息领域更是如此。

2.Rabin密码体制

    Rabin密码体制是RSA密码体制的一种,假定模数n=pq不能被分解,该类体制对于选择明文攻击是计算安全的。因此,Rabin密码体制提供了一个可证明安全的密码体制的例子:假定分解整数问题是整数上不可行的,那么Rabin密码体制是安全的。

    Eabin密码体制是对RSA的一种修正,它有以下两个特点:

    ●    它不是以一一对应的单向陷门为基础,对同一密文,可能有两个以上对应的明文。

    ●    破译该体制等价于对大整数的分解。

    RSA中选取的公开密钥e满足 1 < e < φ(n),且gcd(e,φ(n))=1.Rabin密码体制则取e = 2。

2.1秘钥的产生

    随机选择两个大素数p、q,满足p ≡ q ≡ 3 mod 4,即这两个素数形式为4k + 3;计算n = p × q。以n作为公开秘钥,p、q作为私秘钥。

2.2加密

其中m是明文分组,c是对应的密文分组。

2.3解密

    解密就是求c模m的平方根,即解,该方程等价于方程组:

由于p ≡ q ≡ 3 mod 4,下面将看到,方程组的解可容易地求出,其中每个方程都有两个解,即

经过组合可得4个同余方程组

      ①                                                                  ②             

  

 ③                                                                  ④       

由中国剩余定理可解出每一方程组的解,共四个,即每一密文对应的明文不唯一。


例一:    在Rabin密码体制中设 p = 53,q = 59;

            (1)确定1在模n下的4个平方根。

            (2)求明文消息2347所对应的密文。

            (3)对上述密文,确定可能的4个明文。

(1)



(2)

(3)

直接代入公式进行计算:

.........(后续的计算步骤省略)

计算可得对密文(1762)确定的可能明文为(1075,2347,780,2052)

#转载请注明出处!
快来制作你的简历吧 ,请猛戳这里→点击在线制作
宝塔服务器面板,一键全能部署及管理,送你3188元礼包。请猛戳这里→点我领取

本文标题:《Rabin密码体制》作者:xuanzhe
原文链接:https://blog.xuanzhe.club/?id=24
特别注明外均为原创,转载请注明。

分享到微信

扫描二维码

可在微信查看或分享至朋友圈。

上一篇: 背包密码体制
下一篇: 第一章绪论

相关文章

发表评论:
验证码

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

你好,朋友

真是美好的一天!

访客信息

  • IP: 52.90.49.108
  • 地点: United StatesVirginiaAshburn

毒鸡汤

  • API可调用次数不足...请尝试检查插件设置的APIKEY
  • 英语小句子

  • 木有了,杯具了...请尝试检查插件设置的APIKEY
  • 标签列表

    站点信息

    • 文章总数:48
    • 页面总数:2
    • 分类总数:15
    • 标签总数:22
    • 评论总数:6
    • 浏览总数:20147
    您好,欢迎到访网站!
    忘记密码

    精美句子

  • 木有了,杯具了...请尝试检查插件设置的APIKEY
  • 网站分类

    文章归档

    歌曲 - 歌手
    0:00