Kyberkristalle geben dem Lichtschwert seine Farbe – das sollte allgemein bekannt sein. Darüber hinaus handelt es sich bei CRYSTALS-Kyber um ein vom NIST empfohlenes asymmetrischen Verfahren, das auch im Zeitalter der Quantencomputer noch sicher ist. An dieser Stelle ist einzuräumen, dass wir mit der Aussage noch vorsichtig sein müssen. Jüngst wurden Seitenkanalangriffe bekannt und zur Berechnung der Sicherheit gab es einen wirklich dummen Rechenfehler. Im April 2024 stellte sich kurzzeitig Panik ein: in einem Papier wurde Kyber als gebrochen erklärt. Allerdings wurde die Aussage von den Autoren recht zügig widerrufen.

WolfSSL hat mittlerweile Kyber integriert. Auch Amazon Web Services scheint Kyber mittlerweile zu verwenden. Es ist meine feste Erwartung, dass Kyber auch in TLS 1.4 Einzug halten wird. Im Signal-Protokoll ist es schon produktiv im Einsatz. Im Februar 2024 wurde von Apple verkündet, dass Kyber für IMessage eingesetzt werden soll.

Ich habe mir deshalb die Arbeit gemacht, Kyber genauer zu betrachten und so aufzubereiten, dass es ohne tiefgehende mathematischen Kenntnisse nachvollziehbar wird. Achso, falls die Frage aufkam: Ja, die Anspielung an Star Wars war bei der Namenswahl von den Entwicklern beabsichtigt.

Hinweis: Im Folgenden wird eine vereinfachte Form von Kyber erläutert, um das Konzept und die Falltür leichter verständlich zu machen. Eine noch detailliertere Darstellung findet sich in diesem Blogartikel.

Die Falltür

Der erste Schritt, um eine asymmetrische Verschlüsselung zu verstehen, ist die Betrachtung der Falltürfunktion. Das ist die Funktion, die sich in eine Richtung leicht berechnen lässt, jedoch nur schwer umzukehren ist. Genauer soll die Umkehrung, also die Entschlüsselung, nur mit dem Wissen des privaten Schlüssels möglich sein. Bei Kyber besteht die Falltür aus einem Problem, welches eigentlich leicht zu verstehen ist, jedoch auch für Quantencomputer ein schwieriges Problem darstellen soll: Learning with Errors (LWE).

Wir können uns LWE mal ganz langsam über simple Grundlagen aus der linearen Algebra nähern. Das Produkt einer Matrix A mit einem Vektor s ergibt einen Vektor t; hier mit entsprechendem Berechnungsbeispiel.

Nicht ganz neu ist, dass wir (je nach Matrix A) die Operation umkehren können. Mit dem Gauß-Verfahren gelingt dies mit polynomieller Laufzeitkomplexität. Mit A^-1 wird hier die Umkehrung durchgeführt, also das s aus A und t berechnet.

Wir erweitern nun die ursprüngliche Berechnung um eine weitere additive Komponente: den Fehler e. Nach der Multiplikation von Matrix und Vektor addieren wir diesen Fehler hinzu.

Die Umkehrung hierfür ist jedoch ein schwieriges Problem. Es ist die Schwierigkeit, aus der Gleichung (A und t) mit unbekanntem Fehler e die ursprüngliche Variable s zu bestimmen. Ein Teil des Problems ist, dass es bei unbekanntem s und e mehrere Möglichkeiten gibt, die Gleichung zu erfüllen. Es gibt also nicht länger eine eindeutige Lösung, sondern es kommen verschiedene (s,e)-Kombinationen in Frage.

Wir sind aber noch nicht ganz fertig, denn für LWE kommt noch ein weiteres „Problem“ hinzu. Wir würden es auch vermissen, wenn es fehlen würde: eine Primzahl. Somit werden die Komponenten der Matrizen und Vektoren (und die Berechnungsergenisse) modulo q gerechnet.

