#Python 与 RSA 算法

本周，Computer Security 这门课的作业是用代码实现 RSA 算法，要求加密 + 解密都要实现，语言不限。

这种东西网上一搜一大把，但因为 RSA 太重要了，老师额外要求要 “Defend your code!”(相当于当着他面，一对一做一次 Code Review)。没办法，老老实实的把相关课件重新学了一遍，然后动笔实现。害怕到时候讲不清楚，所以特地写一篇博客理一遍思路。

虽说语言不限，但能方便快捷的操作这么大的数 (老师要求使用至少 1024 bit 的质数！) 的语言还真不多，对比了一下，最终选择了 Python。

##快速模幂运算

快速模幂运算，是与 RSA 相关的算法中最基础也是最核心的一个算法了。毕竟 RSA 加密和解密的本质就是做一个模幂运算；而求我们生成一个大质数的过程中也需要用到这个函数 (费马定理，验证这个数是否为质数)。

这个算法主要是为了减少计算机的计算量，毕竟要硬算 $1.047247e152^{5.80901e149} \pmod{65537}$ 这样的大数的模幂可不容易。

我们都知道，关于取模，有这么一个公式：

$c \bmod m = (a \cdot b) \bmod m = [(a \bmod m) \cdot (b \bmod m)] \bmod m$

再结合 $a^{b + c} = a^{b} \cdot a^{c}$ ，我们可以很容易将我们的模幂运算分解：

$a^e \bmod m = a^{b + c} \bmod m = [(a^{b} \bmod m) \cdot (a^{c} \bmod m)] \bmod m$

但是，如何分解 $e = b + c$ 最高效又成了问题。这里我们使用平方求幂原理。

首先将 $e$ 表示成二进制，即：

$e = \sum*{i = 0}^{n - 1} a_i 2^i, (a*{n - 1} = 1)$

$b^{e}$ 可以表现为：

$b^{e} = b^{(\sum*{i = 0}^{n - 1} a_i 2^i)} = \prod*{i = 0}^{n - 1} (b^{2^{i}})^{a_i}$

因此， $e$ 为：

$e \equiv \prod_{i = 0}^{n - 1} (b^{2^{i}})^{a_i} \pmod m$

具体实现的代码如下 (递归)：

虽说递归的实现最为直观，但我在后面的实际使用过程中遇到了性能问题，不得已重新用 while 重构了一遍：

##生成一个大大的 (伪) 质数

接着，我们需要一个函数用来生成一个固定位数的大数，这个数可能是质数也可能是合数。

我们直接用 Python 的 random 模块来生成一个 w 位的二进制字符串 (仅有 0 和 1 组成的字符串)，然后将字符串转化为数字 (十进制)：

需要注意的是，二进制字符串的首位必须位 '1'，因为如果首位为 0，就不能保证转换后的数字是 w 位了。同时，末尾也必须为 '1'，因为我们的这个函数的目的是生成 (伪) 质数，而所有的偶数都是合数。

##米勒-拉宾素性检验

接下来我们需要一个函数来对生成的 (伪) 质数进行验证，这里我们需要用到米勒-拉宾素性检验 (Miller-Rabin prime test)。

这种算法基于大名鼎鼎的黎曼猜想，其利用了费马小定理的结论：

对于素数 $n$ 和任意整数 $a$ ，有：

$a^{n − 1} \equiv 1 \pmod n$

米勒-拉宾素性检验在费马定理的基础上增加了推论：对于任何大于 $2$ 的素数 $p$ ，不存在 $1 \bmod p$ 的「非平凡平方根」。

我们发现 $1^{2} \bmod p$ 和 $(-1)^{2} \bmod p$ 总是得到 $1$ ，我们称 $−1$ 和 $1$ 是 $1 \bmod p$ 的「平凡平方根」。

让我们假设 $a$ 是 $1 \bmod p$ 的平方根之一 ( $0 < a < p$ )，于是有：

$a^{2} \equiv 1 \pmod p \newline (a - 1)(a + 1) \equiv 0 \pmod p$

因为 $p$ 是质数， $(a - 1) \bmod p$ 和 $(a + 1) \bmod p$ 均不可能为 $0$ 。

那么唯一的可能性只能是：

$(a - 1)(a + 1) = 0 \space or \space (a - 1)(a + 1) = p$

所以：

$a = 1 \space or \space a = p - 1$

