Varianten des NTRU-Kryptosystems

Abstract

Die vorliegende Arbeit behandelt das NTRU-Kryptosystem, welches zu den Public-Key-Kryptosystemen gehört. Bei den Public-Key-Kryptosystemen gibt es jeweils einen öffentlichen 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 öffentlich zugänglich ist. Einem Angreifer eines Kryptosystems darf es also nicht möglich sein aus der Kenntnis des öffentlichen 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 Angriffe sehr viel Zeit beansprucht. Ein anderes Public-Key-Kryptosystem, das Diffie-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 Ineffizienz ist der Grund, warum das Vernom-One-Time-Pad in der Praxis nur selten Anwendung findet. In dieser Diplomarbeit wollen wir das NTRU-Verfahren genauer betrachten. Das NTRU-Kryptosystem wurde 1996 von Hoffstein, Pipher und Silverman im Rahmen der RUMP Session auf der CRYPTO '96 vorgestellt. Erst kürzlich wurde es als Standard in der Finanzbranche zertifiziert. 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 Diffie-Hellman stützt sich diese Annahme auf experimentelle Ergebnisse, die auf eine exponentielle Laufzeit der Angriffsversuche hindeuten. Im Rahmen dieser Diplomarbeit werden wir grundlegend das NTRU-Verfahren und einige Angriffe vorstellen. Anschließend wollen wir den algebraischen Grundraum R mit einer leicht modifizierten Version austauschen und so modifizierte 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 modifizierten Varianten auf ihre theoretische Sicherheit hin überprüfen. Dabei werden wir insbesondere auf die sogenannten Gitterangriffe gegen ein NTRU-System eingehen.