---

#!/usr/bin/env python3
import urllib.request
import json
import base64
import struct
import sys

BASE = sys.argv[1] if len(sys.argv) > 1 else "http://tasks.duckerz.ru:30030"

R = 0xE1000000000000000000000000000000
MASK128 = (1 << 128) - 1

def gf128_mul(x, y):
    z = 0
    v = x & MASK128
    for i in range(128):
        if (y >> (127 - i)) & 1:
            z ^= v
        msb = (v >> 127) & 1
        v = (v << 1) & MASK128
        if msb:
            v ^= R
    return z & MASK128

def ghash(H_bytes, aad, ct):
    H = int.from_bytes(H_bytes, "big")
    len_block = struct.pack(">QQ", len(aad) * 8, len(ct) * 8)
    data = aad + ct + len_block
    Y = 0
    for i in range(0, len(data), 16):
        block = data[i:i+16]
        if len(block) < 16:
            block = block + b"\x00" * (16 - len(block))
        X = int.from_bytes(block, "big")
        Y = gf128_mul(Y ^ X, H)
    return Y.to_bytes(16, "big")

def solve_linear_with_kernel(H_k, D):
    cols = [gf128_mul(H_k, 1 << i) for i in range(128)]
    rows = []
    for j in range(128):
        row = 0
        for i in range(128):
            if (cols[i] >> j) & 1:
                row |= (1 << i)
        if (D >> j) & 1:
            row |= (1 << 128)
        rows.append(row)
    pivot_row = 0
    pivot_cols = []
    for col in range(128):
        pivot = -1
        for r in range(pivot_row, 128):
            if (rows[r] >> col) & 1:
                pivot = r
                break
        if pivot == -1:
            continue
        rows[pivot_row], rows[pivot] = rows[pivot], rows[pivot_row]
        for r in range(128):
            if r != pivot_row and ((rows[r] >> col) & 1):
                rows[r] ^= rows[pivot_row]
        pivot_cols.append(col)
        pivot_row += 1
    free_cols = [c for c in range(128) if c not in pivot_cols]
    kernel_basis = []
    for free in free_cols:
        k = 1 << free
        for i, col in enumerate(pivot_cols):
            if (rows[i] >> free) & 1:
                k |= (1 << col)
        kernel_basis.append(k)
    X0 = 0
    for i, col in enumerate(pivot_cols):
        if (rows[i] >> 128) & 1:
            X0 |= (1 << col)
    return X0, kernel_basis

def post(path, payload):
    req = urllib.request.Request(BASE + path, data=json.dumps(payload).encode(),
        headers={"Content-Type": "application/json"}, method="POST")
    with urllib.request.urlopen(req, timeout=15) as resp:
        return json.loads(resp.read().decode())

def get(path):
    with urllib.request.urlopen(BASE + path, timeout=15) as resp:
        return json.loads(resp.read().decode())

def main():
    print(f"[TEST] 1*1 = {gf128_mul(1,1):x} (должно 1)")
    print(f"[TEST] 2*2 = {gf128_mul(2,2):x} (должно 4)")

    r = get("/flag")
    flag_blob = base64.b64decode(r["flag_blob"])
    FLAG_IV  = flag_blob[:12]
    FLAG_CT  = flag_blob[12:-16]
    FLAG_TAG = flag_blob[-16:]
    print(f"[+] FLAG_IV  = {FLAG_IV.hex()}")
    print(f"[+] FLAG_CT  = {FLAG_CT.hex()} ({len(FLAG_CT)} bytes)")
    print(f"[+] FLAG_TAG = {FLAG_TAG.hex()}")

    r = post("/aes_ecb_service", {"block_b64": base64.b64encode(b"\x00" * 16).decode()})
    GLOBAL_H = base64.b64decode(r["cipher_b64"])
    print(f"[+] GLOBAL_H = {GLOBAL_H.hex()}")

    FLAG_J0 = FLAG_IV + b"\x00\x00\x00\x01"
    r = post("/aes_ecb_tenant", {"who": "victim", "block_b64": base64.b64encode(FLAG_J0).decode()})
    E_K_J0 = base64.b64decode(r["cipher_b64"])
    print(f"[+] E_K(J0) = {E_K_J0.hex()}")

    known = bytes(a ^ b for a, b in zip(FLAG_TAG, E_K_J0))
    print(f"[+] known = {known.hex()}")

    AAD_PREFIX = b"user-aad-prefix:"
    G0 = ghash(GLOBAL_H, AAD_PREFIX + b"\x00" * 16, FLAG_CT)
    print(f"[+] G0 = {G0.hex()}")

    diff = bytes(a ^ b for a, b in zip(known, G0))
    diff_int = int.from_bytes(diff, "big")
    print(f"[+] diff = {diff.hex()}")

    N = 2 + (len(FLAG_CT) + 15) // 16 + 1
    k = N - 1
    print(f"[+] N = {N}, k = {k}")

    H = int.from_bytes(GLOBAL_H, "big")
    H_k = 1
    for _ in range(k):
        H_k = gf128_mul(H_k, H)
    print(f"[+] H^k = {H_k:032x}")

    print("\n[*] Ищем решение с ядром...")
    X0, kernel = solve_linear_with_kernel(H_k, diff_int)
    print(f"[+] X0 = {X0:032x}")
    print(f"[+] размер ядра = {len(kernel)} (должно 3)")
    for i, kvec in enumerate(kernel):
        print(f"    kernel[{i}] = {kvec:032x}")
    print(f"[+] Проверка X0 * H^k = {gf128_mul(X0, H_k):032x}")
    print(f"[+]                     diff = {diff_int:032x}")

    print("\n[*] Перебираем 2^3 = 8 вариантов...")
    SECRET_VICTIM = None
    for mask in range(1 << len(kernel)):
        X = X0
        for i in range(len(kernel)):
            if (mask >> i) & 1:
                X ^= kernel[i]
        SV = X.to_bytes(16, "big")
        check = ghash(GLOBAL_H, AAD_PREFIX + SV, FLAG_CT)
        if check == known:
            print(f"*** mask={mask}: SECRET_VICTIM = {SV.hex()} ***")
            SECRET_VICTIM = SV
            break
        else:
            print(f"    mask={mask}: {SV.hex()} - не подходит")
    if SECRET_VICTIM is None:
        print("[-] Не найдено")
        return None

    print("\n[*] Отправляем на /verify...")
    r = post("/verify", {"who": "victim",
        "blob": base64.b64encode(flag_blob).decode(),
        "aad_hex": SECRET_VICTIM.hex()})
    print(f"[+] /verify response: {r}")
    if "plaintext_b64" in r:
        flag = base64.b64decode(r["plaintext_b64"]).decode()
        print(f"\n[***] FLAG: {flag}")
        return flag
    return None

if __name__ == "__main__":
    main()