谈谈 RSA 非对称加密算法原理及流程
实话说，要是非要让我列举最让我着迷的计算机科学算法，那我一定会不假思索的说出：加密算法 和 压缩算法 。而在上篇「在 GitHub 上使用 GPG 认证你的 Git Commit」中关于加密流程竟只用一句「合适的流程」就带过了？别急，这篇文章就专门针对 非对称加密算法 的原理及流程，一点不落。
关于 RSA
开篇先讲点历史。
在早期，如果甲乙之间想要安全的传输，就只能：
- 甲选择一种规则对信息进行加密
- 乙必须使用同一种规则对甲发来的信息进行解密
这样加密解密使用同样的规则，就被称为 对称加密算法 。
而对称加密算法最大的问题就是怎么传输这个规则（也就是密钥）呢？
直到后来 Rivest、Shamir 和 Adleman 三个人设计了一种算法，可以实现非对称加密。「非对称」就是指加密解密不一定要用同一种规则，只要两者之间满足一定的关系即可，避免了传输密钥带来的隐患。这种算法就直接用他们的名字命名——RSA 非对称加密算法。
而将近半个世纪过去了，这个算法都没有人能够破解，可以说它奠定了后面互联网安全的基石。
前置知识
既然是算法，肯定会有一些数学上特别是数论方面的结论会要用到，而且我也没有打算用所谓的「定理」二字带过。但是请放心，所有用到的定理都是初等数论范围内的。所谓「初等」，就是中学阶段就可以涉及的，所以不用急着关页面。
这次会用到定理只有 欧拉定理 和 扩展欧几里得定理 ，再辅佐一些 同余 、互素 等数论基础。
我们开始吧。
欧拉定理
欧拉定理是 RSA 算法中的核心，能够理解欧拉定理后面流程中的计算和推理就会轻松很多。
互质 / 互素
如果一个整数 $a$ 进行除以 $b$ 的带余除法中，余数为 0 ，我们就称 $a$ 是 $b$ 的倍数，$b$ 是 $a$ 的因数，记作 $b \ | \ a$。显然，1 是所有自然数的因数。
如果对于一个整数对 $x,y$ ，整数 $a$ 同时满足：$a \ | \ x \ , \ a \ | \ y$ ，那么就称 $a$ 为 $x,y$ 的公因数。而对于 $x,y$ 最大的公因数就称最大公因数，记作 $(x,y)$ 。而对于所有的公因数 $a$ ，总有 $a \ | \ (x,y)$ 。
如果两个正整数没有除了 1 以外的公因数，我们就称这两个数互质（互素）。而对于那些除了自己的倍数其他都与之互质的数，就称为质数。
而对于所有的非零整数 $a$，都可以唯一的分解成类似：
$$
a = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot p_3^{\alpha_3} \cdots
$$
其中 $(p_1,p_2,p_3,\cdots)=(2,3,5,\cdots)$ 表示从小到大所有素数。
$(\alpha_1,\alpha_2,\alpha_3,\cdots)$ 由 $a$ 的值为一确定，且只有有限个非零。
证明也不难：
如果假设 $\exists (p_1,p_2,p_3,\cdots,p_n)$ 其中 $p_1 \leq p_2 \leq p_3 \leq \cdots \leq p_n$ 均为质数，同样还有 $(q_1,q_2,q_3,\dots,q_m)$ ，满足 $a=p_1 \cdot p_2 \cdot p_3 \cdots p_n= q_1 \cdot q_2 \cdot q_3 \cdots q_m$
因为 $p_1,p_2,p_3,\dots,q_1,q_3,q_3,\dots$ 都是质数，所以有：
$$
\forall i \in [1,n], \ p_i | (q_1 \cdot q_2 \cdot q_3 \cdots q_m) \Rightarrow \exists j \in [1,m], \ p_i = q_j
$$
然后逐个消去即证。
这称为成为数的 唯一分解定理 ，而这种分解也叫 $a$ 的 标准分解 。
剩余系 / 同余系
在数论范围中，由于某些原因，我们通常不直接对数字本身进行研究，而是对它不断减去一个特定整数，直到不够再减为止，最后研究那个「剩下的」东西。
如果 $(a-b) \ | \ m$ 则称 $a$ 与 $b$ 模 m 意义下同余 ，记作 $a \equiv b (mod \ m)$ , 表示 a 和 b 在 模 m 意义下是等价的。
显然如果确定了一个 $a$ ，那么就有无限个 $b$ 与之对应，我们把这一类 $b$ 称为模 m 的一个同余类，记作 $M_a$。
由于模 m 的余数只能在 $[0,m)$ 这个范围内，所以从这 m 个剩余系中每个挑选一个代表（具体是那个无所谓，毕竟他们在模 m 意义下都是等价的），这样的 m 个数就称为模 m 的 完全剩余系 ，简称完系。换句话说如果称 $b_1,b_2,b_3,\cdots,b_m$ 为模 m 完系，那么它们两两之间互模 m 不同余。
如果一个数 $i$ 与 $m$ 互素，那么可知整个 $M_i$ 中所有的数都与 $m$ 互素。而所有这样的同余类称为模 m 的 缩同余类 ，简称缩系。
欧拉函数
欧拉函数 $\varphi(m)$ 就表示模 m 的缩系个数，也等价于 $1,2,\cdots,m-1$ 中与 $m$ 互质的数的个数。
这里列举欧拉函数的几个基本性质：
欧拉函数是积性函数，即若 $(p_1,p_2)=1$ 则有： $\varphi(p_1 \times p_2)=\varphi(p_1) \times \varphi(p_2)$ 。证明会用到裴蜀定理（其实就是欧几里得定理扩个倍），我手写了一份，放到 附录1 中了。
如果有上面的铺垫，接下来的欧拉函数通用计算公式就很好理解了。
首先由于素数性质，显然有：$\varphi(p)=p-1$ ，这里 p 是素数。
于是就有
$$
\varphi(p^k)=\varphi(p) \times \varphi(p^{k-1}) = \varphi(p) \times \varphi(p) \times \varphi(p^{k-2}) = \cdots = (\varphi(p))^k = (p-1)^k = p^k \cdot (1- \frac{1}{p})
$$
又由于所有非零整数都可以唯一的分解为：
$$
n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot p_3^{\alpha_3} \cdots p_m^{\alpha_m}
$$
所以对于所有非零整数 $n$ ，都可以这样计算欧拉函数 $\varphi(n)$ 的值：
$$
\begin{split}
\varphi(n) &= \varphi(p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot p_3^{\alpha_3} \cdots p_m^{\alpha_m}) \\
&= \varphi(p_1^{\alpha_1}) \cdot \varphi(p_2^{\alpha_2}) \cdot \varphi(p_3^{\alpha_3}) \cdots \varphi(p_m^{\alpha_m}) \\
&= p_1^{\alpha_1} \cdot (1-\frac{1}{p_1}) \times p_2^{\alpha_2} \cdot (1-\frac{1}{p_2}) \times p_3^{\alpha_3} \cdot (1-\frac{1}{p_3}) \times \cdots \times p_m^{\alpha_m} \cdot (1-\frac{1}{p_m}) \\
&= p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_m^{\alpha_m} \times (1-\frac{1}{p_1}) \cdot (1-\frac{1}{p_2}) \cdots (1-\frac{1}{p_m}) \\
&= n \cdot (1-\frac{1}{p_1}) \cdot (1-\frac{1}{p_2}) \cdots (1-\frac{1}{p_m})
\end{split}
$$
欧拉定理
如果 $(a,n)=1$ ，则有：
$$
a^{\varphi(n)} \equiv 1 \ (mod \ n)
$$
关于证明：
任取模 n 的缩系 $(r_1,r_2,\cdots,r_{\varphi(m)})$ ，因为 $(a,n)=1$ ，所以 $(ar_1,ar_2,\cdots,ar_n)$ 也是模 m 的缩系，从而有：
$$
r_1 \cdot r_2 \cdots r_{\varphi(n)} \equiv ar_1 \cdot ar_2 \cdots ar_{\varphi(n)} = a^{\varphi(n)} \times r_1 \cdot r_2 \cdots r_{\varphi(n)} \ (mod \ n)
$$
两边约去 $r_1 \cdot r_2 \cdots r_{\varphi(n)}$ 即证！
导出公式
欧拉定理可以推出许多有意思的结论。
当欧拉定理中的 $n=p$ 为素数时候，就有：
$$
a^{p-1} = a^{\varphi(p)} \equiv 1 \ (mod \ p)
$$
这就是 费马小定理 。
而对于一个正整数 $a$ ，如果另外一个正整数 $b$ 满足：
$$
a \cdot b \equiv 1 \ (mod \ p)
$$
则称 $b$ 为 $a$ 模 p 意义下的 乘法逆元，有点像整数意义中的倒数
此时运用欧拉定理：
$$
a \cdot a^{\varphi(n)-1} = a^{\varphi(n)} \equiv 1 \ (mod \ p)
$$
所以 $\forall a \in N_+, \ \exists b \in N_+$ 使得：$a \cdot b \equiv 1 \ (mod \ p)$ 。即若 $(a,p)=1$ ，那么总存在这样一个满足的 $b$ 。
扩展欧几里定理
与其说是「定理」，我更愿意称之为「算法」。扩展欧几里得算法给出了裴蜀等式的一组基本解。
首先说说欧几里得算法，这个大家应该都不陌生，他还有个更广为人知的名字——辗转相除法。这是一个计算机求最大公因数常用的算法。
欧几里得定理 / 算法
设 $a,b$ 为整数，$b>0$ ，用下述方式反复进行带余除法，有限步后必然停止（余数为零）
- a 除以 b ：$a=bq_0+r_0, \ 0<r_0<b$
- b 除以 $r_0$ ：$b=r_0q_1+r_1, \ 0<r_1<r_0$
- $r_0$ 除以 $r_1$ ：$r_0 = r_1q_2+r_2, \ 0<r_2<r_1$
- ……
- $r_{n-2}$ 除以 $r_{n-1}$ ：$r_{n-2}=r_{n-1}q_n+r_n, \ 0<r_n<r_{n-1}$
- $r_{n-1}$ 除以 $r_n$ ：$r_{n-1}=r_nq_{n+1}$
这样 $(a,b)=r_n$
事实上，由于 $r_1,r_2,\cdots,r_n \in N/{0}$ ，且 $r_0>r_1>\cdots>r_n>\cdots \geq 0$ ，所有有限步内余数必然归零。
欧式算法不仅能算出 $(a,b)$ ，还能证明 $ax+by=(a,b)$ 总有解，并实际地求出这组解。这个过程就被成为扩展欧几里得算法。
扩展欧几里得算法
扩展欧几里得算法就是将上面的欧几里得算法推回去。
首先由上面过程中倒数第二行：
$$
(a,b) = r_n = r_{n-2} - r_{n-1} q_n
$$
就得到一个「$(a,b) = r_{n-2} \times$ 整数 $+ \ r_{n-1} \times$ 整数」的形式
而继续往前推，将 $r_{n-3} = r_{n-2} q_{n-1} + r_{n-1}$ 代入：
$$
(a,b) = r_{n-2} (1 + q_{n-1} q_n) - r_{n-3} q_n
$$
这又得到「$(a,b) = r_{n-3} \times$ 整数 $+ \ r_{n-2} \times$ 整数」的形式。
反复进行，最后就能推到「 $(a,b) = a \ \times$ 整数 $+ \ b \ \times$ 整数」的形式了。而其中那两个整数就是我们要算的 $(x,y)$ 。
RSA 算法流程
完成了上面一点点基础铺垫后，我们就可以来看看这个算法是怎么工作的了。
密钥生成流程
我们还是使用甲和乙想进行加密对话为例，只不过他们这次生活在现代。
一、生成两个不相等的素数 $(p,q)$
随便选取两个不相等的素数，这里为了方便演示，选 71 和 67。
而在应用中，这两个数字通常选得非常大，这样几乎无法破解。
二、计算 $n = p \times q$
甲把 71 和 67 乘起来，得到 4757 。
这个 n 的二进制数码长度就是密钥的「位数」。如 4757 的二进制 1001010010101 有 13 位，那么这个密钥的长度就是 13 位的。一般 RSA 密钥的长度会去到 2048 甚至 4096 位，是相当大的数了。
三、计算出 $\varphi(n) = (p-1) \times (q-1)$
甲根据欧拉函数性质算出 $\varphi(4757) = 4620$
四、在 $(1,\varphi(n))$ 范围内随机选取一个的 $e$
为了方便演示，这里甲选取了 19 作为这个 $e$ 。
五、计算 $e$ 关于 $\varphi(n)$ 的乘法逆元 $d$
上面说过可以使用欧拉定理求解，但是那样做结果太大了，我们不妨换一个思路。
$$
e d \equiv 1 \ (mod \ \varphi(n)) \Leftrightarrow e d - 1 = k \varphi(n) \ (k \in Z)
$$
所以我们改求方程：
$$
e \cdot d + \varphi(n) \cdot k = 1
$$
的整数解 $(d,k)$ 。
这时就可以使用扩展欧几里得算法得到绝对值比较小的解了。显然扩欧给计算机来完成更加合理，我分别用 Python 和 C++ 编写了这个算法的程序，地址放在 附录2 。
好的，这样甲根据 $(e,\varphi(n))=(19,4620)$ 算出对应的 $(d,k) = (1459,-6)$
六、将 $(n,e)$ 封装为公钥，$(n,d)$ 封装为私钥
完成上面所有计算后，甲将 $(4757,19)$ 封装为公钥，将 $(4757,1459)$ 封装为私钥。
至此你已经完成了所有生成密钥的工作。
加 / 解密 流程
加密详细
假如乙要向甲发送加密信息 “m” ，m 必须是整数（字符串可以采用编码来转换）且 $(0 \leq)\ m < n$ 。
那么乙就必须要使用甲的公钥对 m 进行加密。而所谓「加密」，就是算出这样的 c ：
$$
m^e \equiv c \ (mod \ n)
$$
假如乙的 $m=53$ ，则乙的 c 不难算出：
$$
53^{19} \equiv 3328 \ (mod \ 4757)
$$
这样就加密好了，乙把 3328 发给甲。
解密详细
如果对于上面模式生成的 c ，那么下述等式必然成立：
$$
c^d \equiv m \ (mod \ n)
$$
证明十分基础，但是过程有点长，这里证明就用到了欧拉定理，我手写了一份放在 附录3 。
甲使用自己的私钥解密：
$$
3328^{1459} \equiv 53 \ (mod \ 4757)
$$
这样就得到了原来的信息。而中途别人没有私钥，便无从知道信息。
而由于 $e$ 是 $d$ 的乘法逆元同时也意味着 $d$ 为 $e$ 的乘法逆元，就像我本身是我的倒数的倒数一样。所以 $e,d$ 是对称的，将上面 $d,e$ 互换，效果完全不变。也就是我使用私钥加密的信息也只能使用公钥解开，过程就不再重复了。
RSA 算法安全性
在上面生成密钥的流程中，我们一共接触了 6 个数字：
- $p$
- $q$
- $n$
- $\varphi(n)$
- $e$
- $d$
其中 $(n,e)$ 公开，所以一旦泄露了 $d$ 就意味着私钥泄露。
那么我们有没有一种方法可以科学地算出 d 呢？
首先注意一下这些数的先后顺序，$e$ 是我们取的，在此之前已经算好了 $\varphi(n)$ ，再才是根据 $e d \equiv 1 \ (mod \ \varphi(n))$ 算出 $d$ 。
所以我们的目标转换为算出 $\varphi(n)$ ，而 $\varphi(n)$ 也是根据 $\varphi(n) = (p-1)(q-1)$ 算出来的，进而我们需要算 $p,q$ 。
而唯一的关于 $p,q$ 唯一（公开）的信息只有：$n = p \times q$ ，所以 如果我们能将 n 质因数分解，那么我们就能爆算出 d ！这样就意味着私钥被破解。
遗憾的是 目前人类没有找到一种在可接受复杂度内的质因数分解算法，同时也没有人能证明这种算法不存在。而除了暴力破解，还没发现一种行之有效的方法。
目前有被报道的最大破解的密钥长度为 768 ，一般我们认为密钥长度在 2048 以上都是安全的了。
长信息细节处理
由于用于加密的 m 必须小于 n ，所以一些很长的内容就没办法这样压缩。一种方法是像 BitTorrent 一样将信息分块，然后对每一块加密。
但是比起其他对称加密算法，RSA 的加密速度实际上要慢得多！所以一般使用对称加密算法来加密内容，然后再使用 RSA 加密这个对称密钥。
后
或许对于压缩算法来说，它提升了我们上网的体验，并降低了许多上网的成本，使资源能够更加高效地利用。
而对于非对称加密算法来说，它才是真正让我们目前许多网上操作可以进行的保障。现在极大地方便我们生活的网络平台，如网购、即时通讯等，如果没法妥善保管好你的信息，这将是件多么不敢想象的事情，这些平台也许根本没法得到应用。
现在我们看着这个算法很好理解，甚至感觉有点理所当然。但理所当然在真正蜕变为理所当然前从来不会认为是理所当然的，它是各大数学家、计算机科学家等各行各业的天才们费尽心血创造出来的奇迹，让你敢于将自己相当一部分最重要的数据放在自己看不见摸不着的地方。
就像不敢想象数据无法妥善保管一样，我同样不敢想象要是没有网络我们的生活还会变成什么样。感谢这些前辈大佬们，致敬！
Attachments：
字写得不好，献丑了。
附录3：Page
