Constructing and attacking NTRU public key cryptosystem¶
In contrast to cryptosystems such as RSA, Diffie-Hellman or ECC which are based on Group operations, the NTRU cryptosystem is a ring-based cryptosystem, specifically convolution polynomial rings, but it's underlying hard mathematical problem can also be interpreted as SVP or CVP in a lattice.
NTRUEncrypt¶
The NTRU public key cryptosystem, parameterized by integers $N$, $p$, $q$ and $d$ such that $$ \begin{aligned} \text{1.}&\; N \in \mathbb{P} \; \text{is prime} \newline \text{2.}&\; \gcd(N,q) = \gcd(p,q) = 1 \newline \text{3.}&\; d > 0 \newline \text{4.}&\; q > (6d + 1)p \end{aligned} $$ is based on operations in three polynomial rings $R, R_p, R_q$ $$ R = \frac{\mathbb{Z}[X]}{X^{N} - 1}, \quad R_p = \frac{\mathbb{Z}_p[X]}{X^{N} - 1}, \quad R_q = \frac{\mathbb{Z}_q[X]}{X^{N} - 1} $$ and ternary polynomials defined for any positive integers $d_1$ and $d_2$ as $$ \mathcal{T}(d_1, d_2) = \left\{ a(x) \in R \; \middle| \; \begin{array}{l} a(x) \; \text{has} \; d_1 \; \text{coefficients equal to 1,}\newline a(x) \; \text{has} \; d_2 \; \text{coefficients equal to -1,}\newline a(x) \; \text{has all other coefficients equal to 0} \end{array} \right\} $$
Key creation¶
Let $(N, p, q, d)$ be publicly known parameters of the NTRU cryptosystem, chosen by some trusted authority.
Private key consists of two randomly chosen polynomials
$$
f(x) \in \mathcal{T}(d + 1, d) \qquad \text{and} \qquad g(x) \in \mathcal{T}(d, d)
$$
To set up public key we first need to calculate inverses
$$
F_q(x) = f(x)^{-1} \; \text{in} \; R_q \qquad \text{and} \qquad F_p = f(x)^{-1} \; \text{in} \; R_p
$$
The $f(x)$ must be chosen such that inverses $F_q(x)$ and $F_p(x)$ exists.
The polynomial $h(x)$ defined as $$ h(x) = F_q(x) \cdot g(x) \; \text{in} \; R_q $$ will be a public key
Private key: $(f(x), g(x))$
Public key: $h(x)$
import numpy as np
from lbpqc.primitives.polynomial.polyqring import PolyQuotientRing, from_ideal
from lbpqc.primitives.lattice import fullrank, reductions
from lbpqc.primitives.integer.integer_ring import center_mod_reduce
# Let's choose NTRU parameters and private key (f,g)
N, p, q, d = 7, 3, 41, 2
Rq = from_ideal("-", N, q)#(X^N + 1)
Rp = from_ideal("-", N, p)#(X^N + 1)
f = np.array([-1, 0, 1, 1, -1, 0, 1], dtype=int) #f(x) = x^6 - x^4 + x^3 + x^2 - 1
g = np.array([0, -1, -1, 0, 1, 0, 1], dtype=int) #g(x) = x^6 + x^4 - x^2 - x
# Now lets compute inverses Fq and Fp
Fq = Rq.inv(f)
Fp = Rp.inv(f)
# Lets check if the inverses are correct
print("f^-1 in Rq:")
print(Fq)
print("f * f^-1:", Rq.mul(f, Fq))
print()
print("f^-1 in Rp:")
print(Fp)
print("f * f^-1:", Rp.mul(f, Fp))
print()
# Now let's calculate public key h
h = Rq.mul(Fq, g)
print("h = Fq * g:")
print(h)
print()
print("Private key: (f(x), Fp(x))")
print("f(x) = ", f)
print("g(x) = ", g)
print()
print("Public key: h(x)")
print("h(x) = ", h)
sk = (f, Fp)
pk = h
f^-1 in Rq: [37 2 40 21 31 26 8] f * f^-1: [1] f^-1 in Rp: [1 1 1 1 0 2 1] f * f^-1: [1] h = Fq * g: [30 26 8 38 2 40 20] Private key: (f(x), Fp(x)) f(x) = [-1 0 1 1 -1 0 1] g(x) = [ 0 -1 -1 0 1 0 1] Public key: h(x) h(x) = [30 26 8 38 2 40 20]
Encryption¶
Plaintext $m$ has a form of polynomial $m(x) \in R$ whose coefficients satisfy $ \; -\frac{1}{2}p < m_i \leq \frac{1}{2}p $.
In order to encrypt $m$ we also need a random polynomial $r(x) \in \mathcal{T}(d,d)$ then
$$
e(x) \equiv p h(x) \cdot r(x) + m(x) \quad \mod q
$$
is a ciphertext and $e(x) \in R_q$
# plaintext
m = np.array([ 1,-1, 1, 1, 0,-1], dtype=int)
print("plaintext m(x) =", m)
# random element
r = np.array([-1, 1, 0, 0, 0,-1, 1], dtype=int)
print("random element r(x) =", r)
print()
# ciphertext
e = Rq.add(p * Rq.mul(r, pk), m)
print("ciphertext e(x) =", e)
plaintext m(x) = [ 1 -1 1 1 0 -1] random element r(x) = [-1 1 0 0 0 -1 1] ciphertext e(x) = [25 3 40 2 4 19 31]
Decryption¶
To decrypt ciphertext $e(x)$ we first need to compute $$ a(x) \equiv f(x) \cdot e(x) \quad \mod q $$ then $$ b(x) \equiv F_p(x) \cdot \text{center\_lift} (a(x)) \quad \mod p $$ is equal to the plaintext $m(x)$
a = center_mod_reduce(Rq.mul(sk[0], e), q)
d = center_mod_reduce(Rp.mul(sk[1], a), p)
print("Decrypted message d:")
print(d)
print("Original message m:")
print(m)
Decrypted message d: [ 1 -1 1 1 0 -1] Original message m: [ 1 -1 1 1 0 -1]
NTRU as a lattice¶
Given NTRU cryptosystem with parameters $(N,p,q,d)$ we are going to identify each pair of polynomials $$ a(x) = a_0 + \ldots + a_{N-1}x^{N-1} \qquad \text{and} \qquad b(x) = b_0 + \ldots + b_{N-1}x^{N-1} $$ in $R$ with $2N$-dimensional vector $$ (a,b) = (a_0, \ldots, a_{N-1}, b_0, \ldots, b_{N-1}) \in \mathbb{Z}^{2N} $$
from lbpqc.primitives.polynomial.poly import monomial, pad
from lbpqc.primitives.lattice.reductions import LLL
L11 = np.identity(N, int)
L12 = np.array([pad(Rq.mul(monomial(1, i), h), N - 1) for i in range(N)])
L21 = np.zeros((N,N), int)
L22 = q * np.identity(N, int)
NTRU_B = np.block([[L11, L12], [L21, L22]])
print("NTRU as lattice:")
print(NTRU_B)
NTRU as lattice: [[ 1 0 0 0 0 0 0 30 26 8 38 2 40 20] [ 0 1 0 0 0 0 0 20 30 26 8 38 2 40] [ 0 0 1 0 0 0 0 40 20 30 26 8 38 2] [ 0 0 0 1 0 0 0 2 40 20 30 26 8 38] [ 0 0 0 0 1 0 0 38 2 40 20 30 26 8] [ 0 0 0 0 0 1 0 8 38 2 40 20 30 26] [ 0 0 0 0 0 0 1 26 8 38 2 40 20 30] [ 0 0 0 0 0 0 0 41 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 41 0 0 0 0 0] [ 0 0 0 0 0 0 0 0 0 41 0 0 0 0] [ 0 0 0 0 0 0 0 0 0 0 41 0 0 0] [ 0 0 0 0 0 0 0 0 0 0 0 41 0 0] [ 0 0 0 0 0 0 0 0 0 0 0 0 41 0] [ 0 0 0 0 0 0 0 0 0 0 0 0 0 41]]
LLL_B = LLL(NTRU_B).astype(int)
w = LLL_B[0]
print("Short vector from LLL reduced basis:")
print(w)
f_prim = w[:N]
g_prim = w[N:]
f_prim_inv_q = Rq.inv(f_prim)
f_prim_inv_p = Rp.inv(f_prim)
print("f'^-1 in Rq:")
print(f_prim_inv_q)
print("f'^-1 * f':", Rq.mul(f_prim_inv_q, f_prim))
print()
print("f'^-1 in Rp:")
print(f_prim_inv_p)
print("f'^-1 * f':", Rp.mul(f_prim_inv_p, f_prim))
print()
Short vector from LLL reduced basis: [ 1 0 -1 1 0 -1 -1 -1 0 -1 0 1 1 0] f'^-1 in Rq: [20 10 15 33 4 39 1] f'^-1 * f': [1] f'^-1 in Rp: [2 0 1 2 2 2 2] f'^-1 * f': [1]
a_prim = center_mod_reduce(Rq.mul(f_prim, e), q)
d_prim = center_mod_reduce(Rp.mul(f_prim_inv_p, a_prim), p)
print("Decrypted message d:")
print(d_prim)
print("Original message m:")
print(m)
Decrypted message d: [ 1 -1 1 1 0 -1] Original message m: [ 1 -1 1 1 0 -1]