Coppersmith

总结思路（逐步推理）和为什么 getFullP 里用多项式 P - N

为什么把多项式构造成 p(x) - n

---

一、从已知条件出发的代数关系（推导低位 p 的来源）

已知：RSA 参数 $n=pq$、公钥指数 $e=3$、私钥 $d$ 满足

$3d \equiv 1 \pmod{\varphi(n)}.$

所以存在整数 $k$ 使得

$3d = 1 + k\varphi(n).$

并且 $\varphi(n)=(p-1)(q-1)=n-p-q+1$。

两边乘以 $p$：

$3pd = p + k\;p\varphi(n).$

把 $\varphi(n)$ 展开并化简（注意 $pq=n$）：

$p\varphi(n)=p(n-p-q+1)=p n - p^2 - p q + p = p n - p^2 - n + p.$

因此

$3pd = p + k\big(p n - p^2 - n + p\big).$

现在你知道 $d$ 的低 512 位（代码里的 low_d = d & ((1<<512)-1)），于是把上式对 $2^{512}$ 取模：

$3p\cdot (\text{low\_d}) \equiv p + k\big(p n - p^2 - n + p\big)\pmod{2^{512}}.$

这就是 phase4 里用 solve_mod(..., 2^512) 去解的同余方程——解出的就是 $p$ 的低 512 位候选（maybe_p）。

（代码里循环 $k=1$ 到 $3$ 是因为 $3d=1+k\varphi(n)$ 中 $k$ 通常很小，试几个小的 $k$ 就可以覆盖实际情形。）

---

二、从低位 $p$ 恢复完整的 $P$：为什么把多项式写成 $p(x)-n$

假设通过上一步我们得到了 $p$ 的低 512 位（记为 low_p）。把完整的素因子写成

$P = \text{low\_p} + x\cdot 2^{512},$

其中 $x$ 是未知的高位整数量（待求）。令多项式（关于未知整数 $x$）

$p(x) := x\cdot 2^{512} + \text{low\_p}.$

关键事实：真正的 $x_0$（使得 $p(x_0)=P$）满足

$p(x_0) - n = P - n = -P(q-1).$

因此 $p(x_0)-n$ 被 $P$ 整除，换句话说

$p(x_0)-n \equiv 0 \pmod{P}.$

也就是说， $x_0$ 是多项式 $f(x)=p(x)-n$ 在模 $P$ 下的根（根是模 $P$ 的）。

Coppersmith 小根法（及其在 Sage/NTL 中的实现）可以 在已知合数 $n$ 的条件下 找到使得 $f(x)\equiv 0\pmod{p}$ 的“小”整数根 $x$（这里 $p$ 是 $n$ 的一个大素因子），前提是 $x$ 的绝对大小小于某个界（我们在代码中用 X=2^128 指定）。在 Sage 中通常把多项式放在 Zmod(n) 上，调用 .small_roots()，算法会寻找可以使得 $f(x)$ 在 $n$ 的某个素因子上为 0 的小根 —— 恰好是我们需要的 $x_0$。

因此把多项式构造成

$f(x) = p(x) - n$

的理由是：

1. 对真实的 $x_0$，$f(x_0)=P-n$ 被 $P$ 整除：这给出了“模 $P$ 的零点”这一性质，正是 Coppersmith 能利用的结构。
2. 我们知道 $n$ 和 low_p，所以 $f(x)$ 的系数是已知的整数（可直接构造）。
3. 在实现上把多项式放在 PolynomialRing(Zmod(n)) 上并 .monic().small_roots(X, beta)，可以在 n 上构造格并搜索在某个因子（即 $P$）模下的小根。

（补充：理论上用 $g(x)=p(x)$ 也是在模 $P$ 下为 0 的，但常见的做法是用 $p(x)-n$ 来把“与 $n$ 的整除关系”显式编码进多项式，这样在构造 lattice 时更自然，并且与已有实现习惯一致。）

---

三、参数选择与验证

• p = x*2^512 + low_p：这是把已知低 512 位固定下来，未知高位写作 $x$。
• X = 2^128：这是对 $x$ 的上界估计。为什么 128？因为如果 $P$ 的总体位长是 $512+128=640$（例如），那么高位的范围就是 $<2^{128}$。你需要把 X 设为可以覆盖真实 $x$ 的值但又不能太大，否则 Coppersmith 的小根条件不会成立。
• beta = 0.4：这是小根算法的一个参数（表示目标模因子 $P$ 相对于 $n$ 的规模比），需要根据 $n$ 的长度与因子大小做合理设定。实务中会调整 beta,X 以保证算法能工作。
• .monic()：把多项式首项标准化为 1，便于用格方法做 LLL 等数值运算。
• 找到候选根 r 之后，getFullP 返回 p(r)，再验证 P * (n//P) == n，这一步一定要做以排除错误根。

---

四、整体流程回顾

1. 从 3d ≡ 1 (mod φ(n))、已知 low_d 通过模 $2^{512}$ 的方程求出 $p$ 的低 512 位候选 maybe_p（phase4 的前半部分）。

2. 对每个 low_p 候选，调用 getFullP(low_p, n)：

   • 构造 $p(x)=x\cdot2^{512}+{\rm low\_p}$；
   • 构造 $f(x)=p(x)-n$（放在 $\mathbb Z_n[x]$）并用 Coppersmith（.small_roots）找小根 $x$；
   • 若找到根，计算 $P=p(x)$，再 P*Q==n 验证通过则成功恢复 $P,Q$。

3. 恢复 $d=\text{inv\_mod}(3,\ (P-1)(Q-1))$，然后用 $m = c^d \bmod n$ 解密得到消息。

---

五、补充说明（直观理解）

• 把多项式写成 p(x)-n 的直观原因：我们利用的是“$P$ 与 $n$ 的整除关系”。真实的 $x_0$ 使得 $p(x_0)$ 恰好等于 $P$，而 $P$ 是 $n$ 的因子，所以 $p(x_0)-n$ 在模 $P$ 下为 0——这就是 Coppersmith 能够抓住的模式。把已知的 $n$ 显式放进多项式，可以把“根模素因子”这一性质编码到求解问题里，从而用小根算法恢复未知高位。

---

关于整除的详解

1. 已知关系

我们已经知道：

• $n = P \cdot Q$，其中 $P,Q$ 是素数。

• $p(x)$ 的定义是：

  $p(x) = x\cdot 2^{512} + \text{low\_p}$

• 真实的 $x_0$ 使得 $p(x_0)=P$。

---

2. 把 $p(x_0)-n$ 展开

代入 $p(x_0)=P$：

$p(x_0)-n = P - n$

再把 $n = P Q$ 代入：

$p(x_0)-n = P - P Q = P(1 - Q) = -P(Q-1)$

---

3. 得出整除结论

右边是 $-P(Q-1)$，显然含有因子 $P$，所以：

$p(x_0)-n \equiv 0 \pmod{P}$

换句话说，对模 $P$ 来说，$x_0$ 是多项式 $p(x)-n$ 的一个根。

---

4. 为什么重要

我们并不知道 $P$，但是我们知道 $n$。把多项式放在模 $n$ 的多项式环里，去找一个小的整数根 $x$，Coppersmith 方法就能找到这个 $x_0$，因为它必须满足：

• 在模 $P$ 下 $p(x_0)-n=0$，而且
• $x_0$ 是一个很小的整数

一旦找到了 $x_0$，就能恢复 $P = p(x_0)$。