imported>SchlurcherBot: Bot: http → https

2026-04-19T00:05:49Z

Bot: http → https

Neue Seite

'''NTRUEncrypt''' ist ein [[Asymmetrisches Kryptosystem|asymmetrisches Verschlüsselungsverfahren]], das 1996 von den Mathematikern [[Jeffrey Hoffstein]], [[Jill Pipher]] und [[Joseph H. Silverman]] entwickelt wurde.<ref>Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. {{Webarchiv|url=http://www.securityinnovation.com/uploads/Crypto/ANTS97.pdf |wayback=20130130160752 |text=NTRU: A Ring Based Public Key Cryptosystem |archiv-bot=2019-05-03 02:06:03 InternetArchiveBot }}. 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.</ref> Es basiert lose auf [[Gitter (Mathematik)|Gitterproblemen]], die selbst mit [[Quantenrechner]]n 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.<ref>{{Patent
| Land = US
| V-Nr = 7031468
| Typ = Erteilung
| Titel = Speed enhanced cryptographic method and apparatus
| A-Datum = 2001-08-24
| V-Datum = 2006-04-18
| Erfinder = Jeffrey Hoffstein, Joseph H. Silverman
| Anmelder = NTRU Cryptosystems, Inc.
| DB = Google
}} (Auslaufen der 20-jährigen Frist am 24. August 2021)</ref> NTRUEncrypt ist durch IEEE P1363.1 standardisiert. Eingesetzt wird es z. B. von den US-Firmen WiKID,<ref>{{Webarchiv|url=http://www.wikidsystems.com/learn-more/twofactorarch/twofactorclient |wayback=20111214141458 |text=WiKID-Authentifizierungsgeräte |archiv-bot=2019-05-03 02:06:03 InternetArchiveBot }}.</ref> Echosat,<ref>{{Toter Link |datum=2019-05 |url=http://www.networkworld.com/news/2011/042011-ntrue-algorithm-x9.html |text=Artikel über NTRU in Networkworld vom 20. April 2011 |archivebot=2019-05-03 02:06:03 InternetArchiveBot}}.</ref> yaSSL<ref>[http://www.yassl.com/yaSSL/Products-cyassl.html CyaSSL Embedded SSL Library].</ref> und unter anderem dem Programm [[OpenSSH]].<ref>{{Internetquelle |url=https://www.openssh.com/txt/release-9.0 |titel=OpenSSH Release Notes 9.0 |datum=2022-04-08 |abruf=2022-04-12}}</ref>

== Beschreibung des Verfahrens ==
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|Vor- und Nachbearbeitung]]''.

Alle Berechnungen finden, soweit nicht anders vermerkt, im [[Polynomring|Ring]] <math>R = \Z_q[X]/(X^N-1)</math> statt, d. h. der Grad des Polynoms übersteigt nie <math>N</math>. Die Multiplikation „*“ ist eine [[zyklische Faltung]] modulo <math>q</math>:
Das Produkt zweier Polynome <math>f = [f_0, f_1, \ldots, f_{N-1}]</math> und <math>g = [g_0, g_1, \ldots, g_{N-1}]</math> ist <math>f*g = \Big[ \sum_{i+j \equiv k \mod N}f_i \cdot g_j \mod q \Big]_{k=0,...,N-1}</math>.

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

=== Verschlüsselung ===
# Umwandlung des Klartexts in ein Polynom <math>m</math>.
# Wahl eines zufälligen Polynoms <math>r</math> mit kleinen Koeffizienten.
# Das Polynom <math>e \equiv pr*h+m \mod q</math> ist der [[Geheimtext]].

=== Entschlüsselung ===
# Berechnung von <math>a \equiv f*e \mod q</math> mit Wahl der Repräsentanten der Koeffizienten von <math>a</math> im Intervall <math>[-q/2, q/2)</math>.
# Berechnung von <math>c \equiv f_p*a \mod p</math>.
# Durch Umwandlung des Polynoms <math>c</math> in die Textdarstellung ergibt sich der Klartext.

