# [zer0pts CTF 2020] nibelung
###### tags: `zer0pts CTF` `crypto`

## Overview
The server gives us the randomly encrypted flag.

    # 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}

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)