defget_otp_samples(count=1200): samples = [] print(f"[*] Collecting {count} samples") for i inrange(count): # 进度条 if i % 100 == 0: sys.stdout.write(f'\r{i}') sys.stdout.flush() io.sendlineafter(b'> ', b'') line = io.recvline().strip() try: samples.append(int(line)) except ValueError: pass return samples
defrecover_key(samples, bit_length=512): """通过统计偏差恢复密钥""" recovered_key_int = 0 for i inrange(bit_length): ones_count = 0 for num in samples: if (num >> i) & 1: ones_count += 1 freq = ones_count / len(samples)
defsolve(): print(f"[*] 开始穷举 r (权重=4, N={N})...") for indices in itertools.combinations(range(N), 4): for signs in itertools.product([-1, 1], repeat=4): rh = [0] * N for i inrange(4): idx = indices[i] # r 非零项的位置 sgn = signs[i] # r 非零项的值 (+1 或 -1) # 累加到 rh 向量中 for k inrange(N): # 循环卷积下标计算:(k - idx) % N # rh[k] += r[idx] * h[k-idx] val = (sgn * h[(k - idx) % N]) rh[k] = (rh[k] + val) % q
# 4. 计算 m = c - rh (mod q) m_candidate = [] valid_ascii = True for k inrange(N): val = (c[k] - rh[k]) % q # 检查解出来的值是否像 ASCII 字符 ifnot (0 <= val < 128): valid_ascii = False break m_candidate.append(val) # 5. 如果看起来像 Flag,输出结果 if valid_ascii: # 尝试转成字符串 try: flag = "".join(chr(x) for x in m_candidate) # 简单的启发式检查:通常 flag 包含 "{" 或 "flag" 或字母 if"{"in flag or"flag"in flag.lower() or"ctf"in flag.lower(): print(f"\n[+] 找到潜在 Flag!") print(f"Indices: {indices}") print(f"Signs: {signs}") print(f"Message (int): {m_candidate}") print(f"Flag: {flag}") return except: pass
from sage.allimport * from Crypto.Util.number import long_to_bytes
# ================= 题目数据 ================= n = 20416580311348568104958456290409800602076453150746674606637172527592736894552749500299570715851384304673805100612931000268540860237227126141075427447627491168 c = 8195229101228793312160531614487746122056220479081491148455134171051226604632289610379779462628287749120056961207013231802759766535835599450864667728106141697
defbxor(a: bytes, b: bytes) -> bytes: returnbytes(x ^ y for x, y inzip(a, b))
defbuild_msg(T: int = 16) -> bytes: blocks = [] for t inrange(T): for i inrange(128): v = (2 * i) & 0xFF# even => LSB=0 b = bytearray(16) b[0:2] = t.to_bytes(2, "big") b[3] = v b[4:6] = (t ^ 0x1234).to_bytes(2, "big") b[7] = v b[8:10] = (t ^ 0xBEEF).to_bytes(2, "big") b[11] = v blocks.append(bytes(b))
blocks2 = [bxor(b, DELTA) for b in blocks] msg = b"".join(blocks + blocks2)
# 唯一性自检(可留可删) assertlen(set(msg[i:i+16] for i inrange(0, len(msg), 16))) * 16 == len(msg) return msg
defdecide_coin(hint: bytes, T: int) -> int: blocks = [hint[i:i+16] for i inrange(0, len(hint), 16)] for t inrange(T): for i inrange(128): c1 = blocks[t*128 + i] c2 = blocks[(T+t)*128 + i] d = bxor(c1, c2) if0in d[12:16]: # last 32-bit word bytes contain 0 return1# random return0# real encryption
defmain(): T = 16 msg = build_msg(T).hex().encode()
io = remote(HOST, PORT)
for r inrange(128): io.recvuntil(b"msg > ") io.sendline(msg)
line = io.recvline().decode().strip() assert line.startswith("hint: ") hint_hex = line.split("hint: ", 1)[1] hint = bytes.fromhex(hint_hex)
io.recvuntil(b"give me coin > ") io.sendline(str(decide_coin(hint, T)).encode())
print(io.recvall().decode(errors="ignore"))
if __name__ == "__main__": main()
subgroup_lattice
题目在干什么?
classPRNG: def__init__(self, state): self.mask = 2147483647# m = 2^31-1 self.state = [s & self.mask for s in state] defnext(self): tmp = 0 for i inrange(len(self.state)): tmp = (tmp + self.state[i] * C[i]) % self.mask self.state = self.state[1:] + [tmp] return tmp defgetrandbits(self, k): returnself.next() >> (self.mask.bit_length() - k)
defrecover_state(hints, C): print("[*] Recovering hidden low-bits (z) ...") samples = len(hints) # 构造转移矩阵 T T = Matrix(GF(m), n, n) for i inrange(n-1): T[i, i+1] = 1 for i inrange(n): T[n-1, i] = C[i] M_gen = Matrix(GF(m), samples, n)
print("[*] Using Error-Recovery Lattice Strategy (LWE style)...") # 1. 生成所有线性关系 # s_k = \sum M_{k,j} s_j M_all = Matrix(GF(m), samples, n) A_all = vector(GF(m), samples) # 观测值 (hints << beta) T_curr = T for k inrange(samples): row = T_curr.row(n-1) for j inrange(n): M_all[k, j] = row[j] # 观测值中心化 A_all[k] = hints[k] * shift + shift//2 T_curr = T_curr * T M0 = M_all[:n, :] M1 = M_all[n:, :] A0 = A_all[:n] A1 = A_all[n:] try: M0_inv = M0.inverse() except: print("[-] Matrix not invertible, need more samples or luck.") returnNone # 转移矩阵 U = M1 * M0^{-1} U = M1 * M0_inv # 常数项 V = A1 - U * A0 V = A1 - U * A0
dim_eq = samples - n dim_vars = samples dim_total = dim_eq + dim_vars + 1 L = Matrix(ZZ, dim_total, dim_total) # 1. Modulo constraints for equations for i inrange(dim_eq): L[i, i] = m for i inrange(n): # Fill H^T part (which corresponds to columns of U) for k inrange(dim_eq): L[dim_eq + i, k] = int(U[k, i]) L[dim_eq + i, dim_eq + i] = 1# Measure length of e_i for i inrange(dim_eq): row_idx = dim_eq + n + i L[row_idx, i] = -1# The -I part of H L[row_idx, row_idx] = 1# Measure length # 3. Target for k inrange(dim_eq): L[dim_total-1, k] = -int(V[k]) L[dim_total-1, dim_total-1] = shift # Weight for the '1' print(f"[*] Lattice built. Dimension: {dim_total}. Solving for errors...") L_red = L.BKZ(block_size=20) # Use BKZ for better quality for row in L_red: ifabs(row[dim_total-1]) == shift: print("[+] Found potential error vector!") # Extract errors errors = [] sign = 1if row[dim_total-1] > 0else -1 # The middle block (dim_vars size) contains the errors for i inrange(dim_vars): val = row[dim_eq + i] * sign errors.append(val) # Check if errors are small # They should be around [-shift/2, shift/2] ifall(abs(e) < shift for e in errors): print(f"[+] Errors are small: {errors[:5]}...") # Recover s_init using s = M0^{-1} (A0 + e_top) # e_top is errors[:n] e_top = vector(GF(m), errors[:n]) s_recovered = M0_inv * (A0 + e_top) # Verify s_list = [int(x) for x in s_recovered] print(f"[+] Recovered State: {s_list}") returnsum(s_list) else: # pass continue returnNone