//Classically — Writeup

Author: infernosalex (challenge)

Challenge slogan: "Do you think you can solve this classically?"

Flag format: ctf{...}

>TL;DR ✅

• The challenge gives a statically defined 64×64 matrix M (in M.py) and shows main.py which computes result = M * flag under modulo 65537.

• Because this is a linear transformation mod a prime, we can recover the flag by solving the linear system M*flag = b (mod 65537) using modular Gaussian elimination.

• The flag recovered is: ctf{s0lve_th3_equ4t10n5_t0_f1nd_fl4g_h3r3_w4s_easy_en0ugh_NO???}

>Details — what we found

• M.py contains a 64×64 matrix of integers.

• main.py shows the code that multiplies a 64-byte flag (explicit length check) by the matrix and prints the resulting result vector modulo 0x10001 (65537), a prime (Fermat prime).

• Knowing M and seeing result, we can solve for the flag bytes using modular linear algebra.

Why this is 'classical': The problem is a plain linear algebra system over the finite field Z_p where p=65537.

Important observations:

• The flag length matches the dimension of the matrix: 64 bytes.

• The modulus 65537 is prime, so inverses exist for non-zero pivot elements; Gaussian elimination works modulo this prime.

• After solving, all 64 solution entries are in 0..255 — this is likely because the original flag bytes are typical ASCII bytes.

>Solving strategy (step-by-step)

1. Extract the matrix M from M.py (challenge file).

2. Extract the output vector b (either from the remote service (if provides) or main.py output). In our main.py file the printed vector was included as a comment; otherwise the remote service would return the vector.

3. Solve M*flag = b in Z_65537 with Gaussian elimination. The algorithm:

   - Build the augmented matrix [M | b]

   - Perform row swapping, normalization (multiply rows by inverse mod p), and elimination to reduce to reduced row-echelon form.

   - Extract solution vector x from augmented column.

1. Convert solution vector to bytes; check prefix ctf{ and suffix } as validation.

Because p = 65537 (> 255), recovered byte values are identical to the original bytes of the flag.

>Reproducible code

All code I used is provided in solve.py (simple modular gaussian elimination) — below is the solver and a small script to run it locally.

solve.py (already in repo)

• Imports M from M.py.

• Accepts a --bfile or --b to load the output vector b.

• Solves and prints the recovered flag.

Usage examples (local):

cd /home/noigel/CTF/null/crypto/Classically

# If you have b vector inline (from main.py print), use --b

python3 solve.py --b "[29839, 662, 50523, 15906, 32667, 25159, ... , 1337]"

  

# Or save the vector in a file result.txt and use --bfile

echo "[29839, 662, 50523, 15906, ...]" > result.txt

python3 solve.py --bfile result.txt

Alternatively, you can run the solver with the vector printed by main.py (the sample in the challenge):

python3 solve.py --b "[29839, 662, 50523, 15906, 32667, 25159, 5172, 11685, 5618, 62174, 54405, 34902, 12259, 59526, 12299, 37286, 6055, 16813, 42488, 40708, 7662, 24263, 24047, 55429, 64420, 18167, 36330, 18325, 61471, 559, 32085, 23807, 26543, 26886, 24249, 45980, 23360, 15196, 42894, 33054, 22073, 23786, 63308, 44883, 60088, 38633, 54798, 42893, 29049, 25567, 33563, 49913, 63714, 51666, 60112, 19656, 13133, 11756, 34277, 55622, 14539, 54580, 48536, 1337]"

Example output (successful run):

>Local vs Remote

• Local (what we did): We used the M.py matrix and the printed vector from main.py (embedded in the challenge). By solving that linear system locally, we successfully extracted the flagged message.

• Remote (generic instructions): If the challenge exposed an interactive service, you would typically connect and receive the vector b (likely printed in the same manner). Steps for remote:

  1. Connect (telnet/nc/http as appropriate), read the output vector.

  2. Copy the vector into a file or pass it directly to solve.py --b "[...]".

  3. Run the solver script to recover the flag.

Notes for remote parsing: Services sometimes format vectors with newlines, commas, or additional text around them. The solve.py has a parse_b_from_string helper that is forgiving: it supports Python list literals (with square brackets), comma or whitespace separated numbers, or small variations.

If the server is interactive and prints extra text, you can use small shell tools to extract the numeric list. For example, if the server prints vector = [n, n, ...] or similar, you can do:

# example using `nc` for a TCP service env

nc some.host.tld 12345 | sed -n 's/^.*\[\(.*\)\].*/\[\1\]/p' > result.txt

python3 solve.py --bfile result.txt

If the server prints numbers one per line, you can convert them:

nc host 12345 | grep -E '^[0-9]+' > result.txt

python3 solve.py --bfile result.txt

You can also wrap the parsing into a short Python snippet for robust handling.

>Implementation details: a note about modular arithmetic

• Because p = 65537 is prime, for any non-zero a (mod p), inverse(a) exists as a^(p-2) mod p.

• We use the inverse via Python pow(a, p-2, p) to normalize pivot rows.

• The elimination routine handles zero pivots with row swaps.

• If the matrix is singular modulo p (rare but possible), this method will report it.

Edge cases:

• If the service uses a different modulus (not 65537), adapt the MOD constant.

• If the vector b isn't 64 values, re-check that matrix dimension matches the provided b vector.

>Final Remarks

• This is a nice demonstration of a simple but robust classical linear algebra attack: when you have a linear transform of plaintext into ciphertext and you know the transformation and the ciphertext, the problem reduces to solving a linear system.

• Because we used a prime modulus > 255 and the flag bytes were encoded directly, the solution was direct.

Good luck in the writeup contest — the core idea is easy to follow: show M, show the printed result, show the modular gauss elimination code, and show the recovered flag. Make it clear why each step is safe and how to reproduce the process in remote settings.

Appendices

Flag

ctf{s0lve_th3_equ4t10n5_t0_f1nd_fl4g_h3r3_w4s_easy_en0ugh_NO???}

Source files

• M.py — the static 64×64 matrix (from challenge)

• main.py — a sample program combining flag and M to form result

• solve.py — modular Gaussian elimination solver (this repo)

 - solve_remote.py — helper script that extracts numeric vector b from arbitrary text piped into stdin and solves it (for remote automation)

 - solve_inline.py — the quick inline solver used during interactive testing (identical algorithm but inlined for simple runs)

If you want, I can also:

• Add solve_remote.py to automatically probe a remote challenge and extract b from the output, then call solve.py.

• Add requirements.txt or Dockerfile to reproduce the environment easily for testing.

• Expand the writeup with more mathematical background on Gaussian elimination over finite fields.

Automating remote capture (example commands)

If the challenge is hosted remotely, use any of the following patterns to capture and solve the returned b vector. The solve_remote.py script accepts arbitrary text from stdin and will extract numeric tokens for solving.

# direct pipeline to extractor

nc some.host.tld 12345 | python3 solve_remote.py

  

# store then solve offline

nc some.host.tld 12345 > remote_output.txt

python3 solve_remote.py < remote_output.txt

  

# HTTP JSON endpoint example

curl -s "http://example.com/vector_endpoint" | python3 solve_remote.py

In all these cases, solve_remote.py finds the first 64 numbers in the input and tries to solve for the flag; if there are more numbers (or labels), you may prefer to extract a list literal using sed/jq or other utilities before solving.