LWE学习

碰到过几次了,整理一下,以后还碰到会持续更新

基本概念

如果有一组线性方程组:

As=b(modq)A s = b \pmod q

其中矩阵 A∈Zqm×nA \in \mathbb{Z}_q^{m \times n},秘密向量 s∈Zqns \in \mathbb{Z}_q^n。当已知 AA 和 bb 时,只要方程数 m≥nm \ge n,用经典的高斯消元法就能在多项式时间内轻松解出 ss。

LWE 的核心改动是在每个等式中混入微小的随机噪声(Error):

b=As+e(modq)b = A s + e \pmod q

这时:

  • s∈Zqns \in \mathbb{Z}_q^n:秘密向量(Secret)。
  • A∈Zqm×nA \in \mathbb{Z}_q^{m \times n}:均匀随机采样的已知矩阵。
  • e∈Zqme \in \mathbb{Z}_q^m:从某种特定分布(通常是离散高斯分布 χ\chi)中抽取的微小误差向量,满足 ∥e∥≪q\Vert{}e\Vert{} \ll q。
  • b∈Zqmb \in \mathbb{Z}_q^m:计算出的带噪目标值。
    一旦引入微小噪声 ee,传统的高斯消元法在消元过程中会导致误差迅速被放大并模 qq 扩散,导致完全无法恢复出 ss。此时,求解 ss 变成了在格(Lattice)中寻找最接近目标向量的格点(即 CVP / BDD 问题)。

一般的LWE有两种形式:

Search-LWE(计算型/搜索型):给定 (A,b=As+e(modq))(A, b = As + e \pmod q),求出秘密向量 ss

Decision-LWE(判定型):给定样本对 (A,v)(A, v),区分 vv 究竟是真实的 LWE 样本 As+e(modq)As + e \pmod q,还是从 Zqm\mathbb{Z}_q^m 中完全均匀随机抽取的向量。

常见分析方法

1.Kannan 嵌入

已知信息:

给定矩阵 A∈Zqm×nA \in \mathbb{Z}_q^{m \times n}、向量 b∈Zqmb \in \mathbb{Z}_q^m 和模数 qq,已知存在秘密向量 s∈Zns \in \mathbb{Z}^n 与小误差向量 e∈Zme \in \mathbb{Z}^m,满足:

As+e≡b(modq)  ⟺  b−As=e+qk(∃k∈Zm)As + e \equiv b \pmod q \iff b - As = e + qk \quad (\exists k \in \mathbb{Z}^m)

分析:

由于 e=b−As(modq)e = b - As \pmod q,存在整数向量 k∈Zmk \in \mathbb{Z}^m 满足:

$$As + qk - b = -e$$

我们目标就是将未知的小误差 ee 构造为格上的极短向量

构造格基矩阵: 构造 (n+m+1)(n + m + 1) 阶(或通过主元消去后化简为 (m+1)(m + 1) 阶)矩阵。常用形式为:

B=(qIm0m×n0m×1ATIn0n×1bT01×nM)∈Z(m+n+1)×(m+n+1)B = \begin{pmatrix} q I_m & 0_{m \times n} & 0_{m \times 1} \\ A^T & I_n & 0_{n \times 1} \\ b^T & 0_{1 \times n} & M \end{pmatrix} \in \mathbb{Z}^{(m+n+1) \times (m+n+1)}

选取整数组合系数向量:

v=(kT, −sT, 1)∈Zm+n+1v = (k^T, \, -s^T, \, 1) \in \mathbb{Z}^{m+n+1}

计算对应的格向量 t=v⋅Bt = v \cdot B:

t=(qkT−sTAT+bT,−sT,M)t = \Big( qk^T - s^T A^T + b^T, \quad -s^T, \quad M \Big)

由 As+e≡b(modq)As + e \equiv b \pmod q,即存在 k∈Zmk \in \mathbb{Z}^m 使 b−As+qk=eb - As + qk = e,于是

qkT−sTAT+bT=eTqk^T - s^T A^T + b^T = e^T

得到格点:

t=(eT, −sT, M)∈Λ(B)t = (e^T, \, -s^T, \, M) \in \Lambda(B)

由此还原秘密向量s

