Read between the lines

This challenge was made by me for CrewCTF 2024 as a member of thehackerscrew. We are provided with the Python source code to encrypt the flag:

#!/usr/bin/env python3

from random import shuffle
from Crypto.Util.number import getPrime


with open('flag.txt', 'rb') as f:
    FLAG = f.read().strip()

assert len(FLAG) < 100

encoded_flag = []

for i, b in enumerate(FLAG):
    encoded_flag.extend([i + 0x1337] * b)

shuffle(encoded_flag)

e = 65537
p, q = getPrime(1024), getPrime(1024)
n = p * q
c = sum(pow(m, e, n) for m in encoded_flag) % n  

with open('output.txt', 'w') as f:
    f.write(f'{n = }\n{e = }\n{c = }\n')

We also have the output of the script:

n = 11570808501273498927205104472079357777144397783547577003261915477370622451850206651910891120280656785986131452685491947610185604965099812695724757402859475642728712507339243719470339385360489167163917896790337311025010411472770004154699635694228288241644459059047022175803135613130088955955784304814651652968093606122165353931816218399854348992145474578604378450397120697338449008564443654507099674564425806985914764451503302534957447420607432031160777343573246284259196721263134079273058943290282037058625166146116257062155250082518648908934265839606175181213963034023613042840174068936799861096078962793675747202733  
e = 65537
c = 7173375037180308812692773050925111800516611450262181376565814072240874778848184114081029784942289615261118103256642605595499455054072839201835361613983341298973366881719999836078559255521052298848572778824157749016705221745378832156499718149327219324078487796923208917482260462508048311400560933782289383624341257636666638574026084246212442527379161504510054689077339758167386002420794571246577662116285770044542212097174474572856621921237686119958817024794843805169504594110217925148205714768001753113572920225449523882995273988088672624172009740852821725803438069557080740459068347366098974487213070886509931010623

Source code analysis

First, the flag is encoded as the index of the flag character $i + \mathtt{0x1337}$ repeated $b_i$ times, where $b_i$ is the ASCII value of the $i$-th character:

encoded_flag = []

for i, b in enumerate(FLAG):
    encoded_flag.extend([i + 0x1337] * b)  

This encoded_flag is shuffled, but it is irrelevant as we will see later:

shuffle(encoded_flag)  

Then this is the ciphertext:

e = 65537
p, q = getPrime(1024), getPrime(1024)
n = p * q
c = sum(pow(m, e, n) for m in encoded_flag) % n  

Solution

So, in math terms we have:

$$ c = \sum_{m \in \mathtt{encoded\_flag}} m^e \mod{n} $$

Remember that each $m$ in encoded_flag is $i + \mathtt{0x1337}$ repeated $b_i$ times, so we have

$$ c = \sum_{i = 0}^{N - 1} b_i \cdot (i + \mathtt{0x1337})^e \mod{n} $$

Where $N$ is the flag length and $b_i$ is the $i$-th character of the flag. Notice that the shuffling is irrelevant because addition is commutative, so the order does not matter.

We can express $c$ as follows:

$$ c = b_0 (0 + \mathtt{0x1337})^e + b_1 (1 + \mathtt{0x1337})^e + \dots + b_{N - 1} (N - 1 + \mathtt{0x1337})^e \mod{n} $$

Lattice reduction

Observe that we can pre-compute $(i + \mathtt{0x1337})^e \mod{n}$, we want to find the coefficients $b_i$. For this, we can use a lattice technique such as LLL.

First of all, we will get rid of $\mod{n}$ to work over the integers, so for some $k \in \mathbb{Z}$ we have:

$$ b_0 (0 + \mathtt{0x1337})^e + b_1 (1 + \mathtt{0x1337})^e + \dots + b_{N - 1} (N - 1 + \mathtt{0x1337})^e + k \cdot n - c = 0 $$

Now, we will use the lattice spanned by the columns of

$$ M = \begin{pmatrix} (0 + \mathtt{0x1337})^e & (1 + \mathtt{0x1337})^e & \dots & (N - 1 + \mathtt{0x1337})^e & n & -c \\ 1 & 0 & \dots & 0 & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & 0 & 0 \\ 0 & 0 & \dots & 0 & 1 & 0 \\ 0 & 0 & \dots & 0 & 0 & R \\ \end{pmatrix} $$

Where $R$ is an arbitrarily large number such as $R = 2^{1024}$. The target vector is $(0, b_0, b_1, \dots, b_{N - 1}, k, R)$, which belongs to the lattice because:

$$ \begin{pmatrix} (0 + \mathtt{0x1337})^e & (1 + \mathtt{0x1337})^e & \dots & (N - 1 + \mathtt{0x1337})^e & n & -c \\ 1 & 0 & \dots & 0 & 0 & 0 \\ 0 & 1 & \dots & 0 & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & 0 & 0 \\ 0 & 0 & \dots & 0 & 1 & 0 \\ 0 & 0 & \dots & 0 & 0 & R \\ \end{pmatrix} \cdot \begin{pmatrix} b_0 \\ b_1 \\ \vdots \\ b_{N - 1} \\ k \\ 1 \\ \end{pmatrix} = \begin{pmatrix} 0 \\ b_0 \\ b_1 \\ \vdots \\ b_{N - 1} \\ k \\ R \\ \end{pmatrix} $$

And since the target vector is short (because all $0 \leqslant b_i \lt 256$), we can find it using LLL on the matrix $M$. We can use the $R$ to find the target vector on the reduced lattice matrix:

N = 100
cts = [pow(m + 0x1337, e, n) for m in range(N)]

R = 2 ** 1024
M = Matrix([
    [*cts, n, -c],
    *[[0] * i + [1] + [0] * (len(cts) - i + 1) for i in range(len(cts))],  
    [0] * len(cts) + [0, R]
])

L = M.T.LLL()
assert L[-1][0] == 0 and L[-1][-1] == R
res = L[-1][1:-1]

flag = [v for v in res if v != 0]
print(bytes(flag).decode())

Flag

With this, we will have the flag:

$ python3 solve.py
crew{D1d_y0u_3xp3cT_LLL_t0_b3_h1Dd3n_b3tw3en_th3_l1n3s???}  

The full script can be found in here: solve.py.