NTRUEncrypt

schéma de chiffrement asymétrique à base de réseaux euclidiens

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

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

Histoire

modifier

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

modifier

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

modifier

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

modifier

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

modifier

É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

modifier

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

modifier
(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),‎ (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 ).
  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 ().

Bibliographie

modifier