1. RSA 的数学基础

1.1. 欧拉函数

互素（互质）：两个整数的最大公约数为1，则称这两个数互素。

欧拉函数 $\varphi(n)$ ：$\varphi(n)$ 表示在小于或等于 $n$ 的正整数中，与 $n$ 互素的数的个数。

欧拉函数性质

1. 假如 $n$ 为素数，则 $\varphi(n)$ 为 $n-1$ ，因为一个素数和任何一个小于它的数都互素。
2. 假如 $m$ 和 $n$ 互素，则 $\varphi(mn) = \varphi(m) * \varphi(n)$ 。

1.2. 费马小定理

费马小定理：

$$ 假设 a 为一个整数，p 为一个素数，且a不是p的倍数。则 a^{p-1}-1=kp，其中 k 为一个正整数。 $$

将上式稍作变换：

$$ \frac{a^{p-1}}{p} - \frac{1}{p} = k $$

由上式可以推得 $a^{p-1} \div p$ 和 $1 \div p$ 的余数相同，即 $a^{p-1}$ 和 $1$ 对于 $p$ 同余。数学上记作：

$$ a^{p-1} \equiv 1 (mod p) $$

同余有一个性质我们后面要用到，即

$$ 假如 a - b = kn，其中k为一个整数。则 a \equiv b (mod n) $$

这个很好想，两数之差为 $n$ 的倍数，则两数除 $n$ 的时候余数肯定一样。

1.3. 欧拉定理

欧拉在 1736 年在费马小定理的基础上推导出了更一般化的欧拉定理：

$$ 假设a为一个整数，n也为一个整数，且a与n互素。则 a^{\varphi(n)} - 1 = kn，其中k为一个正整数。 $$

写成同余形式：

$$ a^{\varphi(n)} \equiv 1 (mod n) $$

可知，当 $n$ 为素数时，$\varphi(n) = n - 1$ ，上式可变为 $a^{n-1} \equiv 1(mod n)$ ，即费马小定理。

2. RSA 算法

2.1. RSA 算法的过程

首先直接来说一下 RSA 算法的过程，该过程可以分为四步，分别是 密钥生成、密钥分发、加密、解密。

现在 Alice 和 Bob 要用 RSA 进行通信。为了让 Bob 能加密他发送的信息，Alice 首先要生成自己的公钥和私钥：

1. 首先随机选取两个不相等的大质数 $p$ 和 $q$ 。然后计算出乘积 $N$ ，$N = p * q$ 。$N$ 的二进制长度一定就是 RSA 公钥的二进制长度。（实际应用中，RSA密钥一般是1024位，重要场合则为2048位）
2. 然后计算 $N$ 的欧拉函数值 $\varphi(N)$ 。$\varphi(N) = \varphi(p) * \varphi(q) = (p - 1)(q - 1)$ 。
3. 随机选取一个整数 $e$ 。满足 $e < \varphi(N)$ 且 $e$ 与 $\varphi(N)$ 互素。此时得到了 RSA 加密的公钥，即 $(N, e)$ 。（现实中 $e$ 常取 65537）
4. 计算出一个数 $d$ 。满足 $ed - 1 = k\varphi(N)$ ，其中 $k$ 为一个正整数。即 $ed \div \varphi(N)$ 的余数为 $1$ 。这个 $d$ 称作 $e$ 关于 $\varphi(N)$ 的模逆元。写成同余的形式就是 $ed \equiv 1 (mod \varphi(N))$ 。可以看到这个式子中有两个变量分别是 $d$ 和 $k$ ，这就相当于求一个二元方程的解，这里可以用 扩展欧几里得算法 快速求出一组整数解。此时得到了 RSA 加密的私钥，即 $(N, d)$ 。

然后 Alice 将公钥直接发给 Bob，则 Bob 发送消息之前先用公钥将要发送的信息加密：

