Not TRUe picoCTF 2026 Solution

Description

1. Step 1

   Identify NTRU encryption

   Observation

   I noticed the challenge title 'Not TRUe' is a phonetic pun on NTRU, and the public.txt parameters (N, p, q, h polynomial, ciphertext) exactly match the NTRU public-key format, which suggested this is a textbook NTRU instance and that the attack would exploit its lattice structure.

   The name 'Not TRUe' is a hint at NTRU, a lattice-based public-key cryptosystem. The public key h = p*g*f^(-1) mod q, where f and g are short polynomials. The ciphertext e = r*h + m mod q.

   Learn more

   NTRU (N-th degree Truncated polynomial Ring Units) is a lattice-based public-key cryptosystem invented in 1996. Unlike RSA or ECC, its security rests on the hardness of finding short vectors in lattices over polynomial rings rather than integer factoring or discrete logarithms.

   NTRU operates over the ring of polynomials modulo x^N - 1 with three integer parameters: N (degree), p (small modulus), and q (large modulus). The private key consists of two small-coefficient polynomials f and g. The public key is h = p·g·f⁻¹ mod q. Encryption of a message m uses a random blinding polynomial r: e = r·h + m mod q.

   The reason the title is a joke is that NTRU stands for "N-Th degree TRUncated polynomial Ring Units" - and this challenge shows that when parameters are small, NTRU is emphatically not secure. NTRU lattice structures underpin several post-quantum algorithms. FALCON (standardized as FIPS 206 / FN-DSA), a digital signature scheme, uses NTRU lattices internally. However, NTRU encryption itself was not selected by NIST - CRYSTALS-Kyber (ML-KEM / FIPS 203) won the key-encapsulation category instead.

2. Step 2

   Attack via lattice reduction (LLL)

   Observation

   I noticed the NTRU parameter N was small (only 11 in the example), which meant the private-key polynomials f and g are short vectors in a low-dimensional lattice and suggested that LLL reduction on the standard 2N-by-2N NTRU basis would efficiently recover them.

   Construct the NTRU lattice from the public key h. The private key (f, g) corresponds to a short vector in this lattice. Run LLL to find it.

   python

   # In SageMath:
   sage << 'EOF'
   # Load parameters from public.txt
   N  = YOUR_N
   p  = YOUR_P
   q  = YOUR_Q
   h  = YOUR_H_POLY_COEFFS  # list of N integers
   
   # Build the NTRU lattice (2N x 2N)
   R = ZZ
   M = Matrix(R, 2*N, 2*N)
   
   # Top-left: identity
   for i in range(N):
       M[i, i] = 1
   
   # Top-right: h convolution matrix
   h_vec = vector(ZZ, h)
   for i in range(N):
       for j in range(N):
           M[i, N + j] = h_vec[(j - i) % N]
   
   # Bottom-right: q * identity
   for i in range(N):
       M[N + i, N + i] = q
   
   L = M.LLL()
   
   # The first row of L should be (f, g) - check if short
   f_candidate = list(L[0][:N])
   print("Candidate f:", f_candidate)
   EOF

   Copied!

   What didn't work first

   Tried: Using LLL on only an N-by-N circulant matrix of h instead of the full 2N-by-2N NTRU lattice.

   The N-by-N circulant alone does not encode the lattice constraint that f*h - g = 0 mod q. Without the bottom-right q*I block, the modular reduction is not enforced and LLL finds short vectors that are meaningless in the NTRU sense. The 2N-by-2N construction is required so the integer relation f*h = g mod q is embedded as an exact (non-modular) equation inside the lattice.

   Tried: Taking row 0 of the LLL-reduced matrix as f without checking if it is actually short, and treating it as the private key regardless.

   LLL may return the short vector on row 0 but sometimes it appears on row 1 or with an overall sign flip (all coefficients negated). If f_candidate passes the check f*h mod q = g (also short) it is valid; if not, try -f_candidate or other early rows. Blindly using row 0 without validation produces a g that is not short, and decryption yields garbage bytes.

   Learn more

   The LLL algorithm (Lenstra-Lenstra-Lovász, 1982) is the most important practical lattice reduction algorithm in cryptanalysis. Given a lattice basis, LLL returns a "reduced" basis where the first vector is guaranteed to be at most 2^(N/2) times the length of the shortest lattice vector.

   The NTRU lattice is a 2N×2N matrix constructed from the public key h. The key insight is that the private key polynomials f and g are short - their coefficients are ±1 or 0. This means (f, g) concatenated is a short vector in the lattice. LLL is powerful enough to find this short vector when N is small (say, N ≤ 251).

   The construction places the N×N identity in the top-left block, the cyclic convolution matrix of h in the top-right, and q·I in the bottom-right. The cyclic convolution matrix sits in the top-right because polynomial multiplication in the ring Z[x]/(x^N - 1) is exactly equivalent to multiplying a coefficient vector by a circulant matrix: row i of the matrix is the coefficients of x^i · h mod (x^N - 1), which cyclically rotates h. So writing the lattice condition f·h ≡ g (mod q) in matrix form forces the cyclic structure into that block.

   • LLL runs in polynomial time but gives only an approximate shortest vector
   • For NTRU with large N (e.g. N=509 or N=677), LLL alone is insufficient and stronger algorithms (BKZ) are needed
   • This attack works here because the challenge uses artificially small N for CTF purposes
   • Related lattice attacks against RSA (e.g. Coppersmith) are covered in the RSA attacks for CTF post.
