LE CRYPTOSYSTÈME NTRU

Abderrahmane Nitaj

Janvier 2003

Abstract. NTRU est nouveau cryptosystème à clé publique dont la sécurité n’est basée ni sur difficulté de la factorisation des entiers, ni sur celle de la résolution du logarithme discret mais sur la difficulté de trouver un vecteur court dans un réseau de grande dimension. Dans ce rapport, on présente ce cryptosystème et les différentes attaques pour le casser.

Contents

1. Introduction

2. Les produits de convolution

3. Description de NTRU 3.1. Le problème 3.2. Ali fabrique sa clé publique 3.3. Brigitte envoie un message 3.4. Ali décrypte le message de Brigitte 3.5. Explications 3.6 Conditions pour le décryptage

4. Choix des paramètres par NTRU

5. Les attaques 5.1. Attaques forcées contre la clé 5.2. Attaques forcées contre le message 5.3. Attaques forcées avec rencontre au milieu contre la clé 5.4. Attaques forcées avec rencontre au milieu contre le mes-

sage 5.5. Attaques en cas de multiples transmissions

6. Attaques basées sur les réseaux 6.1. Attaques contre la clé publique 6.2. Attaques contre le message

7. La signature NSS 7.1. La signature 7.2. Attaques contres la signature

8. Conclusion-Challenges

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 94A60, 11T06.

Key words and phrases. Cryptosystèmes, NTRU, Réseaux.

1. Introduction.

J. Hoffstein, J. Pipher et J.H. Silverman [3] de l’université de Brown (USA) ont proposé en 1996 un cryptosystème qu’ils ont appelé NTRU, mais ce n’est qu’en 2000 qu’ils ont déposé leur découverte et ont reçu des investissements (38 millions de $ de la part de Sony, de TI, Greylock,....). Ils ont choisi le nom NTRU en hommage a leur groupe de travail “Number Theory Research Unit”, mais comme préfère le dire Silverman, cela rime avec “Number Theorists R Us”.

Ce cryptosystème permet de crypter, décrypter, authentifier, signer et engendrer des clés.

Chaque système utilisé en cryptographie est basé sur la difficulté de résoudre un problème. Ainsi, RSA [8] est lié à la factorisation des nombres, et El Gamal [2] est lié au problème du logarithme discret. Le nouveau cryptosystème NTRU est basé sur la difficulté de trouver le plus court vecteur d’un réseau de grande dimension.

Les cryptosystèmes basés sur des variations du problème du Sac à Dos ont été cassés à l’aide des techniques de réduction des réseaux. Contrairement à ces cryptosystèmes qui “craignent la réduction des réseaux”, le nouveau système de cryptographie NTRU est basé sur l’idée que la détermination d’un vecteur très courts dans un réseau n’est pas facile.

Les opérations nécessaires pour la fabrication d’un cryptosystème basé sur NTRU sont beaucoup plus simples que celles utilisées pour d’autres systèmes tels RSA, El Gamal et ECC. Ces derniers utilisent en fait l’exponentiation, qui est très couteuse en opérations, alors que NTRU n’en nécessite aucune.

2. Les produits de convolution.

Soit N un entier. On pose R = ℤ[X]/(X^{N} − 1). Soient F et G deux éléments de R définis par :

F (X) = ∑_{i=0}^{N−1} F_{i}X^{i}, G(X) = ∑_{i=0}^{N−1} G_{i}X^{i}.

Soient α et β deux entiers. La somme de αF et βG est défini par

αF + βG = ∑_{i=0}^{N−1}(αF_{i} + βG_{i})X^{i}.

Le produit de F et G dans R est défini par

F ∗ G = H = ∑_{i=0}^{N−1} H_{i}X^{i}

avec

H_{i} = ∑_{k=0}^{i} F_{k}G_{i−k} + ∑_{k=i+1}^{N−1} F_{k}G_{N+i−k} = ∑_{k+l≡i (mod N)} F_{k}G_{l}.

Ceci peut s’écrire aussi :

( H_{0} ; H_{1} ; ⋮ ; H_{N−1} ) = ( \begin{matrix}F_{0} & F_{1} & ⋯ & F_{N−1} \\ F_{1} & F_{2} & ⋯ & F_{0} \\ ⋮ & ⋮ & ... & ⋮ \\ F_{N−1} & F_{0} & ⋯ & F_{N−2} \end{matrix} ) ( G_{0} ; G_{N−1} ; ⋮ ; G_{1} )

