Real Eisenstein

This challenge marks a really important point in my CryptoHack journey. I have conquered a lattice related challenge knowing what is going on. Lattices have been something I have zero idea about (and I would looove to stay away from), but thanks to the incredible help and explanation from Kel Zin, I can say I understand 0.01% of how lattices work now.

If we write the problem in mathematical terms, we have the following:

where $p_i$$p_i$ is the $i^{th}$$i^{th}$ prime, and $a_i$$a_i$ is the ASCII integer representation of the character.

A "lattice" like perspective on this, that is, there exists a linear combination of the values $\lfloor 2^{256}\sqrt{p_i}$$\lfloor 2^{256} \sqrt{p_i}$ very close to the given ciphertext $ct$$ct$. This is somewhat like a Shortest Vector Problem: there exists some $a_i$$a_i$ such that

is very small. We are interested in the values of $a_i$$a_i$ (which ideally should contain the ASCII integer value of the flag character), hence we can construct this basic matrix:

The ideas of the $1$$1$ in the matrix is to keep track of the $a_i$$a_i$. The vectors in the lattice is the rows, and you can observe that some linear combinations of the rows, using the coefficients of $a_1,a_2,...,a_n$$a_1, a_2, ..., a_n$ will lead to some shortest vector in the lattice space. The coefficients of the linear combinations should be relatively small, hence a "short" vector should exist.

This is time for the lattice magic (or more like Sage magic). Sagemath has implementations of two algorithms, LLL and BKZ which are both great in finding such short vectors. The content of the flag should be the first line (which is also the shortest vector in the new basis of the lattice field).

Sage Implementation:

xxxxxxxxxx
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103]
ct = 1350995397927355657956786955603012410260017344805998076702828160316695004588429433

mat = [[0 for i in range(len(PRIMES) + 1)] for i in range(len(PRIMES) + 1)]
for i in range(len(PRIMES)):
    mat[i][i] = 1 
    mat[i][-1] = round(2 ^ 256 * sqrt(PRIMES[i]))

mat[len(PRIMES)][len(PRIMES)] = ct 
mat = Matrix(ZZ, mat)
row = mat.LLL()[0] # first row

flag = ""
# Can print out first row, the result is the negative values in the first row
for char in row: 
    if char < 0:
        flag += chr(-char)

print(flag)