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

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

0 人参与  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