MM 是一个调节权重的小常数,此处取 11
向量 (kT,−sT,1)⋅B=(eT,−sT,M)(k^T, -s^T, 1) \cdot B = (e^T, -s^T, M)。 e,se, s 的相对模数 qq 很小,因此此向量在格中是异常短的向量。

关于M的选取:
B 是分块三角阵,detB=qm⋅1⋅M=qmMdetB=q^m⋅1⋅M=q^mM,维数 d=m+n+1d=m+n+1。
高斯启发式给出典型最短向量:λ1(Λ)≈d2πe⋅(det⁡Λ)1/d\lambda_1(\Lambda) \approx \sqrt{\frac{d}{2\pi e}} \cdot (\det \Lambda)^{1/d}
目标向量长度是:∥(e,s,M)∥=∥e∥2+∥s∥2+M2\|(e, s, M)\| = \sqrt{\|e\|^2 + \|s\|^2 + M^2}
成功条件:
最后一维是 tMtM,起惩罚作用:MM 太大,t=±1t=\pm 1 的目标向量被撑长,可能输给 t=0t=0 的短向量;MM 太小,最后一维几乎不贡献长度,tt 可以随便取大而不受惩罚,嵌入就失去筛选作用。

实用判据只有一条:目标向量长度要明显小于 λ1\lambda_1。这里 ∥e∥≈80⋅2/3≈7.3\|e\| \approx \sqrt{80 \cdot 2/3} \approx 7.3,∥s∥≈40⋅2/3≈5.2\|s\| \approx \sqrt{40 \cdot 2/3} \approx 5.2,取 M=1M=1 时目标向量长 ≈7.32+5.22+1≈9\approx \sqrt{7.3^2 + 5.2^2 + 1} \approx 9;而由高斯启发式

λ1≈1212πe⋅(332980)1/121≈2.66×213≈567\lambda_1 \approx \sqrt{\tfrac{121}{2\pi e}} \cdot (3329^{80})^{1/121} \approx 2.66 \times 213 \approx 567

差 60 倍以上,MM 随便取个 1 都够。不让MM 把目标放大过 λ1\lambda_1即可

直接在 SageMath 中使用 B.LLL() 或结合 fpylll 调用 BKZ 算法提取短向量。

进一步:ss 不小时的处理

上面那个格能成立,前提是 ss 本身也是短向量 —— 目标向量 (e,s,M)(e, s, M) 的长度里含着 ∥s∥\|s\|。若 ss 在 Zq\mathbb{Z}_q 上均匀取,∥s∥∼q\|s\| \sim q,整个目标向量一点都不短,嵌入直接失败。

我们需要构造新格,把 ss 从格里彻底消掉。

定义:

Λq(A)={As+qk:s∈Zn, k∈Zm}⊆Zm\Lambda_q(A) = \{As + qk : s \in \mathbb{Z}^n,\ k \in \mathbb{Z}^m\} \subseteq \mathbb{Z}^m

由 b=As+e(modq)b = As + e \pmod q 知,bb 到 Λq(A)\Lambda_q(A) 的距离恰好是 ∥e∥\|e\| —— 所以问题就是一个 mm 维格上的 BDD,与 ss 的大小无关。这是 qq-ary 格,rank⁡A=n\operatorname{rank} A = n 时

det⁡Λq(A)=q m−n\det \Lambda_q(A) = q^{\,m-n}

写出 Λq(A)\Lambda_q(A) 的 mm 维基

把 AA 分块成 (A1A2)\begin{pmatrix} A_1 \\ A_2 \end{pmatrix},A1∈Zqn×nA_1 \in \mathbb{Z}_q^{n \times n} 可逆,A2∈Zq(m−n)×nA_2 \in \mathbb{Z}_q^{(m-n)\times n},令

P=A2A1−1(modq)∈Zq(m−n)×nP = A_2 A_1^{-1} \pmod q \in \mathbb{Z}_q^{(m-n)\times n}

对 x=As+qkx = As + qk:前 nn 维是 A1s+qk1A_1 s + qk_1,后 m−nm-n 维是 A2s+qk2=P(A1s)+qk2A_2 s + qk_2 = P(A_1 s) + qk_2,于是

