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

.

### Like this:

Like Loading...

## One thought on “VolgaCTF – XXY”