Bei diesen kleinen Zahlen scheint das mit dem Modulo eher unsinnig. Daher werden wir A und q für die weiteren Beispiele etwas vergrößern. Wir setzen daher q auf 47 und nehmen auch für A und s neue Werte. Kyber schreibt vor, dass e und s keine großen Werte aufweisen sollen und wir werden später auch leicht nachvollziehen können, weshalb das so ist. Bitte einen kurzen Moment Zeit nehmen, um die Berechnung nachzuvollziehen, die neuen Werte werden auch bis zum Ende beibehalten.

Tatsächlich ist damit die Falltür für Kyber schon vollständig erläutert. Die Matrix A und das Ergebnis t stellen den öffentlichen Schlüssel dar. Der Vektor s ist der private Schlüssel. Bei e handelt es sich um einen Fehler der normalverteilt gewürfelt wird. Für s und e besteht bei Kyber die Einschränkung, dass die Werte nicht zu hoch sein dürfen. Die Primzahl q ist Teil des Verfahrens und ändert sich nicht: im „echten“ Kyber ist q immer 3329.

Merke: (A, t) ist der öffentliche Schlüssel, bei s handelt es sich um den geheimen Schlüssel und e ist ein Fehlervektor.

Jetzt, wo das Schlüsselmaterial generiert ist, kann dies übermittelt werden. In unserem Fall ist der Sender die Person, die gerne eine Nachricht übermitteln möchte, und der Empfänger soll diese im Anschluss entschlüsseln. Somit hat der Empfänger das Schlüsselmaterial generiert und übermittelt dies dem Sender.

Bevor es weitergeht, folgt an dieser Stelle noch ein kleiner Disclaimer. Die hier vorgestellte Falltür basiert auf dem Learning with Errors (LWE) Problem. Bei Kyber kommt allerdings Module Learning with Errors M-LWE zum Einsatz. Das ändert nichts daran, dass es sich bei A um eine Matrix und bei s, e und t um Vektoren handelt. Allerdings sind die Komponenten der Matrizen und Vektoren keine Elemente aus einem Restklassenring, sondern es sind Polynome aus einem Polynomring. Dies bedeutet, dass Addition (trivial) und Multiplikation (etwas schwieriger aufgrund Polynomdivision) in dieser algebraischen Struktur durchgeführt wird. Das ist für die Verschlüsselung leider nicht ganz unwichtig, wenn mehr als nur ein Bit verschlüsselt werden soll. Aber an dieser Stelle wollte ich von diesem Polynomring zunächst abstrahieren. Aufgrund der Abstraktion können wir deshalb nur ein Bit verschlüsseln, was uns aber erstmal genügen muss. Wem das doch nicht genügt, bekommt in diesem Blogartikel Kyber auf Basis von M-LWE näher erläutert.

Der Einsatz eines Polynomrings ändert im Übrigen nichts daran, dass alle Koeffizienten Modulo q gerechnet werden. Primzahlen sind und bleiben wichtig: auch für Verschlüsselungen im Zeitalter der Quantencomputer.

Verschlüsselung

Wir haben nun erfolgreich Schlüsselmaterial erzeugt. Der Sender, der eine Nachricht verschlüsseln möchte, wird nun im Folgenden zwei Komponenten erzeugen: u und v. Wir wissen noch nicht, wie diese aussehen. Aber vermutlich lässt sich schon erahnen, dass eine dieser Komponenten die Nachricht m enthalten wird. Spoileralarm: In v ist die verschlüsselte Nachricht enthalten und u wird benötigt um diese, mit Kenntnis des privaten Schlüssels s, beim Empfänger auszupacken. Wir können also v als ein gut verpacktes DHL-Paket mit unserer Nachricht ansehen und mit u und s können wir den Karton öffnen.