3. Step 3

   Decrypt the ciphertext

   Observation

   I noticed LLL returned a short candidate polynomial f that satisfied f*h = g mod q, confirming recovery of the private key, which meant I could apply the standard NTRU two-step decryption (centre-lift f*e mod q, then multiply by f_p mod p) to recover the plaintext message.

   With the recovered private polynomial f, decrypt the NTRU ciphertext: a = f*e mod q (centred), then m = a*f_p mod p.

   python

   # In SageMath:
   # a   = (f * e) % q  (centre-lift to [-q/2, q/2])
   # m   = a * f_p % p  where f_p = f^{-1} mod p
   print(bytes(m_coeffs))

   Copied!

   Expected output

   picoCTF{ntru_lll_att4ck_...}

   What didn't work first

   Tried: Skipping the centre-lift and taking coefficients of f*e mod q directly into the second step.

   Without centre-lifting, large coefficients near q-1 stay positive instead of folding to small negatives. The subsequent mod-p step then produces wrong residues and the message bytes come out garbled. Centre-lifting to the range (-q/2, q/2] is mandatory because the noise term p*r*g + f*m is only guaranteed to have small absolute values, not small positive values.

   Tried: Computing f_p as the modular inverse of f using the full integer inverse rather than the polynomial ring inverse mod (x^N - 1).

   NTRU arithmetic happens in the quotient ring Z[x]/(x^N - 1), not ordinary integers. f_p must be the polynomial ring inverse of f modulo p and modulo x^N - 1, computed via the extended Euclidean algorithm in that ring. Using an integer inverse gives a scalar that multiplies a_coeffs entry-by-entry incorrectly, producing nonsense output.

   Learn more

   NTRU decryption is a two-step process. First, compute a = f·e mod q and centre-lift the result: map each coefficient from [0,q) to (-q/2, q/2]. Concretely, with q=1024: a coefficient that comes out as 300 stays 300 (it's already below q/2 = 512), but a coefficient of 800 gets mapped to 800 - 1024 = -224. This works because f·e = f·(r·h+m) = f·r·p·g/f + f·m = p·r·g + f·m mod q, and since p·r·g + f·m has small coefficients (below q/2), the centre-lift recovers the exact polynomial without modular wrap-around.

   The second step computes m = a·f_p mod p, where f_p is the inverse of f modulo p. This strips away the randomisation term p·r·g (which vanishes mod p) and the factor of f, leaving the original message m. The message polynomial coefficients can then be directly read as bytes.

   This two-modulus design (q for the first step, p for the second) is the elegant mathematical core of NTRU. It separates the two "noise" terms (randomisation and private key multiplication) using different modular arithmetic, making decryption possible while keeping the scheme hard to break without the private key.

Flag

Submit the recovered plaintext bytes wrapped as picoCTF{...}; the "not TRUe" phrase in the description is just the title pun, not the literal flag format. NTRU private keys (f, g) are short lattice vectors and LLL on the NTRU lattice recovers them when parameters are small.