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:

1. M is confirmed symmetric by checking M[i][j] == M[j][i] for all i,j
2. The matrix is 52×52, matching the flag length (32 flag chars + 20 padding spaces)
3. 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

Confirm M[i][j] == M[j][i] for all i,j — this allows simplifying the gradient equation from (M + M^T)x = 2c to Mx = c.

Step 3: Solve Mx = c (mod 257) via Gaussian elimination

Perform Gauss-Jordan elimination over GF(257):

• For each column, find a pivot row with non-zero entry
• Scale the pivot row by the modular inverse of the pivot element (using extended GCD)
• Eliminate all other entries in that column using row operations mod 257

Step 4: Decode the solution

The 52-element solution vector contains ASCII byte values that decode to the flag followed by space padding.

#!/usr/bin/env python3
# Solve Mx = c mod 257 using Gaussian elimination over GF(257)

p = 257

# M and c parsed from out.txt (52x52 matrix and 52-element vector)
M_rows = [
[15,26,200,249,121,16,105,250,144,239,154,243,80,251,52,134,100,39,122,32,91,220,249,212,212,114,24,252,206,190,8,24,60,166,226,188,26,52,154,0,218,75,208,237,214,232,12,239,69,192,51,205],
[26,1,130,115,191,130,252,156,187,158,204,226,213,180,40,136,194,165,137,160,214,152,80,224,206,17,41,5,164,131,12,135,254,144,78,56,150,56,58,140,36,217,47,233,185,172,27,126,45,139,187,221],
[200,130,183,49,136,47,69,117,255,94,16,138,237,177,181,213,188,57,159,24,208,177,242,169,197,53,88,28,126,91,158,131,208,169,111,173,147,227,31,191,137,10,255,55,11,151,195,27,153,120,219,59],
[249,115,49,61,146,203,193,206,50,56,190,157,42,45,179,68,138,23,82,46,36,152,45,125,212,41,208,199,204,208,39,80,161,158,232,25,194,93,97,33,196,192,182,121,51,146,9,195,77,83,75,29],
[121,191,136,146,14,160,165,200,98,117,125,73,109,164,246,5,200,59,52,71,10,236,30,137,158,220,95,83,167,223,217,215,5,25,118,31,92,240,111,133,185,240,196,31,38,147,210,221,194,163,57,21],
[16,130,47,203,160,115,232,59,234,195,70,195,242,53,117,41,184,244,140,168,123,99,256,193,159,179,31,39,117,232,204,175,97,22,100,207,38,0,68,229,79,210,102,207,112,206,170,187,205,200,110,78],
[105,252,69,193,165,232,58,208,154,89,220,60,251,240,188,251,256,105,18,36,161,47,251,45,153,22,159,125,5,153,7,225,91,243,104,94,189,188,70,119,40,210,247,80,136,214,252,24,74,240,7,152],
[250,156,117,206,200,59,208,202,64,192,25,193,153,20,56,37,40,121,225,57,224,159,13,39,39,211,170,26,154,224,80,45,190,218,215,9,206,40,68,45,85,248,91,101,141,224,41,134,44,158,234,39],
[144,187,255,50,98,234,154,64,137,39,87,3,124,63,6,237,56,151,200,88,97,254,165,65,11,181,138,106,111,92,250,22,220,31,231,255,137,112,65,53,187,37,113,155,193,71,247,42,149,254,176,134],
[239,158,94,56,117,195,89,192,39,181,18,62,60,103,121,91,175,52,126,79,87,112,68,108,102,4,75,178,166,10,165,51,49,88,147,122,244,96,212,169,20,221,233,245,222,136,144,194,224,105,247,180],
[154,204,16,190,125,70,220,25,87,18,176,198,185,128,140,189,225,256,19,247,212,114,249,254,211,53,48,174,18,49,75,90,1,248,30,250,9,203,78,79,158,6,50,15,248,186,115,142,128,74,18,16],
[243,226,138,157,73,195,60,193,3,62,198,54,166,25,223,53,128,144,173,193,112,174,169,200,203,53,216,251,84,0,29,203,116,140,240,3,98,210,57,22,208,55,242,213,164,100,230,71,61,230,60,26],
[80,213,237,42,109,242,251,153,124,60,185,166,236,98,249,237,107,60,226,64,28,205,115,37,76,204,100,228,87,182,129,231,93,142,122,104,15,212,231,6,201,10,136,66,141,64,88,160,1,15,203,219],
[251,180,177,45,164,53,240,20,63,103,128,25,98,251,106,170,231,230,220,144,196,24,207,60,250,25,150,155,157,35,29,28,34,157,224,224,102,183,86,69,218,81,113,253,194,226,84,255,64,50,38,135],
[52,40,181,179,246,117,188,56,6,121,140,223,249,106,173,21,42,104,19,62,28,195,6,58,106,51,4,54,219,1,255,113,113,97,157,154,243,169,119,87,85,223,79,74,182,89,138,43,80,63,118,138],
[134,136,213,68,5,41,251,37,237,91,189,53,237,170,21,7,185,165,186,205,12,116,52,238,70,105,145,3,234,108,84,168,243,92,9,99,50,52,40,97,197,99,132,129,24,19,42,121,53,165,39,119],
[100,194,188,138,200,184,256,40,56,175,225,128,107,231,42,185,48,49,85,232,194,151,63,233,89,3,188,217,226,95,246,122,15,8,66,250,100,232,219,255,247,120,109,222,112,249,256,64,137,187,62,80],
[39,165,57,23,59,244,105,121,151,52,256,144,60,230,104,165,49,171,20,220,135,1,139,77,44,164,43,0,40,6,150,102,239,133,140,51,144,67,76,213,209,40,247,128,156,49,72,3,232,21,102,86],
[122,137,159,82,52,140,18,225,200,126,19,173,226,220,19,186,85,20,30,63,157,45,256,184,181,153,144,243,110,62,8,179,27,205,232,206,253,5,208,11,155,175,216,168,57,114,189,123,12,145,248,197],
[32,160,24,46,71,168,36,57,88,79,247,193,64,144,62,205,232,220,63,39,256,64,29,252,199,2,15,113,56,114,161,205,146,43,80,106,76,213,18,74,210,67,197,209,196,133,66,42,105,199,106,219],
[91,214,208,36,10,123,161,224,97,87,212,112,28,196,28,12,194,135,157,256,191,88,198,160,3,244,19,10,169,227,170,181,222,194,51,121,4,186,187,191,107,130,146,172,199,88,85,11,138,139,203,198],
[220,152,177,152,236,99,47,159,254,112,114,174,205,24,195,116,151,1,45,64,88,56,110,105,44,233,137,90,229,152,98,208,126,153,253,100,49,100,20,11,202,232,187,102,208,201,65,125,112,147,32,114],
[249,80,242,45,30,256,251,13,165,68,249,169,115,207,6,52,63,139,256,29,198,110,249,185,186,12,32,255,121,248,175,47,104,56,217,203,161,97,241,51,49,14,142,65,51,171,176,187,93,247,168,171],
[212,224,169,125,137,193,45,39,65,108,254,200,37,60,58,238,233,77,184,252,160,105,185,132,11,43,233,23,235,96,182,183,205,166,106,145,254,58,211,209,90,226,28,204,178,121,9,54,86,158,36,217],
[212,206,197,212,158,159,153,39,11,102,211,203,76,250,106,70,89,44,181,199,3,44,186,11,50,142,141,70,71,76,95,68,122,160,234,70,238,81,117,221,22,256,221,233,214,41,125,224,3,110,174,213],
[114,17,53,41,220,179,22,211,181,4,53,53,204,25,51,105,3,164,153,2,244,233,12,43,142,64,78,49,17,27,141,102,148,131,236,85,82,149,231,63,201,27,83,170,255,199,239,227,196,106,110,20],
[24,41,88,208,95,31,159,170,138,75,48,216,100,150,4,145,188,43,144,15,19,137,32,233,141,78,35,118,213,104,118,101,239,50,144,251,136,144,241,170,97,117,3,117,24,153,256,209,132,75,197,173],
[252,5,28,199,83,39,125,26,106,178,174,251,228,155,54,3,217,0,243,113,10,90,255,23,70,49,118,67,254,144,31,61,15,39,240,145,10,93,223,71,95,28,230,101,62,77,196,88,172,43,36,87],
[206,164,126,204,167,117,5,154,111,166,18,84,87,157,219,234,226,40,110,56,169,229,121,235,71,17,213,254,102,46,114,178,155,185,133,45,66,58,36,221,26,68,211,113,121,203,98,56,16,41,78,161],
[190,131,91,208,223,232,153,224,92,10,49,0,182,35,1,108,95,6,62,114,227,152,248,96,76,27,104,144,46,88,177,100,69,254,81,4,96,209,135,108,188,110,199,101,49,113,161,187,183,84,18,6],
[8,12,158,39,217,204,7,80,250,165,75,29,129,29,255,84,246,150,8,161,170,98,175,182,95,141,118,31,114,177,206,47,160,250,19,234,168,184,131,177,163,244,209,9,86,84,208,58,78,54,64,158],
[24,135,131,80,215,175,225,45,22,51,90,203,231,28,113,168,122,102,179,205,181,208,47,183,68,102,101,61,178,100,47,79,249,142,103,147,243,48,54,83,197,7,206,255,88,156,86,205,195,88,240,240],
[60,254,208,161,5,97,91,190,220,49,1,116,93,34,113,243,15,239,27,146,222,126,104,205,122,148,239,15,155,69,160,249,85,54,110,3,239,125,135,9,222,1,31,188,136,25,100,148,124,241,245,178],
[166,144,169,158,25,22,243,218,31,88,248,140,142,157,97,92,8,133,205,43,194,153,56,166,160,131,50,39,185,254,250,142,54,116,124,58,74,55,233,223,133,14,187,121,181,37,240,4,80,122,234,96],
[226,78,111,232,118,100,104,215,231,147,30,240,122,224,157,9,66,140,232,80,51,253,217,106,234,236,144,240,133,81,19,103,110,124,79,234,251,103,205,10,178,200,221,250,130,172,181,220,221,170,58,201],
[188,56,173,25,31,207,94,9,255,122,250,3,104,224,154,99,250,51,206,106,121,100,203,145,70,85,251,145,45,4,234,147,3,58,234,117,221,227,15,119,132,215,89,114,50,130,68,79,139,175,243,244],
[26,150,147,194,92,38,189,206,137,244,9,98,15,102,243,50,100,144,253,76,4,49,161,254,238,82,136,10,66,96,168,243,239,74,251,221,161,250,256,26,109,172,93,216,103,220,182,5,129,182,232,205],
[52,56,227,93,240,0,188,40,112,96,203,210,212,183,169,52,232,67,5,213,186,100,97,58,81,149,144,93,58,209,184,48,125,55,103,227,250,19,203,173,86,206,154,142,22,199,23,57,151,44,99,243],
[154,58,31,97,111,68,70,68,65,212,78,57,231,86,119,40,219,76,208,18,187,20,241,211,117,231,241,223,36,135,131,54,135,233,205,15,256,203,99,106,202,21,162,41,164,120,199,234,194,1,233,111],
[0,140,191,33,133,229,119,45,53,169,79,22,6,69,87,97,255,213,11,74,191,11,51,209,221,63,170,71,221,108,177,83,9,223,10,119,26,173,106,218,253,111,256,137,147,153,90,57,220,103,7,245],
[218,36,137,196,185,79,40,85,187,20,158,208,201,218,85,197,247,209,155,210,107,202,49,90,22,201,97,95,26,188,163,197,222,133,178,132,109,86,202,253,8,87,51,40,70,231,150,45,48,242,181,114],
[75,217,10,192,240,210,210,248,37,221,6,55,10,81,223,99,120,40,175,67,130,232,14,226,256,27,117,28,68,110,244,7,1,14,200,215,172,206,21,111,87,198,92,87,109,148,64,42,149,190,214,146],
[208,47,255,182,196,102,247,91,113,233,50,242,136,113,79,132,109,247,216,197,146,187,142,28,221,83,3,230,211,199,209,206,31,187,221,89,93,154,162,256,51,92,32,86,163,115,106,226,18,42,160,98],
[237,233,55,121,31,207,80,101,155,245,15,213,66,253,74,129,222,128,168,209,172,102,65,204,233,170,117,101,113,101,9,255,188,121,250,114,216,142,41,137,40,87,86,237,237,86,84,22,205,87,243,200],
[214,185,11,51,38,112,136,141,193,222,248,164,141,194,182,24,112,156,57,196,199,208,51,178,214,255,24,62,121,49,86,88,136,181,130,50,103,22,164,147,70,109,163,237,119,132,215,141,219,95,205,56],
[232,172,151,146,147,206,214,224,71,136,186,100,64,226,89,19,249,49,114,133,88,201,171,121,41,199,153,77,203,113,84,156,25,37,172,130,220,199,120,153,231,148,115,86,132,28,123,30,53,179,5,222],
[12,27,195,9,210,170,252,41,247,144,115,230,88,84,138,42,256,72,189,66,85,65,176,9,125,239,256,196,98,161,208,86,100,240,181,68,182,23,199,90,150,64,106,84,215,123,125,221,119,255,46,75],
[239,126,27,195,221,187,24,134,42,194,142,71,160,255,43,121,64,3,123,42,11,125,187,54,224,227,209,88,56,187,58,205,148,4,220,79,5,57,234,57,45,42,226,22,141,30,221,159,125,5,200,53],
[69,45,153,77,194,205,74,44,149,224,128,61,1,64,80,53,137,232,12,105,138,112,93,86,3,196,132,172,16,183,78,195,124,80,221,139,129,151,194,220,48,149,18,205,219,53,119,125,108,215,213,168],
[192,139,120,83,163,200,240,158,254,105,74,230,15,50,63,165,187,21,145,199,139,147,247,158,110,106,75,43,41,84,54,88,241,122,170,175,182,44,1,103,242,190,42,87,95,179,255,5,215,244,201,190],
[51,187,219,75,57,110,7,234,176,247,18,60,203,38,118,39,62,102,248,106,203,32,168,36,174,110,197,36,78,18,64,240,245,234,58,243,232,99,233,7,181,214,160,243,205,5,46,200,213,201,173,173],
[205,221,59,29,21,78,152,39,134,180,16,26,219,135,138,119,80,86,197,219,198,114,171,217,213,20,173,87,161,6,158,240,178,96,201,244,205,243,111,245,114,146,98,200,56,222,75,53,168,190,173,62],
]

