WHUCTF2026新生赛WP

z = (a & b) ^ ((b ^ 1) & d) = b ? a : d

L = 83 × 89 + 89 × 97 + 97 = 16,117

R[i] = C[i] ^ IV[i mod 16]
C[i] = R[i] ^ IV[i mod 16]

C_0 = E_K(P_0 ^ IV)
C_j = E_K(P_j ^ C_(j-1))    (j > 0)

P_0 = M = X ^ IV
C_0 = E_K(P_0 ^ IV) = E_K((X ^ IV) ^ IV) = E_K(X)

m = (15 - k) mod 16
j = (m + k) // 16

P_0(g) = 00 00 ... 00 g
X_g = P_0(g) ^ IV

320 + 1 + 14 × 257 = 3,919 < 3,997

import asyncio
import json
import os
import re
import sys
from pathlib import Path

import websockets

URL = 'wss://game.whuctf.club/api/traffic/4AbMXtnI6itFfwxFOVk6k?port=1337'
ROOT = Path(__file__).resolve().parents[1]
EVIDENCE = ROOT / 'evidence'
KNOWN_PATH = ROOT / 'work' / 'known_secret.bin'
TRAINING_QUERIES = 320
MAX_QUERIES = 3997
BLOCK = 16
FLAG_LENGTH = 44


def bytes_to_bits(data: bytes):
    return [(byte >> shift) & 1 for byte in data for shift in range(7, -1, -1)]


def berlekamp_massey(bits):
    c = 1
    b = 1
    length = 0
    last_update = -1
    window = 0
    for n, bit in enumerate(bits):
        window = (window << 1) | bit
        discrepancy = (c & window).bit_count() & 1
        if discrepancy:
            previous = c
            c ^= b << (n - last_update)
            if 2 * length <= n:
                length = n + 1 - length
                b = previous
                last_update = n
    if c.bit_length() - 1 != length:
        raise RuntimeError(f'BM degree mismatch: L={length}, poly_degree={c.bit_length()-1}')
    return length, c


class Predictor:
    def __init__(self, bits, length, polynomial):
        if length <= 0:
            raise RuntimeError(f'invalid linear complexity {length}')
        self.length = length
        self.polynomial = polynomial
        self.mask = (1 << length) - 1
        self.window = 0
        for bit in bits[-length:]:
            self.window = ((self.window << 1) | bit) & self.mask

    def next_bytes(self, size):
        result = bytearray()
        for _ in range(size):
            value = 0
            for _ in range(8):
                bit = ((self.polynomial >> 1) & self.window).bit_count() & 1
                self.window = ((self.window << 1) | bit) & self.mask
                value = (value << 1) | bit
            result.append(value)
        return bytes(result)


class RawStream:
    def __init__(self, ws):
        self.ws = ws
        self.pending = b''

    async def until(self, marker):
        while marker not in self.pending:
            part = await asyncio.wait_for(self.ws.recv(), timeout=20)
            self.pending += part if isinstance(part, bytes) else part.encode('utf-8')
        pos = self.pending.index(marker) + len(marker)
        result, self.pending = self.pending[:pos], self.pending[pos:]
        return result


class Bank:
    def __init__(self, ws, evidence_path):
        self.ws = ws
        self.io = RawStream(ws)
        self.log = evidence_path.open('x', encoding='utf-8', newline='\n')
        self.count = 0
        self.predictor = None

    def record(self, item):
        self.log.write(json.dumps(item, sort_keys=True) + '\n')
        self.log.flush()

    async def start(self):
        greeting = await self.io.until(b'> ')
        self.record({'kind': 'greeting', 'raw': greeting.decode('ascii', 'replace')})

    async def query(self, kind, message_builder=None, byte_index=None):
        expected_iv = None
        if self.predictor is not None:
            expected_iv = self.predictor.next_bytes(BLOCK)
        message = b'' if message_builder is None else message_builder(expected_iv)
        if len(message) > 4096:
            raise RuntimeError('message too long')
        self.count += 1
        if self.count > MAX_QUERIES:
            raise RuntimeError(f'local query count exceeds server cap: {self.count}')
        await self.ws.send(b'1\n')
        await self.io.until(b'Message (hex): ')
        await self.ws.send(message.hex().encode('ascii') + b'\n')
        response = await self.io.until(b'> ')
        match = re.search(rb'IV: ([0-9a-fA-F]{32})\r?\nCiphertext: ([0-9a-fA-F]+)\r?\n', response)
        if not match:
            raise RuntimeError(f'could not parse query response: {response!r}')
        actual_iv = bytes.fromhex(match.group(1).decode())
        ciphertext = bytes.fromhex(match.group(2).decode())
        if len(ciphertext) % BLOCK:
            raise RuntimeError(f'ciphertext has non-block length {len(ciphertext)}')
        if expected_iv is not None and actual_iv != expected_iv:
            self.record({'kind': 'prediction-mismatch', 'q': self.count,
                         'expected_iv': expected_iv.hex(), 'actual_iv': actual_iv.hex()})
            raise RuntimeError(f'IV prediction failed at query {self.count}: expected {expected_iv.hex()}, got {actual_iv.hex()}')
        item = {'kind': kind, 'q': self.count, 'message_hex': message.hex(),
                'iv': actual_iv.hex(), 'ciphertext': ciphertext.hex()}
        if byte_index is not None:
            item['byte_index'] = byte_index
        self.record(item)
        return actual_iv, ciphertext

    async def close(self):
        self.log.close()


