RSA 算法算是比较常见的加密算法了。一直以来对他的了解不算完全。借着研究 CTF 的机会，仔细梳理一遍。顺便写写相关代码和推理下过程。

2022-06-01 把之前学习算法中扩展欧几里得的部分替换了进去。

RSA 算法简介

RSA 加密算法是一种非对称加密算法。在公开密钥加密和电子商业中 RSA 被广泛使用。RSA 是 1977 年由罗纳德 · 李维斯特（Ron Rivest）、阿迪 · 萨莫尔（Adi Shamir）和伦纳德 · 阿德曼（Leonard Adleman）一起提出的。RSA 就是他们三人姓氏开头字母拼在一起组成的。

我主要参考下面两个视频以及维基百科对 RSA 的基本原理做了简单的推理。基本就是跟着视频对路子整理下思路。毕竟这方面我也没啥底子。

00:08:28

探秘公钥加密算法 RSA

9.1万 271

视频奇乐编程学院

00:13:54

10.6万 353

视频可厉害的土豆

RSA 基本原理

这部分基本复刻上面第一个视频的过程。

根据数论，寻求两个大质数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。^[1]

计算 $3^3 \ \mathrm{mod} \ 7$ 很简单：$3^3=27$ ，$27/7=3\cdots6$。

但当 $3^x \ \mathrm{mod} \ 7$ 去求解 $x$ 时，就只能遍历获取。当数字大到一定程度，对模运算求逆基本是不可行的。

因此不妨设

$m^e \ \mathrm{mod} \ n = c$

即使用 $e$ 为密钥，对 $N$ 取余数，以对 $m$ 加密求出密文 $c$。

于是也可以想到，会有一个 $d$ 作为密钥对他进行解密。即：

$c^d \ \mathrm{mod} \ n = m$

两式可以化为（具体过程为还不太会，以后再补充。）：

$\begin{equation} m^{ed} \ \mathrm{mod} \ n = m \label{1} \end{equation}$

通过这个式子，我们就可以通过 $e$ 和 $d$ 的选取，来对 $m$ 进行加密。

那么，如何选取呢？看到这个形式后，接下来需要引入欧拉定理。

欧拉定理是这样的一条定理：

$\text{已知} \ a \ \text{与} \ n \ \text{互质，则} \ a^{\varphi(n)} \equiv 1 \pmod{n}$

即 $a$ 的 $\varphi(n)$ 次方模 $n$ 的值为 $1$，其中 $\varphi(n)$ 为欧拉函数。

对上面的定理左右取 $k$ 次幂，再同乘以 $a$ ，可以化为：

$\begin{equation} a^{k\varphi(n)+1} \ (\mathrm{mod} \ n)= a \label{2} \end{equation}$

这与 $\ref{1}$ 是不是有点相似？

令他们左侧指数部分相等，则易得：

$\begin{aligned} ed=a^{k\varphi(n)+1} \\[2ex] d = \dfrac{k\varphi(n)+1}{e} \end{aligned}$

因此，我们可以通过对 $k \ n \ e$ 的取值来计算解密所用的密钥 $d$ 。

对于自然数 $n$ ，欧拉函数 $\varphi(n)$ 等于其在$1,2,3\cdots n-1$ 中与 $n$ 互为质数的自然数个数。 ^[2]

然而，求一个数的欧拉函数值，即对 $n$ 做质因数分解，在大数上被视为计算上不可能的。

但是，对于质数 $p$ ，存在 $\varphi(p)=p-1$ 。因此我们选取一个质数时，计算就会变得容易很多。

同时我们也有，若 $p$ 与 $q$ 互质，且均为质数，则存在$\varphi(pq)=\varphi(p) \varphi(q) = (p-1)(q-1)$ 。

这样我们的计算就相对容易了很多。

整理一下我们已经有的式子：

$d = \dfrac{k(p-1)(q-1)+1}{e}$ $\begin{aligned} m^e \ \mathrm{mod} \ n = c \\[1ex] c^d \ \mathrm{mod} \ n = m \\[1ex] n = p \cdot q \end{aligned}$

我们自己试试^[3]。 $M$ 的 ASCII 码为 $77$，我们令 $m = 77$ （message）。

