Not TRUe picoCTF 2026 Solution

Description

1. Step 1Identify NTRU encryption
   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 is actually standardized in NIST's post-quantum cryptography project as part of the FALCON and related families, making it practically relevant to understand.

2. Step 2Attack via lattice reduction (LLL)
   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!
   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 3Decrypt the ciphertext
   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!
   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.