Diploma Thesis DIP-3286

BibliographyBächtle, Patrick: Varianten des NTRU-Kryptosystems.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Diploma Thesis No. 3286 (2012).
30 pages, german.
CR-SchemaF.4.3 (Formal Languages)
G.1.3 (Numerical Linear Algebra)
G.2.1 (Discrete Mathematics Combinatorics)
G.3 (Probability and Statistics)
J.2 (Physical Sciences and Engineering)
Abstract

Die vorliegende Arbeit behandelt das NTRU-Kryptosystem, welches zu den Public-Key- Kryptosystemen geört. Bei den Public-Key-Kryptosystemen gibt es jeweils einen öentlichen Schlüsselanteil zum verschlüsseln und einen passenden geheimen Schlüsselanteil, der zum Entschlüsseln benötigt wird. Wie die Bezeichnung bereits vermuten lässt, ist verschlüsseln für jeden möglich, da dieser Schlüsselanteil öentlich zugänglich ist. Einem Angreifer eines Kryptosystems darf es also nicht möglich sein aus der Kenntnis des öentlichen Schlüssels die ursprüngliche Nachricht zu rekonstruieren. Um dies zu gewährleisten greifen Kryptosysteme auf schwer zu lösende mathematische Probleme zurück. Das RSA-Verfahren aus dem Jahr 1977 benutzt hierzu die Schwierigkeit groÿe Zahlen zu faktorisieren. Wählt man die für das RSA-Verfahren benutzten Zahlen groÿ genug, so geht man davon aus, dass ein Angreifer das Verfahren nicht in kurzer Zeit brechen kann. Beweisbar ist diese Sicherheit nicht, auf Experimenten basierende Beobachtungen zeigen jedoch, dass bei geeigneter Parameterwahl die Laufzeit solcher Angrie sehr viel Zeit beansprucht. Ein anderes Public-Key-Kryptosystem, das Die-Hellman-System, basiert auf einem anderen schwer zu lösendem mathematischen Problem. Hierbei verlässt man sich auf die Schwierigkeit des diskreten Logarithmus in endlichen Gruppen. Es ist auch hier die Sicherheit des Verfahrens nicht beweisbar. Für genügend groÿe Parameter liegt aber die gleiche Situation wie beim RSA-Verfahren vor. Ein Verfahren mit beweisbarer Sicherheit ist das Vernom-One-Time-Pad. Dieses Verfahren zeichnet sich einerseits dadurch aus, dass die Schlüssel die gleiche Länge wie die zu verschlüsselnden Nachrichten haben müssen. Bei längeren Nachrichten führt dies zu einem groÿen Aufwand bei der Schlüsselerzeugung. Diese Inezienz ist der Grund, warum das Vernom-One-Time-Pad in der Praxis nur selten Anwendung ndet. In dieser Diplomarbeit wollen wir das NTRU-Verfahren genauer betrachten. Das NTRUKryptosystem wurde 1996 von Hostein, Pipher und Silverman im Rahmen der RUMPSession auf der CRYPTO '96 vorgestellt. Erst kürzlich wurde es als Standard in der Finanzbranche zertiziert. NTRU ist ein Public-Key-Kryptosystem, bei dem Ver- und Entschl üsselung Operationen im Quotienten eines Polynomrings (genauer: R = Z[x]=xN ?? 1) sind. Die Schlüssel, die für das Verfahren benutzt werden sind demnach Polynome aus diesem Polynomring. Wie auch bei den anderen Public-Key-Systemen kann die Sicherheit bei NTRU nicht bewiesen werden. Die Sicherheit basiert auf der Annahme, dass faktorisieren eines Polynoms in R schwer ist. Wie auch schon bei RSA und Die-Hellman stützt sich diese Annahme auf experimentelle Ergebnisse, die auf eine exponentielle Laufzeit der Angrisversuche hindeuten. 1 Im Rahmen dieser Diplomarbeit werden wir grundlegend das NTRU-Verfahren und einige Angrie vorstellen. Anschlieÿend wollen wir den algebraischen Grundraum R mit einer leicht modizierten Version austauschen und so modizierte Variante von NTRU genauer untersuchen. Im Vordergrund dieser Untersuchung steht die Funktionalität des Verfahrens, da schon beim Standard Verfahren Entschlüsselungsfehlern auftreten können. Des Weiteren wollen die modizierten Varianten auf ihre theoretische Sicherheit hin überprüfen. Dabei werden wir insbesondere auf die sogenannten Gitterangrie gegen ein NTRU-System eingehen. 2

Full text and
other links
PDF (217052 Bytes)
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Superviser(s)Kufleitner, Manfred
Entry dateNovember 14, 2012
   Publ. Computer Science