Le produit de convolution ∗ vérifie, en particulier, pour des polynômes F, G et U et des entiers α et β :

F ∗ G = G ∗ F,
F ∗ (G ∗ U) = (F ∗ G) ∗ U,
F ∗ (αG + βU) = αF ∗ G + βF ∗ U,

Si p est un entier, on convient de poser F (mod p) avec la convention

F (mod p) = ∑_{i=0}^{N−1}(F_{i} (mod p))X^{i}.

Le calcul direct de F ∗G a une complexité en O(N^{2}). Cependant, la transformée de Fourier rapide (FFT) requiert uniquement une complexité en O(N log N) lorsque N est une puissance de 2.

3. Description de NTRU.

3.1. Le problème.

Brigitte veut envoyer un message m sous forme crypté e à Ali.

Pour cela, Brigitte doit utiliser les paramètres de NTRU et la clé publique de Ali. Ali et Brigitte vont utiliser le système NTRU. Ils doivent utiliser les paramètres de NTRU composés de trois nombres entiers N, p et q, non nécessairement premiers, avec (p, q) = 1 et q est très grand par rapport à p et quatre sous-ensembles 𝕃_{m}, 𝕃_{f}, 𝕃_{g} et 𝕃_{ϕ} de ℤ[X]/(X^{N} − 1).

3.2. Ali fabrique sa clé publique.

Ali choisit deux polynômes secrets f ∈ 𝕃_{f} et g ∈ 𝕃_{g} et calcule les inverses f_{p}^{−1} et f_{q}^{−1} de f respectivement dans ℤ_{p}[X]/(X^{N} − 1) et ℤ_{q}[X]/(X^{N} − 1). Ainsi f_{q}^{−1} et f_{p}^{−1} sont deux polynômes qui vérifient :

f_{p}^{−1} ∗ f ≡ 1 (mod p)
f_{q}^{−1} ∗ f ≡ 1 (mod q).

Ali calcule ensuite le polynôme :

h ≡ f_{q}^{−1} ∗ g (mod q).

La clé publique d’Ali est alors h. Ses clés privées sont f et g ( et donc aussi f_{p}^{−1} et f_{q}^{−1}).

3.3. Brigitte envoie un message.

Brigitte prend un message clair et le transforme de tel sorte que m ∈ 𝕃_{m} et choisit un polynôme ϕ ∈ 𝕃_{ϕ} et transforme le message clair m en un message crypté e :

e ≡ pϕ ∗ h + m (mod q).

Alors Brigitte envoie le message e à Ali et détruit son polynôme ϕ.

3.4. Ali décrypte le message de Brigitte.

En recevant le message secret e de Brigitte, Ali utilise sa clé secrète f et calcule dans ℤ[X]/(X^{N} − 1) :

a ≡ f ∗ e (mod q),

