AI摘要
基本场景
CTF 中最基础的 RSA 解密题型：已知素数 $p$、$q$、公钥指数 $e$ 和密文 $c$，求明文 $m$。这类题目在已知质因数的情况下几乎没有难度，但对理解 RSA 核心运算——模逆元求解——有奠基意义。
RSA 解密流程
Step 1：计算模数
$$ n = p \times q $$
Step 2：计算欧拉函数
$$ \varphi(n) = (p-1)(q-1) $$
由于 $p$ 和 $q$ 均为素数，$\varphi(pq) = (p-1)(q-1)$ 是欧拉函数的性质。
Step 3：计算私钥指数
$$ d \equiv e^{-1} \pmod{\varphi(n)} $$
即 $d$ 是 $e$ 在模 $\varphi(n)$ 下的乘法逆元，满足 $e \cdot d \equiv 1 \pmod{\varphi(n)}$。
Step 4：解密密文
$$ m \equiv c^d \pmod{n} $$
最后将整数 $m$ 转换为字节串即可得到明文。
核心难点：求模逆元
上述四步中，前三步都是简单算术，唯有第三步求模逆元需要算法支撑。在 Python 中可以用 gmpy2.invert(e, phi) 或 pow(e, -1, phi)（Python 3.8+）一行解决，但理解其背后的数学原理对于深入掌握 RSA 乃至其他数论密码体系至关重要。
问题形式化
给定整数 $a$ 和模数 $m$（$\gcd(a, m) = 1$），求 $x$ 使得：
$$ a \cdot x \equiv 1 \pmod{m} $$
等价的丢番图方程形式：
$$ a \cdot x + m \cdot y = 1 $$
其中 $x$ 即为所求的模逆元，$y$ 是一个辅助整数（符号无关）。
贝祖定理
贝祖定理（Bézout's identity）指出：对于任意整数 $a, b$，存在整数 $x, y$ 使得：
$$ \gcd(a, b) = a \cdot x + b \cdot y $$
当 $\gcd(a, m) = 1$ 时（RSA 中 $e$ 与 $\varphi(n)$ 必然互质），方程变为 $a \cdot x + m \cdot y = 1$。对两边取模 $m$，得 $a \cdot x \equiv 1 \pmod{m}$，故 $x$ 正是 $a$ 在模 $m$ 下的逆元。
因此，求模逆元等价于用扩展欧几里得算法找出贝祖系数。
扩展欧几里得算法的迭代原理
标准欧几里得算法通过反复取余求最大公约数：
$$ \begin{aligned} a &= b \cdot q_1 + r_1 \\ b &= r_1 \cdot q_2 + r_2 \\ r_1 &= r_2 \cdot q_3 + r_3 \\ &\vdots \\ r_{k-2} &= r_{k-1} \cdot q_k + r_k \quad (r_k = \gcd(a, b)) \end{aligned} $$
扩展欧几里得算法在此基础上反向代入，将每一步的余数 $r_i$ 用 $a$ 和 $b$ 的线性组合表示。
设第 $i$ 步有 $r_i = a \cdot x_i + b \cdot y_i$，初始条件：
$$ \begin{aligned} r_0 = a &\Rightarrow (x_0, y_0) = (1, 0) \\ r_1 = b &\Rightarrow (x_1, y_1) = (0, 1) \end{aligned} $$
由带余除法 $r_{i-1} = r_i \cdot q_{i+1} + r_{i+1}$ 知 $r_{i+1} = r_{i-1} - q_{i+1} \cdot r_i$，代入线性组合：
$$ \begin{aligned} r_{i+1} &= (a \cdot x_{i-1} + b \cdot y_{i-1}) - q_{i+1} \cdot (a \cdot x_i + b \cdot y_i) \\ &= a \cdot (x_{i-1} - q_{i+1} \cdot x_i) + b \cdot (y_{i-1} - q_{i+1} \cdot y_i) \end{aligned} $$
于是得到递推关系：
$$ \begin{cases} x_{i+1} = x_{i-1} - q_{i+1} \cdot x_i \\ y_{i+1} = y_{i-1} - q_{i+1} \cdot y_i \end{cases} $$
当 $r_{k+1} = 0$ 时停止，此时 $r_k = \gcd(a, b) = a \cdot x_k + b \cdot y_k$。若 $\gcd(a, b) = 1$，则 $x_k$ 即 $a$ 在模 $b$ 下的逆元（可能需要调整到正数范围）。
迭代过程示例
以脚本 $2$ 中的参数为例：$a = \varphi(n) = (p-1)(q-1)，b = e = 17$。实际计算中 $a$ 和 $b$ 角色可以互换——我们求的是 $e$ 在模 $\varphi(n)$ 下的逆元，即解 $e \cdot d + \varphi(n) \cdot k = 1$，此时 $d$ 对应 $y$ 系数（取决于传参顺序）。
代码实现
综合四种脚本场景，给出以下统一解密实现。首选现代简洁写法，同时保留手动扩展欧几里得的实现作为理解参考。
关于 // 与 / 的说明
脚本 $2$ 中使用 /（Python 2 的整除），这在 Python 3 中会返回浮点数导致错误。统一实现中将 q = a / b 修正为 q = a // b，同时将 x = x1 - q*x2 的内联写法也用明确的元组交换替代，可读性更好。
四种脚本变体分析
实际解题中，根据题目给出的参数组合，会演化出以下四种入口形式：
| 变体 | 给定参数 | 特点 |
|---|---|---|
| pqec | $p, q, e, c$ | 最常见问法，需完整走$n \to \varphi(n) \to d \to m$ 流程 |
| pqe | $p, q, e$ | 仅需计算私钥$d$，不涉及解密，重点在模逆元求解本身 |
| ndec | $n, d, e, c$ | 直接给了$d$，只需 pow(c, d, n) 即可，无计算量 |
| longpqec | 大$p, q, e$ | 与 pqec 同流程，但参数位数极大，考验大数运算能力 |
无论哪种形式，核心算子只有两个：模逆元和模幂运算。其中模逆元的求解是打通 RSA 解密链条的关键一环。
变体 ndec 的特殊性
ndec.py 直接给出 $n, d, e, c$，甚至不需要计算 $\varphi(n)$。这里的 $d$ 可能是从其他渠道获得的，或者是题目设计者直接提供的。只需一行 pow(c, d, n) 解密。这种题型考察的是对 RSA 解密公式本身的熟悉程度，属于最入门的变体。
变体 longpqec 的注意事项
当 $p, q, e$ 非常大时（数百位甚至上千位十进制数字），$d$ 也会非常长。需要注意：
- Python 原生大整数可以处理任意精度，但速度可能较慢；
gmpy2底层使用 GMP 库，对大数运算有显著加速；- 手动实现的扩展欧几里得在大数场景下性能远不如
gmpy2.invert。
总结
RSA 基础解密的核心数学障碍只有一个：求模逆元。扩展欧几里得算法通过贝祖定理将求逆元问题转化为线性组合的系数求解，其正确性由带余除法的递推性质保证。理解了这一算法，也就掌握了 RSA 解密链条中最关键的计算环节。
在实际解题中，优先使用 gmpy2.invert(e, phi_n) 或 pow(e, -1, phi_n)，它们经过了高度优化。手动实现的扩展欧几里得版本更适合作为学习和验证用途，或是在无第三方库的受限环境中使用。
参考资料
- Rivest, R. L., Shamir, A., & Adleman, L. (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2), 120–126.
- Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley. §4.5.2.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. §31.2.
- GMP Library Documentation — Integer Functions
- Python 3 Documentation —
pow()with three arguments - gmpy2 Documentation
