AI摘要
Franklin-Reiter 相关消息攻击
Franklin-Reiter Related Message Attack 是 RSA 密码体制下针对线性相关明文的经典攻击。当两条明文之间存在已知的多项式关系时，攻击者可绕过模数分解，直接解出明文。
1. 攻击场景
Alice 拥有 RSA 公钥 $(n, e)$，她发送了两条密文给 Bob：
$$ c_1 \equiv m_1^{\,e} \pmod n,\qquad c_2 \equiv m_2^{\,e} \pmod n $$
并且 Eve（攻击者）已知两条明文之间存在线性关系：
$$ m_2 \equiv a \cdot m_1 + b \pmod n $$
其中 $a, b \in \mathbb{Z}_n$ 是已知系数，$a \neq 0$。
Eve 的目标：在仅有 $c_1, c_2, n, e, a, b$ 的情况下恢复 $m_1$（进而得到 $m_2$），无需分解 $n$，无需私钥 $d$。
典型 CTF 场景
| 已知量 | 含义 |
|---|---|
| $n$ | RSA 模数 |
| $e$ | 公钥指数 |
| $c_1$ | $m_1^e \bmod n$ |
| $c_2$ | $(a \cdot m_1 + b)^e \bmod n$ |
| $a, b$ | 明文的线性变换系数 |
题目常暗示两条消息有关联，比如"Alice 连续发了两份报告，第二份只是在第一份的基础上加了固定前缀/后缀"。
2. 数学原理
2.1 构造多项式
在环 $\mathbb{Z}_n[x]$ 上定义两个单变量多项式：
$$ \begin{aligned} g_1(x) &= (a \cdot x + b)^e - c_1 \pmod n \\[4pt] g_2(x) &= x^e - c_2 \pmod n \end{aligned} $$
形式更为对称的等价定义（与脚本对应）：
$$ \begin{aligned} g_1(x) &= (a \cdot x + b)^e - c_1 \pmod n \\[4pt] g_2(x) &= (c \cdot x + d)^e - c_2 \pmod n \end{aligned} $$
其中 $(a,b)$ 是第一段明文的变换，$(c,d)$ 是第二段的变换。当第二段是原始明文（不做变换）时，可取 $c=1, d=0$。
2.2 公共根
关键观察：$m_1$ 同时是 $g_1(x)$ 和 $g_2(x)$ 的根。
代入 $x = m_1$：
$$ \begin{aligned} g_1(m_1) &= (a \cdot m_1 + b)^e - c_1 \equiv m_2^{\,e} - c_1 \equiv 0 \pmod n \\[4pt] g_2(m_1) &= m_1^{\,e} - c_2 \equiv 0 \pmod n \end{aligned} $$
因此，$(x - m_1)$ 是 $g_1(x)$ 和 $g_2(x)$ 在 $\mathbb{Z}_n[x]$ 中的公共因式。
2.3 GCD 提取公共根
若 $g_1$ 和 $g_2$ 均无重根，且 $m_1$ 是唯一公共根，则 $\gcd\big(g_1(x),\, g_2(x)\big) = x - m_1$。
更一般地：
$$ \gcd(g_1, g_2) = x - m_1 \quad \text{或形如} \quad (x - m_1) \cdot h(x) $$
提取一次项系数的相反数，即得明文：
$$ m_1 = -\big[\gcd(g_1, g_2)(0)\big] $$
2.4 为什么 GCD 可计算
两个多项式在交换环 $\mathbb{Z}_n[x]$ 上的最大公因式不一定唯一，但当 $n$ 是半素数且 $m_1$ 是两条消息的公共根时，Euclidean 算法仍能返回 $x - m_1$ 或 $\alpha(x - m_1)$（$\alpha$ 为可逆元）。monic() 归一化后即可去除系数歧义。
3. 攻击流程
输入: n, e, c1, c2, a, b (或 a, b, c, d)
输出: 明文 m1
Step 1: 在 Zmod(n)[x] 上构造多项式 g1, g2
g1(x) = (a·x + b)^e - c1
g2(x) = (c·x + d)^e - c2
Step 2: 计算 GCD: h(x) = gcd(g1(x), g2(x)).monic()
Step 3: 提取常数项: m1 = -h(0) (即 h[0] 的相反数)
Step 4: 输出 m1 的字节表示4. SageMath 脚本
4.1 基础模板
4.2 nec1c2.py — 需填入实际 $a,b,c,d$ 的占位脚本
4.3 使用 Sage 内置 gcd 的简化版
Sage 的 PolynomialRing 自带 gcd 方法，可直接调用：
5. 条件与限制
| 条件 | 说明 |
|---|---|
| 已知线性关系 | $m_2 = a \cdot m_1 + b \pmod n$，$a, b$ 必须明确已知 |
| $a \neq 0$ | 若$a = 0$ 则 $m_2$ 为常数，$g_1$ 退化为常数多项式，GCD 无意义 |
| $e$ 较小 | $e$ 越大多项式次数越高，GCD 计算开销急剧增大。实战中 $e=3, 5, 17$ 最常见 |
| $n$ 的无平方性 | 若$\gcd(g_1', g_2') \neq 1$（有重根），GCD 可能返回高次多项式，攻击退化 |
| Sage 环境 | 必须使用 SageMath，Python 原生库无法高效计算$\mathbb{Z}_n[x]$ 上的多项式 GCD |
6. 为什么必须使用 Sage
Python 原生生态（sympy、numpy 等）在以下环节面临困难：
6.1 多项式运算在模合数环上
$\mathbb{Z}_n[x]$ 是一个有限交换环而非域（因为 $n$ 是合数）。这意味着：
- 多项式除法中，首项系数可能不可逆（与 $n$ 不互质），导致 Euclidean 算法中途终止
- 商和余数不唯一，普通多项式库按域假设实现，会得出错误结果
6.2 大系数与模约化
密文 $c$ 通常为 512~2048 位大整数，多项式展开后系数极大。Sage 在每一步自动做模 $n$ 约化，避免系数爆炸。
6.3 Euclidean 算法的正确性
Sage 的 PolynomialRing(Zmod(n)) 在 Euclidean 步骤中遇到不可逆首项时，会尝试伪除（pseudo-division）或其他策略继续计算，最终返回在当前环中可接受的因式。这是手工实现难以正确复现的。
6.4 Sage vs 其他工具
| 工具 | 支持 Zmod(n)[x] GCD | 备注 |
|---|---|---|
| SageMath | 原生支持 | 推荐方案 |
| Magma | 支持 | 商业软件，成本高 |
| NTL (via Sage) | 底层引擎 | Sage 内部就是用 NTL/FLINT |
| SymPy | 不支持模合数环 GCD | 只能做$\mathbb{Q}[x]$ 或 $\mathbb{F}_p[x]$ |
| Python 原生 | 不可行 | 需从头实现环多项式 GCD，工程量大 |
7. 推广：Coppersmith 与 Short-Pad Attack
Franklin-Reiter 攻击可视为更广泛的 Coppersmith 方法的特殊情形：
- Franklin-Reiter（1996）：处理线性相关消息，已知确切变换系数
- Coppersmith's Short-Pad Attack：当 $m_2 = 2^k m_1 + r$ 且 $r$ 未知时，通过结式消除未知量，再结合 Coppersmith 小根定理求解
此外，该攻击自然推广到任意已知多项式关系：
$$ m_2 = f(m_1) \pmod n $$
其中 $f(\cdot)$ 为已知多项式（不限于一次）。对应的多项式为：
$$ g_1(x) = f(x)^e - c_1,\qquad g_2(x) = x^e - c_2 $$
公共根依然是 $m_1$，GCD 思路不变。但 $f$ 次数越高，$g_1$ 次数为 $e \cdot \deg(f)$，计算开销增长较快。
8. 防御措施
| 策略 | 原理 |
|---|---|
| 使用 OAEP 填充 | 加密前加入随机填充，使得同一消息的两次密文完全无关 |
| 避免重复加密相似消息 | 若必须多次发送，确保每次加入独立的随机盐 |
| 增大公钥指数 $e$ | 增加多项式次数，使 GCD 计算在时间/内存上不可行（不推荐作为唯一防御） |
| 不暴露明文关系 | 攻击依赖$a, b$ 已知；若变换系数是随机的且不公开，攻击失效 |
| 密钥隔离 | 相关消息用不同模数加密，从根本上消除公共多项式根 |
核心教训：RSA 的语义安全性依赖于随机化填充。裸 RSA（Textbook RSA）在已知明文关系下是多项式时间可破的。
9. 总结
Franklin-Reiter 攻击从数学构造到代码实现都极为简洁：
- 将密文方程转化为 $\mathbb{Z}_n[x]$ 上的多项式
- 利用公共根 $m_1$ 的存在性，计算 $\gcd$
- 从 $\gcd$ 结果中提取常数项，还原明文
它深刻揭示了Textbook RSA 在明文相关时的不安全性。在学习过程中，该攻击也是理解"多项式环 GCD 在密码分析中如何应用"的绝佳切入点。
