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}
.
One thought on “VolgaCTF – XXY”