当我们使用 git 同步代码，ssh 远程登录虚拟机、使用数字签名、加密哈希函数以及电子支付系统时，都会用到公钥加密系统，而支撑起公钥加密系统的理论便是数论。
数论是关于整数的理论，首先来了解一些基本的概念和理论，然后再看看前人为实现安全加密做出的努力，最后再介绍现在广泛使用的 RSA 公钥加密算法。
整除
定义：a 整除 b，当且仅当存在某个整数k，使得 $ak = b$。
通常用符号 $a | b$ 来表示 a 整除 b。根据定义，如果 $a | b$，那么 b 就是 a 的整数倍。从这个定义可以得出，任何整数都可以整除 0。
关于整除的一些引理
- 如果 $a | b$，那么对于任意 c，都有 $a | bc$
- 如果 $a | b$ 并且 $b | c$， 那么 $a | c$
- 如果 $a | b$ 并且 $a | c$，那么对于任意 s 和 t 都有 $a | sb + tc$
- 对于任意 $c \neq 0$, $a | b$ 当且仅当 $ca | cb$
当无法整除的时候 …
整除定理：令 n 和 d 为整数且$d \gt 0$，存在唯一的一对整数 q 和 r，使得：
$$n = q \cdot d + r \;AND\; 0 \le r \lt d$$
其中 q 称为 n 被 d 除的商，而 r 称为 n 被 d 除的余数。接下来我们用 $qcnt(n, d)$ 和 $rem(n, d)$ 分别表示这两者。举个栗子，$qcnt(2716, 10) = 271$ , $rem(2716, 10) = 6$，因为 $2716 = 271 * 10 + 6$
最大公约数
a 和 b 的最大公约数是指能同时整除 a 和 b 的最大整数，通常用符号 $gcd(a,b)$表示。（gcd 是 greatest common divisor 的缩写）。比如，$gcd(18,24) = 6$
最大公约数和线性组合
定理：a 和 b 的最大公约数是 a 和 b 可能的线性组合中最小的一个。
比如，54和44的最大公约数是4，显然4是52和44的一个线性组合：
$$6 \cdot 52 + (-7) \cdot 44 = 4$$
并且，52和44的其它线性组合没有比4更小的。
推论：一个整数是 a 和 b 的线性组合，当且仅当它是 $gcd(a,b)$ 的倍数
推论：假设我们有两个容量分别为 a 和 b 的容器，每个容器里能准确量出的水量永远是 a 和 b 的线性组合，也即是 a 和 b 的最大公约数的倍数。
最大公约数的性质
- 每一个能整除 a 和 b 的数都能整数 $gcd(a,b)$
- 对于任意 $k>0$, 都有 $gcd(ka,kb) = k \cdot gcd(a,b)$
- 如果 $gcd(a,b) = 1$，并且 $gcd(a,c) = 1$，那么 $gcd(a, bc) = 1$
- 如果 $a | bc$，并且 $gcd(a,b) = 1$，那么 $a | c$
- $gcd(a, b) = gcd(b, rem(a, b))$
其中第5点性质需要特别注意，它指导我们如何快速地计算两个数的最大公约数。比如：
$$gcd(28, 21) = gcd(21, rem(28,21)) = gcd(21, 7) = gcd(7, rem(21, 7)=gcd(7,0) = 7$$
算术基本定理
算术基本定理：每一个正整数都可以写成唯一的由质数相乘的形式：
$$n = p_1 \cdot p_1 \cdot p_2 \cdot \cdot \cdot p_j \; (p_1 \lt p_1 \lt p_2 \cdot \cdot \cdot \lt p_j)$$
这个定理告诉我们，每一个正整数都可以由一组质数相乘得到。
求余运算
同余的定义：a 和 b 对 n 做求模操作是同余的，当且仅当 $n | (a - b)$，这可以写成：
$$a\equiv b\pmod n$$
显然，当 a 和 b 的差能被 n 整除，那么 a 和 b 对 n 求模就没差异了，因为求模过程中要减去尽可能多的 n，而 a，b刚好相差整数个 n。
比如，$29 \equiv 15 \pmod 7$，因为 $7 | (29 - 15)$
同余和余数之间的关系：$a\equiv b\pmod n$ 当且仅当 $rem(a, n) = rem(b, n)$
另一个推论：$a \equiv rem(a, n) \pmod n$
下面是一些同余的其它性质：
- $a \equiv a \pmod n$
- 如果 $a \equiv b \pmod n$，那么 $b \equiv a \pmod n$
- 如果 $a \equiv b \pmod n$ 并且 $b \equiv c \pmod n$，那么 $a \equiv c \pmod n$
- 如果 $a \equiv b \pmod n$，那么 $a + c \equiv b + c \pmod n$
- 如果 $a \equiv b \pmod n$，那么 $ac \equiv bc \pmod n$
- 如果 $a \equiv b \pmod n$ 并且 $c \equiv d \pmod n$，那么 $a+c \equiv b+d \pmod n$
- 如果 $a \equiv b \pmod n$ 并且 $c \equiv d \pmod n$，那么 $ac \equiv bd \pmod n$
质数求模算术
乘法逆元
数 x 的乘法逆元表示为 $x^{-1}$，且有
$$x \cdot x^{-1} = 1$$
有一个例外是0没有逆元。实际上，乘法逆元是作用于实数域中的，比如 $3 * \frac 1 3 = 1$，而一个整数的逆元不可能还是一个整数。
然而，在求模运算中，整数的逆元还可能是整数！比如，假设5是模数，那么 3 就是 7 的乘法逆元，因为：
$$7 \cdot 3 \equiv 1 \pmod 5$$
事实上，所有以5为模数，和3同余的数都是7的乘法逆元。
引理：如果 p 是质数，并且 k 不是 p 的整数倍，那么以 p 为模数，k 存在乘法逆元。
相消
实数算术的一个特点是可以消除公约数，换句话说，如果 $m_1k=m2k$，且 $k \neq 0$，那么我们可以消去 k，得到 $m_1 = m_2$。然而，在求模算术中，消除公约数却是不允许的，比如：
$$2\cdot3 \equiv 4 \cdot 3 \pmod 6$$
消除3，上式就不成立了。然而，当模数是质数时，消除却是成立的。
引理：假设 p 是一个质数，并且 k 不是 p 的倍数。那么：
如果 $ak \equiv bk \pmod p$，就有 $a \equiv b \pmod p$
引理：假设 p 是一个质数，并且 k 不是 p 的倍数。那么序列：
$$rem(1\cdot k, p), rem(2\cdot k, p), …, rem(((p-1)\cdot k), p)$$
是下面序列的一个排序：
$$1, 2, …, (p - 1) $$
也即这两个序列相等，只是元素的顺序不同。
费马小定理
费马小定理：假设 p 是一个质数，k不是 p 的倍数，那么：
$$k^{p-1} \equiv 1 \pmod p$$
根据费马小定理，有：
$$k^{p-2} \cdot k \equiv 1 \pmod p$$
因此，$k^{p-2}$一定是 k 的乘法逆元
任意模量的算术
互质
数 a 和数 b 是互质的，当且仅当 $gcd(a, b) = 1$。比如，8和15是互质的，因为二者的最大公约数为1。注意到，除了质数的倍数，所有整数和某个质数 p 都是互质的。
引理：令 n 是一个正整数。如果 k 与 n 互质，那么存在一个整数 $k^{-1}$使得：
$$k \cdot k^{-1} \equiv 1 \pmod n$$
从这个引理可以看出，不需模数是质数，只要 k 和 n互质，就可以安全地进行消去操作。
推论：假设 n 是一个正整数并且 k 与 n 互质，如果
$$ak \equiv bk \pmod n$$
那么
$$a \equiv b \pmod n$$
引理：假设 n 是一个正整数并且 k 与 n 互质。那么序列：
$$rem(k_1\cdot k, n), rem(k_2\cdot k, n), …, rem((k_r\cdot k), n)$$
是下面序列的一个排序：
$$k_1, k_2, …, k_r$$
也即这两个序列相等，只是元素的顺序不同。
欧拉定理
欧拉函数 $\phi(n)$表示集合${1,2,…,n}$中和 n 互质的数的个数。比如$\phi(7) = 6$，因为1，2，3，4，5，6与7是互质的。
定理：对任意的数 n， 如果$p_1,p_2,…,p_j$ 是 n 的互不相同的质因子，那么：
$$\phi(n) = n(1-\frac 1 p_1)(1-\frac 1 p_2)\cdot \cdot \cdot (1-\frac 1 p_j)$$
推论：令 $n = pq$，p，q 为不同的质数，那么 $\phi(n) = (p - 1)(q - 1)$
欧拉定理：假设 n 是一个正整数并且 k 与 n 互质，那么：
$$k^{\phi(n)} \equiv 1 \pmod n$$
实际上，费马小定理是欧拉定理中的n是质数时的的一个特例，当 n 为质数时有：
$$\phi(n) = n - 1$$
图灵的故事
图灵是计算机领域的天才，也是他最早提出用数论来解决加密传输的问题。当时它未把文章发表，只留有代码，下面我们就看看众多的计算机学家如何从图灵的代码开始，一步步完善，最终形成如今成熟加密系统的过程。
图灵代码（版本1.0）
实现加密传输的第一个问题是要把文字信息转换为整数，这样我们就可以对整数应用数学操作。这个过程不是加密的过程，因此可以使用一些简单的办法，比如把每个字符或者汉子用一个数字表示，所有字符表示的数字串联在一起就形成了一个很大的整数。比如，“今晚两点行动”可以用下面的方法编码：
今 晚 两 点 行 动
22 09 03 20 15 25
图灵的代码需要信息被编码成一个质数，而实际上，通过在原有的整数后面添加几位数可以达到这个要求，这个算法已经比较成熟。信息被编码成质数后，加密和解密的过程按照下面的方式进行。假设 m 是未加密的信息，$m^*$是加密后的信息，k是密钥：
开始前 信息的发送和接收方在某个阴暗的街角确定一个密钥k，k是一个很大的质数。
加密 信息的发送方通过下面的方式加密信息：
$$m^* = m \cdot k$$
解密 信息的接收方通过下面的方式还原信息：
$${m^* \over k} = {m \cdot k \over k} = m$$
图灵算法加密过后的数是原来的质数与一个很大的质数密钥相乘的结果，是一个很大的数，要想直接因式分解这个数得到密钥k是很难得一件事，然而，使用数论的技巧却可以很容易打破这个系统。
假设我们得到了两个经过加密的信息：
$$m_1^\ast= m_1 \cdot k \;and\; m_2^\ast= m_2 \cdot k$$
那么$m_1^\ast$$和$$m_2^\ast$的最大公约数就是k！从前面可以知道，k可以非常快速地求出来！
图灵代码（版本2.0）
开始前 信息的发送和接收方确定一个很大的质数 p, p可以是公开的（p将作为我们的模数）。另外，他们还偷偷地确定一个私有密钥$k\in {1,2,…,p-1}$
加密 信息 m 可以是集合${0,1,2,…,p-1}$中的任意一个数，并且 m 不需要是质数。信息的发送方通过下面的方式加密信息：
$$m^\ast = rem(mk, p)$$
可以看出，加密过程不是简单的求积，而是将求积的结果取了模
解密 解密的过程需要用到前面提到的求模代数里同余和乘法逆元的知识。
根据余数的定义，我们知道加密后的信息是原信息与质数 k 相乘以 p 为模数的余数，即：
$$m^\ast = rem(mk, p) = mk \pmod p$$
现在我们想要从$m^*$求出 m，自然想到如果在上式两边同乘以k的逆元，那么就可以消去和 m 相乘的 k，从而得到 m。
假设 k 的乘法逆元是$k^{-1}$（之所以要假设，是因为k的乘法逆元可能不存在），那么有
$$m^\ast k^{-1} \equiv mk\cdot k^{-1} \equiv m \pmod p$$
由于 $m \in {1, 2, …, p - 1}$，有
$$m = rem(m^\ast k^{-1}, p)$$
实际上，这个思路的公钥k也极容易泄露出去！我们需要知道一对加密前和加密后的信息就可以窃取公钥。下面是具体的做法：
假设加密前的信息 m 和加密后的信息 $m^*$ 被泄露，根据加密过程，有：
$$m^\ast = rem(mk, p)$$
即
$$m^\ast = mk \pmod p$$
由于 p 是一个质数，所以 m 与 p 互质，即：
$$gcd(m, p) = 1$$
由于 m 和 p 已知，可以算出 m 以 p 为模数的乘法逆元 $m^{-1}$，使得
$$m\cdot m^{-1} \equiv 1 \pmod p$$
当我们把已知的 $m^*$ 和 m 的乘法逆元相乘就有：
$$m^\ast \cdot m^{-1} \equiv km \cdot m^{-1} \equiv k \pmod p$$
看到了吗？我们得到了密钥 k ！只要我们继续算出 k 以 p 为模数的乘法逆元，就可以解密任何信息！
RSA 算法
RSA 公钥加密算法是1977年MIT发明的，是目前使用最广泛的加密算法，很难被窃取，它不需要交换私钥，只要数据接收者自己生成一对公钥和一对私钥，任何人都可以使用接收者发布的公钥加密信息，接受者然后使用只有它自己知道的私钥进行解密。
开始前 信息接收方使用下面的方式创建一对公钥和一对私钥
- 生成两个不同的质数，p 和 q。由于它们要用来生成私钥，因此必须要藏好。
- 让 n = pq。n 将作为公钥对的一部分，由于要分解两个大质数的乘积十分困难，因此p和q很难被破解。
- 选择一个整数 e 使得 $gcd(e, (p-1)(q-1)) = 1$。公钥对就是(e, n),可以被广泛分发。
- 计算 d，使得 $de \equiv 1 \pmod {(p-1)(q-1)}$。私钥对就是(d, n),必须要藏好。
可以看出，整数 e 和 d 是以 (p-1)(q-1) 为模的乘法逆元
加密 给定一个信息 m，发送方首先检查 $gcd(m, n) = 1$,接着用公钥对信息进行加密：
$$m^*=rem(m^e,n)$$
解密 使用私钥把加密的信息还原回去：
$$m=rem({m^\ast}^d, n)$$
现在我们证明为了什么可以这么还原回去：
根据加密过程知：
$$m^\ast = rem(m^e,n) \equiv m^e \pmod n$$
即
$$m^\ast \equiv m^e \pmod n$$
两边同时d方：
$${m^\ast}^d \equiv m^{ed} \pmod n$$
由于 e 与 d 互质，根据最大公约数和线性组合的关系知存在 r 使得：
$$e\cdot d = 1 + r(p - 1)(q - 1)$$
代入到上式有：
$${m^\ast}^d \equiv m^{1 + r(p - 1)(q - 1)} \pmod n$$
又因为 $n = pq$，根据费马小定理，有
$$m^{p-1} \equiv 1 \pmod p$$
$$m^{q-1} \equiv 1 \pmod q$$
$${m^\ast}^d \equiv m^{1 + r(p - 1)(q - 1)} \pmod p$$
$${m^\ast}^d \equiv m^{1 + r(p - 1)(q - 1)} \pmod q$$
因此
$${m^\ast}^d \equiv m \pmod p$$
$${m^\ast}^d \equiv m \pmod q$$
即
$$p | {m^\ast}^d - m$$
$$q | {m^\ast}^d - m$$
$$pq | {m^\ast}^d - m$$
所以
$${m^\ast}^d \equiv m \pmod n$$
最后便得到了
$$m=rem({m^\ast}^d, n)$$