Netidee Blog Bild
Putting Everything Together: Integration von NTRU in TinyDTLS
xxx (28.09.2018)
Förderjahr 2016 / Projekt Call #11 / ProjektID: 1886 / Projekt: QUASIKOM

Wie das NTRU-Kryptosystem nun konkret Daten ver- und entschlüsselt wird im Folgenden anhand eines einfachen Beispiels mit "kleinen" Polynomen erklärt. Konkret wird in dem Beispiel ein Polynom-Ring vom Grad 11 verwendet, welcher mit der mathematischen Notation R = Z32[X]/(X^11-1) beschrieben werden kann. Die Elemente dieses Rings sind Polynome mit einem Grad von maximal 10 und Koeffizienten im Bereich zwischen 0 und 31. Solche Polynome können miteinander addiert und multipliziert werden, sodass man als Ergebnis wiederum ein Polynom vom selben maximalen Grad und Koeffizienten im selben Bereich bekommt. Wie eine Addition bzw. Multiplikation von Polynomen des Rings R konkret durchgeführt wird ist in einem früheren Blogeintrag kurz beschrieben.

Im folgenden Beispiel wird angenommen, dass vertrauliche Daten zwischen zwei IoT-Geräten übertragen werden sollen, wobei der Sender der Daten "Gerät A" genannt wird und der Empfänger "Gerät B". Dieses Szenario tritt konkret in der Handshake-Phase des DTLS-Protokolls auf, in der die beiden Geräte einen symmetrischen Schlüssel für das Record-Subprotokoll vereinbaren. Wie im letzten Blogeintrag erklärt, wird im DTLS-Handshake üblicherweise das RSA-Kryptosystem für den Schlüsseltransport verwendet, wobei Gerät A eine Zufallszahl erzeugt und diese dann mit Hilfe des RSA-Algorithmus unter Verwendung des öffentlichen Schlüssels von Gerät B verschlüsselt. Gerät A sendet die verschlüsselte Zufallszahl an Gerät B, welches den RSA-Algorithmus ausführt um mit Hilfe des privaten Schüssels die originale Zufallszahl, die von Gerät A erzeugt wurde, zu berechnen. Auf diese Weise kennen nun sowohl Gerät A als auch Gerät B die Zufallszahl und können daraus einen geheimen Schlüssel für das Record-Subprotokoll ableiten. Ein Außenstehender kann die Zufallszahl nicht herausfinden da sie verschlüsselt übertragen wurde und der private Schlüssel zum entschlüsseln nur Gerät B bekannt ist. Da DTLS ein "algorithmen-agiles" Protokoll ist, kann man im Prinzip relativ einfach den RSA-Algorithmus durch ein anderes Public-Key-Verschlüsselungssystem ersetzen, ohne dass sich am grundlegenden Ablauf des Protokolls etwas ändert. Im QUASIKOM-Projekt wird NTRU anstatt RSA verwendet, was zwei wesentliche Vorteile mit sich bringt. Erstens ist NTRU schneller als RSA, wodurch sich auch der Energieverbrauch der Ver- bzw. Entschlüsselungsoperationen reduziert, was vor Allem bei Batterie-betriebenen Geräten wichtig ist. Zweitens ist NTRU nicht nur in der heutigen Zeit sicher, sondern wird auch dann noch sicher sein, wenn es Quanten-Computer gibt, während der RSA-Algorithmus mit Hilfe eine Quanten-Computers relativ einfach "geknackt" werden kann.

