昨天，心血来潮给大家分享了一个《每天一个算法——霍夫曼编码压缩算法》，大家的反应很好，挺感谢大家的支持。今天，准备继续分享一个算法，我个人认为比较有意思，也比较重要。

RSA算法是一种"公钥加密算法"。早期的加密模式，就是加密和解密都是用同一种规则（密钥）。这种加密模式，就要求加密规则需要在双方进行传递，信息是很不安全的。在这种加密模式下的算法，也叫"对称加密算法"。而我们今天要讲的RSA算法，是一种"非对称加密算法"，加密和解密使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。

这种“非对称加密算法”的模式，信息交互方式如下：

在这种加密模式下，只要私钥不公开，通信就是安全的。

我自己今天看了挺久的加密原理，里面设计到一点数学，具体为什么就要这样做，我也不懂更深层次的原因，这里就讲点比较浅的东西。

即使是浅，我们也要先了解一点比较基本的数学定理：

• 质数（素数）

在大于1的自然数中，除了1和它本身以外不再有其他因数的数称为质数，也叫素数。

• 互质关系

如果两个数除了1以外，没有其他公因子，我们就称这两个数存在互质关系。比如，15和32没有公因子，所以它们之间有互质关系（不是质数也可以构成互质关系）。

• 欧拉函数

在数论中，对于正整数N，小于或等于N （[1,N]），且与N互质的正整数（包括1）的个数，记作φ(n)。

任意两个数p、q，如果p、q存在互质关系，我们有φ(p*q) = (p-1)*(q-1)。这里就不证明了，举个例子就好。互质关系2、5，则φ(10)=1*4。结论，在1到10中，和10互质的正整数有4个（1,3,7,9）。

• 模反元素

如果两个互质数p,q，那么一定可以找到整数x，使得 qx-1被p整除，或者说qx被p除的余数是1。这时，x就叫做q的模反元素。(上面公式，可以变换求xq + yp = 1，求x，这里y为负数)

例子：互质数3、5，这里求5的模反元素，即5x + 3y = 1。可以口算一下，这里x=2，y=-3（或者x=5,y=-8）。可以看出模反元素不唯一，但一旦x确定，y也是确定的。

上面提到的几个概念，大家反复推敲一下，RSA算法的密钥就是从这几个公式中推断出来。了解了上面的几个公式，下面我们来讲解RSA算法，获取到加密的公钥和私钥。

1.随机选择两个不相等的质数p和q。

这里我们选择p = 3 ， q = 11。（实际应用中，这两个质数越大，就越难破解。）

2.计算p和q的乘积n。

n = p * q = 3 * 11 = 33

3.计算n的欧拉函数φ(n)。

φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20

4.随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。

我们选择与20互质的数，e=7（随机选择）。

5.计算e对于φ(n)的模反元素d。

这里要求7对于20的模反元素，可以有多个，我们计算出一个即可。

公式7*d + 20*m = 1，求d。

这里我们选择d=3，m=-1。（m这里没用）

6.将n和e封装成公钥，n和d封装成私钥。

这个例子中n=33，e=7，d=3，所以公钥就是 (33,7)，私钥就是（33, 3）。

有了公钥和私钥，我们就可以进行安全通信，公钥进行加密，私钥解密。但是RSA的算法可靠吗？下面我们来讨论一下。

回顾一下上面密钥的生成步骤，总共出现了六个数字：

在这六个数字中，公钥（33,7）用到了两个（n和e），其他四个数都是不公开的。其中最关键的数是d，因为n和d组成了私钥（33,3），假如d泄漏，就等于知道了n、d、e，密钥就泄露了。

那么，有没有可能在知道n和e的情况下，推导出d？

结论：假如n可以被因数分解，那么d就可以算出，也就意味着私钥被破解。

对大整数进行因式分解，是一件很困难的事情，目前只有用暴力破解，就是一个一个去试。目前已知，被破解最长RSA密钥是768个二进制位。就是说，长度超过768位的密钥，还没有被人破解（至少没公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。

举个例子，我们可以对33进行分解成11和3，但下面这个数你没办法分解：

它等于下面两个质数的乘积：

上面获取到了公钥和私钥，还没用他们加过密。这里来举例一下就好：

公式上大家一一对照就好，具体数学原理这里不做解释了。大家感兴趣可以继续深入研究其背后的数学，我想着才是真正的数学之美。