Im letzten Blogeintrag wurde erwähnt, dass es vermutlich schon noch 10-15 Jahre dauern wird, bis Quantencomputer so leistungsfähig sind, dass sie eine ernste Gefahr für die Sicherheit der heute verwendeten asymmetrischen kryptografischen Algorithmen (z.B. RSA, Diffie-Hellman, oder Elliptische-Kurven-Kryptografie) darstellen. 10-15 Jahre mag in unserer kurzlebigen Zeit als eine halbe Ewigkeit erscheinen, ist aber in Wirklichkeit eine relativ kurze Zeitspanne, wenn man bedenkt, dass neue kryptografische Algorithmen entwickelt, auf ihre Sicherheit hin überprüft, und dann implementiert sowie in Sicherheitsprotokolle wie TLS integriert werden müssen, bevor man sie dann letztendlich in Betriebssysteme und Anwenderprogramme wie Webbroswer und Email-Clients einbauen kann. Der Übergang von den heute verwendeten kryptografischen Algorithmen auf Post-Quanten-Kryptografie ist zweifellos eine der größten Herausforderungen für das Internet seit dem Übergang von IPv4 auf IPv6, da praktisch die gesamte Public-Key Infrastruktur erneuert werden muss. Das ist auch der Grund, warum sich große Internet-Konzerne wie Google oder Microsoft bereits heute mit post-quanten-kryptografischen Algorithmen beschäftigen und versuchsweise in ihre Produkte integrieren.

Wie ebenfalls im letzten Blogeintrag erwähnt, gibt es einige mathematische Probleme, die selbst für den leistungsfähigsten Quantencomputer nicht effizient lösbar sind, und basierend auf solchen Problemen kann Post-Quanten-Kryptografie realisiert werden. Alle zur Zeit existierenden asymmetrischen Verschlüsselungs- und Signaturverfahren, die in der Lage sind, selbst im Post-Quanten-Zeitalter Sicherheit zu gewährleisten, lassen sich im Wesentlichen in fünf Gruppen einteilen: (1) gitterbasierte Kryptografie, (2) codierungsbasierte Kryptografie, (3) hashbasierte Signaturen, (4) multivariate Kryptografie, und (5) Isogenen-basierte Kryptografie. Um nicht den Rahmen dieses Blogeintrags zu sprengen, wird auf die einzelnen Gruppen nicht näher eingehen, sondern auf einen aktuellen Security-Insider-Artikel verwiesen, in dem es ein paar grundlegende Informationen sowie Links zur weiteren Recherche gibt. Die fünf Gruppen unterscheiden sich teilweise sehr stark was den Rechenaufwand für Verschlüsselung bzw. Signaturen betrifft und auch bezüglich der Schlüssellänge bzw. der Länge einer Signatur. Beides sind wichtige Kriterien für das Projekt QUASIKOM, da die Klein- und Kleinstgeräte im Internet der Dinge nur über wenig Rechenleistung verfügen und auch die Datenübertragungsraten eher niedrig sind. Daher war es am Projektstart notwendig, die am besten geeigneten kryptografischen Algorithmen auszuwählen, und nach sorgfältigem Abwägen aller Vor- und Nachteile, ist die Entscheidung letztendlich auf gitterbasierte Kryptografie gefallen, da sich die Algorithmen aus dieser Gruppe durch hohe Effizienz (d.h. relative geringen Rechenaufwand) in Kombination mit einigermaßen kurzen Schlüssel- und Signaturlängen auszeichnen. Die beiden wichtigsten Vertreter von gitterbasierter Kryptografie sind Ring-LWE und NTRU, wobei das letztgenannte Kryptosystem weiter ausgereift ist, und daher ist die Entscheidung zu Gunsten von NTRU gefallen.

NTRU ist die Kurzbezeichnung einer Klasse von gitterbasierten Kryptosystemen, mit denen sich sowohl asymmetrische Verschlüsselung (NTRUEncrypt) als auch digitale Signaturen (NTRUMLS) realisieren lassen. NTRUEncrypt wurde vor über 20 Jahren von drei Mathematikern an der Brown University entwickelt und dann über eine eigens für diesen Zweck gegründete Firma kommerziell verwertet. Im Juni 2000 wurde den Entwicklern ein Patent für NTRUEncrypt erteilt, welches der aktuelle Rechteinhaber (die amerikanische Firma Security Innovation) jedoch seit März dieses Jahres unter einer Creative-Commons-Lizenz zur Verfügung stellt. Somit kann NTRUEncrypt ohne patentrechtliche Bedenken in Open-Source-Projekten wie QUASIKOM verwendet werden. NTRUEncrypt ist zur Zeit das einzige Post-Quanten-Kryptosystem, welches einen Standardisierungsprozess durchlaufen ist, nämlich jenem von IEEE, und dadurch ist NTRUEncrypt Teil des IEEE Standard 1363.1-2008. Auf der deutschsprachigen Wikipedia Seite über NTRUEncrypt sind sowohl das Patent als auch der IEEE Standard erwähnt, jedoch nicht dass NTRUEncrypt jetzt unter einer Creative-Commons-Lizenz steht. Außerdem kann man auf der Wikipedia Seite lesen, dass NTRUEncrypt "bisher nicht so gut untersucht wie gebräuchlichere Verfahren (z.B. RSA)" ist. Das stimmt zwar (und hat teilweise auch patentrechtlichen Gründe), trifft aber in einem noch größeren Ausmaß auf alle anderen Post-Quanten-Kryptosysteme zu.

