RSA 广播攻击与暴力求 e

1. 攻击背景

本题分两步走：先通过暴力搜索恢复公钥指数 $e$，再对已知 $e$ 且同一明文多次加密的场景实施 Håstad 广播攻击。题目给出了 pow(203, e, n) 的已知值，以及同一消息在三个不同模数 $n_1, n_2, n_3$ 下的密文 $c_1, c_2, c_3$。

2. 第一阶段：暴力求 e

2.1 场景

题目提供一个「提示」值：

$$ h = 203^e \bmod n $$

底数 $203$ 和模数 $n$ 已知，指数 $e$ 未知，需先恢复 $e$。

2.2 为什么暴力可行

RSA 实战中 $e$ 通常很小（$65537$、$3$、$17$），但本题 $e$ 可任意取值。若搜索上限控制在 $10^5$ 以内，遍历所有候选 $i$ 计算 $203^i \bmod n$ 与 $h$ 对比，代价完全可接受。

$203$ 与 $n$ 通常互质（否则 $n$ 已被分解），一次模幂 $O(\log i)$ 次乘法，$10^5$ 次迭代在 Python 中仅需数秒。

2.3 暴力搜索算法

输入: n, hint = 203^e mod n
输出: e

for i = 0 to 100000:
    if pow(203, i, n) == hint:
        e = i
        break

复杂度 $O(K \log e_{\max})$，$K$ 为搜索上限。当 $K = 10^5$ 且模数在 $2048$ 位内时，毫秒级即可完成。

2.4 局限性

• 若底数与 $n$ 不互质则 $\gcd(203, n) \ne 1$，$n$ 直接被分解，攻击降维。
• 搜索范围需适当放宽——部分题目将 $e$ 藏在 $50000 \sim 80000$ 之间。
• $e$ 必须为整数（RSA 恒满足），非正整数的指数本方法失效。
• 当 $e > 10^6$ 时纯暴力不可行，需借助离散对数手段或额外信息。

3. 第二阶段：Håstad 广播攻击

3.1 攻击模型

同一明文 $m$ 以相同指数 $e$，分别对 $n_1, n_2, \dots, n_k$ 加密，得密文 $c_1, c_2, \dots, c_k$：

$$ c_i \equiv m^{e} \pmod{n_i}, \quad i = 1, 2, \dots, k $$

若 $k \ge e$ 且各 $n_i$ 两两互质，攻击者无需私钥即可恢复 $m$。这就是 Håstad 1985 年提出的广播攻击（Broadcast Attack）。

核心思想：当 $m^e < \prod_{i=1}^{k} n_i$ 时，中国剩余定理（CRT）将 $k$ 个模方程合并为一个整数域上的等式，直接开 $e$ 次方。

3.2 Håstad 定理

定理 (Håstad, 1985)：设 $n_1, n_2, \dots, n_k$ 为两两互质整数，$m$ 为消息，$c_i \equiv m^{e} \pmod{n_i}$。若 $k \ge e$ 且 $m < \min(n_i)$，则 $m$ 可由 $c_i$ 和 $n_i$ 唯一确定。

经典情形 $e=3$，仅需 $3$ 个互质模数。因为 $m^3 < n_1 n_2 n_3$，整数域上 $m^3$ 即 CRT 合并结果，开三次根得 $m$。

3.3 CRT 公式推导

令 $N = n_1 \cdot n_2 \cdots n_k$。定义：

$$ N_i = \frac{N}{n_i}, \quad d_i \equiv N_i^{-1} \pmod{n_i} $$

CRT 唯一解：

$$ m^{e} \equiv \sum_{i=1}^{k} c_i \cdot d_i \cdot N_i \pmod N \tag{1} $$

在整数域上看：

• 每个 $c_i < n_i$；
• CRT 合并给出 $[0, N)$ 范围内的值 $X$；
• 由于 $m^e < N$（由 $m < \min(n_i)$ 与 $k \ge e$ 保证），整数域上 $m^e = X$；
• 因此 $m = \sqrt[e]{X}$。

关键：CRT 合并出的 $X$ 不是「同余类」而就是真实的 $m^e$，因为它严格小于模数 $N$。

3.4 三模数 $e=3$ 的具体展开

设 $n_1, n_2, n_3$ 已知，密文 $c_1, c_2, c_3$ 满足：

$$ c_1 \equiv m^3 \pmod{n_1},\quad c_2 \equiv m^3 \pmod{n_2},\quad c_3 \equiv m^3 \pmod{n_3} $$

令 $N = n_1 n_2 n_3$，计算：

