上一次《
用吃奶的劲试着解释加密算法的数学原理
》，已经尽了我的最大努力解释 RSA 算法的具体数学原理了。结果还有同学说没看懂
。这在我写的文章里面属于少见的反馈。这不能忍，必须再来一次。
先上例子
假设一个人要把一个数字当众告诉我，却不想让其他人知道。如果我们没有事先约定什么暗号，怎么办？
我这里有一个办法。有三个神奇的数字：
5
,
14
,
11
，其中，
e = 5,
n = 14
作为
公钥
（公开的钥匙），可以告诉任何人，但另外一个
d = 11
作为
密钥
（秘密的，不公开的钥匙），我谁都不告诉。
谁要是想给我传递任何数字，只要用这两个公钥对想传递的数字做点特殊的处理就可以：
取这个数字的 e 次方，再把除以 n 的余数告诉我就可以
。
比如，你想传递给我的数字是
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 的精巧却简单得让人不能相信的设计。