Da NTRUEncrypt eine zentrale Rolle im Projekt QUASIKOM einnimmt, wird es noch in einigen zukünftigen Blogeinträgen ein wichtiges Thema sein. Ein wesentlicher Teil des Projekts ist nämlich, NTRUEncrypt zu implementieren, und zwar so, dass es auf Klein- und Kleinstgeräten im Internet der Dinge lauffähig ist. Ein typisches Beispiel für solche Geräte sind drahtlose Sensorknoten, die oft nur mit einem 8 oder 16-bit Mikrocontroller ausgestattet sind, und daher nur über sehr geringe Rechenleistung und wenig RAM verfügen (zumindest verglichen mit einem herkömmlichen PC). Um die Funktionsweise von NTRUEncrypt der netidee Community ein wenig näher zu bringen, habe ich einen "Bottom-Up" Ansatz gewählt, d.h. ich werde zuerst die wichtigsten Komponenten erklären und wie diese im Projekt implementiert wurden bzw. werden, und dann in nachfolgenden Blogeinträgen wie damit konkret eine NTRUEncrypt Ver- und Entschlüsselung ausführt werden kann. Im weiteren Verlauf dieses Blogeintrags wird auf die grundlegenden arithmetischen Operationen von NTRUEnrypt etwas näher eingehen. Solche arithmetischen Operationen kommen in allen asymmetrischen kryptografischen Algorithmen vor und bestimmen zu einem wesentlichen Teil, wie effizient ein Algorithmus ist und wie gut er sich für Kleingeräte mit wenig Rechenleistung eignet. Beim häufig verwendeten (jedoch nicht post-quanten-sicheren) RSA Algorithmus ist die grundlegende arithmetische Operation eine Modulo-Exponentiation, welche sich wiederum über eine Reihe von Modulo-Multiplikationen realisieren lässt, wobei die involvierten Operanden aus Sicherheitsgründen eine Länge von mindestens 1024 Bit haben müssen. Bei asymmetrischen kryptografischen Algorithmen, die auf elliptischen Kurven basieren (und ebenfalls mit einem Quantencomputer geknackt werden können), ist die grundlegende arithmetische Operation die Addition von Kurvenpunkten, welche wiederum durch arithmetische Operationen (z.B. Addition, Multiplikation) in einem endlichen Körper realisiert werden kann.