1. Bob 要把发送的消息先转换成数字的形式，最简单的当然是使用 ASCII 编码。然后单次要加密的数字形式的消息 $m$ 必须满足 $m < N$ 。
2. Bob 算出一个数 $c$ ，满足 $m^e - c = kN$ ，其中 $k$ 为一个正整数 。写成同余的形式就是 $m^e \equiv c (mod N)$ 。由同余的定义可知可以确定唯一一个小于 $N$ 的 $c$ ，此时 $c$ 就是加密后的密文。同样由于要求的 $c$ 小于 $N$ ，所以可以将求 $c$ 公式改写为这样：$c = m^e mod N$ 。

然后 Bob 把密文 $c$ 传给 Alice ，Alice 收到 $c$ 后要将其解密：

1. Alice 算出一个数 $m$ ，满足 $c^d - m = kN$ ，其中 $k$ 是一个正整数 。写成同余的形式就是 $c^d \equiv m (modN)$，这个 $m$ 在小于 $N$ 的范围内只能找到一个，则这个 $m$ 就是原文。同样由于要求的 $m$ 小于 $N$ ，所以求 $m$ 的公式可以改写成这样：$m = c^d mod N$ 。

2.2. RSA 有了公钥也无法算出私钥

公钥用于加密，明文在网络中传输。私钥用于解密，只有 Alice 才有。就算攻击者截获到了公钥，也无法因此算出私钥。

公钥是 $(N, e)$ ，私钥是 $(N, d)$ 。根据私钥生成规则 $ed - 1 = k\varphi(N)$ ，攻击者想要破解出私钥必须像生成私钥的时候那样计算出一个 $d$，而想算出 $d$ 必须有 $e$ 和 $\varphi(N)$ 。而想知道 $\varphi(N)$ 必须知道 $N$ 的两个素因数 $p$ 和 $q$ ，也就是攻击者必须对大整数 $N$ 进行因数分解。

所以结论就是如果 $N$ 可以被因数分解，$d$ 就可以被算出，也就意味着私钥被破解。

可是，大整数的因数分解，是一件非常困难的事。目前，除了暴力破解，还没有发现别的有效的办法。维基百科这样写道：

　　"对极大整数做因数分解的难度决定了 RSA 算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。

　　假如有人找到一种快速因数分解的算法，那么 RSA 的可靠性就会急速下降。但找到这样的算法的可能性是非常小的。今天只有短的 RSA 密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击 RSA 算法的方式。

　　只要密钥长度足够长，用 RSA 加密的信息实际上是不能被解破的。"

当然，这是 2008 年的老旧信息了。没有哪一个算法可以永远不被破解。一个名叫 Shor 算法的量子算法（在量子计算机上面运作的算法）被证明在大整数因数分解问题上具有很高的效率，所以等到量子计算机更成熟的时候，可能也就是 RSA 要被替换之日了。

2.3. 为什么公钥和私钥可以用来加密和解密

现在我们就来证明一下为什么将原文 $m$ 通过加密公式 $m^e \equiv c (mod N)$ 加密成 $c$ 后，能通过解密公式 $c^d \equiv m (modN)$ 重新算回 $m$ 。

首先，加密公式 $m^e - c = k_1N$ 稍作变换，得到加密后的密文 $c$ ：

$$ c = m^e - k_1N $$

将上式代入要证明的解密公式：

$$ (m^e - k_1N)^d \equiv m(modN) $$

它等同于求证：

$$ m^{ed} \equiv m(modn) $$

简要证明一下上一步。$(m^e - k_1N)^d$ 分解成多项式后，可知第一项是 $m^{ed}$ ，而后的每一项一定都包含 $N$ 的次幂，可知这些项做 $modN$ 运算的时候不影响总的结果，所以等同于求证上式。

根据私钥生成规则 $ed \equiv 1(mod\varphi(N))$ 可得：

$$ ed = k_2\varphi(N) + 1 $$

将上式代入上上式得：