任选两个质数 $p = 107 , q = 109$。计算$n = 107 \cdot 109 = 11663$ 。 $\varphi(n) = (106)(108) = 11448$

任选整数 $e = 2345 $ 符合 $e$ 与 $\varphi(n)=11448$ 互质，$1<e<11448$ 。

将 $e, \varphi(n)$ 带入 $d = \dfrac{k(p-1)(q-1)+1}{e}$，得:

$\begin{aligned} d = \dfrac{11448k+1}{2345} \\[2ex] 2345d - 11448k = 1 \end{aligned}$

求出其的一组解即可，二元一次方程的整数解求解，采用扩展欧几里得算法（gmpy2.gcdext(2345,-11448)）。具体流程下一部分说明。不管怎样我们求出：

$d = 3017 , k = 618$

于是我们就有了加密用的公钥：$(e,n)$ 和解密用的私钥：$(d,n)$。

加密试试：

$\begin{aligned} c &= m^e \ \mathrm{mod} \ n\\[2ex] & = 77^{2345} \mathrm{mod} \ 11663 \\[2ex] &= 2635 \\[2ex] \end{aligned}$

我们得出密文 $2635$ 。

接着我们尝试解密：

$\begin{aligned} m &= c^d \ \mathrm{mod} \ n \\[2ex] &= 2635^{3017} \ \mathrm{mod} \ 11663 \\[2ex] &= 77 \end{aligned}$

得回结果。

你也可以在这个网站尝试一下这个过程。

扩展欧几里得算法

欧几里得算法

即辗转相除法，用于求解两个数 $a$,$b$ 的最大公因数（Greatest Common Divisor）。公式表示为：

$\gcd(a,b) = \gcd(b,a\%b)$

程序的递归实现中，首先要确定好递归边界，即：$b=0$ 时代表已经除尽，程序结束，应输出 $a$，即：

1
2
3

def gcd(a,b):
    if(b==0): return a
    return gcd(b,a%b)

得到最大公约数即可求解最小公倍数（Least Common Multiple），公式为：

$\operatorname{lcm}(a,b) = a*b/\gcd(a,b)$

在 C 语言等静态类型语言中，若数据类型为 int，$a*b$ 很容易超范围，因此一般调整顺序，先使用 $a/\gcd(a,b)$ 再乘以 $b$。（此处均为整除，由于 gcd 为其最大公约数，结果也必然为整数）。

Python 的 Math 库中自带 math.gcd 与 math.lcm 的实现，但是 math.lcm 是 Python 3.9 后才加入的，许多平台目前都未到达该版本。

若求多个值的 $\gcd$ 或 $\operatorname{lcm}$ ，可以先求出前两部分再作为下一个因子与后面的值进行计算。

扩展欧几里得算法

裴蜀定理

我们先引入裴蜀定理，他可以简单表示为：若 $a,b$ 为整数，一定存在 $x,y$ 满足下式（裴蜀等式）:

$ax+by = \gcd(a,b)$

而扩展欧几里得算法，即是在计算 $\gcd$ 的前提下，求解 $x,y$ 的算法。

我们可以简单推导一下他，前文中我们得到了：

$\gcd(a,b) = \gcd(b,a\%b)$

不妨将 $b,a\%b$ 带入裴蜀等式的 $a,b$，即：

$bx_0 + (a\%b)y_0 = \gcd(b,a\%b)$

此处 $x,y$ 与原式不同，所以我们表述为：$x_0,y_0$。

又由欧几里得算法，这个式子与裴蜀等式仍然相等，所以我们有：

$bx_0 + (a\%b)y_0 = ax+by$

又有：$a\%b = a-(a/b)*b$（此处除法为整除向下取整），可得：

$bx_0 + (a-(a/b)*b)y_0 = ax+by$

整理可得：

$ay_0 - b(x_0 - (a/b)y_0) = ax + by$

对比等号左右关系，我们有：