Die grundlegende arithmetische Operation bei NTRUEncrypt ist die Multiplikation in einem speziellen mathematischen Gebilde, dem sogenannten Ring der Faltungspolynome vom Grad N, welchen man mit der Notation R = Zq[X]/(X^N-1) beschreiben kann. Die Elemente eines solchen Rings sind Polynome mit einem Grad von maximal N-1, wobei die Koeffizienten wiederum ganze Zahlen zwischen 0 und q-1 sind. Um ein ausreichendes Maß an Sicherheit zu gewährleisten, wird typischerweise ein Grad von N = 439 verwendet und q auf 2048 gesetzt. Somit haben die Polynome, mit denen in NTRUEncrypt gerechnet wird, einen Grad von bis zu 438 und Koeffizienten zwischen 0 und 2047. Eine Multiplikation von zwei Polynomen im Ring R wird auch als "Faltung" bezeichnet, daher stammt der Begriff der Faltungspolynome. So eine Faltung ist im wesentlichen eine gewöhnliche Polynom-Multiplikation, jedoch mit zwei Besonderheiten. Wenn man nämlich zwei Polynome a(X) und b(X) vom Grad N-1 miteinander multipliziert, bekommt man als Ergebnis r(X) = a(X)*b(X), wobei r(X) wieder ein Polynom ist, jedoch mit einem (maximalen) Grad von 2N-2. Somit würden die Polynome mit jeder Multiplikation länger werden, was natürlich nicht praktisch ist. Um das zu verhindern, wird das erhaltene Produkt r(X) modulo dem Polynom X^N-1 reduziert, d.h. man hat dann als Ergebnis den Rest wenn man r(X) durch X^N-1 dividiert. Polynom-Divisionen sind im Allgemeinen recht komplizierte Operationen, nicht jedoch man so wie in NTRUEncrypt das Polynom X^N-1 als Divisor verwendet. In diesem Fall erhält man den Rest der Division einfach in dem man die obere Hälfte des Produkts r(X), d.h. alle Koeffizienten von r(X) mit einem Grad der größer oder gleich N ist, zur unteren Hälfte von r(X) addiert, d.h. zu den Koeffizienten vom Grad 0 bis N-1. Ein zweites Problem ist dass bei einer normalen Polynom-Multiplikation nicht nur der Grad sondern auch die Koeffizienten immer größer werden, d.h. wenn man zwei Koeffizienten im Intervall zwischen 0 und 2047 miteinander multipliziert, dann liegt das Produkt im Intervall zwischen 0 und 2047^2 = 4190209. Somit würde sich die Bitlänge der Koeffizienten bei jeder Multiplikation ungefähr verdoppeln, was wiederum nicht praktisch ist. Und auch bei diesem Problem behilft man sich mit einer Modulo-Reduktion, d.h. man reduziert das Produkt von zwei Koeffizienten modulo q = 2048. Eine Reduktion einer Zahl x modulo 2048 ist ganz besonders einfach durchzuführen, da 2048 gleich 2^11 ist, und man somit in der Binärdarstellung von x nur alle Bits ab dem zwölften Bit auf 0 setzen muss. Durch diese beiden Tricks wird erreicht, dass das Ergebnis einer Multiplikation von zwei Elementen des Rings R einen maximalen Grad von N-1 hat, und dass seine Koeffizienten kleiner als 2048 sind.

Bei NTRUEncrypt kann man noch einen weiteren Trick anwenden, um die Effizienz der Polynom-Multiplikation zu steigern. Es ist nämlich möglich, eines der beiden Polynome, die miteinander multipliziert werden müssen, so zu wählen, dass seine Koeffizienten nur die Werte 0, 1 und -1 haben. Dadurch lässt sich eine Polynom-Multiplikation über Additionen bzw. Subtraktionen von Koeffizienten realisieren, d.h. es müssen keine Multiplikationen von Koeffizienten mehr ausgeführt werden. Das ist natürlich besonders nützlich wenn man NTRUEncrypt für kleine 8 oder 16-bit Microcontroller implementiert, da diese normalerweise nur mit einem langsamen Multiplizierer ausgestattet sind, und somit für die Exekution einer Multiplikation relativ viele Taktzyklen benötigen. Eine Implementierung der Polynom-Multiplikation mit den drei erwähnten Tricks befindet sich im Github Repository des Projekts QUASIKOM, und zwar in Form der Funktion ring_mul_sparse(), welche sich in der Datei ring_arith.c im Unterverzichnis src/ntru befindet. Da der Source Code nicht sonderlich kompliziert aussieht, sollte man meinen, dass ein optimierender C Compiler in der Lage ist, effizienten Binärcode daraus zu generieren. Nach einer Inspektion des vom Compiler erzeugten Assembler-Outputs wurde jedoch sehr schnell klar, dass dies leider nicht der Fall ist. Deshalb wurden alle performance-kritischen Teile der Polynom-Multiplikation auch in Assembler implementiert, wodurch sich die Ausführungszeit um fast 30% verringert hat. Die Assembler-Source-Codes für 8-bit AVR Prozessoren befinden sich im Unterverzeichnis avrasm. Auf einem 8-bit AVR ATmega128 Prozessor beträgt die Ausführungszeit einer Polynom-Multiplikation mit den Parametern N = 439 und q = 2048 etwas mehr als 250000 Taktzyklen, was bei einer typischen Taktfrequenz von 8 MHz ungefähr 32 Millisekunden entspricht. Das hört sich recht wenig an, jedoch muss dabei berücksichtigt werden, dass die Polynom-Multiplikation nur eine Komponente von NTRUEncrypt ist. Die weiteren Komponenten, und wie sich diese auf die gesamte Ausführungszeit einer NTRUEncrypt Verschlüsselung auswirken, werden dann in den weiteren Blogeinträgen erklärt.

Der nächste Blogeintrag wird am 30. November online gehen. Dieser 30. November 2017 ist nämlich ein ganz spezielles Datum für Alle die am Thema Post-Quanten-Kryptografie interessiert sind. Warum das so ist wird dann nächste Woche aufgeklärt. Stay Tuned!