async def solve_session(session_no):
    known = KNOWN_PATH.read_bytes() if KNOWN_PATH.exists() else b''
    if len(known) >= FLAG_LENGTH:
        raise RuntimeError(f'already have {len(known)} bytes')
    count = min(14, FLAG_LENGTH - len(known))
    evidence_path = EVIDENCE / f'session-{session_no:02d}.jsonl'
    async with websockets.connect(URL, open_timeout=20, close_timeout=3,
                                  max_size=2**20, ping_interval=20, ping_timeout=20) as ws:
        bank = Bank(ws, evidence_path)
        try:
            await bank.start()
            ivs = []
            for i in range(TRAINING_QUERIES):
                iv, _ = await bank.query('training-empty')
                ivs.append(iv)
                if (i + 1) % 100 == 0:
                    print(f'session={session_no} training={i+1}/{TRAINING_QUERIES}', flush=True)
            bits = bytes_to_bits(b''.join(ivs))
            length, polynomial = berlekamp_massey(bits)
            bank.predictor = Predictor(bits, length, polynomial)
            bank.record({'kind': 'linear-recurrence', 'training_queries': len(ivs),
                         'training_bits': len(bits), 'linear_complexity': length,
                         'polynomial_hex': f'{polynomial:x}'})
            print(f'session={session_no} BM_bits={len(bits)} linear_complexity={length}', flush=True)
            await bank.query('prediction-verification-empty')
            print(f'session={session_no} heldout_IV_prediction=PASS', flush=True)

            recovered_this_session = []
            for k in range(len(known), len(known) + count):
                message_len = (15 - k) % BLOCK
                target_index = (message_len + k) // BLOCK
                target_iv, masked_ct = await bank.query(
                    'secret-byte-target', lambda iv, n=message_len: bytes(n), byte_index=k)
                target_ct = bytes(value ^ target_iv[i % BLOCK] for i, value in enumerate(masked_ct))
                if len(target_ct) <= target_index * BLOCK:
                    raise RuntimeError(f'target block {target_index} missing for byte {k}')
                target_block_ct = target_ct[target_index * BLOCK:(target_index + 1) * BLOCK]
                previous_ct = target_iv if target_index == 0 else target_ct[(target_index - 1) * BLOCK:target_index * BLOCK]
                prefix = bytes(message_len) + known
                if len(prefix) != message_len + k:
                    raise RuntimeError(f'prefix length mismatch for byte {k}: {len(prefix)} vs {message_len+k}')
                matches = []
                for guess in range(256):
                    plaintext = prefix + bytes([guess])
                    block = plaintext[target_index * BLOCK:(target_index + 1) * BLOCK]
                    if len(block) != BLOCK:
                        raise RuntimeError(f'candidate plaintext block malformed at byte {k}')
                    aes_input = bytes(a ^ b for a, b in zip(block, previous_ct))
                    aes_iv, aes_masked_ct = await bank.query(
                        'candidate-aes-encryption', lambda iv, x=aes_input: bytes(a ^ b for a, b in zip(x, iv)), byte_index=k)
                    aes_output = bytes(a ^ b for a, b in zip(aes_masked_ct[:BLOCK], aes_iv))
                    matched = aes_output == target_block_ct
                    if matched:
                        matches.append(guess)
                    bank.record({'kind': 'candidate-comparison', 'q': bank.count, 'byte_index': k,
                                 'candidate': guess, 'aes_input': aes_input.hex(),
                                 'aes_output': aes_output.hex(), 'target_output': target_block_ct.hex(),
                                 'match': matched})
                if len(matches) != 1:
                    raise RuntimeError(f'byte {k} produced {len(matches)} matches: {matches}')
                recovered_this_session.append(matches[0])
                known += bytes([matches[0]])
                KNOWN_PATH.write_bytes(known)
                print(f'session={session_no} recovered_byte[{k}]=0x{matches[0]:02x} queries={bank.count}', flush=True)
            print(f'session={session_no} recovered={bytes(recovered_this_session)!r} total={len(known)} queries={bank.count}', flush=True)
        finally:
            await bank.close()


def main():
    session_no = int(sys.argv[1]) if len(sys.argv) > 1 else 1
    asyncio.run(solve_session(session_no))

if __name__ == '__main__':
    main()

import asyncio
import re

import websockets

from solve_session import (
    BLOCK, EVIDENCE, FLAG_LENGTH, KNOWN_PATH, TRAINING_QUERIES,
    Bank, Predictor, berlekamp_massey, bytes_to_bits,
)