Damit eine Ver- und Entschlüsselung mit NTRU funktionieren kann, müssen beide Geräte die selben System-Parameter verwenden, welche im Wesentlichen aus einem Tripel der Form (N,q,p) bestehen. Der Parameter N bestimmt den Grad des Polynom-Rings, während der Parameter q, welcher "großer Modul" genannt wird, den Wertebereich der Koeffizienten der Polynome definiert. Wie bereits erwähnt, kommen im folgenden Beispiel N=11 und q=32 zum Einsatz. Einige der in NTRU verwendeten Polynome haben jedoch kleinere Koeffizienten, deren Wertebereich durch den Parameter p eingegrenzt ist, der als "kleiner Modul" bezeichnet wird. Üblicherweise wird p = 3 verwendet, womit die Koeffizienten solcher "kleinen" Polynome nur drei verschiedene Werte annehmen können, nämlich entweder 0, 1, 2 oder -1, 0, 1. Um die Funktionsweise von NTRU anschaulich zu erklären, wird hier ein Beispiel mit den Parametern (N,q,p) = (11,32,3) wiedergegeben, das ursprünglich von einem NTRU Tutorial von der Firma SecurityInnovation stammt und auf deren Homepage verfügbar ist. Es sei jedoch ausdrücklich darauf hingewiesen, dass dieses Beispiel nur für Demonstrationszwecke geeignet ist und nicht in der Praxis eingesetzt werden solle, da die Verschlüsselung wegen der kleinen Parameter nicht sicher ist. Um ein ausreichendes Maß an Sicherheit zu gewährleisten, werden üblicherweise Polynom-Ringe mit einer Ordnung zwischen N=400 und N=700 verwendet und ein kleiner Modul von q = 2048. Die kleinen Parameter haben jedoch den Vorteil, dass man die Polynom-Multiplikationen "händisch" nachrechnen kann, um dadurch einen genauen Einblick in die Funktionsweise von NTRU zu erlangen. Alternativ kann das Beispiel natürlich auch mit Hilfe eines Computer-Algebra-Programms wie z.B. Magma oder Sage nachgerechnet werden. Das Buch "Solving Problems with Magma" beschreibt in Kapitel 33.1 eine einfache Magma-Implementierung von NTRU, wobei die selben Parameter wie im NTRU Tutorial verwendet werden. Um die Implementierung selbst zu testen braucht man nur den Magma-Code in den Online-Calculator kopieren und nach einem Mausklick werde die hoffentlich richtigen Ergebnisse angezeigt. Natürlich kann das Beispiel auch mit der im Rahmen des QUASIKOM-Projekts entwickelten Implementierung der Polynom-Arithmetik berechnet werden.

Wie bei Public-Key-Kryptosystemen üblich haben auch bei NTRU die beiden involvierten Geräte jeweils ein Schlüsselpaar bestehend aus einem privaten Schlüssel, der geheim gehalten werden muss, und einem öffentlichen Schlüssel. Eine genaue Erklärung wie ein Schlüsselpaar erzeugt wird und welche Kriterien es erfüllen muss, würde den Rahmen dieses Blogeintrags sprengen, deshalb sei an dieser Stelle auf die Wikipedia, einen Fachartikel über NTRU, sowie die NTRU-Spezifikation verwiesen. Da Gerät B der Empfänger ist und die von Gerät A gesendeten Daten entschlüsseln soll, ist in erster Linie das Schlüsselpaar von Gerät B relevant. Ein privater Schlüssel besteht aus zwei Polynomen f(X) und fp(X) mit einem Grad von maximal N-1, wobei die Koeffizienten von f(X) im Bereich [ -1, 0, 1 ] liegen und jede von fp(X) im Bereich [ 0, 1, 2 ]. Im vorliegenden Beispiel aus dem NTRU Tutorial ist f(X) = -1 + X + X2 - X4 + X6 + X9 - X10 und fp(X) = 1 + 2*X + 2*X3 + 2*X4 + X5 + 2*X7 + X8 + 2*X9. Der dazugehörende öffentliche Schlüssel ist ein Polynom g(X) mit einem Grad von maximal N-1 und Koeffizienten, die vom großen Modul begrenzt sind, d.h. im Bereich [ 0, 1, ..., q-1 ] liegen. Konkret wird im Beispiel g(X) = 8 + 25*X + 22*X2 + 20*X3 + 12*X4 + 24*X5 + 15*X6 + 19*X7 + 12*X8 + 19*X9 + 16*X10 verwendet. Neben dem Schlüsselpaar werden natürlich noch die zu verschlüsselten Daten, d.h. der sogenannte Klartext, als Input benötigt. Dieser Klartext muss vor der eigentlichen Verschlüsselung zuerst in ein Polynom m(X) mit "kleinen" Koeffizienten, d.h. Koeffizienten im Bereich [ -1, 0, 1 ] umgewandelt werden. Eine Beschreibung wie diese Konvertierung genau durchgeführt wird kann in der NTRU-Spezifikation nachgelesen werden. Im konkreten Beispiel ist m(X) = -1 + X3 - X4 - X8 + X9 + X10. Wie viele andere Public-Key-Kryptosysteme benötigt auch NTRU eine Zufallszahl um eine Verschlüsselung durchführen zu können, wobei diese bei NTRU eigentlich ein Zufallspolynom r(X) mit Koeffizienten im Bereich [ -1, 0, 1 ] ist. Bei der Erzeugung dieses Zufallspolynoms kommt auch die Hashfunktion SHA-256 zum Einsatz, was im Laufe dieses Blogeintrages noch häher erklärt wird. In dem Beispiel aus dem NTRU Tutorial ist r(X) = -1 + X2 + X3 + X4 - X5 - X7.

