五分钟知识科普：什么是 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 算法为保证安全性，会大大提升密钥长度，导致运算速度变慢。这导致它在大量数据加密时并不适用。