NTRUEncrypt

Le système de cryptographie asymétrique NTRUEncrypt, aussi connu comme l'algorithme de chiffrement NTRU, est une alternative au chiffrement RSA et à la cryptographie sur les courbes elliptiques reposant sur des hypothèses sur les réseaux euclidiens et en particulier sur le problème du plus court vecteur (en) (dont il n'existe pas en 2016 d'attaques par un ordinateur quantique). Les opérations sont effectuées dans un anneau de polynômes tronqués ${\displaystyle R=\mathbb {Z} [X]/(X^{N}-1)}$ muni du produit de convolution.

Ce cryptosystème a été proposé en 1996 par Hoffstein, Pipher et Silverman[1].

Histoire

Le cryptosystème NTRUEncrypt est relativement récent. Sa première version, simplement appelée NTRU, a été développée en 1996 par trois mathématiciens (Jeffrey Hoffstein, Jill Pipher et Joseph H. Silverman), qui, avec Daniel Lieman, ont fondé la même année NTRU Cryptosystems et breveté ce système.

Depuis sa première présentation, des changements ont été apportés pour améliorer ses performances, notamment la vitesse, et sa sécurité. Les concepteurs ont réagi aux descriptions de failles de sécurité de NTRUEncrypt en introduisant de nouveaux paramètres plus fiables par rapport aux attaques connues et augmentant raisonnablement la puissance de calcul.

De 2008 à 2019, ce cryptosystème a fait partie de la norme IEEE P1363 .1 (cryptographie à clé publique basée sur les réseaux).

Depuis avril 2011, NTRUEncrypt fait partie du standard ANSI X9.98, pour usage dans l'industrie des services financiers.

Il est un des candidats à la normalisation par le NIST dans l'initiative de cryptographie post-quantique, où il a déjà réussi 3 sélections[2].

Grâce à sa vitesse et à sa faible consommation de mémoire[3], ce cryptosystème peut être utilisé pour des applications telles que les appareils mobiles ou les Smart-cards.

Construction

Le cryptosystème NTRUEncrypt est paramétré par un triplet d'entiers (N,p,q) avec p et q premiers entre eux. Une liste de paramètres donnés dans la proposition au NIST sera donnée plus loin.

Les éléments modulo p (respectivement q) sont donnés dans l'ensemble [-p/2, p/2[ (respectivement [-q/2, q/2[) au lieu de la représentation usuelle entre [0, p-1] (respectivement [0, q-1] dans la suite.

Génération d’une paire de clés

La génération de la paire de clés de chiffrement et de déchiffrement se fait de la manière suivante. Des polynômes f et g dans ${\displaystyle \mathbb {Z} [X]/(X^{N}-1)}$ à coefficients dans {-1,0,1} sont tirés uniformément au hasard. Si f n'est pas inversible dans ${\displaystyle \mathbb {Z} _{p}[X]/(X^{N}-1)}$ et ${\displaystyle \mathbb {Z} _{q}[X]/(X^{N}-1)}$ (ce qui peut se vérifier par l'algorithme d'Euclide sur les polynômes), alors on en tire un autre jusqu'à ce que cette propriété soit vérifiée. Les inverses de f modulo p et q sont notés ${\displaystyle {\textbf {f}}_{p}}$ et ${\displaystyle {\textbf {f}}_{q}}$ respectivement.

On calcule ensuite ${\displaystyle {\textbf {h}}:=p{\textbf {f}}_{q}\cdot {\textbf {g}}{\bmod {q}}}$.

La clé publique de chiffrement est définie comme h et la clé privée de déchiffrement par f, ${\displaystyle {\textbf {f}}_{p}}$ et g.

Chiffrement

