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 eigenen 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 Onboard Security 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", welches online frei verfügbar ist, 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 + X^2 - X^4 + X^6 + X^9 - X^10 und fp(X) = 1 + 2*X + 2*X^3 + 2*X^4 + X^5 + 2*X^7 + X^8 + 2*X^9. 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*X^2 + 20*X^3 + 12*X^4 + 24*X^5 + 15*X^6 + 19*X^7 + 12*X^8 + 19*X^9 + 16*X^10 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 + X^3 - X^4 - X^8 + X^9 + X^10. 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, welches in der NTRU-Spezifikation "Blinding Polynomal" heißt, kommt auch die Hashfunktion SHA-256 zum Einsatz, worauf am Ende dieses Blogeintrages noch näher eingegangen wird. In dem Beispiel aus dem NTRU Tutorial ist r(X) = -1 + X^2 + X^3 + X^4 - X^5 - X^7.

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*X^2 + 23*X^3 + 15*X^4 + 16*X^5 + 30*X^6 + 7*X^7 + 26*X^8 + 5*X^9 + 18*X^10. Wenn nun m(X) zu diesem Produkt addiert wird, bekommt man als Ergebnis den Geheimtext e(X) = 14 + 11*X + 26*X^2 + 24*X^3 + 14*X^4 + 16*X^5 + 30*X^6 + 7*X^7 + 25*X^8 + 6*X^9 + 19*X^10. 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*X^2 + 21*X^3 + 10*X^4 + 7*X^5 + 6*X^6 + 7*X^7 + 5*X^8 + 29*X^9 +25*X^10. Als nächstes werden die Koeffizienten so modifiziert, dass sie zwischen -q/2 und q/2 liegen, was folgendes Zwischenergebnis liefert: a(X) = 3 - 7*X - 10*X^2 - 11*X^3 + 10*X^4 + 7*X^5 + 6*X^6 + 7*X^7 + 5*X^8 - 3*X^9 - 7*X^10. Danach werden die Koeffizienten noch modulo 3 reduziert und mit Werten zwischen -1 und 1 dargestellt, sodass sich letztendlich a(X) = -X - X^2 + X^3 + X^4 + X^5 + X^7 - X^8 - X^10 ergibt. In der nun folgenden zweiten Polynom-Multiplikation wird das Produkt m(X) = fp(X)*a(X) berechnet, wodurch man m(X) = -1 + X^3 - X^4 - X^8 + X^9 + X^10 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.

Zum Schluss noch ein paar Worte zum Zufallspolynom r(X). Der übliche Weg, ein Polynom mit "zufälligen" Koeffizienten zu erzeugen, ist die Verwendung eines Zufallszahlengenerators bzw. Pseudo-Zufallszahlengenerators, welcher auch bei der Erzeugung von geheimen Schlüsseln zum Einsatz kommt. Um für kryptografische Anwendungen geeignet zu sein, muss ein (Pseudo-)Zufallszahlengenerator eine Reihe von Bedingungen erfüllen; insbesondere dürfen die Zufallszahlen nicht erratbar oder vorhersagbar sein. Streng genommen ist es technisch gar nicht möglich, mit Hilfe einer Software-Prozedur "echte" Zufallszahlen zu erzeugen, da Software-Algorithmen deterministisch sind und somit bei gleichen Anfangsbedingungen immer dieselben Ergebnisse liefern. Deshalb wird für einen echten Zufallszahlengenerator (engl. True Random Number Generator bzw. TRNG) spezielle Hardware benötigt, die unvorhersehbare physikalische Prozesse oder Ereignisse ausnützt, wie beispielsweise thermisches Rauschen in Transistoren und anderen elektronischen Bauteilen, Frequenzschwankungen (Drift) von Oszillatoren, oder Metastabilität bei taktflankengesteuerten Flipflops. Leider gehört solche Zufallszahlen-Hardware nicht zur Standardausrüstung von handelsüblichen PCs und Laptops (und noch weniger zur Ausstattung von IoT-Geräten), weshalb man in der Praxis auf mehr oder weniger unvorhersehbare Systemereignisse wie z.B. Tastatureingaben, Mausbewegungen, oder Empfangszeitpunkte von Netzwerkpaketen zurückgreift. Häufig kommen dabei hybride Lösungen in der Form eines Pseudo-Zufallszahlengenerators (engl. Pseudo Random Number Generator bzw. PRNG) zum Einsatz, welche auf einem deterministischen Algorithmus basieren, als Startwert (engl. Seed) jedoch Systemereignisse verwenden, die als zufällig erachtet werden können. Ein korrekt implementierter Pseudo-Zufallszahlengenerator zeigt praktisch keinerlei statistische Auffälligkeiten, jedoch kann die Entropie der generierten Zufallszahlen nicht größer sein als die Entropie des Startwerts. In Software werden Pseudo-Zufallszahlengenerator üblicherweise mit Hilfe eines linear rückgekoppelte Schieberegisters, einer Blockchiffre (z.B. AES im Counter-Mode), oder einer Hashfunktion (z.B. SHA-2, SHA-3) realisiert. In der NTRU-Spezifikation ist dafür eine spezielle Methode namens Blinding Polynomial Generation Method (BPGM) definiert, die im Prinzip wie ein hashbasierter Pseudo-Zufallszahlengenerator funktioniert, als Startwert jedoch einen Bitstring verwendet, der aus dem Klartext-Polynom Polynom m(X), einem Teil des öffentlichen Schlüssels h(X), einer Zufallszahl, sowie einer Object-ID (OID) zusammengesetzt ist. Abhängig von den verwendeten System-Parametern kann die Anzahl der notwendigen Ausführungen der Hashfunktion zwischen 8 und 15 liegen, was einen nicht unwesentlichen Einfluss auf die Gesamtlaufzeit einer NTRU-Verschlüsselung hat. Neben der Polynom-Arithmetik ist die Hashfunktion die Performance-kritischste Komponente von NTRU, und genau aus diesem Grund wurde sie auch in Assembler implementiert.