python

# CGL Hash Inversion - Complete SageMath Solution
#
# This script should be run in SageMath (not plain Python).
# It correctly implements BFS on the 2-isogeny graph to find the path.

PRIME = (2**13) * (3**7) - 1
print(f\"PRIME = {PRIME}\")

# Setup the field and curve
K.<i> = GF(PRIME**2, modulus=x**2 + 1)
Y = polygen(K)

E0 = EllipticCurve(K, [0, 6, 0, 1, 0])
start_j = E0.j_invariant()
print(f\"start_j = {start_j}\")

# Classical modular polynomial of level 2
Phi2 = classical_modular_polynomial(2).change_ring(K)
vars2 = Phi2.parent().gens()

# CGL hash function (forward)
def CGL_hash(msg_bits, j_start):
    curr_j = j_start
    prev_j = None
    for bit in msg_bits:
        f = Phi2.subs({vars2[0]: curr_j, vars2[1]: Y})
        if hasattr(f, 'univariate_polynomial'):
            f = f.univariate_polynomial()
        roots = f.roots(multiplicities=False)
        valid_neighbors = [r for r in roots if r != prev_j]
        valid_sorted = sorted(valid_neighbors, key=lambda r: [int(c) for c in r.list()])
        prev_j = curr_j
        curr_j = valid_sorted[bit]
    return curr_j

# Get neighbors function
def get_neighbors(j):
    f = Phi2.subs({vars2[0]: j, vars2[1]: Y})
    if hasattr(f, 'univariate_polynomial'):
        f = f.univariate_polynomial()
    return f.roots(multiplicities=False)

# BFS to find path from start_j to target_j
def BFS_find_path(start_j, target_j, max_depth=100):
    from collections import deque

    queue = deque()
    queue.append((start_j, None, []))  # (curr_j, prev_j, path)
    visited = set()
    visited.add((start_j, None))

    nodes_explored = 0

    while queue:
        curr_j, prev_j, path = queue.popleft()
        nodes_explored += 1

        if nodes_explored % 10000 == 0:
            print(f\"  Explored {nodes_explored} nodes, depth {len(path)}\")

        if len(path) > max_depth:
            continue

        neighbors = get_neighbors(curr_j)
        valid = [r for r in neighbors if r != prev_j]
        if prev_j is None:
            valid = neighbors  # At first step, all 3 neighbors are valid (bits 0 and 1 use first 2)

        valid_sorted = sorted(valid, key=lambda r: [int(c) for c in r.list()])

        for bit_idx in range(min(2, len(valid_sorted))):
            next_j = valid_sorted[bit_idx]
            new_path = path + [bit_idx]

            if next_j == target_j:
                return new_path

            state = (next_j, curr_j)
            if state not in visited:
                visited.add(state)
                queue.append((next_j, curr_j, new_path))

    print(f\"Explored {nodes_explored} nodes, target not found.\")
    return None

# Target j-invariant from the problem
target_j = K(17702267 + 9824216*i)
print(f\"target_j = {target_j}\")

# Run BFS
print(\"\
Running BFS to find path...\")
path = BFS_find_path(start_j, target_j, max_depth=80)

if path is None:
    print(\"Path not found within depth limit.\")
else:
    print(f\"\
Found path: {path}\")
    print(f\"Path length: {len(path)}\")

    # Verify
    computed = CGL_hash(path, start_j)
    print(f\"Computed target: {computed}\")
    print(f\"Expected target: {target_j}\")

    if computed == target_j:
        print(\"\
✓ Path verified! Now decrypting...\")

        # Decrypt
        from Crypto.Cipher import AES
        from Crypto.Util.Padding import unpad
        import hashlib

        secret_path_str = str(path)
        print(f\"Secret path string: {secret_path_str}\")
        aes_key = hashlib.sha256(secret_path_str.encode()).digest()[:16]
        print(f\"AES key (hex): {aes_key.hex()}\")

        ct_hex = \"3cea38f9b42cb724edf17080682bf33f782f1a9652163a87001f0aab505ae39d86a808b0a7b817d83082ef7fdd3d195662d78c34aeda37e32f16f5303d352c12\"
        ct = bytes.fromhex(ct_hex)
        iv = ct[:16]
        cipher = AES.new(aes_key, AES.MODE_CBC, iv=iv)
        pt = unpad(cipher.decrypt(ct[16:]), 16)
        print(f\"\
*** FLAG: {pt.decode()} ***\")
    else:
        print(\"Path verification FAILED!\")

# If BFS doesn't find the path, try with larger depth or different strategy
print(\"\
Done.\")