# [zer0pts CTF 2020] nibelung ###### tags: `zer0pts CTF` `crypto` ## Overview The server gives us the randomly encrypted flag. ```python # Create flag F n = math.ceil(math.sqrt(len(flag))) F = bytes2gl(flag, n) p = F.p # Generate private key U = FiniteGeneralLinearGroup(n, p) while U.determinant() == 0: U.set_random() eF = encrypt(U, F) assert decrypt(U, eF) == F ``` `FiniteGeneralLinearGroup` is just a matrix class over a finite field. We can encrypt and decrypt arbitrary messages. Encryption is defined as below: $$Y = UXU^{-1}$$ Dectyption is defined as below: $$X = U^{-1}YU$$ You can immediately understand it works because $$DEC(ENC(X)) = U^{-1} (UXU^{-1})U = X$$ and vice versa. ## Solution So, you just need to put the encrypted flag to the decrypt function? No. We can set an element of the matrix to a value between between 0 and 255. $$E = UFU^{-1}$$ The easy (to come up with) way is making E sum of small matrices. Let $N_{i,j}$ denote a matrix whose $(i,j)$ elements are 0 for $i \neq j$ and 1 for $i = j$. Then, $E$ can be expressed like this: $$E = e_{1,1}N_{1,1} + e_{1,2}N_{1,2} + ... + e_{n,n}N_{n,n}$$ $DEC(E)$ is \begin{align} DEC(E) &= U^{-1}(e_{1,1}N_{1,1} + e_{1,2}N_{1,2} + ... + e_{n,n}N_{n,n})U \\ &= e_{1,1}DEC(N_{1,1}) + e_{1,2}DEC(N_{1,2}) + ... + e_{n,n}DEC(N_{n,n}) \end{align} ```python from ptrlib import * from fglg import FiniteGeneralLinearGroup as Matrix import re import base64 import math import pickle import sys def encrypt(data, p): sock.sendlineafter("> ", "1") sock.sendlineafter("Data: ", base64.b64encode(data)) return recv_gl(p) def decrypt(data, p): sock.sendlineafter("> ", "2") sock.sendlineafter("Data: ", base64.b64encode(data)) return recv_gl(p) def recv_gl(p = None): sock.recvline() mat = [] for i in range(n): mat.append([]) r = re.findall(b"\d+", sock.recvline()) for elm in r: mat[-1].append(int(elm)) if p is None: return mat X = Matrix(n, p) for i in range(n): for j in range(n): X.set_at((j, i), mat[i][j]) return X def split(x, base, result): if x < base: return x # x = base ^ q + r q = int(math.log(x) / math.log(base)) r = x - base ** q result.append(q) return split(r, base, result) n = 6 if __name__ == '__main__': sock = Socket("13.231.224.102", 3002) # Get eF and p mat = recv_gl() sock.recvuntil("p = ") p = int(sock.recvline()) eF = Matrix(n, p) for i in range(n): for j in range(n): eF.set_at((j, i), mat[i][j]) # Create table decN = [[None for j in range(n)] for i in range(n)] for i in range(n): for j in range(n): data = b'\x00' * (n*n) data = data[:i*n+j] + b'\x01' + data[i*n+j+1:] decN[i][j] = decrypt(data, p) F = Matrix(n, p) for i in range(n): for j in range(n): F += decN[i][j] * eF.get_at((j, i)) print(F) flag = '' for i in range(n): for j in range(n): flag += chr(F.get_at((j, i))) print(flag) ```