From gcd to RSA
这篇文章是有个朋友要选一门数学素养课，涉及到的内容其实并不复杂，就心血来潮的写了这篇文章梳理一下从小学数学到理解 RSA 需要的基础知识。阅读这篇你只需要有基础的阅读能力即可。
这篇文章只是一篇简单的 Walkthrough，如果对其中的某个定理想有更深入的研究，请复制到搜索引擎，网上会有更详细和严谨的资料。同时感谢龙二的审稿。
数学运算
基本运算
为了方便叙述，我们定义基本运算为下面三种：
- 加法运算 $+$；
- 减法运算 $-$；
- 乘法运算 $\times$ 或者 $\cdot$。
上述三种运算均满足交换律（$a+b=b+a$）和结合律（$(a+b)+c=a+(b+c)$）。乘法运算对于加减法满足分配律，即 $(a\pm b)\times c = a\times c\pm b\times c$。
取余与同余运算
取余运算：令 $a=kb+r$，其中 $k$ 最大，则 $a$ 模 $b$ 的余数为 $r$，记作 $a{\ \text{mod}\ } b = r$。
同余运算：如果 $a{\ \text{mod}\ } r=b{\ \text{mod}\ } r$，则称 $a$ 和 $b$ 模 $r$ 同余，记作 ${{a}\equiv {b}\pmod {r}}$。
整除运算：如果 $a{\ \text{mod}\ } b=0$，则称 $b$ 整除 $a$，记作 $b|a$。
模 $n$ 同余的所有数构成的等价类叫做同余类。假定余数为 $a$，则同余类可记作 $[a]=\{\cdots,a-2n,a-n,a,a+n,a+2n,\cdots\}$。如 $3$ 的同余类有 $[0], [1], [2]$ 三个。
取余和同余保持基本运算（将 $a{\ \text{mod}\ } b = r$ 看作 ${{a}\equiv {r}\pmod {b}}$)，也就是说：
$$ \left. \begin{matrix} {{a}\equiv {b}\pmod {m}} \\{{c}\equiv {d}\pmod {m}} \end{matrix} \right\} \Rightarrow \left\{ \begin{matrix} {{a\pm c}\equiv {b\pm d}\pmod {m}} \\{{ac}\equiv {bd}\pmod {m}} \end{matrix} \right. $$
最大公约数
约数与 gcd 运算
约数：能整除 $n$ 的正整数为 $n$ 的约数，所有这样的约数构成约数集合 $D_n=\{d|n, d\in\mathbb{N}^+\}$。
最大公约数：两个数公共的最大约数就叫做两个数的最大公约数(Greatest Common Divisor)，记作 $\gcd(a, b)$。例如，$\gcd(15,27)=3$。
在日常计算过程中，我们通常使用短除法来手动计算两个数的最大公约数。
辗转相除法
$\forall a,b\in \mathbb{Z}$，不失一般性，设 $a>b$，则 $\gcd(a, b) = \gcd(b, a{\ \text{mod}\ } b)$，不断迭代至其中较小的一项等于 $0$ 为止，此时的非 $0$ 项就是答案。
如果 $a{\ \text{mod}\ } b = r$，也可写作 $\gcd(a,b)=\gcd(b,r)$。
令 $a=kb+r$，我们需要证明 $\gcd(a,b)=\gcd(b,r)$。
从 $\gcd(a,b)$ 出发，我们有：
$$ \begin{aligned} &\gcd(a,b)|a \land \gcd(a,b)|b \\\mathllap{\implies} & \gcd(a,b) | (a-kb) \\\mathllap{\implies} & \gcd(a,b) | r \\\mathllap{\implies} & \gcd(a,b)\le\gcd(b,r) \end{aligned} $$
关于 $3\to4$ 的提示：考虑任意因子 $q|b, q|r$，易得 $q\le\gcd(b,r)$。第三步我们证明了 $\gcd(a,b)|r$，而我们自然有 $\gcd(a,b)|b$，则 $\gcd(a,b)\le\gcd(b,r)$，即为第四步。
从 $\gcd(b,r)$ 出发，我们有：
$$ \begin{aligned} &\gcd(b,r)|b \land \gcd(b,r)|r \\\mathllap{\implies} & \gcd(b,r) | (kb+r) \\\mathllap{\implies} & \gcd(b,r) | a \\\mathllap{\implies} & \gcd(b,r)\le\gcd(a,b) \end{aligned} $$
综合两式立即可得 $\gcd(a,b)=\gcd(b,r)$。
而易知 $|r|<|b|$，我们总可在有限步后得到 $b{\ \text{mod}\ } r=0$，此时算法退出，我们得到的 $r$ 就是答案，得证。◼
裴蜀定理
裴蜀定理的证明与本文相关性不大，感兴趣的参考 ProofWiki 上的证明。
质数与互质
质数：也叫素数。质数指大于 $1$ 且只能被自己和 $1$ 整除的自然数，常见的质数为 $2$, $3$, $5$, $7$ 和 $11$。不是质数的自然数被称为合数。
互质：两个数 $a,b$ 互质即 $\gcd(a,b)=1$。
同余除法第一原理
考虑 $a,b,c,n\in\mathbb{Z}$，如果 $c$ 和 $n$ 互质，那么：
$$ {{ca}\equiv {cb}\pmod {n}}\implies{{a}\equiv {b}\pmod {n}} $$
证明较为简单，留作习题。（提示：考虑 $ca=xn+r, cb=yn+r$，然后讨论 $n$ 整除性即可。）
代数系统、群、环
代数系统
考虑有一个元素集合 $A$（如自然数集合），我们定义某一种运算（通常为二元运算），如果任意在 $A$ 中的元素经过这种运算之后的结果仍然在 $A$ 内，我们就称这个集合 $A$ 关于此运算封闭。
由一个元素集合 $A$ 和一系列在 $A$ 上封闭的运算组成的系统就叫做代数系统（也叫做代数结构）。
半群和幺半群
考虑代数系统 $(S,\times)$，如果满足：
- 结合律：$\forall a,b,c\in S, (a\times b)\times c=a\times(b\times c)$。
那么我们称 $(S, \times)$ 是一个半群。
考虑半群 $(M, \times)$，如果满足：
- 存在单位元：$\exists e\in M$ 使得 $\forall a\in M, a\times e=e\times a=a$。
那么我们称 $(M,\times)$ 是一个幺半群。
群和阿贝尔群
考虑幺半群 $(G, \times)$，如果满足：
- 存在逆元：$\forall a\in G$ 总满足 $\exists x\in G, a\times x=x\times a=e$，通常也记 $x=a^{-1}$。
那么我们称 $(G,\times)$ 是一个群。
考虑群 $(A, \times)$，如果满足：
- 交换律：$\forall a,b\in A, a\times b=b\times a$。
那么我们称 $(A, \times)$ 是一个阿贝尔群或交换群。
环
考虑代数系统 $(R, +, \times)$，如果满足：
- $(R, +)$ 为阿贝尔群。
- $(R, \times)$ 为半群。
- $\times$ 关于 $+$ 运算可分配：
- $\forall a,b,c\in R, a\times(b+c)=a\times b+a\times c$；
- $\forall a,b,c\in R, (a+b)\times c=a\times c+b\times c$。
那么我们称 $(R, +, \times)$ 为环。
整数模 $n$ 乘法群
我们定义整数模 $n$ 乘法为 $a\cdot b = a\times b{\ \text{mod}\ } n$。
考虑所有和 $n$ 互质的小于 $n$ 的整数集合 $\mathbb{Z}/n$，那么 $(\mathbb{Z}/n, \cdot)$ 称作整数模 $n$ 乘法群，我们通常记作 $(\mathbb{Z}/n\mathbb{Z})^\times$。
这个乘法群同样可以被描述为：
- 原始模 $n$ 同余类：由所有与 $n$ 互质的同余类构成的集合。
- 模 $n$ 乘法环的单位群。
我们来证明 ${(\mathbb{Z}/{n}\mathbb{Z})^\times}$ 构成一个群。
- 封闭性：$\forall a,b\in {(\mathbb{Z}/{n}\mathbb{Z})^\times}, \gcd(a,n) = 1, \gcd(b,n)=1\implies\gcd(ab,n)=1$。由于 ${(\mathbb{Z}/{n}\mathbb{Z})^\times}$ 包含了所有模 $n$ 且与 $n$ 互质的数，则 $ab\in{(\mathbb{Z}/{n}\mathbb{Z})^\times}$，得证。
- 交换律：由取余运算保持乘法运算律立即可证。
- 单位元：选择 $e=1\in{(\mathbb{Z}/{n}\mathbb{Z})^\times}$，易得 $\forall a\in{(\mathbb{Z}/{n}\mathbb{Z})^\times}, 1\cdot a\equiv a\cdot1\equiv a\pmod n$，得证。
- 逆元：任选 $a\in{(\mathbb{Z}/{n}\mathbb{Z})^\times}$，我们有 $\gcd(a,n)=1$，则根据裴蜀定理知 $ax+yn=1$ 有解，则可得 $1{\ \text{mod}\ } n=ax\implies{{ax}\equiv {1}\pmod {n}}$；而 $ax+yn=1$ 可以得出 $\gcd(x,n)=1$，则 $x\in{(\mathbb{Z}/{n}\mathbb{Z})^\times}$。所以 $x$ 为 $a$ 的一个逆元。
则整数模 $n$ 乘法构成一个群，得证。◼
特别的，对于质数 $p$，根据定义我们可得 ${(\mathbb{Z}/{p}\mathbb{Z})^\times}$ 为小于 $p$ 的所有正整数。
欧拉函数和欧拉定理
欧拉函数
我们定义欧拉函数 $\phi(n)$ 为对于正整数 $n$，小于 $n$ 且与 $n$ 互质的数的数目。从定义可知，$|{(\mathbb{Z}/{n}\mathbb{Z})^\times}|=\phi(n)$。
欧拉函数有以下两个性质：
- 对于质数 $p$，有 $\phi(p)=p-1$；
- 欧拉函数为积性函数，即对于互质的整数 $a$ 和 $b$，$\phi(ab)=\phi(a)\phi(b)$。
欧拉函数的求法和更多性质不在本文的范围内，感兴趣的可以看 Wolfram Mathworld 上的介绍。
欧拉定理
对于互质整数 $a, n$，下面同余式恒成立：
$$ {{a^{\phi(n)}}\equiv {1}\pmod {n}} $$
如 $n$ 为一个质数 $p$，有：
$$ {{a^{p-1}}\equiv {1}\pmod {p}} $$
上式即为费马小定理，可以看出来是欧拉定理的一个特殊形式。
考虑 ${(\mathbb{Z}/{n}\mathbb{Z})^\times}=\{p_1,\cdots,p_{\phi(n)}\}$，我们先证明 $a{(\mathbb{Z}/{n}\mathbb{Z})^\times}=\{ap_1,\cdots,ap_{\phi(n)}\}$ 在模 $n$ 意义下等于 ${(\mathbb{Z}/{n}\mathbb{Z})^\times}$。
- 元素是唯一的：假设存在 ${{ap_i}\equiv {ap_j}\pmod {n}}$，那么自然有 $n|a(p_i-p_j)$，由于 $a$ 以及 $p_i-p_j$ 均和 $n$ 互质，产生矛盾，即不存在 ${{ap_i}\equiv {ap_j}\pmod {n}}$，得证。
- 元素均在 ${(\mathbb{Z}/{n}\mathbb{Z})^\times}$ 内：由于 $a$ 和 $n$ 互质，$a\in{(\mathbb{Z}/{n}\mathbb{Z})^\times}$，又由于 ${(\mathbb{Z}/{n}\mathbb{Z})^\times}$ 是阿贝尔群，关于乘法运算封闭，则 $\forall p\in{(\mathbb{Z}/{n}\mathbb{Z})^\times},ap\in{(\mathbb{Z}/{n}\mathbb{Z})^\times}$。
那立即可得 $|a{(\mathbb{Z}/{n}\mathbb{Z})^\times}|=\phi(n)$，且元素两两不同，两个集合相等即证。
由于 ${(\mathbb{Z}/{n}\mathbb{Z})^\times}=a{(\mathbb{Z}/{n}\mathbb{Z})^\times}$，我们把两个集合的元素各求一个积，易得：
$$ \begin{aligned} \prod_{i=1}^{\phi(n)}p_i&\equiv\prod_{i=1}^{\phi(n)}ap_i\pmod n \\\prod_{i=1}^{\phi(n)}p_i&\equiv a^{\phi(i)}\prod_{i=1}^{\phi(n)}p_i\pmod n \\\end{aligned} $$
由于 $p_i$ 均和 $n$ 互质，可知 $\prod_{i=1}^{\phi(n)}p_i$ 也与 $n$ 互质。应用同余除法第一原理，立即可得 ${{a^{\phi(i)}}\equiv {1}\pmod {n}}$，得证。◼
RSA
RSA 简介
RSA 加密演算法是一种非对称加密演算法，在公开密钥加密和电子商业中被广泛使用。RSA 是 1977 年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。
RSA 算法
- 密钥对产生
- 任选两个足够大的质数 $p$ 和 $q$，计算 $n=pq$。
- 计算 $\phi(n)=\phi(p)\times\phi(q)=(p-1)(q-1)$。丢弃 $p$ 和 $q$。
- 选择一个 $e$ 满足 $1<e<\phi(n)$ 且 $\gcd(e,\phi(n))=1$，将 $(n, e)$ 作为公钥。
- 选择一个 $e$ 的逆元 $d$ 满足 ${{ed}\equiv {1}\pmod {\phi(n)}}$，将 $(n, d)$ 作为私钥。
- 加密：将信息编码为 $m$，其中 $0<m<n$。 计算 $c=m^e{\ \text{mod}\ } n$，$c$ 即为加密后的信息。
- 解密：计算 $m=c^d{\ \text{mod}\ } n$, $m$ 被还原。
关于加解密的正确性我们需要证明 ${{m^{ed}}\equiv {m}\pmod {n}}$。
$m$ 和 $n$ 互质
由于 ${{ed}\equiv {1}\pmod {\phi(n)}}$，则 $ed=k\phi(n)+1$，那么 $m^{ed}=m^{k\phi(n)+1}=m^{k\phi(n)}\cdot m$。由欧拉定理可知 ${{m^{\phi(n)}}\equiv {1}\pmod {n}}$，那么有 ${{m^{k\phi(n)}\cdot m}\equiv {m}\pmod {n}}$，得证。
$m$ 和 $n$ 不互质
考察 ${{m^{ed}}\equiv {m}\pmod {n}}$，对 $n$ 分解因子有 ${{m^{ed}}\equiv {m}\pmod {p}}$ 和 ${{m^{ed}}\equiv {m}\pmod {q}}$。我们现在要证明这两个式子。
由于 $p, q$ 均为质数，而 $m$ 和 $n$ 不互质，则 $m$ 必为其中的一个整数倍。不失一般性，令 $m=kp$，则第一个式子立即得证。由于 $m=kp<n=pq$，则 $k<p$，可知 $k\in{(\mathbb{Z}/{p}\mathbb{Z})^\times}$，那么立即有 $\gcd(kp, q)=1$。
现在我们来证明第二个式子。由于 $kp$ 和 $q$ 一定互质，又有 ${{ed}\equiv {1}\pmod {\phi(n)}}\implies ed=h(p-1)(q-1)+1$，则：
$$ \begin{aligned} m^{ed}&\equiv m^{h(p-1)(q-1)+1}\pmod q \\&\equiv (m^{q-1})^{h(p-1)}\cdot m\pmod q \\&\equiv (m^{\phi(q)})^{h(p-1)}\cdot m\pmod q \\&\equiv m\pmod q \end{aligned} $$
则原式得证。
所以 ${{m^{ed}}\equiv {m}\pmod {n}}$ 恒成立，正确性得证。◼
安全性
如果想要计算出 $d$，我们需要先因式分解出 $n=pq$，然后计算同余方程 ${{de}\equiv {1}\pmod {(p-1)(q-1)}}$。而目前并没有任何办法证明是否存在一种多项式时间的因式分解算法，因此只需要 $n$ 选的足够大，我们就可以认为 RSA 算法是安全的。