Gitterbasierte Kryptografie

Wenn du im Internet Daten verschickst, werden sie verschlüsselt: aus dem Text wird ein Zahlensalat, den nur der Empfänger zurückrechnen kann. Damit das sicher ist, braucht man eine Rechenaufgabe, die leicht in eine Richtung geht und praktisch unmöglich zurück. Gitterbasierte Kryptografie benutzt dafür Punktgitter. Ein Gitter ist ein regelmäßiges Muster aus Punkten im Raum, ähnlich den Kreuzungen von Millimeterpapier, nur nicht in zwei, sondern in hunderten Richtungen gleichzeitig. Die schwere Aufgabe lautet: Gegeben ein beliebiger Punkt im Raum, finde den nächstgelegenen Gitterpunkt. In wenigen Richtungen ist das einfach, in hunderten Richtungen kennt niemand ein schnelles Verfahren. Genau diese Lücke zwischen leicht und unmöglich macht das Verschlüsseln möglich.

Der Grund für die weltweite Umstellung

Fast alle heute verwendeten Verfahren im Internet beruhen auf zwei Aufgaben: dem Zerlegen sehr großer Zahlen in ihre Faktoren und einer ähnlich gebauten Aufgabe mit Potenzen. Beide sind für normale Computer aussichtslos schwer. Für einen Quantencomputer, also einen Rechner, der auf quantenphysikalischen Effekten statt auf normalen Schaltern beruht, sind sie es nicht. Der Mathematiker Peter Shor zeigte 1994 einen Rechenweg, der beide Aufgaben auf so einer Maschine schnell löst.

Solche Quantencomputer existieren bisher nur in kleinen, fehleranfälligen Versionen. Trotzdem ist die Gefahr real, und zwar aus einem unangenehmen Grund. Ein Angreifer kann verschlüsselten Datenverkehr heute aufzeichnen und jahrzehntelang speichern. Sobald die passende Maschine existiert, entschlüsselt er das Archiv rückwirkend. Fachleute nennen das „jetzt ernten, später entschlüsseln“. Für Krankenakten, Staatsgeheimnisse oder Bankdaten ist das ein ernstes Problem.

Bei Gittern kennt bisher niemand einen Quanten-Rechenweg, der die Aufgabe entscheidend beschleunigt. Die US-Behörde NIST hat deshalb nach einem jahrelangen offenen Wettbewerb 2024 mehrere Verfahren zum Standard erklärt. Die wichtigsten davon, Kyber zum Schlüsselaustausch und Dilithium für digitale Signaturen, sind gitterbasiert.

Rauschen als Schutzschild

Der zentrale Trick heißt „Learning with Errors“, also Lernen mit Fehlern. Man stellt viele einfache Gleichungen auf, etwa der Art: drei mal die erste Geheimzahl plus fünf mal die zweite ergibt einen bestimmten Wert. Aus genügend solchen Gleichungen könnte jeder Schüler die Geheimzahlen ausrechnen. Nun wird auf jedes Ergebnis absichtlich ein kleiner Zufallsfehler addiert, ein Rauschen.

Damit bricht das übliche Auflösen zusammen. Jeder Rechenschritt vergrößert den Fehler, und am Ende bleibt nur Unsinn übrig. Wer dagegen die Geheimzahlen kennt, kann das Rauschen wegrunden, weil er weiß, wo das Ergebnis ungefähr liegen muss. Der geheime Schlüssel ist also das Wissen, welche Gitterrichtungen kurz und übersichtlich sind. Der öffentliche Schlüssel beschreibt dasselbe Gitter, aber in verzerrten, langen Richtungen, mit denen man nichts anfangen kann.

Praktisch rechnet man nicht mit einzelnen Zahlen, sondern mit Polynomen, also Ausdrücken wie x hoch drei plus zwei x. Das erlaubt schnelle Rechentricks und hält die Schlüssel handlich. Ein Kyber-Schlüssel ist rund 800 bis 1600 Byte groß. Das ist etwa zwanzigmal mehr als bei den alten Verfahren, dafür ist die Rechenzeit oft sogar kürzer. Ein verbreiteter Irrtum ist übrigens, dass hier Quantenphysik zum Einsatz kommt. Die Verfahren laufen auf ganz normalen Computern, sie sollen nur Quantenangriffen widerstehen.

Wo Kyber und Dilithium schon laufen

Du benutzt gitterbasierte Kryptografie sehr wahrscheinlich täglich, ohne es zu merken. Google hat Kyber in den Chrome-Browser eingebaut, Apple sichert damit die Nachrichten in iMessage, und der Messenger Signal nutzt es ebenfalls. Meist läuft das „hybrid“: Es wird gleichzeitig alt und neu verschlüsselt. Sollte im neuen Verfahren eine Schwäche gefunden werden, schützt noch die bewährte Methode.

In den Wirtschaftsnachrichten tauchen die Begriffe unter dem Schlagwort Post-Quanten-Kryptografie auf. Banken, Rechenzentren und Behörden stehen vor teuren Umstellungsprojekten, weil Verschlüsselung in unzähligen Geräten und Programmen steckt. Das deutsche BSI und US-Behörden nennen die frühen 2030er Jahre als Zielmarke. Wer Chips oder Sicherheitssoftware herstellt, verdient daran, und entsprechende Firmen werden an der Börse aufmerksam beobachtet.

Zur Abgrenzung: Gitterverfahren sind nicht dasselbe wie Quantenkryptografie. Diese verschickt einzelne Lichtteilchen über Glasfaser und braucht spezielle Hardware. Gitterbasierte Verfahren sind reine Software und lassen sich per Update verteilen. Genau deshalb sind sie der Weg, für den sich die Industrie entschieden hat.