Description
no. no. that's Not TRUe. that's impossible! Download the encrypt.py and public.txt .
Setup
Download encrypt.py and public.txt.
Read encrypt.py to understand the NTRU encryption parameters (N, p, q) and key structure.
cat encrypt.py
cat public.txt
Solution
- Step 1Identify NTRU encryptionThe 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.
- 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.# 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
- Step 3Decrypt the ciphertextWith the recovered private polynomial f, decrypt the NTRU ciphertext: a = f*e mod q (centred), then m = a*f_p mod p.# 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))
Flag
picoCTF{ntru_lll_att4ck_...}
NTRU private keys (f, g) are short lattice vectors -- LLL on the NTRU lattice recovers them when parameters are small.