Challenge

from Crypto.Util.number import getPrime as getAnchor
import random
from secrets import flag


class AffineNoiseCipher:
    """
    ┌───────────────────────────────────────────────────────────────────┐
    │     A N C   :   A F F I N E   N O I S E   C I P H E R             │
    │───────────────────────────────────────────────────────────────────│
    │ "If truth must be hidden, drown it in the thunder of primes."     │
    │                                                                   │
    │ The cipher binds each bit to noise:                               │
    │      c = p*q  +  2*r  +  b                                        │
    │                                                                   │
    │ Where:                                                            │
    │   p — Anchor, whispered to be soul-bound to each user             │
    │   q — structural distortion                                       │
    │   r — deep noise harvested from entropy rituals                   │
    │   b — the message bit, the ghost in the machine                   │
    └───────────────────────────────────────────────────────────────────┘
    """

    def __init__(self, anchor):
        self.anchor = anchor

    def inscribe_noise(self, message: str):
        """
        A ritual engraving: truth carved into chaos.
        Echo Mirage claimed bits do not travel—they haunt.
        """

        bits = "".join(f"{ord(c):08b}" for c in message)
        ciphertext = []
        for bit in bits:
            b = int(bit)

            distortion = random.randint(self.anchor, self.anchor**2)
            entropy = random.randint(2**256, 2**512)

            c = self.anchor * distortion + 2 * entropy + b
            ciphertext.append(c)

        return ciphertext


print(">> Initiating Noise Inscription Ritual...")
print(">> Echo Mirage watches from the static.")


anchor = getAnchor(1024)
noise = AffineNoiseCipher(anchor)

with open("output.txt", "w") as file:
    file.write(str(noise.inscribe_noise(flag)))

Solution

Understanding the challenge

Every bit $b$ of the flag is encrypted separately as

$c = \text{anchor}\cdot\text{distortion} + 2\cdot\text{entropy} + b$

distortion and entropy are fresh random numbers for every bit, but the anchor is the same for all of them. To keep the notation short:

• $p$ = anchor: a secret 1024-bit prime, shared by all ciphertexts
• $q_i$ = distortion of the $i$-th ciphertext (between about $2^{1023}$ and $2^{2048}$)
• $r_i = 2\cdot\text{entropy}_i + b_i$ = the noise (at most 513 bits)

Every ciphertext then has the form

$c_i = p\cdot q_i + r_i, \qquad r_i < 2^{513} \ll p$

Each $c_i$ is a multiple of the secret $p$ plus a small error, and its size is up to $1024 + 2048 = 3072$ bits. This is the Approximate Common Divisor (ACD) problem: given several noisy multiples of the same hidden number, recover that number.

Recovering $p$ is enough to decrypt. Since $r_i < p$, we have $c_i \bmod p = r_i$, and $r_i = 2\cdot\text{entropy}_i + b_i$ has the same parity as $b_i$:

$b_i = (c_i \bmod p) \bmod 2$

If we knew $p$, we would be done. In a previous writeup we used LLL to solve linear systems, but there the hidden value was different. Here we have to find $p$ itself, so we need a different LLL construction.

Background: lattices and LLL

A lattice is the set of all integer combinations of some basis vectors. In 2D it is a regular grid of points. The same grid can be described by long, skinny basis vectors or by short, nearly perpendicular ones, and the second description is much more useful.

Finding a good basis is hard in general. LLL (Lenstra–Lenstra–Lovász) does it in polynomial time: it takes any basis and returns a reduced one whose vectors are short and nearly orthogonal. Its formal guarantee is weak (the first vector is within $2^{(d-1)/2}$ of the shortest possible), but in practice it works well when the lattice contains a vector that is much shorter than a random lattice of that size would have.

That gives the plan. We build a lattice that secretly contains an unusually short vector encoding $p$, and let LLL find it.

The key idea

Take two ciphertexts $c_0 = pq_0 + r_0$ and $c_1 = pq_1 + r_1$. If we knew $q_0$ and $q_1$:

$q_0\,c_1 - q_1\,c_0 = q_0(pq_1 + r_1) - q_1(pq_0 + r_0) = q_0 r_1 - q_1 r_0$

The huge term $p\,q_0 q_1$ cancels. The right-hand side is at most about $2^{2561}$, while a generic combination of $c_0, c_1$ would be around $2^{3072}$.

We don’t know the $q_i$, but we can ask LLL for integers $k_0, k_1, \dots$ with the same property. With $n+1$ ciphertexts, we want