我们获得推论：如果 $p$ 是素数，则 $a^{2} \equiv 1 \pmod p$ 的解为 $a = 1$ 或 $a = p−1$ 。

但是对于所有数都使用米勒-拉宾素性检验有点不划算，因为这种算法的开销其实还是挺大的。

我们可以先将 $1$ 至 $100$ 以内的所有素数列出来，用这些素数对需要测试的数取模，其结果如果为 $0$ ，则必并是合数 (素数的倍数必定是合数)；然后再对非零的情况使用米勒-拉宾素性检验：

需要注意的是，米勒-拉宾素性检验是个证明素数的只是一个必要但不充分条件，有极小的概率误判；不过当我们取多个 a 都能通过测试的话，我们可以将误判的概念忽略不计。

因此用一个函数 prime_test 将 prime_miller_rabin 包装一下，生成多个随机数 a，测试其是否都符合条件。

接着用 prime_test 来测试 fake_prime 生成的数是否是质数，如果不是，则重新生成，直到获得一个质数为止。

##实现 RSA 加密

终于可以正式开始实现 RSA 算法了！

我们先来看一下公式：

$C = M^{e} \bmod n$

$M$ 是需要加密的信息。 $(n, e)$ 是我们的公钥。其中 $n$ 就是 $p$ 与 $q$ 的乘积，即：

$n = p \cdot q$

而 $e$ 是一个小于 $r$ 并且与 $r$ 互质的正整数。

$r$ 就是所谓的欧拉函数，公式如下：

$r = \phi(n) = \phi(p) \cdot \phi(q) = (p - 1) \cdot (q - 1)$

$e$ 的大小直接影响了加密的速度，所以一般不会很大，也不会很小，并且里面 (二进制) 的 1 要尽可能的少。这里我们选择 0b1000000000001 (即 4097) 作为默认的 $e$ 。

这个 $r$ 虽然不直接参与 RSA 加密，但其必须 $e$ 互质；我们通过欧几里得算法求 $e$ 与 $r$ 的最大公约数，进而判断它们是否互质；如果不互质，就换一个 $e$ (e -= 1)：

套用公式，实现对 $M$ 的加密：

##实现 RSA 解密

除了加密，我们还需要实现解密。

同样的，先来看一看公式：

$M = C^{d} \bmod n$

这里的 $C$ 是上一步得到的密文。 $(n, d)$ 是我们的私钥。

$n$ 已经解释过了，是 $p$ 与 $q$ 的乘积 ( $n = p \cdot q$ )。

这个 $d$ 是 $e$ 关于 $r$ 的逆模元，即：

$e \cdot d \equiv 1 \pmod r$

所以：

$d = e^{-1} \bmod r$

###拓展欧几里得算法

这里我们使用拓展欧几里得算法：

令 $s_0 = e$ ， $s_1 = r$ ， $x_0 = 1$ ， $x_1 = 1$ ， $y_0 = 0$ ， $y_1 = 1$ ，

当 $s_{i} > 0$ 时：

$x*{i} = \lfloor \dfrac{s*{i-2}}{s*{i-1}} \rfloor \cdot x*{i-1} + x*{i-2} \newline y*{i} = \lfloor \dfrac{s*{i-2}}{s*{i-1}} \rfloor \cdot y*{i-1} + y*{i-2} \newline s*{i} = s*{i-2} \bmod s_{i-1}$

当 $s_{n-1} = 0$ 时：

$(e, r) = s*{n} \newline x = (-1)^{n} \cdot x*{n} \newline y = (-1)^{n+1} \cdot y_{n}$

写成代码就是：

然后套用公式，就可以对 $C$ 进行解密了：

到现在为止，虽然 RSA 算法已经可以用了，但仍然很慢；特别是解密，当质数的位数非常大时就非常容易卡死。因此，我们需要使用中国剩余算法对解密进行优化。

##中国剩余算法

中国剩余算法来自于《孙子算经》的第 26 题：

今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三。术曰：三三数之剩二，置一百四十；五五数之剩三，置六十三，七七数之剩二，置三十，并之。得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十；五> 五数之剩一，则置二十一；七七数之剩一，则置十五；一百六以上以一百五减之即得。

其核心思想就是辗转相除法。

对于给定的数 $k$ ，令 $n*{i} (1 \leq i \leq k)$ 与其互质；令 $a*{i} (1 \leq i \leq k)$ 满足 $0 \leq a*{i} \leq n*{i}$ 。此时，有且只有一个数 $x$ 同时满足：