# VolgaCTF – XXY

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)

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

with open(ciphertext_file_name, 'r') as f:
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 $38 \times 38$ matrix $\mathbf{W}$, which in this case is the public key. The ciphertext $\mathbf{e}$ is formed by computing $\mathbf{m}\mathbf{W} + \mathbf{e}$, were $\mathbf{m}$ is the message and $\mathbf{r}$ is a random error vector with entries in the range $[-\delta+1,\delta-1]$. Now, we could use the $\textsf{decrypt}$ 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, $\mathbf{V}'$ and can then easily obtain the flag by feeding the $\textsf{decrypt}$ function with the known $\mathbf{e}, \mathbf{W}$ and the estimate $\mathbf V'$. Doing so, outputs the flag VolgaCTF{GGH_uses_Babai_and_hates_LLL}.