NTRUEncrypt

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.

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.

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.

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}}}$ .

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

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

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.