LCG 参数恢复:连续输出差分 gcd 求模数、乘数与种子
crypto/prng · verified
一句话结论
当拿到 LCG 的连续输出 s_i 时,相邻差 d_i=s_{i+1}-s_i 满足 d_{i+2}·d_i - d_{i+1}^2 ≡ 0 (mod m);对所有项取最大公约数即可恢复模数 m,再用首两个差分求乘数 a、用首两个状态求增量 b,最后反解 seed。
原理
- LCG 递推:
s_{i+1} = (a·s_i + b) mod m。相邻差d_i = s_{i+1}-s_i = a·(s_i-s_{i-1}) = a·d_{i-1} mod m,所以d_i本身也是一个乘数为a的 LCG(无增量)。 - 消去 a:
d_{i+1} ≡ a·d_i (mod m),d_{i+2} ≡ a·d_{i+1} (mod m);两式相乘/相除消去a得d_{i+2}·d_i ≡ d_{i+1}^2 (mod m)。因此m整除d_{i+2}·d_i - d_{i+1}^2。 - 恢复 m:对所有
i计算该差值并取gcd(含 0 时跳过);gcd可能是m的倍数/小因子,需要结合多个样本和验证。本题 gcd 直接给出 1321...771。 - 恢复 a/b:
a = d_1 · d_0^{-1} mod m(要求gcd(d_0,m)=1);b = (s_1 - a·s_0) mod m。 - 恢复 seed:题目给出的第一个状态是
seed迭代一次后的结果,s_0 = (a·seed + b) mod m,所以seed = (s_0-b)·a^{-1} mod m。 - 为什么成立:LCG 是线性递推,差分把仿射项消掉,剩下纯乘性关系;连续输出足够多时,模数可被差分关系唯一确定(最多差一个因子)。
触发条件
- 拿到至少 4 个连续 LCG 输出(本题 10 个),且输出没有截断/取高位。
m未知但为常数;a、b未知;gcd(d_0,m)=1以保证可求逆(否则需用其他差分/扩展欧几里得)。- 已知递推形式与输出顺序;第一个输出是否等于 seed 需按题目确认。
- 输出是精确整数(不是
% 2^k截断),否则差分关系不完整。
利用步骤
- 计算相邻差分
d_i = s_{i+1} - s_i。 - 对每个
i计算d_{i+2}·d_i - d_{i+1}^2,与当前g取gcd;忽略 0。 - 把
g作为候选m,用更多项验证d_{i+1} ≡ a·d_i mod m;若失败,尝试g的因子/倍数。 - 求
a = d_1·d_0^{-1} mod m,b = (s_1 - a·s_0) mod m。 - 反解
seed = (s_0-b)·a^{-1} mod m;按题目要求转字节/十六进制。 - 用
s_{i+1} == (a·s_i+b) mod m回代验证全部状态;本题seed转字节得到b'{solvethelastlag}'。
PoC
from math import gcd
states = [
421212310892931870090770823648461624975774,
862129767917451191679336928145552691547367,
1079761070727277937369386910846268488929766,
40605969152837342975500589521586616251762,
439006148938366452242502948541061704411062,
954155169757201085402176495152430057621156,
563168879613345685512623653387438510002584,
561093487257447844384066670581505915222992,
368958647863543275592990859614306474308863,
197354019925819894610192413469597110533773,
]
delta = [b - a for a, b in zip(states, states[1:])]
m = 0
for i in range(len(delta) - 2):
relation = delta[i + 2] * delta[i] - delta[i + 1] ** 2
m = gcd(m, abs(relation))
a = delta[1] * pow(delta[0], -1, m) % m
b = (states[1] - a * states[0]) % m
seed = (states[0] - b) * pow(a, -1, m) % m
plain = seed.to_bytes((seed.bit_length() + 7) // 8, "big")
print("m =", m)
print("a =", a)
print("b =", b)
print("seed =", seed)
print(plain) # b'{solvethelastlag}'
assert all((a * x + b) % m == y for x, y in zip(states, states[1:]))
变体与关联
- 变体(截断输出):只给
s_i mod 2^k或高位时,差分关系被破坏,需要 HNP/格方法或更多信息。 - 变体(未知增量/乘数):已知
m时用两组方程解a,b;未知m时先恢复m。 - 变体(多组 LCG/交错):不同 LCG 输出混在一起时,先按周期/统计分离。
- 关联卡片:[[crypto-prng-mt19937-seed-recovery-lfsr-noise-batch-alignment]](MT19937 状态恢复)、[[crypto-prng-glibc-rand-output-sequence-prediction]](线性递推预测)、[[crypto-prng-srand-time-seed-2fa-code-prediction]](弱种子)。
- 边界:输出不足、
gcd(d_0,m)>1、模数不唯一时需要额外验证;浮点/截断输出不适用。
检测与防御
- 不要用 LCG 做安全随机数:LCG 线性可预测,连续输出即可恢复参数与种子;密钥/token 使用 CSPRNG。
- 种子管理:即使种子随机,LCG 状态泄露也会导致后续输出可预测;输出应经过加密/哈希。
- CTF 识别:看到连续大整数、递推关系、模数未知,优先尝试差分 gcd;用回代验证。