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

RSA加密算法简介[通俗易懂]背景RSA加密算法是公钥密码最著名的算法之一,是由MIT三位(RonRivest,AdiShamir,LenAdleman)提出的,也就以三位的名字首字母命名。该算法的理论基础是“大数分解和素数检测“,如果说有一天,大数分解和素数检测的数学理论被证明可以简单解决,那么RSA算法的加密将没有任何意义。有提出说量子计算机的出现可以大大提高RSA的破解效率。下面我们将简单学习RSA加密算法的

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

背景

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,有这里写图片描述
  2. 对所有M< n,计算M^e和C^e是比较容易的;
  3. 由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加密后的密文就相当于裸奔了。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • ubuntu pycharm2021.12 profession激活码【2021.10最新】

    (ubuntu pycharm2021.12 profession激活码)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~F…

  • TCP三次握手详解-深入浅出(有图实例演示)[通俗易懂]

    TCP三次握手详解-深入浅出(有图实例演示)[通俗易懂]TCP是属于网络分层中的传输层,因为OSI分为层,感觉太麻烦了,所以分为四层就好了,简单。分层以及每层的协议,如下两张图:TCP三次握手TCP三次握手简单如下图:TCP三次握手的过程描述:1.客户主动(activeopen)去connect服务器,并且发送SYN假设序列号为J,服务器是被动打开(passiveopen)2.服务器在收到SYN后,它…

  • 基于Spring MVC + Spring + MyBatis的【密室逃脱游戏主题排行榜】

    基于Spring MVC + Spring + MyBatis的【密室逃脱游戏主题排行榜】一、语言和环境实现语言:Java语言环境要求:eclipse/myeclipse/idea、maven、mysql使用技术:Spring、SpringMVC、MyBatis、连接池和json包自行选择二、实现功能密室逃脱游戏越来越受年轻人的喜欢,现在将各地密室游戏主题进行排名,评选2021年度最受玩家喜欢的密室主题。说明:下列界面样式仅供参考,实际完成效果美观合理即可。1.显示数据:根据图1格式,显示t_games表中所有的数据,并且按照【票数】列进行降序排序,其实【主题种类】一列在t_g

  • vim 配置文件 .vimrc

    vim 配置文件 .vimrc在终端下使用vim进行编辑时,默认情况下,编辑的界面上是没有显示行号、语法高亮度显示、智能缩进等功能的。为了更好的在vim下进行工作,需要手动设置一个配置文件:.vimrc。在启动vim时,当前用户根目录下的.vimrc文件会被自动读取,该文件可以包含一些设置甚至脚本,所以,一般情况下把.vimrc文件创建在当前用户的根目录下比较方便,即创建的命令为:$vi~/.vi

  • Web安全 支付逻辑漏洞(不用钱 买任何东西.(也能让商家倒贴钱给我们.))

    Web安全 支付逻辑漏洞(不用钱 买任何东西.(也能让商家倒贴钱给我们.))?我们购买东西正常情况下都是要钱的,如果说平台出现了(支付逻辑漏洞.)那么我们就可以,利用这个漏洞实现不用钱买任何东西,???或者是商家倒贴钱给我们来购买他的东西.(这不学起来吗?)

  • .npy文件_文件后缀名是npy怎么打开

    .npy文件_文件后缀名是npy怎么打开深度学习–迁移学习在使用训练好的模型时,其中有一种保存的模型文件格式叫.npy。打开方式·实现代码:importnumpyasnptest=np.load(‘./bvlc_alexnet.npy’,encoding=”latin1″)#加载文件doc=open(‘1.txt’,’a’)#打开一个存储文件,并依次写入print(test,file=doc)#…

    2022年10月22日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号