Not TRUe picoCTF 2026 Solution

Description

1. Step 1Identify NTRU encryption

   Observation

   The title puns on NTRU, and the parameters in public.txt match the NTRU public-key format exactly. This is a textbook instance, so attack 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, the digital signature scheme NIST selected to become FN-DSA, uses NTRU lattices internally; its standard, FIPS 206, is still unpublished, while FIPS 203, 204 and 205 were finalised in August 2024. However, NTRU encryption itself was not selected by NIST - CRYSTALS-Kyber (ML-KEM / FIPS 203) won the key-encapsulation category instead.

2. Step 2Attack via lattice reduction (LLL)

   Observation

   N is tiny here, so the private polynomials f and g are short vectors in a low-dimensional lattice. LLL over the standard 2N-by-2N basis recovers them quickly.

   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 circulant alone does not encode the constraint that f*h minus g vanishes mod q. Without the q times identity block, the reduction is unenforced and LLL returns short vectors that mean nothing here. The doubled construction embeds that relation as an exact 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 often puts the short vector on the first row, and sometimes on the second, or negated throughout. Check each candidate against f*h mod q and confirm the result is also short. Take the first row on faith and you get a g that is not short at all, and decryption produces garbage.

   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 tiny, as it is here (N is 11, so the lattice is only 22 dimensions); real NTRU parameter sets defeat plain LLL long before N reaches the hundreds.

   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 3Decrypt the ciphertext

   Observation

   LLL returns a short candidate f satisfying f*h = g mod q, which confirms the private key. From there, ordinary NTRU decryption applies: centre-lift f*e mod q, then multiply by the inverse of f mod p.

   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{th4ts_s0_N0t_TRU3_...}

   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, coefficients near q stay large and positive instead of folding to small negatives, so the mod-p step produces wrong residues and garbled bytes. The noise term is guaranteed small in absolute value, not small and positive, which is exactly what centre-lifting accounts for.

   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 lives in a polynomial quotient ring, not the integers. The inverse you need is the ring inverse of f, modulo p and modulo the ring polynomial, found with the extended Euclidean algorithm there. An integer inverse gives a scalar that multiplies coefficient by coefficient and produces nonsense.

   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.