AI摘要
RSA dp/dq 泄露攻击
本文整理自 CTF 密码学题目，涵盖 dp 泄露、dp 部分泄露、dp+dq 联合恢复三种典型攻击场景，附完整脚本与推导。
1. 背景：CRT-RSA 与 dp/dq
在标准 CRT-RSA 中，私钥操作通过中国剩余定理加速：
$$ \begin{aligned} dp &\equiv d \pmod{p-1} \\ dq &\equiv d \pmod{q-1} \end{aligned} $$
解密时分别计算 $m_p = c^{dp} \bmod p$ 与 $m_q = c^{dq} \bmod q$，再 CRT 合并得出 $m$。
当 $dp$ 或 $dq$ 泄露时，无需 $d$ 即可恢复明文，或直接分解 $n$。以下是三种实战脚本。
2. 场景一：dp 泄露 → 分解 n（nec dp）
脚本来源
nec dp.py
已知条件
| 参数 | 含义 |
|---|---|
| $n$ | 模数 |
| $e$ | 公钥指数 |
| $dp$ | CRT 参数$d \bmod (p-1)$ |
| $c$ | 密文 |
核心原理
由 $dp \equiv d \pmod{p-1}$，得：
$$ dp \cdot e \equiv 1 \pmod{p-1} $$
即存在整数 $k$ 使得：
$$ dp \cdot e = 1 + k(p-1) $$
整理：
$$ p = \frac{dp \cdot e - 1}{k} + 1 $$
因为 $dp < p-1$，所以 $k < e$。从 $1$ 到 $e-1$ 穷举 $k$，满足 $n \bmod p = 0$ 即得 $p$。
攻击流程
- 枚举 $k \in [1, e)$
- 检查 $(e \cdot dp - 1) \bmod k == 0$
- 计算 $p = (e \cdot dp - 1)//k + 1$
- 若 $n \bmod p == 0$，得到分解
- 计算 $q = n // p$，$\varphi(n) = (p-1)(q-1)$
- 求 $d = e^{-1} \bmod \varphi(n)$，解密 $m = c^d \bmod n$
完整脚本
复杂度分析
枚举 $k \in [1, 65537)$，每次一次取模和除法，毫秒级完成。$e$ 越小攻击越快，这也是为何生产环境常用 $e=65537$ ——攻击仍线性但常数较大。
3. 场景二：dp 部分信息 + 已知 p → 逐位恢复明文（pcbe dp）
脚本来源
pcbe dp.py
已知条件
| 参数 | 含义 |
|---|---|
| $p$ | 已分解出的素因子 |
| $dp$ | 部分泄露的 d mod (p-1) |
| $c$ | 密文 |
| $b$ | 与指数相关的边界参数 |
| $e$ | 公钥指数 |
核心原理
该场景比较特殊：已知 $p$ 但 $dp$ 信息不全，需要利用 Hensel 提升逐位恢复 $m_p = c^{dp} \bmod p$。
算法思路：
- 初始猜测 $m_{p}^{(0)} = c^{dp} \bmod p$
- 利用 $e$ 次幂验证：如果 $m_{p}^{(i)}$ 是正确部分解，那么 $c \equiv (m_{p}^{(i)})^e \pmod{p^{i+1}}$
- 设 $x = c - (m_{p}^{(i)})^e \pmod{p^{i+1}}$
- 修正项 $y = x \cdot m_{p}^{(i-1)} \cdot (e^{-1} \bmod p) \pmod{p^{i+1}}$
- 更新 $m_{p}^{(i+1)} = m_{p}^{(i)} + y$
- 迭代至收敛
完整脚本
适用场景
- $dp$ 被截断（低位缺失若干比特）
- $p$ 已通过侧信道或其它方式泄露
- 需要 Hensel 提升思想恢复模 $p^t$ 下的解
4. 场景三：dp 与 dq 双泄露 → 重构私钥 d（pqc dp dq）
脚本来源
pqc dp dq.py
已知条件
| 参数 | 含义 |
|---|---|
| $p, q$ | 两个素因子 |
| $dp$ | $d \bmod (p-1)$ |
| $dq$ | $d \bmod (q-1)$ |
| $c$ | 密文 |
核心原理
当 $p, q, dp, dq$ 全泄露时，可直接重构 $d$ 而无需分解 $n$。
设 $g = \gcd(p-1, q-1)$，由中国剩余定理构造：
$$ d \equiv \left[ \frac{dp - dq}{g} \cdot \left(\frac{q-1}{g}\right)^{-1} \bmod \frac{p-1}{g} \right] \cdot (q-1) + dq $$
验证：该 $d$ 满足 $d \equiv dp \pmod{p-1}$ 与 $d \equiv dq \pmod{q-1}$。
完整脚本
公式推导
由同余方程组：
$$ \begin{cases} d \equiv dp \pmod{p-1} \\ d \equiv dq \pmod{q-1} \end{cases} $$
设 $g = \gcd(p-1, q-1)$。将 $d$ 表示为 $d = dq + k(q-1)$，代入第一式：
$$ dq + k(q-1) \equiv dp \pmod{p-1} \\ k(q-1) \equiv dp - dq \pmod{p-1} $$
两侧除以 $g$：
$$ k \cdot \frac{q-1}{g} \equiv \frac{dp - dq}{g} \pmod{\frac{p-1}{g}} $$
因此：
$$ k \equiv \frac{dp - dq}{g} \cdot \left(\frac{q-1}{g}\right)^{-1} \pmod{\frac{p-1}{g}} $$
代回 $d = dq + k(q-1)$ 即得最终公式。
备注
- 若 $dp > dq$，差值为正，自然执行整除
- 需确保 $\gcd(p-1, q-1) \mid (dp - dq)$，否则泄露数据不一致
- 该公式在 CTF 中非常常见，建议熟记
5. 攻击总结与对比
| 场景 | 泄露量 | 关键技巧 | 复杂度 |
|---|---|---|---|
| dp only | $dp$ | 穷举$k \in [1,e)$ 恢复 $p$ | $O(e)$，毫秒级 |
| dp + p partial | $dp$（不全） + $p$ | Hensel 提升逐位恢复 | $O(b)$ 次模幂 |
| dp + dq + p + q | $dp, dq, p, q$ | CRT 解同余方程组 | $O(1)$ |
6. 防御建议
- 避免侧信道泄露：在 CRT 解密中计算 $m_p = c^{dp} \bmod p$ 时，若出错返回不同结果会泄露 $p$
- 使用 Blinding：对输入 $c$ 做随机盲化后再解密
- 清除中间变量：$dp, dq$ 使用后立即从内存擦除
- 密钥生成隔离：$d$ 本身不必在每次签名/解密时加载