$k_0\,c_i - k_i\,c_0 \quad\text{small for every } i$

Once $k_0$ is fixed, we can choose $k_i$ freely to subtract from $k_0 c_i$ the multiple of $c_0$ that brings it closest to zero. So this is the same as asking for a $k_0$ such that $k_0 c_i \bmod c_0$ is small for all $i$ at once. A random $k_0$ gives residues around $2^{3072}$, but $k_0 = q_0$ gives residues around $2^{2561}$. That planted short vector is what LLL finds.

Building the lattice

Use any ciphertext as $c_0$ (the script picks the largest) and $n$ others $c_1,\dots,c_n$. Let $\rho = 513$ be the bit-size bound of the noise (the code uses 512, which also works in practice). Then:

$$M = \begin{bmatrix} 2^{\rho+1} & c_{1} & c_{2} & \dots & c_{n}\\ 0 & -c_{0} & 0 &\dots & 0 \\ 0 & 0 & -c_{0} & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 &\dots &-c_{0}\\ \end{bmatrix}$$

A lattice vector is an integer combination $\sum_j k_j\cdot\text{row}_j$, which gives

$v = \big(2^{\rho+1}k_0,\; k_0c_1 - k_1c_0,\; \dots,\; k_0c_n - k_nc_0\big)$

The row of $-c_0$‘s is what lets us subtract multiples of $c_0$ from each $k_0 c_i$. The intended short vector uses $k_j = q_j$:

$v^\ast = \big(2^{\rho+1}q_0,\; q_0r_1 - q_1r_0,\; \dots,\; q_0r_n - q_nr_0\big)$

Why $2^{\rho+1}$ in the top-left corner? The entries $q_0 r_i - q_i r_0$ are about $q_0\cdot 2^{\rho}$. The first entry, $2^{\rho+1}q_0$, has the same size. The weight puts all coordinates on the same scale, so $v^\ast$ is a balanced vector of length roughly $2^{2562}$, while typical lattice vectors have entries around $2^{3072}$. With weight 1, the first coordinate would be negligible next to the others.

Recovering the anchor

LLL returns $v^\ast$ (up to sign) as the first row of the reduced basis, so $k_0 = |v_0| / 2^{\rho+1} = q_0$. Since $c_0 = pq_0 + r_0$ with $0 \le r_0 < q_0$:

$\left\lfloor \frac{c_0}{q_0}\right\rfloor = p + \left\lfloor \frac{r_0}{q_0}\right\rfloor = p$

The script then checks that the result is a 1024-bit prime before decrypting.

How many ciphertexts do we need?

For LLL to find $v^\ast$, it must be shorter than the typical shortest vector of a random lattice with the same determinant (the Gaussian heuristic). Let $\gamma \approx 3072$ be the bit-size of $c_0$ and $\eta = 1024$ the bit-size of $p$. The condition works out to roughly

$n > \frac{\gamma - \eta}{\eta - \rho} \approx \frac{2048}{511} \approx 4$

So about 5 extra ciphertexts is the minimum, and the script uses 20 to be safe.

Solve script

ct = []
with open("output.txt", "r") as file:
    ct = [int(c.strip()) for c in file.read().strip()[1:-1].split(",")]


M_rows = len(ct)

M_rows = min(M_rows,20) ## We probably just need 5 but who knows

print(M_rows)
rho = 512 #### maximum size of error vector

x_p = max(ct)
index_removed = ct.index(x_p)
ct.remove(x_p)
scale = 2^(rho+1) 

################################################################
#Filling the Matrix

rows = [[scale] + ct[:M_rows]]

for i in range(1,M_rows+1):
    vec = [0] * (M_rows + 1)
    vec[i] = - x_p
    rows.append(vec)

M = Matrix(ZZ,rows)

################################################################

RES = M.LLL()

k_0 = abs(RES[0][0] // scale )

anchor = x_p // k_0

################################################################
# This is because it's probable that the anchor value is multiplied by small factors that LLL couldn't reduce any better

for small_prime in prime_range(1000):
    while anchor % small_prime == 0:
        anchor //= small_prime
        
################################################################
      
print("Bit length:", anchor.bit_length())
print("Is Prime?:", is_prime(anchor))

ct.insert(index_removed,x_p)

flag = ""

for c in ct:
    flag += str( (c % anchor) % 2)
    
flag = long_to_bytes(int(flag,2))

print(f"[^] FLAG IS {flag} [^]") 

Flag

HTB{LLL_r3c0V3R_7H3_tRu7H_fR0m_7H3_n0153}