$$ m^{k_2\varphi(N) + 1} \equiv m(modN) $$

接下来分两种情况证明上式。

m 与 N 互质

首先同余有如下幂运算法则：

$$ 如果 a \equiv b(modm)，则 a^n \equiv b^n(modm) $$

和如下乘法运算法则：

$$ 如果 a \equiv b(modm) ，则 a*n \equiv b*n (modm) $$

因为 $m$ 和 $N$ 互质，所以根据欧拉定理：

$$ m^{\varphi(N)} \equiv 1(modN) $$

将上边的同余表达式进行幂运算和乘法运算，可以得到

$$ (m^{\varphi(N)})^{k_2} * m \equiv m(modN) $$

即 $m^{k_2\varphi(N) + 1} \equiv m(modN)$ 得证。

m 与 N 不互质

首先，$m$ 与 $N$ 不互质，说明 $m$ 与 $N$ 必定有非1公因子。而 $N$ 又等于 $p * q$ ，加上加密时候的限制条件 $m < N$ ，可以知道这个公因子要么是 $p$ 要么是 $q$ 。从而说明 $m$ 要么可以表示为 $kp$ 要么可以表示为 $kq$ 。

以 $m = kp$ 为例，由加密时的限制条件 $m < N$ 以及 $m = p * k$ ，$N = p * q$ 可知 $k < q$ ，而 $q$ 又是一个素数，所以 $k$ 必定与 $q$ 互素。既然 $k$ 和 $p$ 都与 $q$ 互素，可知 $kp$ 不可能和 $q$ 有非1公因子，所以 $m = kp$ 也和 $q$ 互素。套用欧拉定理可以得到

$$ (kp)^{\varphi(q)} \equiv 1(mod q) $$

$\varphi(q) = q - 1$ ，所以

$$ (kp)^{q-1} \equiv 1 (mod q) $$

根据同余的幂运算法则和乘法法则可以得到

$$ [(kp)^{q-1}]^{h(p-1)} * kp \equiv kp(mod q) $$

简化为

$$ (kp)^{h(q-1)(p-1) + 1} \equiv kp(modq) $$

根据私钥计算公式 $ed = 1+ k\varphi(N)$ 可将上式简化

$$ (kp)^{ed} \equiv kp(mod q) $$

由同余的定义可知，对 $q$ 同余的 $(kp)^{ed}$ 和 $kp$ 一定相差 $q$ 的倍数，所以上式可以写成

$$ (kp)^{ed} = tq + kp $$

其中 $t$ 为一个整数。等式两边同时除以 $p$ ，得

$$ k^{ed}p^{ed-1} = \frac{tq}{p} + k $$

可知等式左边一定是一个整数，所以右边也必须是一个整数，由于 $q$ 和 $p$ 互质，则 $t$ 必须满足 $t = t_1p$ 才能是一个整数。所以上上式可以变为

$$ (kp)^{ed} = t_1pq+kp $$

由 $m = kp$ 和 $N = pq$ 可得

$$ m^{ed} = m + t_1N $$

即

$$ m^{ed} \equiv m(mod N) $$

原式得到证明。

2.4. 一个小例子

来个小例子把。

第一步，随机选取两个不相等的质数 $p$ 和 $q$ 。

Alice 选择了 61 和 53 。（由上面的讨论可知，此处的 $p$ 和 $q$ 越大，就越难对他们的乘积 $N$ 因式分解）

第二步，计算乘积 $N$ 。

$N = 61 * 53 = 3233$

$N$ 的二进制长度就是最终的密钥长度。3233 写成二进制就是 110010100001 ，一共 12 位，所以密钥就是 12 位。实际应用中，RSA 密钥一般是 1024 位，在安全性要求高的场合可能是 2048 位。

第三步，计算欧拉函数 $\varphi(N)$ 。

$\varphi(N) = \varphi(p) * \varphi(q) = (p-1) * (q-1) = 3120$