en s’arrageant pour que les coefficients de a soient dans l’intervalle [−q/2, q/2]. S’ils sont tous dans ] − q/2, q/2[ alors il calcule :

b = f_{p}^{−1} ∗ a.

en s’arrageant pour que les coefficients de b soient dans l’intervalle [−p/2, p/2]. Alors Ali sait maintenant que le message clair de Brigitte est b = m.

3.5. Explications.

Si les coefficients de a sont tous dans ] − q/2, q/2[, alors il vérifie :

a ≡ f ∗ e ≡ f ∗ (pϕ ∗ h + m) (mod q)
≡ pϕ ∗ f ∗ h + f ∗ m (mod q)
≡ pϕ ∗ f ∗ (f_{q}^{−1} ∗ g) + f ∗ m (mod q)
≡ pϕ ∗ g + f ∗ m (mod q).

De même, le polynôme b vérifie :

b ≡ f_{p}^{−1} ∗ a ≡ f_{p}^{−1} ∗ (pϕ ∗ g + f ∗ m) (mod p)
≡ f_{p}^{−1} ∗ f ∗ m (mod p)
≡ m (mod p).

3.6 Conditions pour le décryptage.

Le décryptage peut ne pas fonctionner dans certains cas. Ceci est du au fait qu’une équivalence modulo q peut être fausse modulo p et inversement. Un exemple numérique est :

1 ≡ 17 (mod 16), mais 1 ≢ 17 (mod 5).

Soient u et v deux entiers. Si u ≡ v (mod q) et u ≡ v (mod p), alors u − v ≡ 0 (mod q) et u − v ≡ 0 (mod p). Comme (p, q) = 1, alors u − v ≡ 0 (mod pq). Ainsi Pour que l’équivalence u ≡ v (mod q) se transforme en u ≡ v (mod p), il faut que u − v soit un multiple de p et un multiple de q.

Supposons maintenant que u et v sont dans l’intervalle [−q/2, q/2] et que u ≡ v (mod q). Alors la valeur exacte de u − v est :

u − v = \{ \begin{matrix}−q & si u = −v = −\frac{q}{2}, \\ q & si u = −v = \frac{q}{2}, \\ 0 & sinon, \end{matrix}

Ainsi, pour que u ≡ v (mod p), il faut que u et −v ne soient pas égaux à ±q/2. Dans le procéssus de décryptage, on a

a ≡ pϕ ∗ g + f ∗ m (mod q).

Pour que cette équivalence se transmette modulo p, il faut que tous les coefficients de a coincident avec les coefficients dans le calcul exact (dans ℤ[X]/(X^{N} − 1)) de a_{0} = pϕ ∗ g + f ∗ m, en excluant ±q/2. Alors dans ce cas, b est le message clair m.

Comme ni Ali ni Brigitte ne connaissent f, g et ϕ en même temps, alors le polynôme a_{0} ne peut être explicitement calculé. On peut cependant donner condition pour que le décryptage aboutisse.

On pose

a_{0} = ∑_{i=0}^{N−1} α_{i}X^{i},

et

ā_{0} = \frac{1}{N} ∑_{i=0}^{N−1} α_{i}, |a_{0}|_{∞} = max_{i} α_{i} − min_{i} α_{i}, |a_{0}|_{2′} = ( ∑_{i=0}^{N−1} α_{i}^{2} − Nā_{0}^{2})^{1/2} .

Pour le décryptage donne le message m, il faut |a_{0}|_{∞} < q, donc |pϕ∗g+f ∗m|_{∞} < q. Comme

|pϕ ∗ g + f ∗ m|_{∞} ≤ |pϕ ∗ g|_{∞} + |f ∗ m|_{∞},

on peut se contenter de prendre

|pϕ ∗ g|_{∞} ≤ \frac{q}{4} et |f ∗ m|_{∞} ≤ \frac{q}{4}.

Or, il existe [3] deux constantes γ_{1} et γ_{2} dépendant de N tels que pour deux polynômes F et G on ait:

γ_{1}|F |_{2′}|G|_{2′} ≤ |F ∗ G|_{∞} ≤ γ_{2}|F |_{2′}|G|_{2′}.

Ainsi, on obtient :

|ϕ|_{2′}|g|_{2′} ≤ \frac{q}{4pγ_{2}} , |f|_{2′}|m|_{2′} ≤ \frac{q}{4γ_{2}} .

Comme

|ϕ|_{2′} = \sqrt{2d_{ϕ}}, |g|_{2′} = \sqrt{2d_{g}}, |f|_{2′} = \sqrt{2d_{f} − 1 − N^{−1}}, |m|_{2′} ≤ \frac{p}{2}\sqrt{N},

alors on peut exprimer d_{f}, d_{g} et d_{ϕ} en fonction de p, q et N. Ceci permet à NTRU de choisir les paramètres d_{f}, d_{g} et d_{p}hi.

4. Choix des paramètres par NTRU.

Soient d_{1} et d_{2} deux nombres entiers. On pose

𝕃(d_{1}, d_{2}) = \{F ∈ ℤ[X]/(X^{N} − 1), F a\{ \begin{matrix}d_{1} & coefficients 1, \\ d_{2} & coefficients − 1, \\ N − (d_{1} + d_{2}) & coefficients 0, \end{matrix} \}

Pour que le décryptage se passe bien, NTRU [3] suggère les paramètres suivants:

𝕃_{m} = ℤ_{p}[X]/(X^{N} − 1),

et pour des entiers d_{f}, d_{g} et d_{ϕ},

𝕃_{f} =𝕃(d_{f}, d_{f} − 1),
𝕃_{g} =𝕃(d_{g}, d_{g}),
𝕃_{ϕ} =𝕃(d_{ϕ}, d_{ϕ}),

La sécurité du système NTRU dépend non seulement de N, p et q mais aussi des entiers d_{f}, d_{g} et d_{ϕ}. NTRU [3] préconise les valeurs suivantes, qui ont été choisies expérimentalement de telle sorte que la probabilité pour que le message m de Brigitte ne soit décodable par Ali est inférieure à 5.10^{−5} :

Sécurité  N  p, q  d_{f}  d_{g} d_{ϕ}
Modérée  107 3, 64  15 12 5
Haute  167 3, 128 61 20 18
Très Haute 503 3, 256 216 72 55

5. Les attaques

5.1. Attaques forcées contre la clé.

La clé publique f d’Ali peut être découverte en essayant tous les polynômes F de 𝕃_{f} et en regardant si F ∗ h (mod q) a des coefficents assez petits. En effet si

F ∗ h ≡ F ∗ f_{q}^{−1} ∗ g (mod q),

a des coefficents assez petits, on peut recouvrir f en prenant F^{−1} (mod q). Comme chaque polynôme de 𝕃_{f} a d_{f} termes égaux à 1, et d_{f} − 1 termes égaux à −1, alors le nombre de choix possible pour F est

#𝕃_{f} = \binom{N}{d_{f}}\binom{N − d_{f}}{d_{f} − 1}.

De même la clé publique d’Ali peut être recouverte en essayant tous les polynomes G de 𝕃_{g} et en regardant si G∗h^{−1} (mod q) a des coefficents assez petits. Le nombre de choix possible pour les polynomes G est alors :

#𝕃_{g} = \binom{N}{d_{g}}\binom{N − d_{g}}{d_{g}}.

5.2. Attaques forcées contre le message.

Le message clair de Brigitte vérifie m = e − pϕ ∗ h (mod q). L’attaquant connait e, p et h. Il peut donc tester tous les polynômes Φ de 𝕃_{ϕ} et regarder si e − pΦ ∗ h (mod q) a des coefficents assez petits. Le nombre de choix possible pour Φ est alors :

#𝕃_{ϕ} = \binom{N}{d_{ϕ}}\binom{N − d_{ϕ}}{d_{ϕ}}.

Les paramètres d_{f}, d_{g} et d_{ϕ} de NTRU vérifient d_{ϕ} < d_{g} < d_{f}, le tableau suivant donne un aperçu de la taille de #𝕃_{p}hi :

Sécurité  N  d_{ϕ}  #𝕃_{ϕ}
Modéré  107  5  0.6.10^{26}
Haute  167  18  0.6.10^{44}
Très Haute  503  55  0.3.10^{100}

5.3. Attaques forcées avec rencontre au milieu contre la clé.

La clé publique d’Ali f peut être découverte en essayant tous les polynômes F_{1} et F_{2} dans 𝕃_{f} tels que F_{1} ∗ h (mod q) et −F_{2} ∗ h (mod q) ont des coefficients voisins. Ainsi le polynôme F = F_{1} + F_{2} et tel que F ∗ h a de petits coefficients et on se trouve donc dans le cas d’une attaque forcée, décrite ci-dessus. Avec cette méthode [12], le nombre de choix des polynômes F_{1} et F_{2} se limite à \sqrt{#𝕃_{g}}.

5.4. Attaques forcées avec rencontre au milieu contre le message.

De façon similaire, l’attaquant peut chercher des polynômes P hi_{1} et P hi_{2} tels que e − pΦ_{1} ∗ h (mod q) et −(e − pΦ_{2} ∗ h) (mod q) ont des coefficients voisins. En prenant alors Φ = Φ_{1} +Φ_{2}, on se trouve dans le cas d’une attque forcée. Le nombre de choix des polynômes Φ_{1} et Φ_{2} se limite alors [12] à \sqrt{#𝕃_{ϕ}}.

5.5. Attaques en cas de multiples transmissions.

Si Brigitte envoie le même message m sous formes cryptées e_{i}, i = 1, ⋯, r, avec la même clé h, mais avec des polynômes différents ϕ_{1}, ...,ϕ_{r}, alors un attaquant peut facilement recouvrir le message m. Comme

e_{i} ≡ pϕ_{i} ∗ h + m (mod q), , i = 1, ⋯, r,

alors :

ϕ_{i} − ϕ_{1} = (e_{i} − e_{1}) ∗ p^{−1}h^{−1} (mod q), i = 2, ⋯, r.

Comme chaque coefficient de ϕ_{i} − ϕ_{1} est dans {−2, −1, 0, 1, 2}, alors il recouvre l’expression exacte de ϕ_{i} − ϕ_{1}. Posons :

ϕ_{i} = ∑_{k=0}^{N−1} α_{i,k}X^{k},

ϕ_{i} − ϕ_{1} = ∑_{k=0}^{N−1} β_{i,k}X^{k}.

Alors pour tout i = 2, ⋯, r et tout k = 0, ⋯ N, on a

β_{i,k} = α_{i,k} − α_{1,k}.

Si β_{i,k} = −2, alors α_{i,k} = −1 et α_{1,k} = 1. Si β_{i,k} = 2, alors α_{i,k} = 1 et α_{1,k} = −1.

Comme la probabilité que β_{i,k} = −2, 2 est 2/9, alors ceci permet donc de trouver 2/9 des coefficients de ϕ_{1}. En prenant tous les polynômes ϕ_{i}, l’attaquant peut ainsi recouvrir une grande partie de ϕ_{1}, et à l’aide d’une attaque forcée, il peut trouver les coefficients manquants et compléter ϕ_{1} et donc exprimer le message clair m de Brigitte :

m ≡ e_{1} − pϕ_{1} ∗ h (mod q).

Une façon de rendre la transmission sûre du même message m en l’envoyant r fois avec la même clé h est la suivante. Brigitte prend 2r polynômes ϕ_{i} et Φ_{i}, i = 1, ⋯, r dans 𝕃_{ϕ} et envoie les r couples (e_{i}, E_{i}) avec :

e_{i} = pϕ_{i} ∗ h + Φ_{i}, E_{i} = pΦ_{i} ∗ e_{i} + m.

Alors Ali commence par calculer Φ_{i} par sa clé secrète f à partir de e_{i}, puis recouvrir m à partir de E_{i}.

6. Attaques basées sur les réseaux

6.1. Attaques contre la clé publique.

La clé publique d’Ali est calculée avec la formule h ≡ f_{q}^{−1} ∗ g mod q et donc f ∗ h ≡ g (mod q).

Soit α un nombre réel assez petit. Soient u et v deux éléments de ℤ_{q}[X]/(X^{N} −1) avec u = ∑_{i=0}^{N−1} u_{i}X^{i} et v = ∑_{i=0}^{N−1} v_{i}X^{i}. On considère l’ensemble

L_{h} = {(αu_{0}, ⋯ αu_{N−1}, v_{0}, …, v_{N−1}) = (αu, v), u ∗ h = v (mod q)}.

Cette ensemble définit en fait un réseau de ℝ^{2N} de dimension 2N. D’autre part, le couple (αf, g) est un élément de L_{h}. Les normes euclidiennes de αf et g sont:

||αf||_{2} = |α|\sqrt{2d_{f} − 1}, ||g||_{2} = \sqrt{2d_{g}},

et donc la norme de (αf, g) est

||(αf, g)||_{2} = \sqrt{(2d_{f} − 1)α^{2} + 2d_{g}},

qui peut être rendue très petite relativement à la dimension 2N de L_{h}. Ceci signifie que le couple (αf, g) est un vecteur de petite longueur dans L_{h}. Si on peut donc trouver une base de L_{h} et des vecteurs assez courts, on peut alors déterminer les clés secrètes f et g par identification.

Soit (αu, v) un élément de L_{h}. Alors u ∗ h ≡ v (mod q) et donc il existe un vecteur F de ℤ_{q}[X]/(X^{N} − 1) tel que v = u ∗ h + qF, ce qui s’écrit :

(v_{0}, v_{1}, ⋯, v_{N−1}) = (u_{0}, u_{1}, ⋯, u_{N−1}) ( \begin{matrix}h_{0} & h_{1} & ⋯ & h_{N−1} \\ h_{N−1} & h_{0} & ⋯ & h_{N−2} \\ ⋮ & ⋮ & ... & ⋮ \\ h_{1} & h_{2} & ⋯ & h_{0} \end{matrix} )

+ q (F_{0}, F_{1}, ⋯, F_{N−1})

On peut donc écrire

(αu, v) = (u, F)M_{α},

où M_{α} est la matrice de Coppersmith et Shamir [1] :

( \begin{matrix}α & 0 & ⋯ & 0 & h_{0} & h_{1} & ⋯ & h_{N−1} \\ 0 & α & ⋯ & 0 & h_{N−1} & h_{0} & ⋯ & h_{N−2} \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & α & h_{1} & h_{2} & ⋯ & h_{0} \\ 0 & 0 & ⋯ & 0 & q & 0 & ⋯ & 0 \\ 0 & 0 & ⋯ & 0 & 0 & q & ⋯ & 0 \\ ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & ⋯ & 0 & 0 & 0 & ⋯ & q \end{matrix} )

Les colonnes (b_{0}, b_{1}, ⋯, b_{2N−1}) de cette matrice forment une base de L_{h}.

On peut donc chercher le vecteur le plus court (αu, v) et en déduire les clés secrètes f et g. Le vecteur le plus court d’un réseaux de dimension n et de déterminant D est de la forme

βD^{1/n}\sqrt{\frac{n}{2πe}}, β ∈ [1, \sqrt{2}] .

Avec n = 2N et D = α^{N}q^{N}, cette valeur prend la forme :

β\sqrt{\frac{Nαq}{πe}} = βs.

On peut alors, en variant α, chercher un vecteur (αu, v) de norme minimal par rapport à s. Comme on veut en plus u = f et v = g, alors

||(αu, v)||_{2} = ||(αf, g)||_{2} = \sqrt{α^{2}||f||_{2}^{2} + ||g||_{2}^{2}} = \sqrt{α^{2}(2d_{f} − 1) + 2d_{g}}.

Rappelons que d_{f} et d_{g} sont publiques et que α est une valeur variable. Le problème se réduit donc à maximiser la valeur

\frac{s}{||(αu, v)||_{2}} = \frac{s}{\sqrt{α^{2}||f||_{2}^{2} + ||g||_{2}^{2}}} ,

ce qui revient en élevant au carré et en retirant les valeurs fixes N et q et la constante πe à maximiser la valeur

\frac{α}{α^{2}||f||_{2}^{2} + ||g||_{2}^{2}} .

la valeur maximale est alors atteinte avec α = ||g||_{2}/||f||_{2}. Une autre façon d’aborder ce problème est de minimiser la valeur

c_{h} = \frac{||(αu, v)||_{2}}{s} .

Avec u = f, v = g et α = ||g||_{2}/||f||_{2}, on obtient :

c_{h} = \sqrt{\frac{2πe||f||_{2}||g||_{2}}{Nq}} .

Ainsi, si c_{h} est très petit, l’algorithme LLL peut donc aboutir rapidement aux clés f et g. NTRU a donc intérêt à choisir d_{f} et d_{g} pour que c_{h} soit assez grand. Numériquement, pour le cas N = 503 (haute sécurité), on a c_{h} = 0, 18. Ceci n’est pas très grand mais la dimension du réseau est 2N = 1006. NTRU estime qu’un ordinateur avec un Pentium 200 Mhz doit fonctionner pendant 6, 2.10^{27} années pour déterminer le plus court vecteur.

6.2. Attaques contre le message.

Le message codé e de Brigitte est calculé avec la formule e ≡ pϕ∗h+m (mod q), et donc e − m ≡ pϕ ∗ h (mod q). Pour un réel α, on considère maintenant le réseau de dimension 2N :

L_{e} = {(αu_{0}, ⋯ αu_{N−1}, v_{0}, …, v_{N−1}) = (αu, v), e − m ≡ pϕ ∗ h (mod q)}.

Ainsi (αm, ϕ) est un élément de L_{e} et comme ||m||_{2} et ||ϕ||_{2} = \sqrt{2d_{p}hi} sont petits relativement à N, la détermination d’un vecteur de L_{e} de petite taille peut aboutir à la découverte de m et ϕ. De façon similaire, la valeur α = ||ϕ||_{2}/||m||_{2} maximise les chances de découverte de m et ϕ. Ceci aboutit à une valeur c_{e} analogue de c_{h} :

c_{e} = \sqrt{\frac{2πe||m||_{2}||ϕ||_{2}}{Nq}} .

Ainsi un message est vulnérable si la valeur de c_{e} est très petite. Comme les coefficients de m sont compris entre −p/2 et p/2, alors

||m||_{2} ≤ \frac{1}{2}p\sqrt{N},

et donc c_{e} dépend essentiellement de d_{ϕ}. Alors NTRU doit choisir d_{ϕ} avec c_{e} assez grand.

NTRU a expérimenté la version Schnorr-Euchner de LLL [9] avec une machine 200 Mhz et a conclu que le temps nécessaire pour recouvrir le message m ou les clés secrètes f et g est au moins exponentiel en N. Le temps nécessaire est de 9 jours dans le cas Modéré, 380 années dans le cas Haute Sécurité et 6.2.10^{27} années dans le cas Très Haute Sécurité.

7. La signature NSS.

7.1. Description.

La signature NSS (NTRU Signature Scheme) fut proposée en 2001 pour authentifier les messages. Tout comme le système NTRU, elle repose sur un certain nombre de paramètres.

• N est un nombre entier fixé. Les opérations ont lieu dans ℤ[X]/(X^{N} − 1), muni du produit de convolution.

• p est un entier non nécessairement premier.

• q est un entier vérifiant (p, q) = 1, q est très grand par rapport à p.

• D_{min} est une borne inférieure fixée.

• D_{max} est une borne supérieur fixée.

• L_{f} = L(d_{f}, d_{f}) est l’ensemble des clés privées, où d_{f} est un entier donné.

• L_{f} = L(d_{f}, d_{f}) est l’ensemble des clés privées, où d_{f} est un entier donné.

• L_{g} = L(d_{g}, d_{g}) est l’ensemble des clés privées, où d_{g} est un entier donné.

• L_{w_{2}} = L(d_{w_{2}}, d_{w_{2}}) est l’ensemble de polynômes intervenant dans la création de la signature, où d_{w} est un entier donné.

• L_{m} = L(d_{m}, d_{m}) est l’ensemble des messages, où d_{m} est un entier donné.

• f_{0} et g_{0} sont deux polynômes fixés dans ℤ[X]/(X^{N} − 1).

• Dev est une fonction définie de la façon suivante:

Si F et G sont deux polynômes de ℤ[X]/(X^{N} − 1), on pose F̄ ≡ F (mod q) (mod p), et Ḡ ≡ G (mod q) (mod p), avec des coefficients compris dans ]−q/2, q/2] et ] − p/2, p/2]. Alors, en posant F̄ = ∑_{i=0}^{N−1} F_{i}X^{i} et Ḡ = ∑_{i=0}^{N−1} G_{i}X^{i}, on a

Dev(F, G) = #{i : F_{i} ≠ G_{i}}.

Problème : Brigitte veut envoyer un message m et une signature s à Ali.

7.1.1. Brigitte fabrique sa clé de vérification publique NSS.

Brigitte choisit deux polynômes secrets f_{1} ∈ 𝕃_{f} et g_{1} ∈ 𝕃_{g} et calcule

f = f_{0} + pf_{1}, g = g_{0} + pg_{1}.

Elle calcule ensuite l’inverse f_{q}^{−1} de f dans ℤ_{q}[X]/(X^{N} − 1). Ainsi f_{q}^{−1} est un polynôme qui vérifie :

f_{q}^{−1} ∗ f ≡ 1 (mod q).

Brigitte calcule ensuite le polynôme :

h ≡ f_{q}^{−1} ∗ g (mod q).

La clé de vérification publique de Brigitte est alors h. Ses clés privées sont f et g ( et donc aussi f_{q}^{−1}).

7.1.2. Brigitte fabrique sa signature. Brigitte transforme le message m ∈ L_{m} en un message e avec la clé publique NTRU d’Ali. Brigitte choisit un polynôme w_{2} ∈ 𝕃_{w_{2}} et un autre w_{1} ∈ 𝕃_{w} et calcule

w ≡ m + w_{1} + pw_{2} (mod q).

Elle calcule ensuite

s ≡ f ∗ w (mod q).

Le message signé de Brigitte est donc (e, s).

7.1.3. Ali vérifie la signature.

En recevant le couple (e, s) de Brigitte, Ali calcule le message m à l’aide de ses clés privées relatives à NTRU. Il calcule ensuite

t ≡ h ∗ s (mod q).

Il vérifie ensuite si s ≠ 0 et si les deux conditions suivantes sont satisfaites: (i) D_{min} ≤ Dev(s, f_{0} ∗ m) ≤ D_{max}, (ii) D_{min} ≤ Dev(t, g_{0} ∗ m) ≤ D_{max}. Si toutes ces conditions sont satisfaites, alors Ali accepte la signature et le mes-

sage.

7.2. Attaques contres la signature.

Stern [11] a montré récemment comment forger une signature s′ a tout message m de telle sorte que le couple (m, s′) convienne pour la signature NSS. Ceci a obligé les auteurs de NSS de changer de procédures et ont ainsi présenté une nouvelle méthode appelée NTRUSign [10].

8. Conclusion-Challenges.

La création de clés, le codage et le décodage avec le cryptosystème NTRU utilisent uniquement des produits, des sommes et des inverses de polynômes dans ℤ[X]/(X^{N} − 1) modulo des entiers petits p et q. Le plus coûteux est certainement le calcul de l’inverse d’un polynôme modulo p ou q. L’utilisation des transformées de Fourier rapides (FFT) permet ceci en un temps en O(qN log N).

Le système NTRU est très performant par rapport à ses concurents essentiellement pour deux raisons:

1. Les opérations nécessaires pour crypter et décrypter sont basées sur des opérations arithmétiques (addition) manipulant des nombres raisonnablement petits, contrairement aux autres systèmes de cryptographie qui sont basés pour la plupart sur l’exponentiation (RSA [8] et El Gamal [2]).

Le tableau suivant [6] donne la rapidité des temps d’execution des systèmes NTRU et RSA pour des niveaux de sécurité équivalents.

Modérés  Hauts  Très Hauts
NTRU 167  NTRU 263  NTRU 503
RSA 512  RSA 1024  RSA 2048
Clé  55.3  146
Codage  2.4  3.9  4.7
Décodage  16.8  74.4  178.2

2. Les méthodes utilisées pour casser NTRU sont basées sur la réduction des réseaux par l’algorithme LLL. Mais cet algorithme ne fonctionne pas en parallèle sur des machines différentes. Ceci donne un avantage de NTRU par rapport à RSA et ECC, pour lesquels les attaques les peuvent être pratiquées sur des machines parallèles.

Les paramètres du système NTRU évoluent très rapidement selon les besoins de son utilisation. Par exemple, la valeur de p peut être considérée comme un polynôme.

La compagnie NTRU propose des challenges [5] pour décrypter des messages pour les trois niveaux de difficultés :

Sécurité  N  p  q  Somme
Haute  251  1 + X  128  25.100$
Haute  347  1 + X  128  34.700$
Très Haute  503  1 + X  256  50.300$

References

1. D. Coppersmith, A. Shamir, Lattice attacks on NTRU Proc. of Eurocypt ’97,, Springer-Verlag,, Lecture Notes in Computer Science 1233, (197), 52–61.

2. Taher El Gamal, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Transactions on Information Theory, IT–31(4) (1985), 515–534.

3. J. Hoffstein, J. Pipher, J.H. Silverman, NTRU: A new high speed public key cryptosystem, in Algorithmic Number Theory (ANTS III), Portland, OR, June 1998, Lecture Notes in Computer Sciences 1423 (J.P. Buhler, ed.), Springer-Verlag, Berlin, 1988,, 267–288.

4. A.K. Lenstra, H.W. Lenstra, L. Lovász, Factoring polynomials with rational coefficients, Math. Annalen 261 (1982), 515–534.

5. NTRU Challenges, <http://www.ntru.com/cryptolab/challenges.htm>.
6. NTRU Learning Center, <http://www.ntru.com/>.
7. NTRU Technical Center, <http://www.ntru.com/cryptolab/>.

8. R.L. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public key cryptosystems, Communications of the ACM 21 (1978), 120–126.

9. C.P. Schnorr, M. Euchner, Lattice basis reduction: improved practical algorithms and solving subset sum problems, Mathematical Programing 66 (1994), 181-199.

10. J. Hoffstein, N. Howgrave-Graham, J.Pipher, J. Silverman, W. Whyte, NTRUSign: Digital Signatures Using the NTRU Lattice, preprint (2002), <http://www.ntru.com/cryptolab/>.

11. J. Stern, Preliminary research annoucement : Cryptanalysis of the NTRU signature shceme

(NSS), preprint (2002), <http://www.di.ens.fr/ stern/nss.html>.

12. J.H. Silverman, A Meet-In-The-Middle Attack on an NTRU Private Key, preprint (2002),

<http://www.ntru.com/cryptolab/tech notes.htm>.