$\left\{ \begin{aligned} & x = y_0 \\ & y = x_0 - (a/b)y_0 \end{aligned} \right.$

确定好边界情况，仍是 $b=0$ 时，这时：

$ax = \gcd(a,0) = a \ \ (\text{y 为任意值})$

此时 $x = 1$ ，为了方便，不妨让 $y = 0$。

因此，我们可以类似于前文写出他的递推函数式：

def exgcd(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = exgcd(b, a % b)
        x, y = y, (x - (a // b) * y)
        return x, y, q

由递推式可得（证明略）：

$\left\{ \begin{aligned} x' = \frac{c}{\gcd}x_0 + \frac{b}{\gcd} * K \\ y' = \frac{c}{\gcd}y_0 - \frac{a}{\gcd} * K \end{aligned} \quad \quad \text{(K 为任意整数)} \right.$

其中， $x$ 的最小整数解为： $
\left(
x\% \dfrac{b}{\gcd} + \dfrac{b}{\gcd}
\right)\%\dfrac{b}{\gcd}
$

特别地，当 $\gcd(a,b)=1$，即 $ax+by=1$ 时，有：

$\left\{ \begin{aligned} x' = x + b * K \\ y' = y - a * K \end{aligned} \quad \quad \text{(K 为任意整数)} \right.$

求解 $ax+by = c$

上一部分中，我们求出了 $ax+by = gcd(a,b)$ 的解。那么如何求解 $ax+by=c$ 呢？观察他们的区别仅在一个 $gcd(a,b)$ 。

那么我们首先假设 $ax+by = gcd(a,b)$ 有一组解 $(x_0,y_0)$。

两侧同乘以 $\dfrac{c}{\gcd}$。就可以有 $a\dfrac{c}{\gcd}x_0 + b\dfrac{c}{\gcd}y_0 = c$。

于是可以得到 $ax+by = c$ 的一组解即：

$(x,y) = \left(\dfrac{c}{\gcd}x_0,\dfrac{c}{\gcd}y_0\right)$

类似于上部分的原理（证明略），可以得出 $ax+by=c$ 的解：

$\left\{ \begin{aligned} x' = \frac{c}{\gcd}x_0 + \frac{b}{\gcd} * K \\ y' = \frac{c}{\gcd}y_0 - \frac{a}{\gcd} * K \end{aligned} \quad \quad \text{(K 为任意整数)} \right.$

其中， $x$ 的最小整数解为

$\left( x\% \dfrac{b}{\gcd} + \dfrac{b}{\gcd} \right)\%\dfrac{b}{\gcd}$

特别地，当 $\gcd(a,b)=1$，即 $ax+by=1$ 时，有：

$\left\{ \begin{aligned} x' = cx_0 + b * K \\ y' = cy_0 - a * K \end{aligned} \quad \quad \text{(K 为任意整数)} \right.$

同余式 $ax \equiv c \pmod m$ 的求解

同余式: 若 $(a-b)\% m = 0$ 则我们称 $a$ 与 $b$ 模 $m$ 同余，记作：$a \equiv b \pmod m$。

因此 $ax \equiv c \pmod m$ 也可以表述为：$(ax-c)\%m = 0$。简单来说就是 $ax-c$ 为 m 的整数倍。

因此存在一个整数 $y$ 满足：$ax-c = my$。移项后得 $ax-my=c$，由于 $y$ 可以为任意整数，所以也可以写为：$ax + my = c$

这样就把同余方程化为了我们前面熟悉的形式。

优化：中国剩余定理

以后有机会再写。

参考文献

[1] 廖滨华著. 网络知识与应用[M]. 2014
[2] （俄）波拉索洛夫著；叶思源译. 代数、数论及分析习题集[M]. 哈尔滨：哈尔滨工业大学出版社, 2017.01.
[3] RSA 算法的加密原理是什么？ https://www.zhihu.com/question/25038691/answer/388573650
[4] https://zh.wikipedia.org/wiki/扩展欧几里得算法

RSA 加密算法： 原理推演以及相关代码实现

RSA 算法简介

RSA 基本原理

扩展欧几里得算法

欧几里得算法

扩展欧几里得算法

裴蜀定理

求解 $ax+by = c$

同余式 $ax \equiv c \pmod m$ 的求解

优化：中国剩余定理

参考文献

RSA 加密算法：原理推演以及相关代码实现