五分钟知识科普：什么是 RSA 算法-程序员宅基地
点击蓝色“五分钟学算法”关注我哟
加个“星标”，一起学算法
RSA 算法历史
RSA 是 1977 年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。
当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。
但实际上，在 1973 年，在英国政府通讯总部工作的数学家克利福德·柯克斯（Clifford Cocks）在一个内部文件中提出了一个相同的算法，但他的发现被列入机密，一直到 1997 年才被发表。
RSA 算法基础知识
密码学知识
明文：是指没有加密的文字（或者字符串）。
加密：是以某种特殊的算法改变原有的信息数据，使得未授权的用户即使获得了已加密的信息，但因不知解密的方法，仍然无法了解信息的内容。
密文：密文是对明文进行加密后的报文。
对称加密：对称是指，在对明文进行加密，对密文执行解密加密过程采用相同的规则（通常将双方采用的规则称为"密钥"）。
例如：
（1）甲方选择某一种加密规则，对信息进行加密；
（2）乙方使用同一种规则，对信息进行解密。
非对称加密：非对称加密是指通信双方采用不同的密钥进行加密解密。
例如：
（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
（2）甲方获取乙方的公钥，然后用它对信息加密。
（3）乙方得到加密后的信息，用私钥解密。
数学知识
互质关系：如果两个正整数，除了数字 1 之外没有其他公因子，我们称这两个数是互质关系。
同余定理：给定一个正整数 m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数 a 与 b 对模 m 同余，记作 a ≡ b(mod m)。
RSA 算法流程
（1）选择两个不相等的质数p和q
例如：选择两个不等质数分别为 61 和 53 （实际应用中选择的质数都相当大）。
（2）计算p和q的乘积n
n = p*q = 61 * 53 = 3233。
（3）计算 n 的欧拉函数 φ(n)
φ(3233) = φ(61 * 53) = φ(61) * φ(53)。
由于 61 为质数，因此 φ(61) = 61 - 1 = 60。同理 φ(53) = 53 - 1 = 52。则 φ(3233) = 60 * 52 = 3120。
（4）随机选择一个整数 e ，条件是1< e < φ(n)，且 e 与 φ(n) 互质
随机选择一个质数e，保证1< e < 3120，这里选择e = 17。
（5）计算e对于φ(n)的模反元素d
e * d ≡ 1 (mod φ(n))。其中e = 17，φ(n) = 3120。
设e*d是φ(n)的k的整数倍，余数为1。则上式可以转化为：
17 * d = 3120k + 1。继续转化得到：
17 * d + 3120y = 1。其中y = -k。
其中，对于d的求解转化为二元一次方程求解。此方程可以使用扩展欧几里得方法进行求解。通过辗转相除法计算出一组解为(2753,-15)。
解得d = 2753。
（6）将n和e封装成公钥，n和d封装成私钥
加密公钥为(3233,17)，私钥为(3233,2753)。
RSA 算法分析
那么 RSA 算法是如何保证安全性的呢？
在 RSA 算法中 n 与 e 是公开的，那么破解 RSA 加密的步骤即为通过 n 与 e 计算出私钥 d 的值。
（1）ed ≡ 1 (mod φ(n))。只有知道 e 和 φ(n)，才能算出 d 。
（2）φ(n) = (p-1)(q-1)。只有知道 p 和 q ，才能算出 φ(n)。
由此得出密码破解的实质问题是：从p * q的值n，去求出 (p-1) 和 (q-1)。换句话说，只要求出 p 和 q 的值，我们就能求出 d 的值而得到私钥。但是，当 p 和 q 是是很大的质数时，从它们的积 p * q 去分解因子 p 和 q ，这是一个公认的数学难题。
比如当p * q大到1024位时，迄今为止还没有人能够利用任何计算工具去完成分解因子的任务。
虽然理论上 RSA 是可以破解的，但是随着密钥长度增加，破解的代价是不可接受的。
因此，只要密钥长度足够长，用 RSA 加密的信息实际上是不能被解破的。目前被破解的最长 RSA 密钥就是 768 位。
RSA 算法总结
RSA 的安全性依赖于大数分解，因此 RSA 算法加密安全性较高。但是，RSA 算法为保证安全性，会大大提升密钥长度，导致运算速度变慢。这导致它在大量数据加密时并不适用。
END
原 创 热 文 推 荐
你点的每个“在看”，我都认真当成了喜欢
智能推荐
CRM是否有效？可通过这些办法判断！_crm如何判断会员唯一性-程序员宅基地
文章浏览阅读204次。CRM就是关于客户与公司销售团队之间的客户关系管理，它是一个销售人员管理工具。作为一个工具型产品，CRM能减少更多的人为错误，提高工作效率，从而达到更好的营收。如果在使用CRM期间出现以下现象：不能从不同潜在客户来源中获取潜在客户，不能将潜在客户转化为销售订单，不能提供合适的销售渠道，不能提高销售人员的工作效率。说明你使用的CRM存在问题。如何判断CRM是否有效？为了检查CRM的有效性，销售人员可以对捕获到的潜在客户和具体需求进行跟踪。销售人员能够判断这个潜在客户是否值得做进一步的跟进，或者是否应该放_crm如何判断会员唯一性
数据库三大范式_怎么理解第三范式-程序员宅基地
文章浏览阅读617次，点赞2次，收藏3次。1.第一范式：强调的是列的原子性，即数据库表的每一列都是不可分割的原子数据项。2. 第二范式：要求实体的属性完全依赖于主关键字。所谓完全依赖是指不能存在仅依赖主关键字一部分的属性。3.第三范式：任何非主属性不依赖于其它非主属性。在实际的开发中需要考虑诸多问题，如：考虑商业化的需求和目标（成本，用户体验），数据库的性能更加重要在规范性能问题的时候，需要适当地考虑一下规范性有时候会故意给某些表增加一些冗余的字段（多表查询→单表查询）_怎么理解第三范式
electron-builder打包后找不到代码文件、打包指定资源到安装目录的问题_electron打包后没有提示安装路径什么的-程序员宅基地
文章浏览阅读115次。_electron打包后没有提示安装路径什么的
网络安全资料-程序员宅基地
文章浏览阅读1.3k次。做安全的，这里有你意想不到的东西分类： 信息于网络安全 2011-09-05 22:03 275人阅读 评论(0)收藏 举报目录(?)[+]Blogs Worth It:Forums:Magazines:Video:Methodologies:OSINTPresentations:People and Organizational:Inf
GDAL：创建矢量线、矢量面数据_gdal创建面-程序员宅基地
文章浏览阅读3.4k次，点赞2次，收藏26次。分享给有需要的人，代码质量勿喷。一、创建矢量线数据 单个要素 void xjCreateVectorLineByGDAL(QList<xjPoint> ListNode, const QString &xjSavePath) { GDALAllRegister(); OGRRegisterAll(); const char *xjDriverName =..._gdal创建面
MATLAB01:基本的数学运算与矩阵运算_matrixxd 赋值-程序员宅基地
文章浏览阅读10w+次，点赞1.6k次，收藏3.9k次。MATLAB01:基本的数学运算与矩阵运算MATLAB基本语法变量变量名保留变量不适合做变量名变量不应当覆盖内置函数MATLAB的调用优先级变量类型数字型变量的显示格式MATLAB命令行使用MATLAB进行数字运算使用MATLAB计算数学表达式MATLAB内置的数学函数使用MATLAB进行矩阵运算定义矩阵向终端输入矩阵使用冒号运算符创建向量定义特殊矩阵矩阵的索引矩阵的操作操作矩阵的运算符操作矩阵的..._matrixxd 赋值
随便推点
详述GPS原理及RTK技术应用_rtk与gps数据的融合过程-程序员宅基地
文章浏览阅读8.9k次，点赞12次，收藏100次。详述GPS原理及RTK技术应用，包括四大卫星定位系统，GPS系统组成：GPS空间部分、地面监控系统和GPS信号接收器（GPS卫星定位车载终端）；GPS定位技术（WGS-84坐标系），GPS定位原理（绝对定位原理，相对定位原理，静态相对定位，动态相对定位）；GPS实时动态定位技术RTK的工作原理以及基准站和流动站组成，GPS实时差分定位RTK技术的缺点，移动站的解算状态；GPS网络RTK技术(VRS系统)组成和原理，作业优势，还有GPS_NMEA 0183协议相关语句介绍。_rtk与gps数据的融合过程
CSS基础（超详解）-程序员宅基地
文章浏览阅读2.3w次，点赞103次，收藏800次。Css (层叠样式表)是种格式化网页的标准方式， 用于控制设置网页的样式，并且允许CSS样式信息与网页内容(由HTML语言定义)分离的一种技术。_css
Android 百度地图SDK 自动定位、标记定位_安卓开发地图获取定位-程序员宅基地
文章浏览阅读1.2w次，点赞98次，收藏201次。先看效果图,如果不是你想要的，也就不浪费你时间了，这样对大家都好。如果是你满意的那样，我们就可以开始写了，首先创建一个名为MapDemo的项目。打开AndroidManifest.xml，复制你的包名然后进入百度地图开放平台，没有注册的小伙伴先注册，已注册的就直接登录，登录进去之后找到控制台→我的应用→创建应用点击之后进入,填写相关资料输入了应用名称、选择了应用类型和启用的服务，输入了包名。还差开发版和发布版的SHA1了① 获取开发版SHA1鼠标点击右侧边栏的Gradle→ app→Ta_安卓开发地图获取定位
java特殊字符转html_html特殊字符转换（java）-程序员宅基地
文章浏览阅读431次。/** * 把文本编码为Html代码 * @param target * @return 编码后的字符串 */ public static String htmEncode(String target) { StringBuffer stringbuffer = new StringBuffer(); int ...
尚硅谷最新版JavaScript基础全套教程完整版（p48-p65）_尚硅谷javascript新书大纲-程序员宅基地
文章浏览阅读237次。尚硅谷最新版JavaScript基础全套教程完整版(140集实战教学,JS从入门到精通)一、基本数据类型和引用数据类型1.基本数据类型-string 、 number 、 Boolean 、null 、undefined2.引用数据类型-object3.区别-JS中的变量都是保存到栈内存中的，基本数据类型的值直接在栈内存中存储，值与值之间是独立存在的，修改一个变量不会影响另外一个变量。-引用数据类型（对象）是保存到堆内存中的，每创建一个新的对象，就会在堆内存中开辟出一个新的空间，而变量保存_尚硅谷javascript新书大纲
ACM--HDOJ 2072--单词数--字符串--水_java acm单词数问题 #结束-程序员宅基地
文章浏览阅读1.2k次。HDOJ题目地址：传送门单词数Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 44934 Accepted Submission(s): 10992Problem Descr_java acm单词数问题 #结束