x∈Λq(A)  ⟺  x2≡Px1(modq)x \in \Lambda_q(A) \iff x_2 \equiv P x_1 \pmod q

即「前 nn 维自由、后 m−nm-n 维带约束」,对应的行基是(PP 是 (m−n)×n(m-n)\times n,挪到右上角要转置)

B0=(InPT0qIm−n)∈Zm×m,det⁡B0=q m−nB_0 = \begin{pmatrix} I_n & P^{T} \\ 0 & q I_{m-n} \end{pmatrix} \in \mathbb{Z}^{m \times m}, \qquad \det B_0 = q^{\,m-n}

取 z=(z1,z2)z=(z_1, z_2),z1∈Zn, z2∈Zm−nz_1 \in \mathbb{Z}^n,\ z_2 \in \mathbb{Z}^{m-n},则 zB0=(z1, z1PT+qz2)z B_0 = (z_1,\ z_1 P^{T} + q z_2),正好是「前 nn 维随便取、后 m−nm-n 维 ≡Px1\equiv P x_1」。

分块位置别写反。 写成 (In0PqIm−n)\begin{pmatrix} I_n & 0 \\ P & qI_{m-n} \end{pmatrix} 时,zB0=(z1+z2P, qz2)z B_0 = (z_1 + z_2 P,\ q z_2),前 nn 维被 z1z_1 填满、后 m−nm-n 维恒 ≡0(modq)\equiv 0 \pmod q,生成的是 Zn×qZm−n\mathbb{Z}^n \times q\mathbb{Z}^{m-n},不是 Λq(A)\Lambda_q(A)。两者行列式都是 qm−nq^{m-n},所以很容易看走眼;只有把它当列基(Sage 的 block_matrix 是行基,必须转置)用的时候,那个形状才成立。

做 Kannan 嵌入

B2=(B00bTM)∈Z(m+1)×(m+1),det⁡B2=q m−nMB_2 = \begin{pmatrix} B_0 & 0 \\ b^T & M \end{pmatrix} \in \mathbb{Z}^{(m+1)\times(m+1)}, \qquad \det B_2 = q^{\,m-n} M

系数向量 (v,1)(v, 1) 给出格点 (b+vB0, M)(b + vB_0,\ M)。取 vB0vB_0 为 −b-b 的最近格点时,第一块就是 ee,得到

(e, M),∥(e,M)∥≈∥e∥2+M2(e,\ M), \qquad \|(e,M)\| \approx \sqrt{\|e\|^2 + M^2}

维度从 m+n+1m+n+1 降到 m+1m+1。

速度更快,而且不依赖s的大小

2.CVP / Babai 视角

实用上不如 Kannan,见得太少了。直接过了

3. Dual对偶攻击​

在对偶格 Λq(A)∨\Lambda_q(A)^\vee 里找一个短向量 ww,满足 wTA≡0(modq)w^T A \equiv 0 \pmod q。于是

⟨w,b⟩=⟨w,As⟩+⟨w,e⟩≡⟨w,e⟩(modq)\langle w, b \rangle = \langle w, As \rangle + \langle w, e \rangle \equiv \langle w, e \rangle \pmod q

真实样本下 ⟨w,b⟩\langle w,b\rangle 服从一个宽度约 σ∥w∥\sigma\|w\| 的窄分布,均匀样本下则是均匀的 —— 据此可以区分;配上足够多样本、再对 ss 的每一位做假设检验,也能恢复 ss。

Dual 攻击在本质上是原生针对 Decision-LWE 设计的区分器,但可以通过“判定到搜索归约”扩展解决 Search-LWE。

例题:

Search-LWE:ZeroG2026

题目

服务器端给出一组LWE数据:

对象 维度
A 80×40 公开,元素均匀取自 Z_3329
s 40×1 秘密,分量 ∈ {-1,0,1}
e 80×1 噪声,分量 ∈ {-1,0,1}
b 80×1 公开,b = A·s + e mod q
要求恢复秘密向量s

分析

模板题,数据设计得很良心
构造格基矩阵B:

$$B = \begin{pmatrix} q I_m & 0 & 0 \\ A^T & I_n & 0 \\ b^T & 0 & M \end{pmatrix}$$

做LLL就行

这种高维的但是分块的矩阵可以分开写,再使用block_matrix()
拼在一起就行了

