NTRUEncrypt ist ein asymmetrisches Verschlüsselungsverfahren, das 1996 von den Mathematikern Jeffrey Hoffstein, Jill Pipher und Joseph H. Silverman entwickelt wurde.[1] 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 liefen im Jahr 2021 aus.[2] NTRUEncrypt ist durch IEEE P1363.1 standardisiert. Eingesetzt wird es z. B. von den US-Firmen WiKID,[3] Echosat,[4] yaSSL[5] und unter anderem dem Programm OpenSSH.[6]

Beschreibung des Verfahrens

Bearbeiten

Es wird im Folgenden lediglich der Kernalgorithmus beschrieben. Dieser ist für sich allein 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

Bearbeiten
  1. Wahl der Parameter   mit  .
  2. Wahl eines zufälligen Polynoms  , dessen Koeffizienten in {−1, 0, 1} liegen. Die Inversen   (das Inverse modulo  ) und   (das Inverse modulo  ) müssen existieren.
  3. Erzeugung eines Zufallspolynoms  , dessen Koeffizienten in {−1, 0, 1} liegen.
  4.   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

Bearbeiten
  1. Umwandlung des Klartexts in ein Polynom  .
  2. Wahl eines zufälligen Polynoms   mit kleinen Koeffizienten.
  3. Das Polynom   ist der Geheimtext.

Entschlüsselung

Bearbeiten
  1. Berechnung von   mit Wahl der Repräsentanten der Koeffizienten von   im Intervall  .
  2. Berechnung von  .
  3. Durch Umwandlung des Polynoms   in die Textdarstellung ergibt sich der Klartext.

Korrektheit

Bearbeiten

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

Effizienz

Bearbeiten

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.[7]

Weiterhin kann man zur Beschleunigung der Multiplikation das Polynom   nach der Formel   bilden, wobei  ,   und   sehr dünn besetzt sein können.[7] 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.[7] Diese Variante taucht aber nur in der älteren Literatur auf.

Sicherheit

Bearbeiten

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.[8]

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

Bearbeiten

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.[9] SVES-3 behebt diese Schwächen und ist im P1363.1-Standard unter der Bezeichnung SVES beschrieben.

Parameter mit 256 Bit Sicherheitsniveau

Bearbeiten

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[10] werden allen derzeit bekannten (Stand 9/2011) Angriffen gerecht:

Bezeichnung N p q df dg
Geringste Schlüssellänge EES1087EP2 1087 3 2048 120 362
Mittlere Schlüssellänge, mittlere Dauer EES1171EP1 1171 3 2048 106 390
Geringste Ver- und Entschl.dauer EES1499EP1 1499 3 2048 79 499

Siehe auch

Bearbeiten
Bearbeiten

Einzelnachweise

Bearbeiten
  1. Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. NTRU: A Ring Based Public Key Cryptosystem (Memento des Originals vom 30. Januar 2013 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/www.securityinnovation.com. In Algorithmic Number Theory (ANTS III), Portland, OR, Juni 1998, J. P. Buhler (Hrsg.), Lecture Notes in Computer Science 1423, Springer-Verlag Berlin, 1998, 267–288.
  2. Patent US7031468: Speed enhanced cryptographic method and apparatus. Angemeldet am 24. August 2001, veröffentlicht am 18. April 2006, Anmelder: NTRU Cryptosystems, Inc., Erfinder: Jeffrey Hoffstein, Joseph H. Silverman. (Auslaufen der 20-jährigen Frist am 24. August 2021)
  3. WiKID-Authentifizierungsgeräte (Memento des Originals vom 14. Dezember 2011 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/www.wikidsystems.com.
  4. Artikel über NTRU in Networkworld vom 20. April 2011@1@2Vorlage:Toter Link/www.networkworld.com (Seite nicht mehr abrufbar, festgestellt im Mai 2019. Suche in Webarchiven)  Info: Der Link wurde automatisch als defekt markiert. Bitte prüfe den Link gemäß Anleitung und entferne dann diesen Hinweis..
  5. CyaSSL Embedded SSL Library.
  6. OpenSSH Release Notes 9.0. 8. April 2022, abgerufen am 12. April 2022.
  7. a b c Hoffstein u. Silverman: Optimizations for NTRU.
  8. Damien Stehlé and Ron Steinfeld: Making NTRU as Secure as Worst-Case Problems over Ideal Lattices. (ens-lyon.fr [PDF]).
  9. The impact of decryption failures on the security of NTRU encryption.
  10. IEEE P1363.1 (Memento des Originals vom 29. Juni 2013 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/grouper.ieee.org (PDF (Memento des Originals vom 30. Dezember 2016 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/pdfs.semanticscholar.org eines Drafts)