=== Korrektheit ===
Für das Polynom <math>a</math> gilt:
<math>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</math>.
Weil die Koeffizienten alle klein sind, gilt diese Gleichung auch im Ring <math>R</math>.
Deshalb wird im zweiten Schritt <math>c = f_p*pr*g + f_p*f*m \mod p = m \mod p</math> korrekt berechnet.

=== Effizienz ===
Um die Multiplikation zu beschleunigen, können die Polynome <math>f</math> und <math>g</math> so gewählt werden, dass viele Koeffizienten Null sind. Dazu werden Parameter <math>d_f, d_g</math> gewählt und bei der Wahl von <math>f</math> werden <math>d_f</math> Koeffizienten gleich 1, <math>d_f -1</math> Koeffizienten gleich −1 und der Rest gleich 0 gesetzt. Bei der Wahl von <math>g</math> werden <math>d_g</math> Koeffizienten gleich 1, <math>d_g -1</math> 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 <math>f</math> nach der Formel <math>f=1+p \cdot f_{1}</math> mit <math>f_1 \in \Z_p[X]</math> bildet. Da dann <math>f_{p}^{-1}=1</math> gilt, entfällt die Berechnung der Inversen modulo <math>p</math>. 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 <math>f_1</math> durchsuchen kann.<ref name=optim>[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.64.6834&rep=rep1&type=pdf Hoffstein u. Silverman: Optimizations for NTRU].</ref>

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

Schließlich kann <math>p</math> statt einer [[Primzahl]] auch als Polynom gewählt werden, wobei <math>p(x)=x+2</math> die günstigste Wahl ist.<ref name=optim /> 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.<ref>{{Literatur | Autor=Damien Stehlé and Ron Steinfeld | Titel=Making NTRU as Secure as Worst-Case Problems over Ideal Lattices | Online=https://perso.ens-lyon.fr/damien.stehle/downloads/ntruenc.pdf}}</ref>

Es sind verschiedene Angriffe auf NTRUEncrypt möglich. Der simpelste davon ist das Durchprobieren aller Polynome <math>f</math>, die für die Parameter <math>N</math> und <math>d_f</math> in Frage kommen. Ein effektiverer Angriff ist der Hälftenangriff (engl. [[Meet-in-the-middle-Angriff|Meet-in-the-middle-Attack]]), bei dem statt eines Polynoms der vollen Länge <math>N</math> zwei Polynome mit nur <math>N/2</math> 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 [[Gitter (Mathematik)#Gitterreduktion|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 (Informatik)|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.<ref>[https://assets.securityinnovation.com/static/downloads/NTRU/resources/cr03_ntru.pdf The impact of decryption failures on the security of NTRU encryption].</ref> [[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 <math>N</math> Werte zwischen 167 und 503 empfohlen, nach dem Bekanntwerden diverser Angriffe wurden die Empfehlungen aber entsprechend angepasst. Die folgenden Parameter<ref>{{Webarchiv|url=http://grouper.ieee.org/groups/1363/lattPK/ |wayback=20130629215819 |text=IEEE P1363.1 |archiv-bot=2019-05-03 02:06:03 InternetArchiveBot}} ({{Webarchiv|url=https://pdfs.semanticscholar.org/4e23/5fd5671971d913f4daee4903ab2aaf84f796.pdf |wayback=20161230141929 |text=PDF |archiv-bot=2019-05-03 02:06:03 InternetArchiveBot}} eines Drafts)</ref> werden allen derzeit bekannten (Stand 9/2011) Angriffen gerecht:

{| class="wikitable"
|-
!
! 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 ==
* [[Post-Quanten-Kryptographie]]

== Weblinks ==
* [https://grouper.ieee.org/groups/1363/private/P1363.1-D12-clean.pdf Beschreibung des Algorithmus und empfohlene Parameter (Registrierung erforderlich)]
* [https://grouper.ieee.org/groups/1363/lattPK/submissions/EESS1v2.pdf Beschreibung des Algorithmus (ohne Registrierung zugänglich)] (PDF-Datei; 315 kB)
* [https://sourceforge.net/projects/ntru/ 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 ==
<references />

[[Kategorie:Asymmetrisches Verschlüsselungsverfahren]]
[[Kategorie:Abkürzung]]

NTRUEncrypt - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https