第四步，随机选择一个整数 $e$ ，条件是 $1 < e < \varphi(N)$ ，且 $e$ 与 $\varphi(N)$ 互质。

Alice 在 1 到 3120 中选择了 17 。（实际应用中常选择 65537）

此时得到了公钥 $(N, e)$ ，即 $(3233, 17)$ 。

第五步，计算 $e$ 对于 $\varphi(N)$ 的模逆元 $d$ 。

即满足 $ed - 1 = k\varphi(N))$ 。将数值代入得 $17d - 1 = 3120k$ ，可以使用扩展欧几里得算法对这个二元方程求解，Alice 最终求出了一组整数解 $d = 2753$ ，$k = -15$ 。

此时得到了私钥 $(N, d)$ ，即 $(3233, 2753)$ 。

实际应用中，公钥和私钥的数据都采用ASN.1格式表达。

第六步，加密。

Alice 将算出的公钥交给 Bob 。假设 Bob 要发送的原文 $m$ 是 65，则根据加密公式 $m^e \equiv c (mod N)$ ，代入数值后为 $65^{17} \equiv c(mod 3233)$ ，可求出唯一一个大于 0 小于 3233 的 $c$ 为 2790 。于是 Bob 将 2790 传输给 Alice 。

第七步，解密。

Alice 根据解密公式 $c^d \equiv m (modN)$ ，带入数值得 $2790^{2753} \equiv m(mod 3233)$ ，可求出唯一一个大于 0 小于 3233 的 $m$ 为 65 ，于是解密成功。

ps. 别看 $2790^{2753}$ 好像很大的样子，但我用 windows 自带的计算器算上面的式子根本没用多长时间，完全没有停顿的就得出了结果。不过这也是建立在我们的 $p$ 和 $q$ 很小的前提下，正如上面所说，实际的 RSA 的 $N$ 大概在 1024 个二进制位朝上，这就不是一个小数目了，所以这也引出了一个 RSA 的缺点，就是慢！

2.5. 思考

https://www.zhihu.com/question/25912483

走到这里，我们可以开始思考一个问题了。 在上面 RSA 加密的推导中，公钥是 $(N, e)$ 用于加密，私钥是 $(N, d)$ 用于解密。那么，用 $(N, d)$ 加密而用 $(N, e)$ 解密可不可以呢？

也就是说，用 $(N, d)$ 加密原文 $m$ ，则此时加密公式变为 $m^d \equiv c(modN)$ 。而用 $(N, e)$ 解密密文 $c$ ，则此时解密公式变为 $c^e \equiv m(modN)$ 。这样是否可行呢？答案是肯定的，或者说在数学上是肯定的。想要证明很简单，只需要像证明 RSA 那样证明被加密后的 $c$ 能被再解密成 $m$ 就行，这里就不再证明一遍了，因为如果你去看那个证明过程，你就会发现虽然 $e$ 和 $d$ 互换了，但证明过程以及结果还是一样的。

这说明了一个问题，RSA 算法计算出来的 $e$ 和 $d$ 在数学上其实是对等的，谁用来加密谁用来解密其实都行，不影响结果。但其实这只是在理论上可行，首先 RSA 生成 $e$ 和 $d$ 的方法都不一样，这其实也是有各自的考量的，总而言之 $e$ 更适合做公钥加密，$d$ 更适合做私钥解密。

那说了这么多，$(N, d)$ 用来加密 $(N, e)$ 用来解密还不是没啥用了？其实还是有用，只不过此时不叫加密和解密了，这就是下一篇博客要介绍的 RSA 数字签名！RSA 不仅可以用来加密，还能用来做认证（certificate）。在 RSA 数字签名技术中，$(N, d)$ 还是私钥，但此时它被用来加密（签名）而不是解密，$(N, e)$ 还是公钥，但此时它被用来解密（验证）而不是加密。

数字签名技术在下一篇博客 https://laihaodong.cn/2318.html