截断 LCG 状态恢复:Coppersmith 求 p 高位缺失 + 格 CVP 求低 256 位
crypto/prng · verified
一句话结论
当 LCG 只输出状态的高位(output_i = s_i >> 256)且模数 p 的高 502 位已知、p | N 时,可以先用 Coppersmith 小根求出 p 的低 502 位,再把 s_i = output_i * 2^256 + e_i 代入递推,得到 e_{i+1} = a*e_i + const_i mod p;所有 e_i < 2^256,构造格用 CVP 求最近向量即可恢复全部低位,拼回 s_0 即 seed。
原理
- 题目给出
p_high = p >> 502,即p = p_high * 2^502 + x,0 <= x < 2^502。由于p | N,x是多项式f(x) = p_high * 2^502 + x模N的小根;2^502接近N^(1/4)边界,可用 Coppersmith(zncoppersmith)求小根。 - LCG 递推:
s_{i+1} = a * (s_i - c) mod p,输出output_i = s_i >> 256。 - 令
s_i = output_i * 2^256 + e_i,0 <= e_i < 2^256。代入递推并整理可得e_{i+1} = a * e_i + const_i mod p,其中const_i = a*(output_i*2^256 - c) - output_{i+1}*2^256。 - 继续展开:
e_i = A_i * e_0 + D_i mod p,A_i = a^i,D_i由常数累积得到。所有e_i都是 256 位小量,而p是 1024 位左右,这是典型 Hidden Number Problem。 - 构造
(dim+1) x (dim+1)格:左上dim x dim为diag(p, ..., p),最后一行前dim列为A_i,最后一列scale;对目标(-D_0, ..., -D_{dim-1}, 0)做 CVP 最近向量,得到e_i的候选(符号可能整体取反),检查是否都落在[0, 2^256)。 - 恢复
e_0后seed = (output_0 << 256) + e_0,再按 LCG 递推验证所有输出,最后把 seed 转字节即 flag/密钥。
触发条件
- LCG 参数
a、c、p已知或部分已知;模数p的高位泄露且p | N(或可通过其他方式恢复 p)。 - 输出为状态的高位截断,且截断位数
k使低位e_i < 2^k相对p足够小。 - 有足够多的连续输出(案例 6 个)构造格;维数越高越稳定。
- 有 Coppersmith 实现(PARI
zncoppersmith)与格工具(fpylll/sage)。
利用步骤
- 从附件读取
N、p_high、a、c、outputs。 - 设
p = p_high * 2^502 + x,用zncoppersmith(x + p0, N, X, sqrtint(N))求小根,得到p;验证N % p == 0。 - 计算每步常数
const_i = a*(output_i*2^256 - c) - output_{i+1}*2^256。 - 迭代
A_i = A_{i-1}*a mod p、D_i = a*D_{i-1} + const_{i-1} mod p,得到e_i = A_i*e_0 + D_i。 - 构造格并做 LLL + CVP,目标为
(-D_i);从最近向量差得到e_i候选,检查范围与符号。 - 拼回
seed,按 LCG 验证所有output_i,转字节输出 flag。
PoC
from fpylll import CVP, IntegerMatrix, LLL
from Crypto.Util.number import long_to_bytes
# N, p_high, a, c, outputs 来自题目
p0 = p_high << 502
# 1) Coppersmith(需在 gp 中运行):
# roots = zncoppersmith(x + p0, N, 2^502, sqrtint(N))
# p = p0 + roots[1]
p = ... # 由 zncoppersmith 得到
assert N % p == 0
k, base = 256, 1 << 256
dim = len(outputs)
consts = [a * (outputs[i] * base - c) - outputs[i + 1] * base
for i in range(dim - 1)]
coeffs, offsets = [1], [0]
for const in consts:
coeffs.append((coeffs[-1] * a) % p)
offsets.append((a * offsets[-1] + const) % p)
scale = 1 << 250
mat = IntegerMatrix(dim + 1, dim + 1)
for i in range(dim):
mat[i, i] = p
for j, value in enumerate(coeffs):
mat[dim, j] = value
mat[dim, dim] = scale
LLL.reduction(mat)
target = tuple([(-d) % p for d in offsets] + [0])
closest = CVP.closest_vector(mat, target)
diffs = [target[i] - closest[i] for i in range(dim)]
for sign in (1, -1):
lows = [sign * d for d in diffs]
if all(0 <= low < base for low in lows):
seed = (outputs[0] << 256) + lows[0]
print(long_to_bytes(seed, 64).rstrip(b"\x00"))
break
案例输出:Nepctf{C0pp3rsm1th_m33ts_LLL_in_Latt1c3_w0rld!}。
变体与关联
- 变体:截断位数不同(
>> k)时把2^256换成2^k,并相应调整scale与格维度。 - 变体:
a、c未知时,先用连续输出差分/gcd 恢复参数(参考 LCG 参数恢复卡),再做 HNP。 - 变体:输出为低位截断或高位+低位组合时,重新推导线性关系,构造相应的 HNP/Coppersmith 格。
- 变体:
p完全未知但N已知时,可先用 Coppersmith 求p的小根或结合其他泄露。 - 关联:[[crypto-prng-lcg-parameter-recovery-delta-gcd]](LCG 参数恢复)、[[crypto-prng-mt19937-seed-recovery-lfsr-noise-batch-alignment]](PRNG 种子恢复)、[[crypto-rsa-williams-p-plus-1-smooth-factor]](同题其他 RSA 分解)。
检测与防御
- 防御:不要用 LCG 生成密钥/种子;使用 CSPRNG(
secrets、os.urandom)并避免输出内部状态的高位/低位。 - 防御:若必须用 LCG,输出前对状态做密码学哈希,且不要连续泄露多个输出的截断值。
- 检测:代码中出现
s = (a*(s-c)) % p、s >> k连续输出、固定a/c/p;对密钥生成做统计随机性检测。 - 响应:发现状态泄露后立即更换密钥/种子,评估历史输出是否可恢复,审计依赖该 PRNG 的协议。