nc 3002
(This was all of the description)


From the organizer’s write-up(Link):

FiniteGeneralLinearGroup is just a matrix class over a finite field.
We can encrypt and decrypt arbitrary messages.
Encryption is defined as: Y = UXU^{-1}.
Decryption is defined as: X = U^{-1}YU.
The size of matrix (from the server) is 6×6.

How to solve

You cannot decrypt the flag directly, because it only accepts the matrix with values in the range 0~255.

Let’s think about (i, j)-th entry of the UXU^{-1}.

(UXU^{-1})_{i, j} = \sum_{i' = 1}^6 \sum_{j'=1}^6 U_{i, i'} X_{i', j'} U^{-1}_{j', j}

If you send the matrix X which has 1 in the (i, j)-th entry and 0 in the others, you can get U_{k, i} U^{-1}_{j, l} values for every (k, l).

Notice that (UXU^{-1})_{i, j} is a linear combination of X_{i', j'} and U_{i, i'} U^{-1}_{j', j}. Because we now know U_{i, i'} U^{-1}_{j', j} values, we can construct the linear system with 36 variables and 36 equations. We can solve the system with sage.

Here’s the extractor code for getting U_{i, i'} U^{-1}_{j', j} values.

from pwn import *
import base64

f = open('data', 'w')

r = remote('', 3002)
r.recvuntil('Encrypted Flag:\n')

eF = r.recvuntil('p = ')[:-5]
p = r.recvuntil('=')[:-1]

eF = eF.replace('\n', ',') + '\n'
f.write(p + eF)

for i in range(36):
    target = b'\x00' * i + b'\x01' + b'\x00' * (35 - i)
    target = base64.b64encode(target)
    v = r.recvuntil('=')[:-2]
    v = v.replace('\n', ',') + '\n'


Here’s the sage solver for the linear system.

from itertools import product as iproduct

# [i][j][i_][j_] = U[i][j] * U**-1[i_][j_]
UUm1_coef = [ [ [ [None for i in range(6)] for j in range(6) ] for k in range(6) ] for l in range(6) ]

with open('data', 'r') as f:
    p = int(f.readline()[:-1])
    eF = eval(f.readline()[:-1])

    for i, j in iproduct(range(6), repeat=2):
        mat = eval(f.readline()[:-1])
        for i_, j_ in iproduct(range(6), repeat=2):
            UUm1_coef[i_][i][j][j_] = mat[i_][j_]

mat = [ [0 for i in range(36)] for j in range(36) ]
vec = [ eF[i // 6][i % 6] for i in range(36) ]

for i, j, i_, j_ in iproduct(range(6), repeat=4):
    mat[i * 6 + j][i_ * 6 + j_] += UUm1_coef[i][i_][j_][j]
    mat[i * 6 + j][i_ * 6 + j_] %= p

R = IntegerModRing(p)
M = Matrix(R, mat)
b = vector(R, vec)
ans = M.solve_right(b)

flag = ''
for i in range(36):
    flag += chr(ans[i])

The flag is zer0pts{r1ng_h0m0m0rph1sm_1s_c00l}.