[matrix(ZZ, 1, m ,list(b)) , zero_matrix(1,n), matrix(ZZ,[[M]])],
])
for row in B.LLL():
ifabs(row[-1]) != 1:
continue
for s in (row[m:m+n], -row[m:m+n]):
ifall(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.allimport ZZ, block_matrix, identity_matrix, matrix, zero_matrix
defmain(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(): ifabs(row[-1]) != M: continue # 令末坐标为 +M,此时向量形式是 (e, -s, M)。 row = row if row[-1] == M else -row e = row[:m] s = -row[m:m + n] ifany(x notin (0, 1) for x in s): continue ifany(abs(x) > 1for x in e): continue ifany((sum(A[i, j] * s[j] for j inrange(n)) + e[i] - b[0, i]) % q for i inrange(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 inzip(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
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)
defencrypt_bit(bit): if bit == 1: samples_list = [lwe() for _ inrange(m)] return [tuple(list(a) + [b]) for a, b in samples_list] else: return [tuple([F.random_element() for _ inrange(n + 1)]) for _ inrange(m)]
encbit = [] for bit in flagbin: encbit.append(encrypt_bit(int(bit)))
withopen("./output", "wb") as f: f.write(str(encbit).encode())
import itertools, random, os from sage.allimport *
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 isNone: raise SystemExit('[-] cannot find output / output.txt') print('[*] reading', path) withopen(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 defprimal_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 isnotNoneand check(e): return vector(ZZ, [ZZ(x) for x in e]) returnNone
defcheck(ee): valid_e = True for x in ee: val = int(x) if val > q // 2: val -= q ifabs(val) > 2 ** 32: valid_e = False break return valid_e
defglobal_ok(s): good = 0 for i inrange(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 inenumerate(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 isNone: continue try: s = matrix(F, A).solve_right(vector(F, b) - vector(F, ee)) except Exception: s = None if s isNone: 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
ifnot found: raise SystemExit("[-] failed")
flag = '' for i inrange(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()
defF0():
D = DiscreteGaussianDistributionIntegerSampler(sigma=3.371)
s = PR([D() for _ inrange(n)])
e = PR([D() for _ inrange(n)])
a = PR([randbelow(p) for _ inrange(n)])
b = (a*s + e) % f
return [a.list(), b.list()]
defF1():
a = PR([randbelow(p) for _ inrange(n)])
b = PR([randbelow(p) for _ inrange(n)])
return [a.list(), b.list()]
withopen("samples.txt", "w") as s:
s.write("output =" + str([F0() if i == "0"else F1() for i inbin(bytes_to_long(flag))[2:].zfill(len(flag)*8)]))