Squares

tjctf

Task: recover secret vector x that is a stationary point of quadratic function H(x) = x^T M x - 2c^T x over GF(257), given 52x52 symmetric matrix M and vector c. Solution: take gradient, reduce to linear system Mx = c (mod 257), solve via Gaussian elimination, decode ASCII.

linear_algebra modular_arithmetic finite_field quadratic_form gf257

linear_system_solvinggaussian_elimination_mod_pgradient_stationary_point

$ ls tags/ techniques/

linear_algebra modular_arithmetic finite_field quadratic_form gf257

linear_system_solvinggaussian_elimination_mod_pgradient_stationary_point

$ cat /etc/rate-limit

Rate limit reached (20 reads/hour per IP). Showing preview only — full content returns at the next hour roll-over.

Squares — TJCTF 2026

Description

A system defines a quadratic function over a finite field: H(x) = x^T M x - 2c^T x (mod p) The secret input x is a stationary point of H(x). Recover x and decode it to obtain the flag.

The challenge provides out.txt containing:

p = 257 (a prime just above the ASCII range)
M = a 52×52 symmetric matrix with entries in [0, 256]
c = a 52-element vector

The goal is to find the secret vector x (the stationary point of H) and decode it as ASCII to get the flag.

Analysis

The quadratic function is:

H(x) = x^T M x - 2c^T x  (mod p)

A stationary point is where the gradient equals zero. Taking the gradient:

∇H(x) = (M + M^T)x - 2c = 0  (mod p)

Since M is symmetric (M = M^T), this simplifies to:

2Mx - 2c = 0  (mod p)
⟹  Mx = c  (mod 257)

This reduces the entire challenge to solving a standard linear system over a finite field. The prime p = 257 is chosen to be just above 255, so all ASCII byte values (including printable characters and the flag format) fit within GF(257).

Key observations:

M is confirmed symmetric by checking M[i][j] == M[j][i] for all i,j
The matrix is 52×52, matching the flag length (32 flag chars + 20 padding spaces)
p = 257 is prime, so GF(257) is a field and modular inverses always exist for non-zero elements

Solution

Step 1: Parse the data

Read the 52×52 matrix M and 52-element vector c from out.txt.

Step 2: Verify M is symmetric

...