Bevor wir uns mit u und v befassen, müssen wir zunächst über die Nachricht m sprechen. Eine Nachricht besteht üblicherweise aus mehreren Bits. Mit der hier betrachteten Vereinfachung (ohne Polynomring) können wir leider nur genau ein Bit verschlüsseln. Das ist natürlich weder sinnvoll noch sicher, aber einfacher zu verstehen. Manchmal genügt auch ein einfaches Ja oder Nein, oder?

Um in Kyber eine Nachricht zu übermitteln, muss diese vorher skaliert werden. Wir haben uns bereits oben auf ein q=47 geeinigt. Angenommen, wir möchten ein „Ja“ verschlüsseln, dann wählen wir für m eine Zahl oberhalb der 24 (das ist q/2 aufgerundet). Wir kodieren eine 1, also ein „Ja“, z. B. mit m=31. Hätten wir hingegen eine 0, also ein „Nein“, wäre z. B. m=11 möglich gewesen. Große Zahl ist 1, kleine Zahl ist 0 und es ist erstmal egal, ob 30, 31 oder 32 für das Ja steht. Das passiert auch in Kyber mit jedem Bit der Nachricht. Warum wir das machen, wird später erläutert. Unser „Ja“ wurde also mit m=31 kodiert – wenn wir von der Nachricht sprechen, ist also die 31 gemeint und steht für ein Ja.

Zur weiteren Verschlüsselung werden ein Vektor r, ein Vektor e₁ und ein Skalar e₂ mit zufälligen Werten benötigt, allerdings: Wie oben bei e und s sollen es kleine Koeffizienten sein, also in diesem Beispiel mit 1, 2 oder 3. An dieser Stelle nochmal ganz deutlich: Das sind zufällig gewählte Werte, wir können diese auch unbeschadet anders wählen!

Mir ist bewusst, dass das jetzt ein ganzer Haufen Buchstaben sind. A, s, e, t, u, v, r… damit könnte man in Scrabble schon viele Punkte erzielen! Es ist ohne Frage schwierig, hier den Überblick zu behalten. Die gute Nachricht ist: r, e₁ und e₂ können wir unmittelbar nach der Verschlüsselung wieder vergessen. Diese Werte brauchen wir dann nicht mehr und haben somit nur einen kurzen Auftritt.

Nun sind wir bereit, um uns u und v genauer anzusehen. Das schmerzt möglicherweise auf den ersten Blick, wird dann aber mit dem zweiten Blick besser. Beginnen wir mit u.

Das „^T“ im Exponenten beschreibt hier die transponierte Matrix. Transponieren bedeutet, dass wir die Matrix einmal an der Hauptdiagonalen spiegeln: Aus Zeilen werden Spalten und umgekehrt. Schauen wir uns das an:

Zugegeben, bei einer 2×2-Matrix ist transponieren nicht so aufregend: Die Hauptdiagonale bleibt unverändert und es tauschen nur zwei Komponenten. Ist halt so!

Um u zu berechnen, müssen wir also die bereits bekannte Matrix A transponieren und mit dem Zufallsvektor r multiplizieren und e₁ addieren. Falls es nicht direkt bemerkt wurde: bei u kommt wieder unsere Falltür ins Spiel, nur mit neuen Werten. Die Falltür wurde also sowohl zur Generierung des öffentlichen Schlüssels benutzt als auch hier zur Verschlüsselung. Warum das A transponiert wurde, wird später noch erläutert.

Wenn man es ganz genau betrachtet, wurde hier das gewürfelte r durch das transponierte A und mit e₁ „verschlüsselt“. Somit ist das r bei Übermittlung nicht mehr sichtbar und ohne Lösung des LWE-Problems auch nicht (einfach) berechenbar.

Jetzt schauen wir uns die zweite Komponente, also das v näher an:

Hierfür wird die t-Komponente aus dem öffentlichen Schlüssel transponiert, mit dem Zufallsfektor r multipliziert und sowohl der Fehler e₂ als auch die Nachricht m aufaddiert. Am Ende, wie immer, modulo q.

