The challenge is presented with the following description:

I remember some of the AI engineers saying this was a very unusual cryptosystem. It was used to encrypt and transmit information of the enormous importance. Moreover, it seems there’s no need to share a key before the transmission.

We’ve found some kind of a key file, a ciphertext and the enciphering script itself. Is it possible to decrypt the data?

The key file consisted of a file with signed 180(?)-bit integers and a ciphertext.

#!/usr/bin/env sage
from sage.all import *


hRR = RealField(10000)


def read_mat(name):
    with open(name, 'r') as f:
        data = f.read()
        data = [map(int, s.split(' '))  for s in data.split('\n')]
        n = len(data)
        M = MatrixSpace(ZZ, n, n)(data)
        return M

def read_ciphertext(ciphertext_file_name):
    with open(ciphertext_file_name, 'r') as f:
        data = f.read()
        e = vector(map(int, data.split(' ')))
        return e

def encrypt(plain_block, W, delta=151):
    n = W.ncols()
    m = vector([ord(ch)  for ch in plain_block])
    r = random_vector(ZZ, n, x=-delta+1, y=delta)
    e = m * W + r
    return e

def decrypt(e, V, W):
    n = V.ncols()
    VV = MatrixSpace(hRR, n, n)(V)
    t = vector([int(round(i))  for i in VV.solve_left(e)])
    v = t * V
    m = W.solve_left(v)
    ciphertext_block = ''.join([chr(i)  for i in m])
    return ciphertext_block

The signed integers forms a matrix , which in this case is the public key. The ciphertext is formed by computing , were is the message and is a random error vector with entries in the range . Now, we could use the function using only the public key. The problem is that it is very ill-conditioned and the basic vectors are not orthogonal and would not produce a correct result.

So, what can we do to remedy the problem? We can use the LLL algorithm, which tranforms the matrix into a very nicely conditioned matrix using no additional information what-so-ever. This is actually the whole key to the attack. Using Sage, we compute the LLL-reduced form, and can then easily obtain the flag by feeding the function with the known and the estimate . Doing so, outputs the flag VolgaCTF{GGH_uses_Babai_and_hates_LLL}.