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  (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  muni du produit de convolution.

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

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  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 , 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.

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

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  à coefficients dans {-1,0,1} sont tirés uniformément au hasard. Si f n'est pas inversible dans  et  (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  et  respectivement.

On calcule ensuite .

La clé publique de chiffrement est définie comme h et la clé privée de déchiffrement par f,  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 ), 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é .

Déchiffrement 

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

On commence par calculer la valeur :
 
On remarque alors que :
 
 
Comme  est l'inverse de f modulo q, alors :
 

Ainsi , et en calculant , on obtient , 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 :

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

Bibliographie 

 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, 
 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, 
 N. Howgrave-Graham, J. H. Silverman et W. Whyte, Meet-In-The-Middle Attack on a NTRU Private Key
  J. Hoffstein, et J. Silverman, « Optimizations for NTRU », Public-Key Cryptography and Computational Number Theory (Warsaw, September 11–15, 2000), DeGruyter
 A. C. Atici, L. Batina, J. Fan et I. Verbauwhede, Low-cost implementations of NTRU for pervasive security

Algorithme de cryptographie asymétrique