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)的模反元素de * 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##
来源 | 五分钟学算法
作者 | 程序员小吴