$$ \begin{aligned} N_1 &= N / n_1 = n_2 n_3,\quad d_1 \equiv N_1^{-1} \pmod{n_1} \\ N_2 &= N / n_2 = n_1 n_3,\quad d_2 \equiv N_2^{-1} \pmod{n_2} \\ N_3 &= N / n_3 = n_1 n_2,\quad d_3 \equiv N_3^{-1} \pmod{n_3} \end{aligned} $$

CRT 合并：

$$ m^3 \equiv c_1 d_1 N_1 + c_2 d_2 N_2 + c_3 d_3 N_3 \pmod N $$

由于 $m^3 < N$，取模运算结果即该和本身。开立方：

$$ m = \sqrt[3]{m^3} $$

3.5 为何不需要 $e$ 的逆元

RSA 解密需私钥 $d \equiv e^{-1} \pmod{\varphi(n)}$。广播攻击完全绕过了 $\varphi(n)$ 的计算，将难题从「分解 $n$」转化为「解低次整数方程」。

3.6 恢复完整私钥

本题广播攻击还原出的是素数 $p$（见第 8 节说明），进而 $q = n / p$，算出 $\varphi(n)$ 后求得 $d$：

$$ d \equiv e^{-1} \pmod{\varphi(n)},\quad m_{\text{flag}} = c^{d} \bmod n $$

4. 统一脚本

5. 脚本逐段解析

5.1 暴力搜索 e

• 遍历 range(100000)，每次计算 pow(203, i, n)；
• pow 内置模快速幂，每次迭代 $O(\log i)$；
• 匹配后立即 break。

5.2 CRT 广播攻击

• $N = n_1 n_2 n_3$，$N_i = N / n_i$；
• gmpy2.invert 调用扩展欧几里得求 $d_i \equiv N_i^{-1} \pmod{n_i}$；
• p_cubed 即 CRT 合并结果，在整数域上等于 $p^3$；
• gmpy2.iroot(p_cubed, 3) 开三次方，返回 (root, is_exact) 元组。

5.3 恢复 flag

• $q = n / p$（整除）；
• $\varphi(n) = (p-1)(q-1)$；
• $d = e^{-1} \bmod \varphi(n)$；
• $m = c^d \bmod n$，转字节串即得 flag。

6. 攻击必要条件

7. 防御措施

8. 进阶讨论

8.1 暴力搜索失败的应对

当 $e > 10^6$ 时纯暴力不可行。可选路线：

• 多组 (底数, 提示值) 可构造离散对数问题；
• $e$ 的结构性质（如 $e$ 是某已知数的幂）；
• 提示值不止一个且底数不同时，可通过比值消元。

8.2 $k < e$ 时的变种：Coppersmith 方法

当密文份数少于 $e$ 时，CRT 合并结果大于 $N$，无法直接开方。此时可借助 Coppersmith（LLL 格基归约）在多项式时间内恢复 $m$，前提是 $m$ 相对 $n_i$ 足够短。这是广播攻击的高阶形式。

8.3 本题为何广播攻击恢复的是 p 而非 flag

本题嵌套设计：广播攻击的目标消息 $m_0$ 是素数 $p$，而非最终 flag。

• 广播攻击还原出 $p$；
• 主密文 $c = \text{flag}^e \bmod n$，其中 $n = p \times q$；
• 恢复 $p$ 等价于分解 $n$，再用私钥解密 $c$ 即得 flag。

CTF 常用此嵌套——广播攻击本身只攻击「同一个数的多次加密」，至于该数是什么（素数、密钥、口令……）取决于出题编排。

8.4 一般的 $e$ 值广播攻击

当 $e=5$ 时需 $5$ 份密文，$e=17$ 时需 $17$ 份。公式 (1) 天然泛化，不限于 $e=3$。只需 $k \ge e$ 即可合并 $m^e$ 后开 $e$ 次方。若 $e$ 较大，密文需求量同比例增长，攻击的实用门槛也随之上升。

9. 总结

两个阶段互补：暴力求 $e$ 属于信息搜集，广播攻击属于密码分析。前者利用 RSA 指数搜索空间有限的信息论弱点；后者利用 CRT 在整数环上的合并能力，将数论难题降维为代数方程求根。

• 暴力求 $e$：搜索空间小时可行，单次模幂 $O(\log i)$；
• 广播攻击：CRT + 整数开 $e$ 次方，无需私钥即可恢复被重复加密的消息；
• 联合利用：先确认 $e$ 以验证攻击条件，再施展 CRT 还原明文。