This is a bit weird challenge in my opinion. It constructs some exotic matrices, mix them up a little bit and expects us to recover the flag from the output. This is the code:

q, v, m = 256, 40, 14
_F = GF(q)

def makeup(M, n):
	for i in range(n):
		for j in range(i, n):
			M[i, j] += M[j, i]
			M[j, i] = 0
		return M

def mitramap():
	_M = []
	for s in range(m):
		M = zero_matrix(_F, v + m, v + m)
		for i in range(0, v):
			M[i, (i + s + 1) % v] = _F.random_element()
			M[i, (i + s) % m + v] = _F.random_element()
		M = makeup(M, v + m)
		_M.append(M)
	return _M

def n2F(n):
	x = _F.gen()
	e = sum(((n >> _) & 1) * x ** _ for _ in range(8))
	return e

def F2n(e):
	x = _F.gen()
	n = 0
	for _ in range(8):
		n |= (int(e.coefficient(x, _)) << _)
	return n

def embed_secret(msg, v, m):
	M = random_matrix(_F, v, m)
	for _ in range(v):
		M[_, 0] = n2F(msg[_])
	return M

def maketrig():
	return block_matrix([[identity_matrix(_F, v), embed_secret(flag, v, m)], [zero_matrix(_F, m, v), identity_matrix(_F, m)]])

def makepub(F, S):
	S = S.submatrix(0, v, v, m)
	Z = zero_matrix(_F, m, v)
	return [
		block_matrix([
			[G := M.submatrix(0, 0, v, v), (G + G.transpose()) * S + (H := M.submatrix(0, v, v, m))],
			[Z, makeup(S.transpose() * G * S + S.transpose() * H, m)]
		])
		for M in F[:m]
	]

F, S = mitramap(), maketrig()
P = makepub(F, S)

print(f'{dumps(F) = }')
print(f'{dumps(P) = }')

Let’s forget about the specifics of the mitramap and makeup functions, as I won’t be using them in this solution. Note that the maketrig function creates a random matrix whose first column is the flag. Our goal is to recover this matrix $S$.

The challenge gives us the generated array F and the result of makepub(F, S). Let’s look at that function.

First, it does S = S.submatrix(0, v, v, m). This is just the interesting piece of the matrix generated by maketrig, which is a $14 \times 40$ matrix, whose first column is the flag. Then, it iterates over the array $F$, and generates an array of matrices from it and $S$.

Focusing on the first element of this resulting array, we can look into its top-right block. It is the result of $(G + G^T)S + H$, where G = M.submatrix(0, 0, v, v) (which we know) and H = M.submatrix(0, v, v, m) (which we know). We also know the output of this operation (because we have the output of the function). Therefore, we only need to take the top-right block of the output (let’s call that $R$) and perform this operation:

$$S = (G + G^T)^{-1}(R - H)$$

Then, we extract the flag by getting the values of the first column:

from sage.all import *

lines = open("output.txt", "rb").readlines()
tmp = []
for line in lines:
    line = b'='.join(line.split(b"=")[1:]).strip()[2:-1]
    tmp.append(line.decode("unicode_escape").encode("latin1"))
F, P = [loads(t) for t in tmp]

v, m = 40, 14

flag = ""
M = F[0]
H = M.submatrix(0, v, v, m)
G = M.submatrix(0, 0, v, v)
H = M.submatrix(0, v, v, m)
R = P[0].submatrix(0, v, v, m)
for i in range(v):
    flag += chr(((G + G.transpose()).inverse() * (R - H))[i][0].to_integer())

print(flag)

Flag: CCTF{Un8reAk4Bl3_MQ-Sign_crYpT0_ma9iC!!}.