NTRUEncrypt
NTRUEncrypt ist ein asymmetrisches Verschlüsselungsverfahren, das 1996 von den Mathematikern Jeffrey Hoffstein, Jill Pipher und Joseph H. Silverman entwickelt wurde. Es basiert lose auf Gitterproblemen, die selbst mit Quantenrechnern als nicht knackbar gelten. Allerdings ist NTRUEncrypt bisher nicht so gut untersucht wie gebräuchlichere Verfahren (z. B. RSA).

Der Algorithmus ist in den USA patentiert; die Patente laufen im Jahr 2021 aus. NTRUEncrypt ist durch IEEE P1363.1 standardisiert. Eingesetzt wird es z. B. von den US-Firmen WiKID, Echosat und yaSSL.

Beschreibung des Verfahrens 
Es wird im Folgenden lediglich der Kernalgorithmus beschrieben. Dieser ist für sich alleine genommen anfällig gegenüber bestimmten Angriffen; siehe den Abschnitt Vor- und Nachbearbeitung.

Alle Berechnungen finden, soweit nicht anders vermerkt, im Ring  statt, d. h. der Grad des Polynoms übersteigt nie . Die Multiplikation „*“ ist eine zyklische Faltung modulo :
Das Produkt zweier Polynome  und  ist .

Schlüsselerzeugung 
 Wahl der Parameter  mit .
 Wahl eines zufälligen Polynoms , dessen Koeffizienten in {−1, 0, 1} liegen. Die Inversen  (das Inverse modulo ) und  (das Inverse modulo ) müssen existieren.
 Erzeugung eines Zufallspolynoms , dessen Koeffizienten in {−1, 0, 1} liegen.
  ist der öffentliche Schlüssel,  der geheime Schlüssel. (Zur schnelleren Entschlüsselung kann auch  mit in den geheimen Schlüssel aufgenommen werden.)

Verschlüsselung 
 Umwandlung des Klartexts in ein Polynom .
 Wahl eines zufälligen Polynoms  mit kleinen Koeffizienten.
 Das Polynom  ist der Geheimtext.

Entschlüsselung 
 Berechnung von  mit Wahl der Repräsentanten der Koeffizienten von  im Intervall .
 Berechnung von .
 Durch Umwandlung des Polynoms  in die Textdarstellung ergibt sich der Klartext.

Korrektheit 
Für das Polynom  gilt:
.
Weil die Koeffizienten alle klein sind, gibt diese Gleichung auch im Ring .
Deshalb wird im zweiten Schritt  korrekt berechnet.

Effizienz 
Um die Multiplikation zu beschleunigen, können die Polynome  und  so gewählt werden, dass viele Koeffizienten Null sind. Dazu werden Parameter  gewählt und bei der Wahl von  werden  Koeffizienten gleich 1,  Koeffizienten gleich −1 und der Rest gleich 0 gesetzt. Bei der Wahl von  werden  Koeffizienten gleich 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  nach der Formel  mit  bildet. Da dann  gilt, entfällt die Berechnung der Inversen modulo . 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  durchsuchen kann.

Weiterhin kann man zur Beschleunigung der Multiplikation das Polynom  nach der Formel  bilden, wobei ,  und  sehr dünn besetzt sein können. An die Stelle des Parameters  treten dann die drei Parameter ,  und . Die Effizienzsteigerung ergibt sich dadurch, dass  gilt ( aber dennoch genügend Koeffizienten ungleich null hat) und deshalb mit  schneller als mit  multipliziert werden kann.

Schließlich kann  statt einer Primzahl auch als Polynom gewählt werden, wobei  die günstigste Wahl ist. Diese Variante taucht aber nur in der älteren Literatur auf.

Sicherheit 
Es gibt für NTRUEncrypt keinen formalen Sicherheitsbeweis wie für andere kryptographische Verfahren, dennoch wird das Verfahren für hinreichend große Parameter für sicher gehalten.
Anfang 2011 erschien eine Arbeit der Kryptologen Damien Stehlé und Ron Steinfeld, in der ein Sicherheitsbeweis für eine abgewandelte Form von NTRUEncrypt geführt wird.

Es sind verschiedene Angriffe auf NTRUEncrypt möglich. Der simpelste davon ist das Durchprobieren aller Polynome , die für die Parameter  und  in Frage kommen. Ein effektiverer Angriff ist der Hälftenangriff (engl. Meet-in-the-middle-Attack), bei dem statt eines Polynoms der vollen Länge  zwei Polynome mit nur  Koeffizienten gleichzeitig durchprobiert werden. Dadurch benötigt dieser Angriff nur die Quadratwurzel der Anzahl der Schritte, die beim primitiven Durchprobieren ausgeführt werden.
Noch effektiver ist eine Gitterreduktion, z. B. mittels des LLL-Algorithmus.

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

Siehe auch 
 Post-Quanten-Kryptographie

Weblinks 
 Beschreibung des Algorithmus und empfohlene Parameter (Registrierung erforderlich)
 Beschreibung des Algorithmus (ohne Registrierung zugänglich) (PDF-Datei; 315 kB)
 NTRUEncrypt als Java-Quelltext
 Eine NTRUEncrypt-Implementation der TU Darmstadt ist per SVN mit dem Befehl svn co --username guest --password guest https://svn.cdc.informatik.tu-darmstadt.de/svn/repos/flexiprovider erhältlich (Der NTRU-Code befindet sich im Verzeichnis flexiprovider/trunk/FlexiProvider/src/de/flexiprovider/pqc/ntru/).

Einzelnachweise 

Asymmetrisches Verschlüsselungsverfahren
Abkürzung