NTRUEncrypt

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.