# RSA公钥密码系统

本节我们将阐述模运算在密码学中的一大应用：RSA密码系统。这一系统的名称来源于它的三位发明者：Ronald Rivest, Adi Shamir 和 Leonard Adleman。

# 场景

RSA的算法是建立在模运算的基础之上的。我们可以将加密与解密的场景进行简化：
- 假设张三需要传递一个数字 $x$ 给李四，那么李四可以先取一个整数 $N=pq$ （其中 $p,q$ 为比较大的质数，大约几百位），并取另一个整数 $e$ ，满足 $e$ 与 $(p-1)(q-1)$ 互质。
- 这样李四就可以将 $(N,e)$ 设为一个公钥（但 $p$ 和 $q$ 不是）。而李四的私钥则是另一个整数 $d$ ，它是 $e$ 模 $(p-1)(q-1)$ 的乘法逆（因为互质所以一定存在）。
- 最后得到的加密与解密过程如下：张三将数字 $x$ （假设已经对 $N$ 取模）使用加密函数 $E(x)\equiv x^e(\mathrm{mod}\hspace{0.2em}N)$ ，并传递给李四；李四得到加密后的 $y=E(x)$ 后，使用解密函数 $D(y)\equiv y^d(\mathrm{mod}\hspace{0.2em}N)$ ，就能得到原始信息 $x$ 。
那么，为什么这个算法是可行的呢？即：为什么上面的算法满足 $D(E(x))=x$ ？我们可以从下面这个定理开始推导。

在介绍费马小定理之前，先引入一个关于幂和模运算的问题：对于正整数 $n$ ，假设整数 $x\in\{1,\cdots,n-1\}$ ，那么满足
$\underbrace{x\cdot x\cdot\cdots\cdot x}_{d\text{个}x}\equiv 1(\mathrm{mod}\hspace{0.2em}N)$
的最小整数 $d$ 是多少？
事实上，这个 $d$ 可以表示为 $\varphi(N)$ （也称为欧拉函数），其值为与 $N$ 互质且不超过 $N$ 的整数个数。
因而我们可以得到： $x^{\varphi(N)}\equiv 1(\mathrm{mod}\hspace{0.2em}N)$ 。
当 $N$ $N$ 取质数时， $\varphi(N)=N-1$ $φ (N) = N - 1$ ，就得到了费马小定理：对任意质数 $p$ $p$ 与任意 $a\in\{1,2,\cdots,p-1\}$ $a \in {1, 2, \dots, p - 1}$ ，有 $a^{p-1}\equiv 1(\mathrm{mod}\hspace{0.2em}p)$ $a^{p - 1} \equiv 1 (mod p)$ .下面对这个定理进行简单证明：
- 由上一节的推导可知，集合 $S=\{1,2,\cdots,p-1\}$ 与 $S'=\{a(\mathrm{mod}\hspace{0.2em}p),2a(\mathrm{mod}\hspace{0.2em}p),\cdots,a(p-1)(\mathrm{mod}\hspace{0.2em}p)\}$ 是完全同构的（只是顺序不同）
- 因而，将 $S$ 中各元素相乘得到的结果与 $S'$ 各元素相乘得到的结果模 $p$ 同余，即：
  $(p-1)!\equiv a^{p-1}(p-1)!(\mathrm{mod}\hspace{0.2em}p)$
- 又因为 $(p-1)!$ 与 $p$ 互质，所以 $(p-1)!$ 模 $p$ 的乘法逆存在。上面的式子两边同时乘以这个乘法逆，就得到 $a^{p-1}\equiv 1(\mathrm{mod}\hspace{0.2em}p)$ .
利用这个定理，我们就能对RSA的正确性进行证明。

即证：
$(x^e)^d\equiv x(\mathrm{mod}\hspace{0.2em}N)\quad\forall x\in\{0,1,\cdots,N-1\}$
因为 $ed\equiv 1(\mathrm{mod}\hspace{0.2em}(p-1)(q-1))$ ，所以设 $ed=k(p-1)(q-1)+1$ ，那么有
$x^{ed}-x=x^{1+k(p-1)(q-1)}-x=x(x^{k(p-1)(q-1)}-1)$
可以证明 $p\mid x^{ed}-x$ ：若 $p\mid x$ ，则显然成立；若 $p\nmid x$ ，则由费马小定理， $x^{p-1}\equiv 1(\mathrm{mod}\hspace{0.2em}p)$ ，故 $x^{k(p-1)(q-1)}-1\equiv 0(\mathrm{mod}\hspace{0.2em}p)$ ，即 $p\mid x^{ed}-x$ 。
由对称性可得 $q\mid x^{ed}-x$ 。因而有 $N=pq\mid x^{ed}-x$ ，故原式得证。
当然上面的证明过程也可以用中国剩余定理（CLT）更加简洁的呈现：由上面的证明得到：
$\left\{ \begin{aligned} &x^{ed}\equiv x(\mathrm{mod}\hspace{0.2em}p)\\ &x^{ed}\equiv x(\mathrm{mod}\hspace{0.2em}q) \end{aligned} \right.$
于是由中国剩余定理，只有唯一的 $x(\mathrm{mod}\hspace{0.2em}pq)$ 同时满足这两个方程。

那么，这个算法是如何保证它能够安全地传输信息呢？其实，这基于一个重要假设：
- 给定 $N,e$ 和方程 $y\equiv x^e(\mathrm{mod}\hspace{0.2em}N)$ ，没有高效的求解 $x$ 的算法。
王五要破解传递的加密信息，要么对 $x$ 进行枚举（这对于极大的整数 $N$ 而言显然不现实），要么尝试对 $N$ 进行质因数分解得到 $p,q$ ，并基于乘法逆推出 $d$ ，而这也是非常困难的（当然这没有被严格证明）。
那么对于张三与李四而言，它们加密与破解信息的难度又如何呢？
- 其实，他们最主要的工作是找到大质数 $p$ 和 $q$ 。验证一个数是不是质数需要的时间复杂度非常低（可达到 $O((\log n)^k)$ 量级），所以李四可以随机生成对应量级的正整数，直到找到合适的 $N=pq$ （相对的，寻找非质数的质因数的时间复杂度就很大）
- 事实上，可以证明：当 $n$ 非常大的时候， $n$ 附近的质数密度与 $\frac{\ln n}{n}$ 近似成正比。
- 另外，对于模运算，在Chapter 6中，我们提到使用重复平方可以大幅优化指数运算效率，最终的运算时间复杂度仅为 $O((\log N)^3)$ （乘法占两次，重复平方模占一次）
正是这种加密解密与破译之间巨大的运算效率差距使得RSA这种密码算法得以广泛应用。