wavy — TJCTF 2026

Description

why does my decode script not work :(

Given two files: flag.enc (35 bytes of encrypted flag data) and decode.py (a broken Python decode script). The goal is to fix the script and decrypt the flag.

Analysis

The decode.py script

The provided script implements a Chebyshev polynomial of the first kind recurrence modulo the secp256k1 prime:

from pathlib import Path
from Crypto.Util.number import long_to_bytes

M = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

def encrypt(val, key):
    amp = val
    p = M
    prev = 1
    current = amp
    for _ in range(key - 1):
        new_val = (2 * amp * current - prev) % p
        prev = current
        current = new_val
    return current

flag_bytes = ("flag.enc").read_bytes()
base_val = 0x1337C0DE
frequency_key = 10**25
secret = encrypt(base_val, frequency_key)
encrypted = bytes([a ^ b for a, b in zip(flag_bytes, long_to_bytes(secret))])
print(encrypted)

The recurrence relation is:

• T(0) = 1
• T(1) = val
• T(n) = 2·val·T(n-1) − T(n-2) mod M

This is the Chebyshev polynomial of the first kind evaluated at val, computed modulo the secp256k1 prime M.

Two bugs in the script

1. Python bug: ("flag.enc").read_bytes() calls .read_bytes() on a bare string, which has no such method. It should be Path("flag.enc").read_bytes().

2. Performance bug: The naive loop iterates frequency_key = 10^25 times. At even 10^9 iterations per second, this would take ~10^16 seconds (300 million years). This is computationally infeasible.

Keystream length mismatch

The secret is computed modulo the 32-byte secp256k1 prime, producing at most 32 bytes. But the flag is 35 bytes long. The original encryption must have cycled the keystream — the zip in the decode script would silently truncate to 32 bytes, losing the last 3 bytes of the flag.

Solution

Matrix exponentiation

The Chebyshev recurrence is a second-order linear recurrence that can be expressed in matrix form:

[T(n+1)]   [2·val  -1] ^(n-1)   [val]
[T(n)  ] = [1       0]        × [1  ]

Using fast matrix exponentiation (repeated squaring), we compute T(10^25) in O(log₂(10^25)) ≈ 83 matrix multiplications instead of 10^25 loop iterations.

Keystream cycling

To handle the 35-byte flag with a 32-byte secret, we pad the secret to 35 bytes (cycling the keystream) before XORing.

Solve script

from Crypto.Util.number import long_to_bytes

M = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

def encrypt_fast(val, key):
    """Compute Chebyshev-like recurrence using matrix exponentiation.
    
    The recurrence is:
      T(0) = 1
      T(1) = val
      T(n) = 2*val*T(n-1) - T(n-2)  mod M
    
    Matrix form: [T(n), T(n-1)] = [[2*val, -1], [1, 0]]^(n-1) * [val, 1]
    """
    amp = val
    p = M
    
    if key == 0:
        return 1
    if key == 1:
        return amp % p
    
    def mat_mul(A, B, mod):
        return [
            [(A[0][0]*B[0][0] + A[0][1]*B[1][0]) % mod, (A[0][0]*B[0][1] + A[0][1]*B[1][1]) % mod],
            [(A[1][0]*B[0][0] + A[1][1]*B[1][0]) % mod, (A[1][0]*B[0][1] + A[1][1]*B[1][1]) % mod],
        ]
    
    def mat_pow(M_mat, n, mod):
        result = [[1, 0], [0, 1]]
        base = M_mat
        while n > 0:
            if n % 2 == 1:
                result = mat_mul(result, base, mod)
            base = mat_mul(base, base, mod)
            n //= 2
        return result
    
    transition = [[(2 * amp) % p, (-1) % p], [1, 0]]
    result_mat = mat_pow(transition, key - 1, p)
    
    current = (result_mat[0][0] * amp + result_mat[0][1] * 1) % p
    return current

# Read encrypted flag
with open("flag.enc", "rb") as f:
    flag_bytes = f.read()

base_val = 0x1337C0DE
frequency_key = 10**25

secret = encrypt_fast(base_val, frequency_key)
secret_bytes = long_to_bytes(secret, 35)  # Pad to flag length

# XOR to decrypt
decrypted = bytes([a ^ b for a, b in zip(flag_bytes, secret_bytes)])
print(decrypted)
# b'tjctf{REDACTED}'