Onlude

def prepare(msg):
	A = zero_matrix(GF(p), 11, 11)
	for k in range(len(msg)):
		i, j = 5*k // 11, 5*k % 11
		A[i, j] = cross(msg[k])
	return A

def keygen():
	R = random_matrix(GF(p), 11, 11)
	while True:
		S = random_matrix(GF(p), 11, 11)
		if S.rank() == 11:
			_, L, U = S.LU()
			return R, L, U

def encrypt(A, key):
	R, L, U = key
	S = L * U
	X = A + R
	Y = S * X
	E = L.inverse() * Y
	return E

A = prepare(flag)
key = keygen()
R, L, U = key
S = L * U
E = encrypt(A, key)
print(f'E = \n{E}')
print(f'L * U * L = \n{L * U * L}')
print(f'L^(-1) * S^2 * L = \n{L.inverse() * S**2 * L}')
print(f'R^(-1) * S^8 = \n{R.inverse() * S**8}')

A contains our flag and we are given \(LUL,L^{-1}S^2L,R^{-1}S^8\) where \(S=LU\) is the LU-decomposition. The flag is also encrypted in a matrix \(E\) that would be trivial to decrypt once we know what \(L,U,R\) is.

\[\left(L^{-1}S^2L\right)\left(LUL\right)^{-1}=L^{-1}S^2LL^{-1}S^{-1}=L^{-1}S=U\] \[U^{-1}\left(L^{-1}S^2L\right)U=S^{-1}S^2S=S^2\] \[\left(S^2\right)^4\left(R^{-1}S^8\right)^{-1}=R\]

In order to solve for \(S\) and finally \(L\), we consider the eigendecomposition of \(S=P^{-1}DP\), then \(S^2=P^{-1}D^2P\). We can compute \(P,D^2\) easily and to get \(D\), we simply square root each term and brute force all possible combination of signs, \(2^8\) possibilities here. Eventually one of those would allow us to decrypt \(E\) and give us the flag.