Die Struktur ist recht ähnlich wie zuvor, jedoch handelte es sich bei A um eine Matrix und bei t um einen Vektor, der transponiert wird. Das ist auch dringend notwendig, damit das Skalarprodukt auch definiert ist. Schauen wir uns schnell das Berechnungsbeispiel an, denn damit wird die Berechnung schnell klar.

Wir haben nun erfolgreich unsere Nachricht m=31 verschlüsselt und erhalten zur verschlüsselten Übermittlung der Nachricht die 6. Zur Entschlüsselung ist natürlich beides erforderlich: das u und das v.

Sind u und v erfolgreich beim Empfänger angekommen, können wir nun mit der Entschlüsselung der Nachricht starten.

Merke: (u,v) werden vom Sender zum Empfänger übermittelt. Dabei ist v die vom Sender verschlüsselte Nachricht und u enthält erforderliche Informationen zur Entschlüsselung.

Entschlüsselung

Eigentlich ist das Schlimmste schon geschafft. Denn während die Verschlüsselung etwas Arbeit ist, gestaltet sich die Entschlüsselung doch recht einfach. Dabei ist m_neu das Ergebnis der Entschlüsselung. Später wird noch deutlich, weshalb dort m_neu und nicht nur m steht.

Wir transponieren also unseren geheimen Schlüssel s und multiplizieren dies mit dem vom Sender empfangenen Vektor u. Aus dieser Skalarmultiplikation kommt ein Wert heraus, der von v subtrahiert wird. Machen wir das einfach und schauen mal was passiert.

Vielleicht noch kurz zur Erinnerung: Wenn bei Operationen ein Wert kleiner 0 herauskommt, wie hier bei 6-118=-112, wird so häufig q aufaddiert, bis wir wieder in den positiven Bereich kommen. Da -18+(3*47)=29 ist, ist 29 auch das Ergebnis der Operation.

Nur wenn wir s transponieren, bekommen wir das Skalarprodukt errechnet. Aber… machen wir damit nicht einiges kaputt, wenn wir das einfach transponieren? Nein, denn in v steckt ja auch das transponierte t und im transponierten t steckt impliziert auch das (dann transponierte) s. Das schauen wir uns im nächsten Abschnitt aber noch genauer an.

Wir haben nun erfolgreich die übermittelte Nachricht entschlüsselt. Aber… was ist denn das? Das m_neu=29 weicht ja von der ursprünglichen Nachricht m=31 ab? Alles falsch? Nein! Das ist richtig und erwartet. Immerhin haben wir mit r, e, e₁ und e₂ mehrere „Fehler“ in der Berechnung, die am Ende nicht alle wieder entfernt werden können. Wir haben für diese Fehler jedoch stets kleine Koeffizienten gewählt. Daher ist hier die Erwartung, dass sich das Ergebnis auch nur leicht verschiebt. Bei Kyber kommen wir deshalb nicht exakt auf den ursprünglich verwendeten Wert. Aber dadurch, dass es eine „kleine“ oder eine „große“ Zahl ist, können wir das ursprüngliche Bit wiederherstellen.

In der folgenden Tabelle sehen wir, mit welchem Klartext m (vor der Verschlüsselung) wir nach der Verschlüsselung landen.

Wenn wir vor der Verschlüsselung einen niedrigen Wert für „Nein“ und einen hohen Wert (wie hier die 31) für „Ja“ wählen, erhalten wir nach der Entschlüsselung auch wieder niedrige und hohe Werte zurück, die wir anschließend auf die Aussagen mappen können. Wir haben somit einen Entscheidungsbereich für das jeweilige Bit. An der Tabelle 1 können wir sehen, dass wenn wir ein „Nein“ mit 11 kodiert und verschlüsselt hätten, wir die 9 als Ergebnis bekommen und dementsprechend einem „Nein“ zuordnen würden.

Aus diesem Grund wird auch klar, weshalb wir in dieser vereinfachten Version mit einem Koeffizienten auch nur ein Bit ver- und entschlüsseln können. In Kyber verwenden wir einfach mehrere diese Werte hintereinander in einem Polynom, um mehrere Bits (256) auf einen Schlag zu verarbeiten.

