当前位置:首页 » 《休闲阅读》 » 正文

密码学---公钥密码---RSA算法_sfakh的博客

19 人参与  2022年02月10日 16:15  分类 : 《休闲阅读》  评论

点击全文阅读


RSA算法

  • RSA算法流程
    • 1.产生密钥
    • 2.分组
    • 加密
    • 解密
    • 实例
  • RSA算法的计算问题
    • 加密和解密中的计算
    • 密钥产生过程的计算问题
  • 改进的RSA算法
  • RSA的安全性
  • RSA的攻击
    • 1.共模攻击
    • 2.低指数攻击

RSA算法流程

RSA算法是迄今为止理论上最为成熟的公钥密码体制,并且已经得到广泛的应用。

1.产生密钥

产生密钥的过程如下:

  1. 选择两个保密的大素数P和q
  2. 计算n=p×q,φ(n)=(p-1)(q-1)
  3. 选择公钥e,e∈(1,φ(n))范围内的一个整数,且gcd(φ(n),e)=1
  4. 计算密钥d,d·e≡1 mod φ(n),即d≡e-1 mod φ(n)
  5. 以{e,n}为公钥,{d,n}为私钥

2.分组

将明文比特串分组,使得每个分组对应的十进制数小于n,即分组长度小于log2n

加密

对每个明文分组m,作加密运算:
在这里插入图片描述

解密

对密文分组的解密运算如下:
在这里插入图片描述

实例

这里以未分组的问题进行示例:
对于分组问题,当加密的时候,需要补零则在后面进行补零操作;解密时需要补0,则在每个分组前面进行补零操作

RSA算法的计算问题

加密和解密中的计算

RSA算法的加密和解密过程都为求一个整数的整数次幂再取模的运算。因此可能有如下问题:
1.中间结果非常大,超出计算机的整数取值范围。
2.指数的运算很复杂

针对不同的问题有不同的解决方法:
1.针对问题1,可以合理运用模运算的性质:
在这里插入图片描述
2.针对问题2,可以通过如下变形提高指数运算的有效性,减少运算次数。

基于该思想有快速指数算法如下:
在这里插入图片描述

应用解决方法的具体示例:
问题:求7560 mod 561.
解:将560协程二进制形式为1000110000,应用快速指数算法的结果为:
在这里插入图片描述

密钥产生过程的计算问题

密钥产生过程中的计算问题主要是大素数的确定问题:

产生密钥时,需要考虑两个大素数p、q的选取,以及e的选取和d的计算。因为n=pq在体制中是公开的,因此为了防止敌手通过穷搜索发现p、q的值,这两个素数应该是在一个足够大的整数集合中选取的大数。且RSA算法的优越性和有效地寻找大素数有密切联系。

寻找大素数一般先随机选取一个大的奇数(如用伪随机数产生器),然后用素性检验算法检验选择的奇数是否是素数,若不是,则选取另一大奇数,直到满足条件为止。后续工作可由Euclid算法完成

改进的RSA算法

改进的RSA算法是利用中国剩余定理来提高解密运算的速度。其解密过程如下:
在这里插入图片描述
由中国剩余定理,有解:
在这里插入图片描述
且已经表明,改进后的算法可以很大程度上减少解密运算时间

RSA的安全性

RSA的安全性是基于分解大整数的困难性假定。
且能够证明由n直接确定n的欧拉函数等价于对n的分解。
因此RSA的安全性对密钥的选取提出了大小的注意,除此还对p和q提出了以下要求:
1.|p-q|要大
2.p、q的选取要保证能使t很大,才能抵抗重复加密攻击

RSA的攻击

RSA由于参数选择不当会存在一下两种攻击

1.共模攻击

共模攻击就是指由于模数相同从而容易造成的攻击方法。可通过给用户设置不同的模数来进行抵抗

2.低指数攻击

低指数攻击是指用户的加密指数很小,攻击者利用中国剩余定理从而求解出m的攻击方法


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/34509.html

算法  密钥  素数  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

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

最新文章

  • [糙汉嘴软心硬,娇妻日日晚起]小说精彩节选免费试读_「黎夏顾卫城」主线最终章倒计时
  • 我的亲妹妹我当做畜生,只有儿子来救我反转剧情试读片段_[***小宝李小翠]精彩章节免费试读
  • 往梦难复温,沈淮霆宋思予在线_往梦难复温,沈淮霆宋思予在线
  • 爱意清浅随风离(简凝夕陆靳燃),爱意清浅随风离
  • 「冲喜而已,侯爷别太爱」小说免费在线阅读_侯府侯爷乐瑶主线最终章倒计时
  • 好看的往梦难复温沈淮霆宋思予_往梦难复温沈淮霆宋思予
  • 天才京剧花旦被废嗓后成为芭蕾舞王+后续+结局(秦意宋笙)全书秦意宋笙结局_秦意宋笙+结局列表_笔趣阁(天才京剧花旦被废嗓后成为芭蕾舞王+后续+结局)
  • (番外)+(全书)往梦难复温(沈淮霆宋思予+番外+全书)_(往梦难复温+番外+全书)免费_笔趣阁(沈淮霆宋思予)
  • 江晚烟陆聿我终于失去了你结局+番外(江晚烟陆聿)列表_江晚烟陆聿我终于失去了你结局+番外(江晚烟陆聿)结局篇+番外在线
  • 池雾陆砚寒结局+番外(陆砚寒池雾)列表_池雾陆砚寒结局+番外(陆砚寒池雾)池雾陆砚寒结局+番外在线
  • 沈静怡傅励行+后续+结局(傅励行沈静怡)列表_沈静怡傅励行+后续+结局(傅励行沈静怡)沈静怡傅励行+后续+结局在线
  • 非典时,我被妻子的白月光误诊遗弃在病房节选角色羁绊特辑‌_田越苏雅白月光角色专属支线试读入口

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1