Pour chiffrer un message m encodé comme un polynôme de degré N à coefficients dans [-p/2, p/2[ (et donc de longueur ${\displaystyle N\cdot \log _{2}(p)}$), on procède comme suit. À l'aide de la clé de chiffrement h, on tire un polynôme r à petits coefficients (il s'agit d'une valeur qui sert à masquer le message) puis on calcule de chiffré ${\displaystyle {\textbf {c}}={\textbf {r}}{\textbf {h}}+{\textbf {m}}{\bmod {q}}}$.

Déchiffrement

Étant donné un chiffré c obtenu par l'algorithme précédent et les clés de déchiffrement f, g et ${\displaystyle {\textbf {f}}_{p}}$, on peut déchiffrer le message en effectuant les opérations suivantes.

On commence par calculer la valeur :

${\displaystyle {\textbf {a}}:={\textbf {f}}{\textbf {c}}{\bmod {q}}.}$

On remarque alors que :

${\displaystyle {\textbf {a}}={\textbf {f}}({\textbf {r}}\cdot {\textbf {h}}+{\textbf {m}}){\bmod {q}},}$

${\displaystyle {\textbf {a}}={\textbf {f}}(p{\textbf {r}}\cdot {\textbf {f}}_{q}\cdot {\textbf {g}}+{\textbf {m}}){\bmod {q}}.}$

Comme ${\displaystyle {\textbf {f}}_{q}}$ est l'inverse de f modulo q, alors :

${\displaystyle {\textbf {a}}=p{\textbf {r}}\cdot {\textbf {g}}+{\textbf {f}}\cdot {\textbf {m}}{\bmod {q}}.}$

Ainsi ${\displaystyle {\textbf {a}}={\textbf {f}}\cdot {\textbf {m}}{\bmod {p}}}$, et en calculant ${\displaystyle {\textbf {f}}_{p}\cdot {\textbf {a}}}$, on obtient ${\displaystyle {\textbf {m}}{\bmod {p}}}$, dont les coefficients appartiennent déjà à [-p/2, p/2[, on retrouve bien le message m.

Sécurité et performances

La soumission au troisième round de la compétition du NIST propose les jeux de paramètres suivants[4] :

Sécurité[5]	N	p	q	Taille de la clé publique ou du chiffré[6] (en octets)
128 bits	509	3	2 048	699
192 bits	701	3	8 192	1 138
192 bits	677	3	2 048	931
256 bits	821	3	4 096	1 230

Ici la colonne « Sécurité » désigne une taille de clés dans un chiffrement par blocs pour laquelle la puissance de calcul nécessaire à une attaque serait équivalente.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « NTRUEncrypt » (voir la liste des auteurs).

1. (en) Jeffrey Hoffstein, Jill Pipher et Joseph H. Silverman, « NTRU: A ring-based public key cryptosystem », Algorithmic Number Theory Symposium (ANTS),‎ 1996 (DOI 10.1007/BFb0054868).
2. (en) Liste des candidats à l’appel à standardisation pour la cryptographie post-quantique du NIST (Round 3).
3. « Introduction », sur yp.to (consulté le 22 avril 2023).
4. (en) NTRU Algorithm Specications And Supporting Documentation
5. (en) Critères d'évaluation de sécurité du NIST pour la standardisation des cryptosystèmes post-quantiques
6. Pour la taille de la clé publique ou du chiffré, elle est donnée dans une colonne unique comme les deux éléments vivent dans le même ensemble (${\displaystyle \mathbb {Z} _{q}[X]/(X^{N}-1)}$).

Bibliographie

• (en) Site officiel
• (en) E. Jaulmes et A. Joux, « A Chosen-Ciphertext Attack against NTRU », Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptography, coll. « Lecture Notes in Computer Science » (vol. 1880), 2000, p. 20-35
• (en) Jeffrey Hoffstein, Jill Pipher et Joseph H. Silverman, « NTRU: A Ring Based Public Key Cryptosystem », J.P. Buhler, Algorithmic Number Theory (ANTS III), Portland, OR, June 1998, coll. « Lecture Notes in Computer Science » (vol. 1423), Springer-Verlag, Berlin, 1998, p. 267-288
• (en) N. Howgrave-Graham, J. H. Silverman et W. Whyte, Meet-In-The-Middle Attack on a NTRU Private Key
• (en) J. Hoffstein, et J. Silverman, « Optimizations for NTRU », Public-Key Cryptography and Computational Number Theory (Warsaw, September 11–15, 2000), DeGruyter
• (en) A. C. Atici, L. Batina, J. Fan et I. Verbauwhede, Low-cost implementations of NTRU for pervasive security