我咋到现在了才会这玩意
Coppersmith：求解 \(f(x) \equiv 0 \pmod p\)，其中 \(p | N\) 是 N 的某个因子。
我们可以构造若干新的多项式，使得它的根与原多项式是相同的。例如，可以构造 \(f(x)^2, x f(x)\) 等，他们具有原多项式的根。
然后，我们通过这些多项式的线性组合，可以尝试得到一个系数较小的多项式 \(g(x)\)。这一步可以很容易地通过 LLL 实现。
那么，如果这个系数足够小，并且预期的解也足够小，小到使得 \(|g(x_0)| < p\)，那么显然 \(g(x) = 0\) 的解就与 \(g(x) \equiv 0 \pmod p\) 相同了。这样，我们只需要解 \(g(x) = 0\) 就可以得到 \(g(x) \equiv 0 \pmod p\) 的解了，而这意味着我们可以在不知道 \(p\) 的情况下求解方程。
Coppersmith 算法中存在两个参数 \(\beta, \epsilon\)，前者表示 \(p \ge N^\beta\)，后者越小运行速度越慢，但越可能出解。
根据 Coppersmith 的理论，我们需要零点 \(x_0 \le N^{\frac{\beta^2}{\delta} - \epsilon}\)，其中 \(\delta\) 是多项式的次数。可以通过下面的代码计算合适的 \(\epsilon\)：
from math import log
N = ...
beta = ... # p >= N^beta
X = ... # 零点的上界
delta = 1
print(beta ** 2 / delta - log(X) / log(N))
例子：如果知道 RSA 中 \(p\) 的高位，我们可以将已知作为 \(p'\)，未知部分设为 \(x_0\)，则 \(p = p' + x_0\)，令 \(f(x) = p' + x\)，我们知道 \(f(x_0) \equiv 0 \pmod p\)，于是就可以用上述算法求解了。
简单估计一下，\(p \approx N^{0.5}\)，所以 \(\beta = 0.5\)，则 \(X \le N^{\beta^2-\epsilon} \approx N^{0.25}\)，所以需要未知位数小于 \(1/4\)，或者说至少知道 \(p\) 的位数的一半以上。
from sage.all import *
from Crypto.Util.number import long_to_bytesn = ...
msb = ...
c = ...
e = 65537
shift = 245p_high = msb << shift
x, = PolynomialRing(Zmod(n), 'x').gens()
f = p_high + xbeta = 0.499
for epsilon in [0.009, 0.008, 0.007, 0.006, 0.005, 0.004, 0.003, 0.002, 0.001]:print(f"Trying beta={beta}, epsilon={epsilon}...")try:roots = f.small_roots(X=2**shift, beta=beta, epsilon=epsilon)except Exception as e:print(f"Error with epsilon={epsilon}: {e}")continue if roots:print(roots)x0 = roots[0]p = p_high + int(x0)if n % p == 0:print(f"Found p: {p}")q = n // pphi = (p - 1) * (q - 1)d = inverse_mod(e, phi)m = pow(c, d, n)print(f"Flag: {long_to_bytes(m)}")else:print("Root found but not a factor?")else:print("No roots found.")
还有很多其它的用途，比如 \(e\) 很小（\(e=3\)）而 \(m\) 很小（未知部分很小），那么我们就是要解 \(f(x) = (m+x)^e - c \equiv 0 \pmod n\)，同样可以 Coppersmith 做。