B=(qI8080×80080×40080×1AT40×80I4040×40040×1bT1×8001×40M1×1)B=\begin{pmatrix} \underset{80\times80}{qI_{80}} & \underset{80\times40}{0} & \underset{80\times1}{0} \\[3ex] \underset{40\times80}{A^{T}} & \underset{40\times40}{I_{40}} & \underset{40\times1}{0} \\[3ex] \underset{1\times80}{b^{T}} & \underset{1\times40}{0} & \underset{1\times1}{M} \end{pmatrix}

还有几个常用的语法要积累一下,不知道的话手搓这个格还会蛮耗时间的

  • identity_matrix(m) 构造m维单位矩阵
  • zero_matrix(m, n) m×nm × n 维零矩阵
  • matrix(ZZ, 1, m, list(b) 把b转成1行m列向量(行向量)
  • block_matrix(ZZ,[]) 拼接矩阵

exp

import json



inst = json.load(open('/home/asus/output.json'))

print(inst)

n,q,m = inst['n'], inst['q'], inst['m']

A = matrix(ZZ, [s['a'] for s in inst['samples']])

b = vector(ZZ, [s['b'] for s in inst['samples']])



M = 1

B = block_matrix(ZZ, [

    [q*identity_matrix(m),       zero_matrix(m, n),    zero_matrix(m, 1)],

    [A.transpose(),              identity_matrix(n),   zero_matrix(n, 1)],

    [matrix(ZZ, 1, m ,list(b)) , zero_matrix(1,n),     matrix(ZZ,[[M]])],

])




for row in B.LLL():

    if abs(row[-1]) != 1:        

        continue

    for s in (row[m:m+n], -row[m:m+n]):  

        if all(x in (0, 1, q-1) for x in (b - A*s) % q):  

            print(''.join('%02x' % (x & 0xff) for x in s))

Search-LWE:强网拟态2026:

题目

给了矩阵 A、向量 b 和 masked_update。参数是 q=7681、n=32、m=64,要恢复秘密向量s

分析

方方正正的Search-LWE问题啊,维度不大,用我们前面造的格直接打就行

exp

import hashlib
import json
import sys
from zipfile import ZipFile

from sage.all import ZZ, block_matrix, identity_matrix, matrix, zero_matrix


def main(path):
with ZipFile(path) as archive:
data = json.loads(archive.read("samples.json"))
q, n, m = data["q"], data["n"], data["m"]
A = matrix(ZZ, data["A"])
b = matrix(ZZ, 1, m, data["b"])
M = 1
assert A.dimensions() == (m, n)

# 行基,严格对应题主给出的分块矩阵。
B = block_matrix(ZZ, [
[q * identity_matrix(ZZ, m), zero_matrix(ZZ, m, n), zero_matrix(ZZ, m, 1)],
[A.transpose(), identity_matrix(ZZ, n), zero_matrix(ZZ, n, 1)],
[b, zero_matrix(ZZ, 1, n), matrix(ZZ, [[M]])],
])
assert B.dimensions() == (m + n + 1, m + n + 1)

for row in B.LLL(delta=0.99).rows():
if abs(row[-1]) != M:
continue
# 令末坐标为 +M,此时向量形式是 (e, -s, M)。
row = row if row[-1] == M else -row
e = row[:m]
s = -row[m:m + n]
if any(x not in (0, 1) for x in s):
continue
if any(abs(x) > 1 for x in e):
continue
if any((sum(A[i, j] * s[j] for j in range(n)) + e[i] - b[0, i]) % q
for i in range(m)):
continue

secret = bytes(int(x) for x in s) # 32 个 0/1 字节,不能打包成 4 字节
key = hashlib.sha256(secret).digest()
masked = bytes.fromhex(data["masked_update"])
flag = bytes(x ^ y for x, y in zip(masked, key))
print("s =", list(s))
print("error max =", max(abs(x) for x in e))
print("verified equations =", m)
print("flag =", flag.decode())
return
raise RuntimeError("LLL 未找到满足全部方程的短向量")


if __name__ == "__main__":
main(sys.argv[1])

Decision-LWE:hgame2026

题目

from Crypto.Util.number import *
from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
from sage.crypto.lwe import LWE
from secret import flag

flagbin = bin(int.from_bytes(flag.split(b'hgame{')[1][:-1], 'little'))[2:].rjust(25 * 8, "0")

n, m = 25, 15
q = getPrime(128)
F = GF(q)
V = VectorSpace(F, n)
D = DiscreteGaussianDistributionIntegerSampler(2**16)
lwe = LWE(n=n, q=q, D=D)

def encrypt_bit(bit):
if bit == 1:
samples_list = [lwe() for _ in range(m)]
return [tuple(list(a) + [b]) for a, b in samples_list]
else:
return [tuple([F.random_element() for _ in range(n + 1)]) for _ in range(m)]

encbit = []
for bit in flagbin:
encbit.append(encrypt_bit(int(bit)))

with open("./output", "wb") as f:
f.write(str(encbit).encode())

# q = 256708627612544299823733222331047933697

分析

题意就是将flag转为数字之后

  • 如果碰到 1 就给出 15 组真实 LWE 样本 (ai,bi)(a_i, b_i):ai∈Zq25a_i \in \mathbb{Z}_q^{25} 随机、s∈Zq25s \in \mathbb{Z}_q^{25} 全局固定、ei∈Ze_i \in \mathbb{Z} 是标量(DD 的 σ=216\sigma = 2^{16}),bi=⟨ai,s⟩+ei mod qb_i = \langle a_i, s \rangle + e_i \bmod q;
  • 碰到 0 就是 15 组完全均匀的随机数

看代码可知只进行了一次lwe初始化,即所有秘密向量s完全相同
我们随机挑选2组使用真实A的数据生成的lwe参数:
b1=A1s+e1b_1 = A_1 s + e_1
b2=A2s+e2b_2 = A_2 s + e_2

注意此时未知量只有s(25个未知数),而两组加起来一共有30个线性方程

方程的矩阵肯定是满秩的
这个s完全可解!

分析到这一层问题就很简单了,前面介绍的两个角度都可以解答:

  • Kannan格恢复s
  • 对偶格统计偏移的方法

exp

这里还是采用最经典的Kannan格方法解答
这里s分布未知所以需要用升级后的Kannan格

import itertools, random, os
from sage.all import *

q = 256708627612544299823733222331047933697
n, m = 25, 15
F = GF(q)

path = next((p for p in ['output.txt', 'output', '/mnt/c/Users/asus/Desktop/output'] if os.path.exists(p)), None)
if path is None:
raise SystemExit('[-] cannot find output / output.txt')
print('[*] reading', path)
with open(path) as f:
data = eval(f.read())

AA = []
bb = []
for i in data:
tmp1, tmp2 = [], []
for j in i:
tmp1.append(j[:-1])
tmp2.append(j[-1])
AA.append(tmp1)
bb.append(tmp2)
AA = [matrix(F, i) for i in AA]
bb = [vector(F, i) for i in bb]


# 格还是 B2(q-ary 格 + Kannan),只把最后一位按 esz 缩放后再 LLL
def primal_attack2(A, b, m, n, p, esz):
L = block_matrix([
[matrix(Zmod(p), A).T.echelon_form().change_ring(ZZ), 0],
[matrix.zero(m - n, n).augment(matrix.identity(m - n) * p), 0],
[matrix(ZZ, [ZZ(x) for x in b]), 1],
])
Q = diagonal_matrix([1] * m + [esz])
L *= Q
L = L.LLL()
L /= Q
res = L[0]

e = None
if res[-1] == 1:
e = res[:m]
elif res[-1] == -1:
e = -res[:m]
if e is not None and check(e):
return vector(ZZ, [ZZ(x) for x in e])
return None


def check(ee):
valid_e = True
for x in ee:
val = int(x)
if val > q // 2:
val -= q
if abs(val) > 2 ** 32:
valid_e = False
break
return valid_e


def global_ok(s):
good = 0
for i in range(len(AA)):
if check(bb[i] - AA[i] * s):
good += 1
return good


K = 3 K = 3 # 3块比2块更稳,实际都能出

random.seed()
found = False
for attempt, idxs in enumerate(itertools.combinations(random.sample(range(len(data)), 30), K), 1):
A = block_matrix(F, [[AA[i]] for i in idxs], ncols=1)
b = vector(F, sum((list(bb[i]) for i in idxs), []))
ee = primal_attack2(A, b, K * m, n, q, 2 ** 16)
if ee is None:
continue
try:
s = matrix(F, A).solve_right(vector(F, b) - vector(F, ee))
except Exception:
s = None
if s is None:
continue
good = global_ok(s)
if good >= 40: # 全局判据:真 s 会让 ~106/200 块残差都很小
print("[+] idxs=%s attempt=%d global-consistent=%d/%d" % (idxs, attempt, good, len(data)))
found = True
break

if not found:
raise SystemExit("[-] failed")

flag = ''
for i in range(200):
if check(bb[i] - AA[i] * s):
flag += '1'
else:
flag += '0'

from Crypto.Util.number import long_to_bytes
print('[+] body = %r' % long_to_bytes(int(flag, 2))[::-1])
print('[+] flag = hgame{%s}' % long_to_bytes(int(flag, 2))[::-1].decode())

Search-LWE:强网杯2026

题目

from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler

from Crypto.Util.number import *

from secrets import randbelow

from secret import flag



p = 0x3ac01f87

PR.<x> = PolynomialRing(GF(p))

f = # 一个贼长的多项式

n = f.degree()



def F0():

    D = DiscreteGaussianDistributionIntegerSampler(sigma=3.371)

    s = PR([D() for _ in range(n)])

    e = PR([D() for _ in range(n)])

    a = PR([randbelow(p) for _ in range(n)])

    b = (a*s + e) % f

    return [a.list(), b.list()]



def F1():

    a = PR([randbelow(p) for _ in range(n)])

    b = PR([randbelow(p) for _ in range(n)])

    return [a.list(), b.list()]



with open("samples.txt", "w") as s:

    s.write("output =" + str([F0() if i == "0" else F1() for i in bin(bytes_to_long(flag))[2:].zfill(len(flag)*8)]))

分析

这个题相较于前三难度真不是一个量级的,感觉没ai的话真是想不出来
这里也是写写ai给我的思路吧

题目给出的 ff 很长,看起来像随机多项式,但分析后发现,它与下面这个稀疏多项式有很大的公共因子:

H(x)=x100+x50−x20+1H(x)=x^{100}+x^{50}-x^{20}+1

进一步去掉 x10+1x^{10}+1,得到:

Q(x)=x90−x80+x70−x60+x50−x10+1.Q(x)=x^{90}-x^{80}+x^{70}-x^{60}+x^{50}-x^{10}+1.

然后计算:

g(x)=gcd⁡(f(x),Q(x)),deg⁡g=58.g(x)=\gcd(f(x),Q(x)),\qquad \deg g=58.

这意味着:

g∣f,g∣Qg\mid f,\qquad g\mid Q

这就是整个攻击的关键结构。

因为 g∣fg\mid f,原来的等式模 gg 后仍然成立:

b≡as+e(modg)b\equiv as+e\pmod g
这里有很巧的一步

但直接模一个任意的 gg,可能把原本很小的系数搅成接近随机的大数。于是先绕一步:**在整数多项式环中模 QQ,令

sQ=s mod Q,eQ=e mod Qs_Q=s\bmod Q,\qquad e_Q=e\bmod Q

由于 g∣Qg\mid Q,它们模 gg后与原来的 (s,e)(s,e) 等价,因此:

b≡asQ+eQ(modg)b\equiv a s_Q+e_Q\pmod g

由此:

  • QQ只有 90 次,(sQ,eQ)(s_Q,e_Q) 各只需要 90 个系数。
  • QQ 的系数很小,且本题实际的整数约化矩阵元素不大,约化后的秘密和误差仍保留“小”的特征。

所以问题转变成了:

在 180 个整数未知量中,寻找一个较短的向量,满足 58 个模 pp 的线性约束。

再把多项式关系改写成“小整数线性方程”。

将 sQ,eQs_Q,e_Q的系数拼成向量:

z=(s0,…,s89,e0,…,e89)Tz=(s_0,\ldots,s_{89},e_0,\ldots,e_{89})^T
我们造Kannan格去打就可以:

BM=(pI5800−ATI1220(t′)T032)∈Z181×181,∣det⁡BM∣=32 p58B_M = \begin{pmatrix} p I_{58} & 0 & 0 \\ -A^T & I_{122} & 0 \\ (t')^T & 0 & 32 \end{pmatrix} \in \mathbb{Z}^{181 \times 181}, \qquad |\det B_M| = 32 \, p^{58}

exp

import argparse, ast, hashlib, json, math, re, sys, time

from pathlib import Path

from flint import nmod_poly, nmod_mat, fmpz_mat

BASE=Path(__file__).resolve().parents[1]

def setup():

    source=(BASE/'inputs/task.sage').read_text(encoding='utf-8-sig')

    p=int(re.search(r'^p\s*=\s*(\S+)',source,re.M)[1],0)

    polytext=re.search(r'^f\s*=\s*(.+)$',source,re.M)[1]

    coeff=[0]*513

    for term in polytext.split(' + '):

        if 'x' not in term: c,k=int(term),0

        else:

            a,_,b=term.partition('x');c=int(a.rstrip('*')) if a else 1;k=int(b[1:]) if b.startswith('^') else 1

        coeff[k]=c

    x=nmod_poly([0,1],p);f=nmod_poly(coeff,p)

    H=x**100+x**50-x**20+1;Q=H//(x**10+1);g=f.gcd(Q)

    assert f.degree()==512 and Q.degree()==90 and g.degree()==58

    q=[1,-1,0,0,0,1,-1,1,-1,1];v=[1]+[0]*8;red=[]

    for _ in range(52):

        red.append(v[:]);top=v[-1];v=[(v[i-1] if i else 0)-top*q[i] for i in range(9)]

    # The saved witnesses use the U52 transform in all ten residue blocks.

    # This remains a valid integral basis for 51-column blocks as well.

    U=fmpz_mat(json.loads((BASE/'evidence/covariance-transform.json').read_text())['u']);Ui=U.inv()

    images=[]

    for r in range(10):

        for j in range(9):

            h=nmod_poly([0],p)

            for i in range(9):h+=int(Ui[i,j])*x**(10*i+r)

            images.append(h%g)

    samples=ast.literal_eval((BASE/'inputs/samples.txt').read_text().split('=',1)[1])

    assert len(samples)==336 and all(len(a)==len(b)==512 for a,b in samples)

    return p,f,g,Q,U,red,images,samples

P,F,G,Q,U,RED,IMAGES,SAMPLES=setup()

def check(i,v):

    assert len(v)==181 and abs(v[-1])==32

    a=nmod_poly(SAMPLES[i][0],P)%G;b=nmod_poly(SAMPLES[i][1],P)%G

    ss=sum((c*h for c,h in zip(v[:90],IMAGES)),nmod_poly([0],P))

    ee=sum((c*h for c,h in zip(v[90:180],IMAGES)),nmod_poly([0],P))

    assert (a*ss+ee-b*(v[-1]//32))%G==0

    assert sum(t*t for t in v)<700**2

    return math.sqrt(sum(t*t for t in v))

def verify():

    data=json.loads((BASE/'evidence/revision-verification.json').read_text());bits=[];norms=[]

    for i,record in enumerate(data['records']):

        assert record['index']==i

        if record['bit']==0:

            v=json.loads((BASE/f'evidence/candidate-{i}.json').read_text());norms.append(check(i,v));bits.append('0')

        else:

            log=(BASE/f'evidence/revision52-{i}.log').read_text()

            assert f'REDUCED {i} 52' in log and f'PRUNED_NO {i} 52' in log

            assert 'TIMEOUT' not in log and 'Traceback' not in log

            bits.append('1')

    msg=bytes(int(''.join(bits[i:i+8]),2) for i in range(0,len(bits),8)).decode()

    assert ''.join(bits)==data['bits'] and msg==data['flag']

    print('modulus p =',P,'degree(f) =',F.degree())

    print('degree(Q) =',Q.degree(),'degree(gcd(f,Q)) =',G.degree())

    print('samples =',len(SAMPLES),'decoded bytes =',len(msg))

    print('exact zero-bit witnesses =',len(norms),'audited one-bit classifications =',bits.count('1'))

    print('witness norm range =',round(min(norms),6),round(max(norms),6))

    print('bit[285] =',bits[285],'; character[35] =',msg[35])

    print('FLAG =',msg)

    print('User confirmed this corrected flag as accepted in the retained AI conversation.')

    print('One-bit classifications are statistical; pruned NO is not a proof of nonexistence.')

    return msg



def recover(idx,basis=None):

    import numpy as np

    from fpylll import IntegerMatrix, BKZ, GSO, Enumeration, EnumerationError

    start=time.time(); n=180

    if basis:

        stored=json.loads(Path(basis).read_text());W=fmpz_mat(stored['W']);rows=stored['rows'];scale=7

    else:

        a=nmod_poly(SAMPLES[idx][0],P)%G;b=nmod_poly(SAMPLES[idx][1],P)%G

        columns=[a*h%G for h in IMAGES]+IMAGES

        C=nmod_mat([[int(h[i]) for h in columns]+[int(b[i])] for i in range(58)],P)

        R,rank=C.rref();assert rank==58

        piv=[next(j for j in range(n) if int(R[i,j])) for i in range(58)];free=[j for j in range(n) if j not in piv]

        rows=[]

        for j in piv:

            row=[0]*181;row[j]=P;rows.append(row)

        for j in free:

            row=[0]*181;row[j]=1

            for k,t in enumerate(piv):row[t]=(-int(R[k,j])+P//2)%P-P//2

            rows.append(row)

        row=[0]*181

        for k,j in enumerate(piv):row[j]=(int(R[k,n])+P//2)%P-P//2

        row[-1]=32;rows.append(row)

        # Same 9x9 integer approximation to covariance whitening as the final audit.

        rr=np.array(U.tolist(),dtype=float)@np.array(RED,dtype=float).T;C9=rr@rr.T

        val,vec=np.linalg.eigh(C9);wn=np.rint(64*(vec@np.diag(val**-.5)@vec.T)).astype(np.int64)

        W=fmpz_mat(wn.tolist());scale=7

        for row in rows:

            for j in range(20):row[9*j:9*j+9]=[int(z) for z in (W*fmpz_mat([[v] for v in row[9*j:9*j+9]])).entries()]

            row[-1]*=scale

        rows=[[int(v) for v in r] for r in fmpz_mat(rows).lll().tolist()]

    Wi=W.inv(); A=IntegerMatrix.from_matrix(rows)

    def candidate(v):

        if abs(v[-1])!=224 or sum(t*t for t in v)>4300**2:return False

        plain=[]

        for j in range(20):

            block=Wi*fmpz_mat([[t] for t in v[9*j:9*j+9]])

            for k in range(9):

                z=block[k,0];assert z.denominator==1;plain.append(int(z))

        plain.append(v[-1]//7);norm=check(idx,plain)

        out=BASE/f'evidence/replay-candidate-{idx}.json';out.write_text(json.dumps(plain))

        print('VERIFIED_ZERO',idx,'norm',norm,'elapsed',round(time.time()-start,3),flush=True)

        return True

    strategies=str(BASE/'evidence/fplll-default.json')

    for block in [0,38,44,48,52,56]:

        if block:

            BKZ.reduction(A,BKZ.Param(block,strategies=strategies,max_loops=2,min_success_probability=.1))

        rows=[[int(A[i,j]) for j in range(181)] for i in range(181)]

        if any(candidate(row) for row in rows):return

        M=GSO.Mat(A);M.update_gso();E=Enumeration(M)

        try:sol=E.enumerate(0,181,3800**2,0,pruning=[min(1,(181-j)/181+.12) for j in range(181)])

        except EnumerationError:

            print('UNKNOWN',idx,'BKZ',block,'elapsed',round(time.time()-start,3),flush=True);continue

        for _,coeff in sol:

            v=[sum(round(coeff[k])*int(A[k,j]) for k in range(181)) for j in range(181)]

            if candidate(v):return

    print('UNRESOLVED: no zero witness found; do not assign 1 solely from this result.')

if __name__=='__main__':

    ap=argparse.ArgumentParser();ap.add_argument('--recover-index',type=int);ap.add_argument('--basis');args=ap.parse_args()

    if args.recover_index is None:verify()

    else:recover(args.recover_index,args.basis)