Die Verschlüsselung von m(X) ist relativ einfach und besteht im Wesentlichen aus einer Polynom-Multiplikation und einer Polynom-Addition. Konkret wird der Geheimtext e(X) über die Formel e(X) = r(X)*h(X) + m(X) berechnet, d.h. das Zufallspolynom r(X) wird mit dem öffentlichen Schlüssel h(X) multipliziert und danach wird der Klartext m(X) zum Produkt addiert. Da der Geheimtext von Gerät A zu Gerät B geschickt wird, muss als öffentlicher Schlüssel h(X) jener vom Gerät B verwendet werden, und nicht der vom Gerät A. Mit den oben angegeben Polynomen für r(X) und h(X) erhält man als Produkt r(X)*h(X) = 15 + 11*X + 26*X2 + 23*X3 + 15*X4 + 16*X5 + 30*X6 + 7*X7 + 26*X8 + 5*X9 + 18*X10. Wenn nun m(X) zu diesem Produkt addiert wird, bekommt man als Ergebnis den Geheimtext e(X) = 14 + 11*X + 26*X2 + 24*X3 + 14*X4 + 16*X5 + 30*X6 + 7*X7 + 25*X8 + 6*X9 + 19*X10. Gerät A kann diesen Geheimtext nun gefahrlos an Gerät B senden, selbst wenn die Datenübertragung abgehört wird, da nur Gerät B den Geheimtext entschlüsseln kann.

Zum Entschlüsseln verwendet Gerät B die beiden Polynome f(X) und fp(X), die zusammen den privaten Schlüssel bilden. Die Entschlüsselung ist etwas aufwändiger als die Verschlüsselung und besteht im Wesentlichen aus zwei Polynom-Multiplikationen. Zuerst wird das Produkt a(X) = f(X)*e(X) berechnet, wobei den Koeffizienten im Bereich zwischen -p/2 und p/2 liegen müssen, und danach der Klartext m(X) mit Hilfe der Multiplikation m(X) = fp(X)*a(X) bestimmt. Mit den im Beispiel angegebenen Polynomen für f(X) und e(X) ergibt sich das Produkt a(X) = 3 + 25*X + 22*X2 + 21*X3 + 10*X4 + 7*X5 + 6*X6 + 7*X7 + 5*X8 + 29*X9 +25*X10. Als nächstes werden die Koeffizienten so modifiziert, dass sie zwischen -q/2 und q/2 liegen, was folgendes Zwischenergebnis liefert: a(X) = 3 - 7X - 10X2 - 11X3 + 10X4 + 7X5 + 6X6 + 7X7 + 5X8 - 3X9 - 7X10. Danach werden die Koeffizienten noch modulo 3 reduziert und mit Werten zwischen -1 und 1 dargestellt, sodass sich letztendlich a(X) = -X - X2 + X3 + X4 + X5 + X7 - X8 - X10 ergibt. In der nun folgenden zweiten Polynom-Multiplikation wird das Produkt m(X) = fp(X)*a(x) berechnet, wodurch man m(X) = -1 + X3 - X4 - X8 + X9 + X10 als Ergebnis erhält. Wie leicht zu Erkennen ist, war die Entschlüsselung erfolgreich, da der von Gerät B berechnete Klartext genau mit dem Klartext von Gerät A übereinstimmt.

 

CAPTCHA
Diese Frage dient der Überprüfung, ob Sie ein menschlicher Besucher sind und um automatisierten SPAM zu verhindern.

    Weitere Blogbeiträge