---

import struct

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

def gf128_mul(x, y):
    z = 0
    v = x & MASK128
    for i in range(128):
        if (y >> 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(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
    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_row += 1
    X = 0
    for r in range(pivot_row):
        for col in range(128):
            if (rows[r] >> col) & 1:
                if (rows[r] >> 128) & 1:
                    X |= (1 << col)
                break
    check = 0
    for i in range(128):
        if (X >> i) & 1:
            check ^= cols[i]
    if check != D:
        return None
    return X

# Данные из прошлого вывода:
H_k = 0x6483f1ed6ad11f379d4e92ad1f96a1e9
diff = 0xe4de107485ab15d0fd86fa9899c1dcce

print("=== Тест: X * H^5 для известного X ===")
test_X = 0x123456789abcdef0123456789abcdef0
test_D = gf128_mul(test_X, H_k)
print(f"test_X = {test_X:032x}")
print(f"test_D = {test_D:032x}")
solved = solve_linear(H_k, test_D)
if solved is None:
    print("solved = None")
else:
    print(f"solved = {solved:032x}")
    print(f"solved == test_X: {solved == test_X}")

print()
print("=== Ищем inv(H^5) ===")
inv_H_k = solve_linear(H_k, 1)
if inv_H_k is None:
    print("inv(H^5) = None")
else:
    print(f"inv(H^5) = {inv_H_k:032x}")
    print(f"H^5 * inv(H^5) = {gf128_mul(H_k, inv_H_k):032x} (должно 1)")

print()
print("=== Ищем SECRET_VICTIM ===")
if inv_H_k is not None:
    SECRET = gf128_mul(diff, inv_H_k)
    print(f"SECRET_VICTIM = {SECRET:032x}")
    print(f"Проверка: SECRET * H^5 = {gf128_mul(SECRET, H_k):032x}")
    print(f"                   diff = {diff:032x}")
    print(f"Совпадает: {gf128_mul(SECRET, H_k) == diff}")