async def main():
    secret = KNOWN_PATH.read_bytes()
    if len(secret) != FLAG_LENGTH:
        raise RuntimeError(f'expected {FLAG_LENGTH} recovered bytes, got {len(secret)}')
    evidence_path = EVIDENCE / 'session-05-independent-verification.jsonl'
    async with websockets.connect(
        'wss://game.whuctf.club/api/traffic/4AbMXtnI6itFfwxFOVk6k?port=1337',
        open_timeout=20, close_timeout=3, max_size=2**20,
        ping_interval=20, ping_timeout=20,
    ) as ws:
        bank = Bank(ws, evidence_path)
        try:
            await bank.start()
            ivs = []
            for _ in range(TRAINING_QUERIES):
                iv, _ = await bank.query('verification-training-empty')
                ivs.append(iv)
            bits = bytes_to_bits(b''.join(ivs))
            length, polynomial = berlekamp_massey(bits)
            bank.predictor = Predictor(bits, length, polynomial)
            bank.record({'kind': 'verification-linear-recurrence',
                         'training_queries': len(ivs), 'training_bits': len(bits),
                         'linear_complexity': length,
                         'polynomial_hex': f'{polynomial:x}'})
            await bank.query('verification-heldout-empty')
            for k, candidate in enumerate(secret):
                message_len = (15 - k) % BLOCK
                block_index = (message_len + k) // BLOCK
                iv, masked_ct = await bank.query('verification-secret-target',
                                                 lambda _, n=message_len: bytes(n),
                                                 byte_index=k)
                ciphertext = bytes(value ^ iv[i % BLOCK] for i, value in enumerate(masked_ct))
                target_block = ciphertext[block_index * BLOCK:(block_index + 1) * BLOCK]
                previous = iv if block_index == 0 else ciphertext[(block_index - 1) * BLOCK:block_index * BLOCK]
                plaintext_prefix = bytes(message_len) + secret[:k + 1]
                candidate_block = plaintext_prefix[block_index * BLOCK:(block_index + 1) * BLOCK]
                if len(target_block) != BLOCK or len(candidate_block) != BLOCK:
                    raise RuntimeError(f'malformed verification block at byte {k}')
                aes_input = bytes(a ^ b for a, b in zip(candidate_block, previous))
                aes_iv, masked_aes_ct = await bank.query(
                    'verification-candidate-encryption',
                    lambda current_iv, x=aes_input: bytes(a ^ b for a, b in zip(x, current_iv)),
                    byte_index=k,
                )
                aes_output = bytes(a ^ b for a, b in zip(masked_aes_ct[:BLOCK], aes_iv))
                matched = aes_output == target_block
                bank.record({'kind': 'independent-byte-verification', 'byte_index': k,
                             'candidate': candidate, 'aes_input': aes_input.hex(),
                             'aes_output': aes_output.hex(), 'target_output': target_block.hex(),
                             'match': matched})
                if not matched:
                    raise RuntimeError(f'independent verification failed at byte {k}')
                if (k + 1) % 8 == 0 or k == len(secret) - 1:
                    print(f'independent verification: {k+1}/{len(secret)} bytes PASS; queries={bank.count}', flush=True)
            bank.record({'kind': 'complete-secret-independent-verification',
                         'length': len(secret), 'secret_hex': secret.hex(),
                         'query_count': bank.count})
            print(f'COMPLETE: {secret.decode("utf-8")} (length={len(secret)}, queries={bank.count})', flush=True)
        finally:
            await bank.close()

if __name__ == '__main__':
    asyncio.run(main())

WHUCTF{b33ef4fd-7a3c-2097-3d75-d50d51011f59}

C:  6x2 - x8 = 0
H: 12x2 + 2x4 - 2x9 = 0
K:  x1 - 2x5 = 0
Mn: x1 - x6 = 0
Na: 2x3 - 2x7 = 0
O:  4x1 + 6x2 + 3x3 + 4x4 - 4x5 - 4x6 - 4x7 - 2x8 - x9 = 0
S:  x3 + x4 - x5 - x6 - x7 = 0

v1 = (-2/3, 1/6, -11/3, -1, -1/3, -2/3, -11/3, 1, 0)
v2 = ( 2/3,   0,   5/3,  1,  1/3,  2/3,   5/3, 0, 1)

(a/6)/b = 311/4893
4893a = 1866b

[2018, 311, 1313, 3027, 1009, 2018, 1313, 1866, 4893]

44f0e7b587b9f6ad6349ccd86ab78f33268d644cce63a6b2989c677fec8b8393

from fractions import Fraction
from functools import reduce
from hashlib import sha256
from math import gcd, lcm

import sympy as sp
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

M = sp.Matrix([
    [0, 6, 0, 0, 0, 0, 0, -1, 0],
    [0, 12, 0, 2, 0, 0, 0, 0, -2],
    [1, 0, 0, 0, -2, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, -1, 0, 0, 0],
    [0, 0, 2, 0, 0, 0, -2, 0, 0],
    [4, 6, 3, 4, -4, -4, -4, -2, -1],
    [0, 0, 1, 1, -1, -1, -1, 0, 0],
])

# 4893*x2 - 311*x9 = 0
constraint = sp.Matrix([[0, 4893, 0, 0, 0, 0, 0, 0, -311]])
A = M.col_join(constraint)
assert M.rank() == 7 and len(M.nullspace()) == 2
assert A.rank() == 8 and len(A.nullspace()) == 1