c = [172,82,213,235,13,18,64,170,4,182,27,155,253,223,233,207,102,111,126,35,113,224,127,64,121,27,175,246,13,35,51,190,222,217,248,47,209,141,7,79,160,206,197,76,252,100,62,205,151,164,113,250]

n = len(c)

def modinv(a, m):
    """Extended Euclidean Algorithm for modular inverse"""
    g, x, _ = extended_gcd(a % m, m)
    if g != 1:
        return None
    return x % m

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x, y = extended_gcd(b % a, a)
    return g, y - (b // a) * x, x

def gauss_elim_mod(A, b, p):
    """Gaussian elimination over Z/pZ"""
    n = len(b)
    aug = [[A[i][j] % p for j in range(n)] + [b[i] % p] for i in range(n)]

    for col in range(n):
        pivot = None
        for row in range(col, n):
            if aug[row][col] % p != 0:
                pivot = row
                break
        if pivot is None:
            return None
        aug[col], aug[pivot] = aug[pivot], aug[col]

        inv = modinv(aug[col][col], p)
        for j in range(n + 1):
            aug[col][j] = (aug[col][j] * inv) % p

        for row in range(n):
            if row != col and aug[row][col] != 0:
                factor = aug[row][col]
                for j in range(n + 1):
                    aug[row][j] = (aug[row][j] - factor * aug[col][j]) % p

    return [aug[i][n] for i in range(n)]

M_mod = [[m % p for m in row] for row in M_rows]
x = gauss_elim_mod(M_mod, c, p)
flag = bytes(x)
print(flag.decode().strip())
# tjctf{m4tr1c3s_4r3_4ll_y0u_n33d}