有人没看懂？再次尝试讲解 RSA 加密算法
上一次《用吃奶的劲试着解释加密算法的数学原理》，已经尽了我的最大努力解释 RSA 算法的具体数学原理了。结果还有同学说没看懂 。这在我写的文章里面属于少见的反馈。这不能忍，必须再来一次。
先上例子
假设一个人要把一个数字当众告诉我，却不想让其他人知道。如果我们没有事先约定什么暗号，怎么办？
我这里有一个办法。有三个神奇的数字：5, 14, 11，其中，e = 5, n = 14 作为公钥（公开的钥匙），可以告诉任何人，但另外一个 d = 11 作为密钥（秘密的，不公开的钥匙），我谁都不告诉。
谁要是想给我传递任何数字，只要用这两个公钥对想传递的数字做点特殊的处理就可以：
比如，你想传递给我的数字是 m = 2， 你就可以公开地把上述处理后的结果 c = 4 告诉我（因为 2 ^ 5 = 2 * 2 * 2 * 2 * 2 = 32。32 % 14 = 4）
我拿到 4 怎么办呢？我用我手里的私钥 d 做点类似上面那样的特殊处理：把别人给我的数字取 d 次方，再除以 n 取余数。得到的余数你猜是几？我们算一下
( 4 ^ 11 ) % 14 = 4194304 % 14 = 2
居然就是你一开始想传递给我的数字 2。
把想传递的数字 m，用公钥处理后的数字 c，再用私钥 d 做点处理就能逆向得到 m 本身（也就是说，2 的 5 次方除 14 取余数得到的数，再 11 次方除 14 取余数，就回到了 2 本身）。更神奇的是，小于 14 的任何一个数 m 的 5 次方再 11 次方，都是它本身 m。见下图：
神奇不神奇？如果找到了这样神奇的数字对，不就可以做加密和解密了？
这里的字母都是有含义的：
e 是 encryption，加密的意思
d 是 decryption，解密的意思
c 是 cipher，密文的意思
m 是 message，消息的意思
背后的数学原理
很显然真实的世界我们不能所有人都用这三个数，这几个数字太简单了。实际上 e 经常取 65537，d 和 n 都是十进制 100 多位的数字。怎么找到这么大却依然符合刚才说的神奇的性质的数字呢？
我们这么找：
先找两个大的素数（就是除了自己和 1 以外不能被任何数整除的数）p, q，把这两个数相乘，结果就是我们想找的 n （ n = p * q )。这样公钥就已经出来了（ e = 65537, n = p * q ）。我们接下来算私钥。
把 p、q 这两个数字各减去 1 ，再相乘，就得到一个新的乘积，我们命名为 φ 。「 φ = ( p - 1 ) * ( q - 1 ) 」。φ 读作 /fai/
φ 和 n 有什么神奇的关系吗？有的！18 世纪中期，大数学家欧拉发现了一个惊人的事实，当 m < n 且和 n 互质① 的时候：
在开头的例子里面，就是欧拉发现了，任何数字的 φ 次方除以 n 的余数都是 1 ！大家可能可以猜得出来，我们就是用 p = 2, q = 7 算出 n = 14，φ = ( 2 - 1 ) * ( 7 - 1 ) = 1 * 6 = 6。欧拉说，任何小于 14 并且和 6 互质的数字的 6 次方除以 14 的余数都是 1 。
你给我一个数字，我知道他的 6 次方除以 14 的余数是 1 有啥用？除了是一个有趣的事实以外，能用来加密解密吗？
名字开头分别是 R、S、A 的三位教授就开始动脑筋了。能不能借用这个性质，把 φ 这个数字硬掰成两个数？然后告诉别人一个，自己留一个，是不是就可以用来加密解密了？接下来就是 RSA 的精巧却简单得让人不能相信的设计。
既然 m ^ φ % n = 1，两边都取 k 次方看看：
除法取余数的等式有一个我以前没有意识到的一个性质，就是都乘以一个数字，或者都加上一个数字，或者都取 k 次方，等式依然成立。
两边都取 k 次方，上面的公式就变成了：
上面就是说，任何一个小于 n 且和 n 互质的数字 m 的 φ 的整数倍除以 n，余数依然是 1 。我们对 1 不感兴趣，对 m 感兴趣。上面的公式两边都乘以 m ，就有意思了：
左边的乘以 m 变成了 m 的 k * φ + 1 次方。右边的 1 乘以 m 变成 m 本身。是不是感觉快到终点了？
我们只需要把 k * φ + 1 分解成两个数字的乘积，不就搞定了？从一个已经知道的数字，找两个数字的乘积是它的倍数加 1 ，这是数学上很简单的问题，这样的数字不止一个，有无数对。
这两个数，一个用做 e，另一个用作 d。只要保证， e * d - 1 能被 φ 整除就可以了。（上面一直讨论 m 和 n 互质的情况。到了这一步，我们发现 m 和 n 不互质的时候依然可以证明成立，这里就略去证明，结论是 m 可以取小于 n 的任何数。）
我们一开始用的例子，现在大家看到了，既然 m 的 6 次方除以 14 余 1，我们找两个乘积是 6 的整数倍加一的数字，m 经过两个数字次方，结果就是 它本身。比如：6 * 9 + 1 = 55，我们就找到了 e = 5 和 d = 11 。
找到了 e 和 d ，整个算法也就豁然开朗了。
我们其实是找到了神奇的数字 e 和 d ，让任何一个数字的 e 次方的 d 次方除以 n 的余数就是它自己。利用这一条，我们可以先用 e 加密，再用 d 解密。
如何破解？
如上过程，从 p，q 算出所有的参数，包括密钥 d，都是举手之劳：随意取 p， q ，算出 n，φ 都是简单乘法，从 φ 找到 e，d 也是简单运算。
那我们从公布的（ e, n ）有可能算出来 d 吗？答案肯定是不可能，否则叫什么加密算法。我们来看为什么。
有了 e，要想知道 d，我们需要知道 φ（当时我们就是从 φ 和 e 算出 d 的）。要想知道 φ，我们只需要知道 p， q 就可以（因为φ 就是 p, q 各减一相乘算出来的）。所以，破解 RSA 的关键，就是我们只要把 n 分解成 p 和 q 的乘积，这里的所有的数都轻而易举的知道了。问题是，一个巨大的自然数 n，我指的是一百多位的自然数，可以被轻易地分解吗？
大数不可分解
3 * 7 算出 21 容易吗？容易。反过来，21 是哪两个数的乘积？也不难，但肯定比算 3 * 7 麻烦。那么 366493 是哪两个数乘积？难多了。现在数学上没有什么简单地算法，基本上就是一个个试，从 1 试到 379 就找到了（967 * 379 ）。随着乘积的不断变大，尝试的成本急速增加。到了 100 位左右的时候，试出来需要耗费的能源已经超过太阳一生发出的能量了。所以，只要 n 无法被分解成 p 和 q，φ 就安全；φ 安全了，d 也就安全了。
这个算法，就是著名的 RSA 非对称性加密算法，也是密码学里面最常用的一种算法。
大家觉得这个版本和上一个版本相比，是不是稍微容易理解一点？或者把两篇文章对照着看更容易一些吧。
注②：感谢 Sarah 的建议和修改（她的播客链接在「阅读原文」）。