Korrektheit

Der beste Weg die Korrektheit des Verfahrens nachzuvollziehen zu können, ist am Ende anzufangen und rückwärts die Variablen zu substituieren. Um die Darstellung zu vereinfachen, verzichte ich auf das „mod q“ – das darf einfach mitgedacht werden. Wir starten daher bei der Entschlüsselung und ersetzen jeweils u und v durch die vorherigen Berechnungen.

Wir sind noch nicht ganz fertig, denn auch das t (welches in u enthalten ist) haben wir ganz am Anfang aus A, s und e berechnet:

Wir ersetzen nun entgültig v und u und schauen uns das Ergebnis an, ohne dabei den Überblick zu verlieren.

Nun stellt sich die Frage, was man hier alles vereinfachen kann. Zum einen kann man sich die Rechengesetze zur transponierten Matrix ansehen. Ich fasse es kurz zusammen:

• (A + B)^T = A^T + B^T
• (A * B)^T = B^T * A^T

Auf dieser Basis können wir die erste Klammer, das ursprüngliche t, ganz einfach umwandeln:

Zum anderen können wir diese Klammer mit dem r ausmultiplizieren, welches unmittelbar daneben steht.

Jetzt schauen wir uns mal die rechte Seite an. Bitte daran denken das Vorzeichen vor dem s zu berücksichtigen!

Also multiplizieren wir die rechte Seite aus wie bekannt.

Da wir jetzt fertig sind, können wir alle Klammern entfernen und uns das Ergebnis anschauen.

Eine ganze Menge Zeug. Aber wie in der Schule schaut man einfach, ob ein Produkt doppelt mit unterschiedlichem Vorzeichen vorkommt. Das ist glücklicherweise der Fall!

So können wir erkennen, dass wir die Matrix A vollständig entfernt bekommen. Aber es wird auch sichtbar, dass einiges übrig bleibt. Wir können mal überlegen, ob wir hier noch etwas verbessern können.

Zur Erinnerung: e hat zwar der Empfänger gewählt, aber das r stammt vom Sender. Das e₂ stammt auch vom Sender und können wir als Empfänger nicht entfernen. Zwar kennen wir als Empfänger den privaten Schlüssel s, jedoch stammt e₁ vom Sender und ist daher unbekannt. An den Farben lässt sich leicht erkennen, dass wir hier als Empfänger nichts mehr tun können. Daher sind wir hier fertig.

An dieser Stelle sollte klar werden, warum die Koeffizienten für die Fehler e, e₁, e₂ und r klein gewählt wurden. Sie verbleiben nach der Verschlüsselung noch im Ergebnis und können nicht restlos entfernt werden. Im Extremfall kann dies tatsächlich dazu führen, dass die Nachricht nicht korrekt entschlüsselt werden kann. Das wurde jedoch im Verfahren bereits berücksichtigt, sollte aber nur selten eintreten.

Epilog

Das war’s. Wir haben erfolgreich ein „Ja“ verschlüsselt und konnten (anhand Tabelle 1) auch sehen, dass es mit einem „Nein“ auch funktioniert hätte. Wir haben mehrfach die Falltür sehen können, sowohl bei der Schlüsselerzeugung, als auch zur Berechnung von u und v.

Es gibt tatsächlich noch einiges zu Kyber zu berichten – z. B. wie sich die Sicherheitsstufen unterscheiden. Wer gerne noch eine Ebene tiefer vordringen möchte, kann sich den Baby Kyber von Ruben Gonzalez ansehen, in dem auch genauer auf die Berechnungen im Polynomring eingegangen wird. Natürlich weise ich auch gerne auf das Originalpapier hin.

Ergänzung: Ich habe diese vereinfachte Kyber-Variante nun auch in einem Excel-Dokument zusammengefasst und in diesem Beitrag veröffentlicht.