v = A.nullspace()[0]
scale = lcm(*(term.q for term in v))
coefficients = [int(term * scale) for term in v]
d = reduce(gcd, map(abs, coefficients))
coefficients = [x // d for x in coefficients]
if next(x for x in coefficients if x) < 0:
    coefficients = [-x for x in coefficients]

assert all(x > 0 for x in coefficients)
assert reduce(gcd, coefficients) == 1
assert M * sp.Matrix(coefficients) == sp.zeros(7, 1)
assert Fraction(coefficients[1], coefficients[8]) == Fraction(311, 4893)

ciphertext = bytes.fromhex(
    "8b79391734e95c64db69e2239546a309"
    "6b765e746854197ea1e063e6ca98d95a"
    "ca4f2c51efb837e55a1eea4f26dce936"
)
key = sha256("_".join(map(str, coefficients)).encode()).digest()
plaintext = unpad(AES.new(key, AES.MODE_ECB).decrypt(ciphertext), 16)
flag = plaintext.decode("ascii")

# 确认解出的明文能重新生成原密文
assert AES.new(key, AES.MODE_ECB).encrypt(pad(plaintext, 16)) == ciphertext
assert flag.startswith("WHUCTF{") and flag.endswith("}")
print(flag)

WHUCTF{ch3m1stry_1s_ju5t_l1n34r_algebra}

from fractions import Fraction
from pathlib import Path
import json
import re
from Crypto.Util.number import isPrime, long_to_bytes

CHALLENGE = Path(__file__).parents[1]
TASK = Path(__file__).parent / "attachment" / "Gauss_Power" / "task.py"
source = TASK.read_text(encoding="utf-8")
values = [int(x) for x in re.findall(r"^# (\d+)$", source, flags=re.MULTILINE)]
if len(values) != 3:
    raise ValueError(f"expected p, h, c in task comments, got {len(values)} integers")
p, h, c = values
placeholder = re.search(r"flag\s*=\s*b'([?]+)'", source)
if not placeholder:
    raise ValueError("could not read flag placeholder length")
nominal_len = len(placeholder.group(1))

# h*f = q*p + g. With 256-bit f and g, q/f is a continued-fraction
# convergent of h/p because the error g/(p*f) is far below 1/f^2.
q_over_f = Fraction(h, p).limit_denominator((1 << 256) - 1)
q, f = q_over_f.numerator, q_over_f.denominator
g = (h * f) % p
assert h * f == q * p + g
assert f.bit_length() == 256 and g.bit_length() == 256
assert isPrime(f) and isPrime(g)
assert (g * pow(f, -1, p)) % p == h

# Lattice points are (S*(h*r - q*p), r). The target is (S*c, 3*2^254).
# S=2^46 balances the nominal 26-byte placeholder against the 256-bit r range.
scale = 1 << (254 - 8 * nominal_len)
target = (scale * c, 3 << 254)
b1 = (scale * p, 0)
b2 = (scale * h, 1)

def dot(a, b):
    return a[0] * b[0] + a[1] * b[1]

def cross(a, b):
    return a[0] * b[1] - a[1] * b[0]

def nearest_integer(num, den):
    if den < 0:
        num, den = -num, -den
    q0, rem = divmod(num, den)
    return q0 + (2 * rem >= den)

def gauss_reduce(u, v):
    while True:
        if dot(v, v) < dot(u, u):
            u, v = v, u
        mu = nearest_integer(dot(u, v), dot(u, u))
        if mu == 0:
            return u, v
        v = (v[0] - mu * u[0], v[1] - mu * u[1])

def closest_vector_2d(basis, target):
    u, v = gauss_reduce(*basis)
    det = cross(u, v)
    beta = Fraction(cross(u, target), det)
    j0 = beta.numerator // beta.denominator
    best = None
    # In a Gauss-reduced 2D basis, check nearby coefficients along v and
    # minimize the distance along u for each coefficient.
    for j in range(j0 - 2, j0 + 4):
        residual = (target[0] - j * v[0], target[1] - j * v[1])
        i = nearest_integer(dot(residual, u), dot(u, u))
        point = (i * u[0] + j * v[0], i * u[1] + j * v[1])
        d2 = (point[0] - target[0]) ** 2 + (point[1] - target[1]) ** 2
        if best is None or d2 < best[0]:
            best = (d2, point, (i, j), (u, v))
    return best

d2, point, coeffs, reduced_basis = closest_vector_2d((b1, b2), target)
r = point[1]
m = (c - (h * r) % p) % p
flag = long_to_bytes(m)

# Verify the recovered message against the public equations.
assert 1 << 255 <= r < 1 << 256
assert (r * h + m) % p == c
assert flag.startswith((b"WHUCTF{", b"whuctf{", b"flag{"))
assert flag.endswith(b"}")
assert len(flag) == (m.bit_length() + 7) // 8

r_is_prime = isPrime(r)
record = {
    "verification_level": "reconstructed_checker",
    "original_checker_available": False,
    "p_bits": p.bit_length(),
    "h_bits": h.bit_length(),
    "c_bits": c.bit_length(),
    "f_bits": f.bit_length(),
    "g_bits": g.bit_length(),
    "f_prime": isPrime(f),
    "g_prime": isPrime(g),
    "nominal_placeholder_len": nominal_len,
    "recovered_message_len": len(flag),
    "r_bits": r.bit_length(),
    "r_prime": r_is_prime,
    "r_even": r % 2 == 0,
    "message_equation_roundtrip": (r * h + m) % p == c,
    "h_ratio_roundtrip": (g * pow(f, -1, p)) % p == h,
    "flag": flag.decode("ascii"),
}

(CHALLENGE / "flag.txt").write_bytes(flag + b"\n")
(CHALLENGE / "evidence").mkdir(exist_ok=True)
(CHALLENGE / "evidence" / "reconstruction-validation.json").write_text(
    json.dumps(record, ensure_ascii=False, indent=2) + "\n", encoding="utf-8"
)
print(json.dumps(record, ensure_ascii=False, indent=2))

whuctf{Gauss_1s_v3ry_p0w3rfu1}

x[n+1] = A*x[n] + C (mod 2^64)

d[n] = (A^2-1)*x[n] + (A+1)*C
x[n+2] = A^2*x[n] + (A+1)*C
因此 d[n+2] = A^2*d[n] (mod 2^64)

d0 = 25BBFA4ECFCE37B6
d1 = BE697D84E2857F66
d2 = 464E814B42595496

r = (d1/2) * inverse(d0/2) mod 2^63
  = A^2 mod 2^63
  = 24CB8AF5C84DDF09

00C2A5EB6A7D657D
40C2A5EB6A7D657D
80C2A5EB6A7D657D
C0C2A5EB6A7D657D

L = 4D173B8CDA0E2B
x_cal = h*2^56 + L

d0/2 = ((A^2-1)/2)*x_cal + ((A+1)/2)*C (mod 2^63)

c_base = 398DC476DBE2B611
gamma  = 0400000000000000
C = c_base + gamma*h + z*2^63 (mod 2^64)

x[t] = P_t*O + S_t*C (mod 2^64)

b*2^56 <= x[t] < (b+1)*2^56

A = 80C2A5EB6A7D657D
C = B18DC476DBE2B611
校验轮起点 = 1E4D173B8CDA0E2B
铸印起点 O = D291122FFC6CE444

import itertools, json
from pathlib import Path
from fpylll import FPLLL, IntegerMatrix, LLL, GSO

BASE = Path(__file__).resolve().parent
CHALLENGE = BASE.parent
Q = 1 << 64
MASK = Q - 1
B = 1 << 56
SCALE = 1 << 49
ins = json.loads((BASE / 'inscriptions.json').read_text(encoding='utf-8'))
d0, d1, d2 = (int(x, 16) for x in ins['calibration']['marks'])
low56 = int(ins['calibration']['inner_trace'], 16)
plates = ins['plates']
r = ((d1 // 2) * pow(d0 // 2, -1, 1 << 63)) % (1 << 63)
roots = [1]
for bit in range(2, 63):
    roots = [x for a in roots for x in (a, a + (1 << bit))
             if (x*x-r) % (1 << (bit+1)) == 0]
As = sorted({a + z*(1 << 63) for a in roots for z in (0, 1)
             if (a + z*(1 << 63)) % 4 == 1})
print('A^2 mod 2^63 =', f'{r:016X}')
print('A candidates:', ' '.join(f'{a:016X}' for a in As), flush=True)

max_tick = max(p['ledger_tick'] + 2 for p in plates)
all_mul, all_add = {}, {}
for A in As:
    mul, add = [1], [0]
    for _ in range(max_tick):
        mul.append(mul[-1] * A & MASK)
        add.append((A * add[-1] + 1) & MASK)
    all_mul[A], all_add[A] = mul, add

for A in As:
    q = ((A + 1) // 2) % (1 << 63)
    rr = ((A*A - 1) // 2) % (1 << 63)
    qinv = pow(q, -1, 1 << 63)
    cbase = (qinv * (d0//2 - rr*low56)) % (1 << 63)
    gamma = (-qinv * rr * B) % (1 << 63)
    for ids in itertools.combinations(range(len(plates)), 8):
        obs = []
        for j in ids:
            p = plates[j]
            for off, byte in enumerate(bytes.fromhex(p['outer_traces'])):
                obs.append((p['ledger_tick'] + off, byte, j))
        obs.sort()
        n = len(obs)
        dim = n + 2
        mul = all_mul[A]
        add = all_add[A]
        avec = [mul[t] for t, _, _ in obs]
        uvec = [(add[t] * gamma) & MASK for t, _, _ in obs]
        wvec = [(add[t] * (1 << 63)) & MASK for t, _, _ in obs]
        baseoff = [(add[t] * cbase) & MASK for t, _, _ in obs]
        target = [((byte * B - boff) & MASK) + B//2
                  for (_, byte, _), boff in zip(obs, baseoff)]
        target = [x % Q for x in target] + [0, 0]
        inv_a0 = pow(avec[0], -1, Q)
        g = [(a * inv_a0) & MASK for a in avec]
        du = [0] + [(uvec[i] - g[i] * uvec[0]) & MASK
                    for i in range(1, n)]
        dw = [0] + [(wvec[i] - g[i] * wvec[0]) & MASK
                    for i in range(1, n)]
        rows = [[1] + g[1:] + [0, 0],
                [0] + du[1:] + [SCALE, 0],
                [0] + dw[1:] + [0, SCALE]]
        for i in range(1, n):
            row = [0] * dim
            row[i] = Q
            rows.append(row)
        mat = IntegerMatrix.from_matrix(rows)
        LLL.reduction(mat, delta=0.99)
        FPLLL.set_precision(200)
        gs = GSO.Mat(mat, float_type='mpfr')
        gs.update_gso()
        coeff = gs.babai(tuple(target))
        vec = [sum(int(coeff[k]) * int(mat[k, j]) for k in range(dim))
               for j in range(dim)]
        h_raw, z_raw = vec[-2] // SCALE, vec[-1] // SCALE
        origin = ((vec[0] - uvec[0]*h_raw - wvec[0]*z_raw) * inv_a0) & MASK
        C = (cbase + gamma*h_raw + (1 << 63)*z_raw) & MASK
        matched = []
        byte_count = 0
        for p in plates:
            ok = []
            for off, byte in enumerate(bytes.fromhex(p['outer_traces'])):
                t = p['ledger_tick'] + off
                state = (mul[t]*origin + add[t]*C) & MASK
                ok.append(state >> 56 == byte)
                byte_count += ok[-1]
            if all(ok):
                matched.append(p['plate'])
        if len(matched) >= 8:
            h_norm, z_norm = 30, 0
            assert (cbase + gamma*h_norm + (1 << 63)*z_norm) & MASK == C
            result = {
                'method': 'fpylll LLL reduction and GSO Babai nearest plane',
                'calibration_a_squared_mod_2^63': f'{r:016X}',
                'multiplier_candidates': [f'{x:016X}' for x in As],
                'selected_parameters': {
                    'A': f'{A:016X}', 'C': f'{C:016X}',
                    'origin': f'{origin:016X}', 'c_base': f'{cbase:016X}',
                    'gamma': f'{gamma:016X}',
                    'h_representative': f'{h_norm:02X}',
                    'z_representative': z_norm,
                    'raw_h': h_raw, 'raw_z': z_raw
                },
                'selected_plates': [plates[j]['plate'] for j in ids],
                'matching_plates': matched,
                'rejected_plates': [p['plate'] for p in plates
                                    if p['plate'] not in matched],
                'matched_bytes': byte_count
            }
            out = CHALLENGE / 'evidence' / 'lattice-result.json'
            out.write_text(json.dumps(result, ensure_ascii=False, indent=2) + '\n',
                           encoding='utf-8')
            print('RESULT', json.dumps(result, ensure_ascii=False), flush=True)
            raise SystemExit(0)
print('NO_CANDIDATE')
raise SystemExit(1)

whuctf{every_wheel_has_its_origin}

#!/usr/bin/env python3
"""Extract the hidden MP4, rebuild its flashed QR code, and verify its RS blocks."""
import argparse
import ctypes as C
from ctypes.util import find_library
import os
import struct
from io import BytesIO
from pathlib import Path
from zipfile import ZipFile

import numpy as np
from PIL import Image
from segno import consts, encoder

FFMPEG = os.environ.get("TXFFMPEG_LIB") or find_library("TXFFmpeg")
assert FFMPEG, "set TXFFMPEG_LIB to a compatible FFmpeg library"
FRAME_IDS = (52, 53, 54)

def extract_mp4(source: Path) -> bytes:
    data = source.read_bytes()
    assert data[:3] == b"ID3" and data[10:14] == b"PRIV"
    frame_size = sum((data[i] & 0x7f) << shift for i, shift in zip(range(14, 18), (21, 14, 7, 0)))
    frame = data[20:20 + frame_size]
    owner, sep, _ = frame.partition(b"\0")
    assert sep and owner == b"archive"
    id3_size = sum((data[i] & 0x7f) << shift for i, shift in zip(range(6, 10), (21, 14, 7, 0)))
    archive_start = data.index(b"PK\x03\x04", 20)
    with ZipFile(BytesIO(data[archive_start:10 + id3_size])) as zf:
        assert zf.namelist() == ["receiver.mp4"]
        mp4 = zf.read("receiver.mp4")
    assert mp4[4:8] == b"ftyp"
    return mp4

def atom_boxes(data: bytes, start: int, end: int):
    result = []
    pos = start
    while pos + 8 <= end:
        size = struct.unpack_from(">I", data, pos)[0]
        kind, header = data[pos + 4:pos + 8], 8
        if size == 1:
            size, header = struct.unpack_from(">Q", data, pos + 8)[0], 16
        elif size == 0:
            size = end - pos
        assert size >= header and pos + size <= end, (kind, pos, size, end)
        result.append((kind, pos, pos + header, pos + size))
        pos += size
    assert pos == end
    return result

def one(boxes, kind):
    return next(box for box in boxes if box[0] == kind)

def children(data: bytes, box):
    return atom_boxes(data, box[2], box[3])

def video_sample_table(mp4: bytes):
    root = atom_boxes(mp4, 0, len(mp4))
    moov = one(root, b"moov")
    for trak in (b for b in children(mp4, moov) if b[0] == b"trak"):
        mdia = one(children(mp4, trak), b"mdia")
        mdia_boxes = children(mp4, mdia)
        hdlr = one(mdia_boxes, b"hdlr")
        if mp4[hdlr[2] + 8:hdlr[2] + 12] != b"vide":
            continue
        minf = one(mdia_boxes, b"minf")
        stbl = one(children(mp4, minf), b"stbl")
        boxes = children(mp4, stbl)
        stsd = one(boxes, b"stsd")
        entry = stsd[2] + 8
        entry_size = struct.unpack_from(">I", mp4, entry)[0]
        assert mp4[entry + 4:entry + 8] == b"avc1"
        avcc = one(atom_boxes(mp4, entry + 86, entry + entry_size), b"avcC")
        extradata = mp4[avcc[2]:avcc[3]]
        stsz = one(boxes, b"stsz")
        _, default_size, count = struct.unpack_from(">III", mp4, stsz[2])
        sizes = ([default_size] * count if default_size else
                 list(struct.unpack_from(f">{count}I", mp4, stsz[2] + 12)))
        stsc = one(boxes, b"stsc")
        nsc = struct.unpack_from(">I", mp4, stsc[2] + 4)[0]
        chunkspec = [struct.unpack_from(">III", mp4, stsc[2] + 8 + 12 * i)[0:2]
                     for i in range(nsc)]
        co = next((b for b in boxes if b[0] in (b"stco", b"co64")))
        nco = struct.unpack_from(">I", mp4, co[2] + 4)[0]
        width = 4 if co[0] == b"stco" else 8
        offsets = list(struct.unpack_from(f">{nco}{'I' if width == 4 else 'Q'}", mp4, co[2] + 8))
        sample_offsets, si = [], 0
        for chunk_no, chunk_offset in enumerate(offsets, 1):
            samples_per_chunk = max(x for x in chunkspec if x[0] <= chunk_no)[1]
            at = chunk_offset
            for _ in range(samples_per_chunk):
                sample_offsets.append(at)
                at += sizes[si]
                si += 1
        assert si == count and len(extradata) > 8
        return sample_offsets, sizes, extradata
    raise AssertionError("video track not found")

class AVCodecParameters(C.Structure):
    _fields_ = [
        ("codec_type", C.c_int), ("codec_id", C.c_int), ("codec_tag", C.c_uint),
        ("extradata", C.c_void_p), ("extradata_size", C.c_int), ("format", C.c_int),
        ("bit_rate", C.c_int64), ("bits_per_coded_sample", C.c_int),
        ("bits_per_raw_sample", C.c_int), ("profile", C.c_int), ("level", C.c_int),
        ("width", C.c_int), ("height", C.c_int),
    ]

class AVFramePrefix(C.Structure):
    _fields_ = [
        ("data", C.c_void_p * 8), ("linesize", C.c_int * 8),
        ("extended_data", C.POINTER(C.c_void_p)), ("width", C.c_int),
        ("height", C.c_int), ("nb_samples", C.c_int), ("format", C.c_int),
    ]

def decode_video(mp4: bytes, out_dir: Path):
    lib = C.CDLL(FFMPEG)
    def api(name, result, args):
        fn = getattr(lib, "liteav_" + name)
        fn.restype, fn.argtypes = result, args
        return fn
    find = api("avcodec_find_decoder_by_name", C.c_void_p, [C.c_char_p])
    alloc_ctx = api("avcodec_alloc_context3", C.c_void_p, [C.c_void_p])
    open_ctx = api("avcodec_open2", C.c_int, [C.c_void_p, C.c_void_p, C.c_void_p])
    par_alloc = api("avcodec_parameters_alloc", C.c_void_p, [])
    par_to_ctx = api("avcodec_parameters_to_context", C.c_int, [C.c_void_p, C.c_void_p])
    send = api("avcodec_send_packet", C.c_int, [C.c_void_p, C.c_void_p])
    receive = api("avcodec_receive_frame", C.c_int, [C.c_void_p, C.c_void_p])
    packet_alloc = api("av_packet_alloc", C.c_void_p, [])
    packet_from_data = api("av_packet_from_data", C.c_int, [C.c_void_p, C.c_void_p, C.c_int])
    packet_unref = api("av_packet_unref", None, [C.c_void_p])
    frame_alloc = api("av_frame_alloc", C.c_void_p, [])
    frame_unref = api("av_frame_unref", None, [C.c_void_p])
    malloc = api("av_malloc", C.c_void_p, [C.c_size_t])

    offsets, sizes, avcc = video_sample_table(mp4)
    codec = find(b"h264")
    assert codec
    ctx, params = alloc_ctx(codec), par_alloc()
    p = C.cast(params, C.POINTER(AVCodecParameters)).contents
    ext = malloc(len(avcc) + 64)
    C.memmove(ext, avcc, len(avcc)); C.memset(ext + len(avcc), 0, 64)
    p.codec_type, p.codec_id = 0, 27
    p.codec_tag = int.from_bytes(b"avc1", "little")
    p.extradata, p.extradata_size = ext, len(avcc)
    p.width, p.height = 960, 640
    assert par_to_ctx(ctx, params) == 0 and open_ctx(ctx, codec, None) == 0

    packet, frame = packet_alloc(), frame_alloc()
    wanted, decoded = {}, 0
    def drain():
        nonlocal decoded
        while True:
            status = receive(ctx, frame)
            if status < 0:
                break
            f = C.cast(frame, C.POINTER(AVFramePrefix)).contents
            assert (f.width, f.height) == (960, 640) and f.data[0]
            if decoded in FRAME_IDS:
                raw = C.string_at(f.data[0], f.linesize[0] * f.height)
                y = np.frombuffer(raw, dtype=np.uint8).reshape(f.height, f.linesize[0])[:, :f.width].copy()
                wanted[decoded] = y
            decoded += 1
            frame_unref(frame)
    for offset, size in zip(offsets, sizes):
        buf = malloc(size + 64)
        C.memmove(buf, mp4[offset:offset + size], size); C.memset(buf + size, 0, 64)
        assert packet_from_data(packet, buf, size) == 0
        assert send(ctx, packet) >= 0
        packet_unref(packet)
        drain()
    send(ctx, C.c_void_p(0))
    drain()
    assert decoded == 240 and set(wanted) == set(FRAME_IDS), (decoded, wanted.keys())
    out_dir.mkdir(parents=True, exist_ok=True)
    for i, frame_y in wanted.items():
        Image.fromarray(frame_y).save(out_dir / f"frame-{i:03}.png")
    return decoded

def decode_qr(out_dir: Path) -> str:
    frames = [np.asarray(Image.open(out_dir / f"frame-{i:03}.png").convert("L"))
              for i in FRAME_IDS]
    matrix = np.zeros((29, 29), dtype=np.uint8)
    for r in range(29):
        y = 152 + 12 * r
        image = frames[0] if y < 242 else frames[1] if y < 398 else frames[2]
        for c in range(29):
            matrix[r, c] = image[y, 312 + 12 * c] < 128

    fmt_positions = []
    for i in range(8):
        off = 1 if i >= 6 else 0
        fmt_positions.append(((i + off, 8), (8, i + off), (8, 28 - i), (28 - i, 8)))
    matches = []
    for idx, fmt in enumerate(consts.FORMAT_INFO):
        distance = 0
        for i, positions in enumerate(fmt_positions):
            v, h = (fmt >> i) & 1, (fmt >> (14 - i)) & 1
            expected = (v, h, v, 1 if i == 7 else h)  # QR's fixed dark module
            distance += sum(int(matrix[r, c]) != bit for (r, c), bit in zip(positions, expected))
        matches.append((distance, idx))
    distance, idx = min(matches)
    assert distance == 0 and idx == 24, (distance, idx)

    function = encoder.make_matrix(29, 29)
    encoder.add_finder_patterns(function, 29, 29)
    encoder.add_alignment_patterns(function, 29, 29)
    function[-8][8] = 1
    bits = []
    for right0 in range(28, 0, -2):
        right = right0 - 1 if right0 <= 6 else right0
        for vertical in range(29):
            for z in range(2):
                c = right - z
                upwards = ((right & 2) == 0) ^ (c < 6)
                r = 28 - vertical if upwards else vertical
                if function[r][c] == 2:
                    bits.append(int(matrix[r, c]) ^ int((r + c) % 2 == 0))
    assert len(bits) == 567 and bits[560:] == [0] * 7
    raw = bytes(sum(bits[i + k] << (7 - k) for k in range(8))
                for i in range(0, 560, 8))
    blocks = [bytearray(), bytearray()]
    pos = 0
    for _ in range(17):
        for block in blocks:
            block.append(raw[pos]); pos += 1
    for _ in range(18):
        for block in blocks:
            block.append(raw[pos]); pos += 1
    assert pos == 70

    def mul(a, b):
        out = 0
        while b:
            if b & 1:
                out ^= a
            a <<= 1
            if a & 0x100:
                a ^= 0x11D
            b >>= 1
        return out
    def power(a, n):
        out = 1
        for _ in range(n):
            out = mul(out, a)
        return out
    def evaluate(poly, x):
        out = 0
        for byte in poly:
            out = mul(out, x) ^ byte
        return out
    assert all(all(evaluate(block, power(2, n)) == 0 for n in range(18))
               for block in blocks)
    data = bytes(blocks[0][:17] + blocks[1][:17])
    stream = "".join(f"{byte:08b}" for byte in data)
    assert stream[:4] == "0100"
    count = int(stream[4:12], 2)
    assert count == 20
    payload = bytes(int(stream[12 + 8*i:20 + 8*i], 2) for i in range(count))
    assert stream[12 + count * 8:16 + count * 8] == "0000"
    flag = payload.decode("ascii")
    assert flag.startswith("whuctf{") and flag.endswith("}")
    return flag

def main():
    parser = argparse.ArgumentParser()
    parser.add_argument("source", type=Path, help="original receiver.mp3")
    parser.add_argument("out", type=Path, help="directory for extracted MP4 and QR frames")
    args = parser.parse_args()
    mp4 = extract_mp4(args.source)
    video_path = args.out / "receiver.mp4"
    args.out.mkdir(parents=True, exist_ok=True)
    video_path.write_bytes(mp4)
    frames = decode_video(mp4, args.out)
    flag = decode_qr(args.out)
    (args.out / "flag.txt").write_text(flag + "\n")
    print(f"mp4_bytes={len(mp4)}; decoded_frames={frames}; QR=V3-Q/mask0; RS=36/36 zero syndromes; flag={flag}")

if __name__ == "__main__":
    main()