Schlüsselerzeugung

1. Wahl der Parameter ${\displaystyle N,p,q}$ mit ${\displaystyle q>p,\operatorname {ggT} (p,q)=1}$.
2. Wahl eines zufälligen Polynoms ${\displaystyle f}$, dessen Koeffizienten in {−1, 0, 1} liegen. Die Inversen ${\displaystyle f_{p}}$ (das Inverse modulo ${\displaystyle p}$) und ${\displaystyle f_{q}}$ (das Inverse modulo ${\displaystyle q}$) müssen existieren.
3. Erzeugung eines Zufallspolynoms ${\displaystyle g}$, dessen Koeffizienten in {−1, 0, 1} liegen.
4. ${\displaystyle h\equiv f_{q}*g\mod q}$ ist der öffentliche Schlüssel, ${\displaystyle f}$ der geheime Schlüssel. (Zur schnelleren Entschlüsselung kann auch ${\displaystyle f_{p}}$ mit in den geheimen Schlüssel aufgenommen werden.)

Verschlüsselung

1. Umwandlung des Klartexts in ein Polynom ${\displaystyle m}$.
2. Wahl eines zufälligen Polynoms ${\displaystyle r}$ mit kleinen Koeffizienten.
3. Das Polynom ${\displaystyle e\equiv pr*h+m\mod q}$ ist der Geheimtext.

Entschlüsselung

1. Berechnung von ${\displaystyle a\equiv f*e\mod q}$ mit Wahl der Repräsentanten der Koeffizienten von ${\displaystyle a}$ im Intervall ${\displaystyle [-q/2,q/2)}$.
2. Berechnung von ${\displaystyle c\equiv f_{p}*a\mod p}$.
3. Durch Umwandlung des Polynoms ${\displaystyle c}$ in die Textdarstellung ergibt sich der Klartext.

Korrektheit

Für das Polynom ${\displaystyle a}$ gilt: ${\displaystyle a\equiv f*e\equiv f*pr*h+f*m\mod q=f*pr*f_{q}*g+f*m\mod q=pr*g+f*m\mod q}$. Weil die Koeffizienten alle klein sind, gilt diese Gleichung auch im Ring ${\displaystyle R}$. Deshalb wird im zweiten Schritt ${\displaystyle c=f_{p}*pr*g+f_{p}*f*m\mod p=m\mod p}$ korrekt berechnet.

Effizienz

Um die Multiplikation zu beschleunigen, können die Polynome ${\displaystyle f}$ und ${\displaystyle g}$ so gewählt werden, dass viele Koeffizienten Null sind. Dazu werden Parameter ${\displaystyle d_{f},d_{g}}$ gewählt und bei der Wahl von ${\displaystyle f}$ werden ${\displaystyle d_{f}}$ Koeffizienten gleich 1, ${\displaystyle d_{f}-1}$ Koeffizienten gleich −1 und der Rest gleich 0 gesetzt. Bei der Wahl von ${\displaystyle g}$ werden ${\displaystyle d_{g}}$ Koeffizienten gleich 1, ${\displaystyle d_{g}-1}$ Koeffizienten gleich −1 und der Rest gleich 0 gesetzt (Bem.: Die Anzahl Einsen muss ungleich der Anzahl Minus-Einsen sein, weil das Polynom sonst nicht invertierbar ist).

Das Entschlüsseln wird effizienter, wenn man das Polynom ${\displaystyle f}$ nach der Formel ${\displaystyle f=1+p\cdot f_{1}}$ mit ${\displaystyle f_{1}\in \mathbb {Z} _{p}[X]}$ bildet. Da dann ${\displaystyle f_{p}^{-1}=1}$ gilt, entfällt die Berechnung der Inversen modulo ${\displaystyle p}$. Es ist jedoch bei der Parameterwahl darauf zu achten, dass das gewünschte Maß an Sicherheit erhalten bleibt, da ein Angreifer nun die Menge der ${\displaystyle f_{1}}$ durchsuchen kann.

Weiterhin kann man zur Beschleunigung der Multiplikation das Polynom ${\displaystyle f}$ nach der Formel ${\displaystyle f(x)=1+p(f_{1}(x)*f_{2}(x)+f_{3}(x)}$ bilden, wobei ${\displaystyle f_{1}}$, ${\displaystyle f_{2}}$ und ${\displaystyle f_{3}}$ sehr dünn besetzt sein können. An die Stelle des Parameters ${\displaystyle d_{f}}$ treten dann die drei Parameter ${\displaystyle d_{f1}}$, ${\displaystyle d_{f2}}$ und ${\displaystyle d_{f3}}$. Die Effizienzsteigerung ergibt sich dadurch, dass ${\displaystyle d_{f1}+d_{f2}+d_{f3}<d_{f}}$ gilt (${\displaystyle f_{1}*f_{2}+f_{3}}$ aber dennoch genügend Koeffizienten ungleich null hat) und deshalb mit ${\displaystyle f_{1}*f_{2}+f_{3}}$ schneller als mit ${\displaystyle f}$ multipliziert werden kann.

Schließlich kann ${\displaystyle p}$ statt einer Primzahl auch als Polynom gewählt werden, wobei ${\displaystyle p(x)=x+2}$ die günstigste Wahl ist. Diese Variante taucht aber nur in der älteren Literatur auf.

Vor- und Nachbearbeitung

Der NTRUEncrypt-Kernalgorithmus bietet keine Sicherheit gegenüber Angreifern, die die Daten nach der Verschlüsselung manipulieren. Dies kann durch ein spezielles Padding behoben werden, anhand dessen der Empfänger manipulierte Chiffrate erkennen kann.

Es sind drei solcher Verfahren bekannt. SVES-1 und SVES-2 sind älter und gegen Angriffe, die Entschlüsselungsfehler ausnutzen, anfällig. SVES-3 behebt diese Schwächen und ist im P1363.1-Standard unter der Bezeichnung SVES beschrieben.

Parameter mit 256 Bit Sicherheitsniveau

Ursprünglich wurden für die Länge von ${\displaystyle N}$ Werte zwischen 167 und 503 empfohlen, nach dem Bekanntwerden diverser Angriffe wurden die Empfehlungen aber entsprechend angepasst. Die folgenden Parameter werden allen derzeit bekannten (Stand 9/2011) Angriffen gerecht: