LLL 恢复小系数多项式:偏移 B 构造短向量,8 组精确求值还原后 SHA-256 派生 AES-CTR key
ctf/crypto · verified
一句话结论
当密钥来自一个次数已知、系数都在已知偏移 B 附近(a_i = B + 小量)的多项式 f(x)=Σa_i x^i,且题目给出若干组精确求值 (x_j, y_j=f(x_j)) 时,可以把“系数向量 + 求值约束”编码进一个格:目标向量是 (a_i−B, 1, 0, …, 0),前段小、后段(求值误差)为零;LLL 找到该短向量后加上偏移 B 即恢复全部系数,再计算 f(0x65537)、SHA-256 派生 AES-CTR key 解密密文。
原理
问题结构
- 设未知多项式
f(x) = a_0 + a_1 x + … + a_N x^N,次数N=128;系数满足a_i = B + e_i,其中B=2^63、e_i是小量(相对 B 很小)。 - 题目给出
M=8组精确求值y_j = f(x_j)(j=0..M−1),没有噪声;未知的是 129 个系数a_i,已知的是 8 个方程和“系数接近 B”这一强约束。 - 直接解 8 个方程无法确定 129 个未知数;但“系数接近 B”把问题变成格中的短向量问题:把所有系数同时减去 B 后,得到一个很短的向量,而求值方程则要求这些短系数与已知 y 的线性组合为零。
格的构造
对每个系数下标 i=0..N 建一行:
row_i = [0,...,1,...,0 | K*x_0^i, K*x_1^i, ..., K*x_{M-1}^i]
即前 N+1 列是单位矩阵(系数坐标),后 M 列是各求值点的 K*x_j^i(K=2^100 用于放大约束)。
再加一行常数行:
row_const = [0,...,0, 1, 0,...,0 | -K*(y_j - B*Σ_i x_j^i) for each j]
其中第 N+1 列(常数坐标)为 1,后 M 列是 -K*(y_j − B*Σ_i x_j^i)。
取格向量:
v = Σ_i (a_i − B) * row_i + 1 * row_const
- 前
N+1个坐标就是a_i − B,因为a_i接近 B,这些都是小量。 - 后
M个坐标:text K * [ Σ_i (a_i−B)x_j^i − (y_j − B*Σ_i x_j^i) ] = K * [ Σ_i a_i x_j^i − y_j ] = 0因为y_j = f(x_j)是精确求值。 - 常数坐标为 1。因此
v是一个“前段小、后段全零、常数项为 1”的短向量;在格中做 LLL 约简,最短向量很可能就是它(或其相反数)。
从短向量恢复系数
- LLL 输出一行若后
M个坐标全为 0,且常数坐标为1或-1,就是目标向量: - 常数坐标为
1:a_i = row[i] + B; - 常数坐标为
-1:先取负,再a_i = -row[i] + B。 - 恢复系数后,题目用
ep = f(0x65537)(即Σ a_i * 0x65537^i)作为秘密;key = SHA-256(str(ep))[:16],再用 AES-CTR 解密ct。 - 该构造之所以有效,是因为“系数接近 B”提供了比方程数更强的先验;8 个方程足以在 129 维格中把目标向量压到最短,而精确求值保证后段严格为零。
触发条件
- 已知多项式次数 N(或可估计),未知系数都在已知偏移 B 附近且偏差远小于 B;求值点 x_j 与结果 y_j 已知。
- 求值是精确的(无噪声);若有小噪声,后段不会严格为零,需要调整 K/用近似格或 CVP,成功率下降。
- 有足够的求值组数把目标向量与格中其它短向量区分开;组数太少可能找到伪短向量,需要用
f(x_j)=y_j回代校验。 - 能运行 LLL(SageMath/FPLLL),矩阵规模在可处理范围内;本例 130×138,系数为大整数,需注意 LLL 精度/时间。
- 密钥派生方式已知(SHA-256 前 16 字节)且 AES 模式/IV 已知。
利用步骤
- 解析题目给出的
(x_j, y_j)、密文ct、nonce;确定次数 N(本例 128)、系数偏移 B(2^63)、缩放 K(2^100)。 - 按上述布局构造
(N+2) × (N+2+M)的整数矩阵:前 N+1 行为单位系数 +K*x_j^i;最后一行常数 +-K*(y_j − B*Σ x_j^i)。 - 对矩阵做 LLL;遍历约简后的行,找后 M 列全为 0、常数列为 ±1 的行。
- 按常数列符号恢复
a_i = ±row[i] + B;用所有(x_j,y_j)回代验证f(x_j)==y_j,排除伪短向量。 - 计算
ep = Σ a_i * 0x65537^i;key = SHA-256(str(ep).encode()).digest()[:16]。 - 用 key 和题目 nonce 构造 AES-CTR 的 16 字节 IV,解密密文;检查明文是否为 flag 格式。
PoC
SageMath(矩阵构造与 LLL;poly_list 为题目给出的 (x, y) 列表):
from sage.all import *
from hashlib import sha256
N = 128
M = 8
B = 2**63
K = 2**100
X = [p[0] for p in poly_list]
Y = [p[1] for p in poly_list]
rows = N + 2
cols = N + 2 + M
mat = Matrix(ZZ, rows, cols)
# 系数坐标 + 求值约束
for i in range(N + 1):
mat[i, i] = 1
for j in range(M):
mat[i, N + 2 + j] = K * (X[j] ** i)
# 常数行:1 * f(x_j) - y_j 的偏移形式
mat[N + 1, N + 1] = 1
for j in range(M):
sum_x_pow = sum(X[j] ** i for i in range(N + 1))
mat[N + 1, N + 2 + j] = -K * (Y[j] - B * sum_x_pow)
L = mat.LLL()
coeffs = None
for row in L:
if all(row[N + 2 + j] == 0 for j in range(M)):
if row[N + 1] == 1:
coeffs = [row[i] + B for i in range(N + 1)]
break
if row[N + 1] == -1:
coeffs = [-row[i] + B for i in range(N + 1)]
break
assert coeffs is not None
assert all(sum(coeffs[i] * X[j] ** i for i in range(N + 1)) == Y[j]
for j in range(M))
ep = sum(c * (0x65537 ** i) for i, c in enumerate(coeffs))
key = sha256(str(ep).encode()).digest()[:16]
print(key.hex())
# 再用 key + nonce 做 AES-CTR 解密 ct
案例解出的 key 为 6ba291ac100d770ebe0fb1220f793fde,AES-CTR 解密得到 DASCTF{Y0u_r3@11y_Kn0w_what_your_3V@lu@t3_pO1ynOmi@1!}。
变体与关联
- 有噪声求值:若
y_j = f(x_j) + noise,后段不再严格为零;可将噪声界纳入格(近似公因子/Coppersmith 风格),或增大 K 并接受近似短向量,再用回代筛选。 - 系数范围未知:B 未知时可以先估计系数上界,或用多个候选 B 跑 LLL;目标向量仍会出现“后段为零、常数 ±1”的特征。
- 模意义求值:若
y_j = f(x_j) mod p,需要把等式改为f(x_j) - y_j - k_j p = 0,把商 k_j 也作为未知量放入格。 - 多变量多项式:把每个单项式作为一格坐标,构造多变量 Coppersmith/LLL;矩阵更大,但“系数小 + 求值约束”思路相同。
- 关联:LLL 短向量/隐藏数问题。
ctf/crypto下已有 LLL hidden short vector、Kannan embedding、HNP 等卡;本卡是“多项式求值 + 小系数偏移”的具体构造。 - 关联:Coppersmith 小根。两者都用格找短向量;Coppersmith 针对模未知因子的根,本卡针对精确求值下的系数向量。
- 防御/设计:不要把密钥直接绑定到“小系数多项式在公开点的值”;使用 CSPRNG/HKDF 生成密钥;若必须用多项式承诺/评估,采用密码学安全的方案并避免泄露足够的精确求值。
检测与防御
- CTF/审计特征:题目给出多组
(x, y)、一个大次数、密钥由hash(str(poly(x)))派生;检查系数是否集中在某个偏移附近。 - 求解校验:LLL 结果必须回代所有
(x_j,y_j);只检查“后段为零”可能拿到伪向量。 - 参数选择:矩阵中 K 要足够大以压制求值误差,但不能大到让 LLL 精度/规模失控;先小规模试跑,再逐步增大 N。
- 防御:密钥派生使用 HKDF/PBKDF2 并加入随机 salt;不要公开多项式在秘密点的精确值;对公开求值点做盲化/加噪;避免使用可被格攻击的小系数结构。
- 监控:在 CTF 之外,这类结构常见于白盒密码/混淆实现;若发现密钥由低熵多项式评估派生,应视为可恢复。