前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >RSA加密算法简介[通俗易懂]

RSA加密算法简介[通俗易懂]

作者头像
全栈程序员站长
发布2022-08-18 20:52:35
3.4K0
发布2022-08-18 20:52:35
举报

大家好,又见面了,我是你们的朋友全栈君。

背景

RSA加密算法是公钥密码最著名的算法之一,是由MIT三位(Ron Rivest, Adi Shamir, Len Adleman)提出的,也就以三位的名字首字母命名。 该算法的理论基础是“大数分解和素数检测“,如果说有一天,大数分解和素数检测的数学理论被证明可以简单解决,那么RSA算法的加密将没有任何意义。有提出说量子计算机的出现可以大大提高RSA的破解效率。下面我们将简单学习RSA加密算法的基本知识。

算法描述

RSA算法使用平方运算,明文以分组为单位进行加密,每个分组的二进制值小于n,即分组的大小必须小于等于log2(n)+1位(通常n的大小为1024位二进制数或309为十进制数,即n<2^1024)。对明文分组M和密文分组C,加密解密过程如下:

加密:

这里写图片描述
这里写图片描述

解密:

这里写图片描述
这里写图片描述

收发双方均已知n,发送方已知e,只有接收方已知d,因此RSA加密算法的公钥PU为{n,e},私钥PR为{n,d}。 d,e,n应满足如下条件:

  1. 可以找到e,d,n,使得对所有M< n,有
这里写图片描述
这里写图片描述

  1. 对所有M< n,计算M^e和C^e是比较容易的;
  2. 由e,n预测d是不可行的。

算法理解

该算法使用上非常简单,将明文分组M进行加密操作得到密文分组C,接收方再对密文分组C进行解密操作得到明文分组M,加密过程也很好理解,就是对明文分组C取指数e后模n。解密过程为对密文分组M取指数d后模n。但是为什么可以这么做呢?如何得到合适的e,d,n呢?

这里面有一个非常重要的等式:

这里写图片描述
这里写图片描述

当e和d互为模

这里写图片描述
这里写图片描述

的乘法逆时,上述关系式成立

其中

这里写图片描述
这里写图片描述

为欧拉函数。也就是说当n=ed时,算法成立。 在《公钥密码 之 素数,费马定理与欧拉定理》中我们提到,对于素数p和q,有

这里写图片描述
这里写图片描述

e和d应满足如下关系:

这里写图片描述
这里写图片描述

即e和d互为模

这里写图片描述
这里写图片描述

的乘法逆。 根据模算数的性质,仅当d(和e)与

这里写图片描述
这里写图片描述

互素时,d和e是模

这里写图片描述
这里写图片描述

的乘法逆元。因为d和

这里写图片描述
这里写图片描述

互素,则一定存在一个整数是d的模反元素。同理对于e也是如此。因此可知d和e互为模反元素,则得到上式等价于

这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述

这里面涉及到了模反元素,模反函数的定义为:

如果两个正整数a和n互素,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。

这里写图片描述
这里写图片描述

其中b叫做a的模反元素。

RSA加密算法密钥生成过程:

这里写图片描述
这里写图片描述

这里面模反元素d比较难计算,可以利用扩展的欧几里得算法计算。大多数情况下我们的素数pq会选的很大,这样得到的n也会很大,可以增加加密算法的安全性。但是为什么呢?

RSA加密算法的安全性

RSA加密算法中一共涉及到p,q,n,

这里写图片描述
这里写图片描述

,e,d六个数字,其中{n,e}为公钥,也就是说n,e是暴露的,那么能否通过n,e来得到密钥{n,d}呢?其中关键就是得到d。 我们来看如何得到d: 1。

这里写图片描述
这里写图片描述

其中e是已知的,那么关键就是如何得到

这里写图片描述
这里写图片描述

。 2。

这里写图片描述
这里写图片描述

p,q成为得到

这里写图片描述
这里写图片描述

的关键,而pq可以从n中得到,并且n是已知的。 3。n=pq,那么对n进行因式分解即可。

到这一步你就知道为什么要使得n很大了吧!也就解释了在一开始提到的该算法的理论基础是“大数分解和素数检测“。如果大数分解被证明是可以很快计算的,那么RSA加密后的密文就相当于裸奔了。

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/135707.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022年5月3,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 背景
  • 算法描述
  • 算法理解
  • RSA加密算法的安全性
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档