samples.json 未完成记录：LWE 秘密向量已恢复，masked_update 仍未解开

这道附件题目前只保留 samples.json，缺少完整题面。已经得到能满足所有方程的秘密向量与误差向量，但 masked_update 的生成规则不明，尚未得到最终 flag。不能把恢复私钥等同于完成整题。

附件结构

1
2
3
4
5
6

q = 7681
n = 32
m = 64
A: 64 × 32
b: 64 维
masked_update: 28 字节

数据满足 LWE 形式：b = A·s + e (mod q)。恢复出的 s 只有 0/1，e 取值为 -1、0、1。

求解思路

把 A 拆成上下两个 32×32 块 A1、A2，b 相应拆成 b1、b2。A1 在模 q 下可逆时：

1
2
3
4
5

s = A1^-1 · (b1 - e1) mod q
M = A2 · A1^-1 mod q
c = b2 - M·b1 mod q

e2 - M·e1 = c mod q

由此构造 64 维 q-ary 格，用 LLL、BKZ 约化，再通过 CVP 找到靠近目标的小误差。原会话在 WSL Kali 中使用 fpylll，求解脚本保留了 BKZ-20/30/40 的处理过程。

这解释的是已有求解脚本的构造，不代表只凭参数就能保证任意同维 LWE 都可这样高效求解。

已恢复并重新核验的结果

1
2
3

s = 10000001000001100011101001110100
按上述位串解释为整数：0x81063a74
汉明重量：12

e 为 64 维三值向量，其中 42 个非零。整理本文时重新从 samples.json 和 lwe_solution.json 计算了全部 64 行残差：

1
2
3
4
5
6

residuals = [
    (sum(a * x for a, x in zip(row, s)) + err - target) % q
    for row, err, target in zip(A, e, b)
]
assert len(residuals) == 64
assert all(r == 0 for r in residuals)

结果全部为零，且 s 的元素集合为 {0,1}、e 为 {-1,0,1}。这证明保存的解满足该实例；本文不据此声称解的唯一性已经被证明。

没完成的是 masked_update

1

7c53ddbd82faf811c0397982909a9498644d63fb50a6e697d7cf97f6

它有 28 字节，与 SHA-224 输出长度相同，但长度相同不能证明它就是 SHA-224 或某种哈希结果。

原会话和工作区尝试过多种候选：s/e 的直接字节或位串异或、常见哈希派生、不同大小端与序列化、若干 PRNG、AES 模式及流密码等。记录中没有得到符合预期格式且经平台确认的 flag。

这些失败只能排除具体脚本覆盖的候选，不能证明“所有常规方案都不可能”。也没有证据支持直接提交 flag{81063a74}。

自动扫 flag 的误报

自动接题器对 samples.zip 与 samples (1).zip 写入过一个含乱码、控制字符的 FrW{...} 候选。它来自附件静态扫描，没有数学推导或判题回执，不能算完成记录。两份样本应合并处理，避免把重复误报计作两道已解题。

后续应先补什么

先找原题名称、描述及生成脚本，确认 masked_update 的含义、字节编码和预期输出格式。保存的 s/e 已足够继续验证具体构造，不必先重跑格约化。

下面提供本题原始数据、已恢复的解以及独立校验脚本；它们只用于复核已完成的数学部分，不包含最终解密程序。

• samples.json
• lwe_solution.json
• verify_solution.py

下载到同一目录后运行 python verify_solution.py。完整误差向量保存在解文件中。

资料来源

依据 10 月 31 日 samples 会话、samples_work/unz/solve_wsl.py、lwe_solution.json 及自动接题索引整理。本文重新执行了方程校验，没有重新运行格求解，也没有猜测最终 flag。