Gitterkryptographie

Wenn du eine Nachricht so verpackst, dass nur der Empfänger sie lesen kann, brauchst du eine Rechenaufgabe, die für Außenstehende praktisch unlösbar ist. Gitterkryptographie benutzt dafür Gitter: regelmäßige Punktmuster im Raum, ähnlich den Ecken eines unendlich großen Karogitters oder Kristalls. Solche Gitter kann man nicht nur flach auf Papier aufspannen, sondern auch in Räumen mit hunderten oder tausenden Richtungen. Und dort ist eine harmlos klingende Frage extrem schwer zu beantworten: Welcher Gitterpunkt liegt einem beliebig vorgegebenen Punkt am nächsten? Diese Schwierigkeit ist der Kern der Verfahren. Sie werden auch gitterbasierte Verfahren genannt und gehören zur Kryptographie, also der Wissenschaft vom Verschlüsseln.

Die Versicherung gegen den Quantencomputer

Fast alles, was heute im Internet verschlüsselt wird, hängt an zwei alten Rechenaufgaben. Die eine ist, eine sehr große Zahl in ihre Primfaktoren zu zerlegen. Die andere ist eng verwandt und heißt diskreter Logarithmus. Normale Computer scheitern daran zuverlässig. Ein ausreichend großer Quantencomputer könnte beide Aufgaben dagegen in überschaubarer Zeit lösen, mit einem seit 1994 bekannten Verfahren von Peter Shor.

Für Gitteraufgaben ist bis heute kein solcher Quanten-Trick bekannt. Deshalb zählt man die Gitterkryptographie zur Post-Quanten-Kryptographie, also zu den Verfahren, die auch nach dem Bau leistungsfähiger Quantencomputer halten sollen. Die US-Behörde NIST hat 2022 nach einem mehrjährigen Wettbewerb ihre ersten Empfehlungen bekanntgegeben. Die wichtigsten davon, heute Kyber und Dilithium genannt, sind gitterbasiert.

Der Umbau ist dringlicher, als er klingt. Ein Angreifer kann verschlüsselte Daten heute mitschneiden, speichern und erst in zehn oder zwanzig Jahren entschlüsseln. Fachleute nennen das „harvest now, decrypt later“, also erst sammeln, später knacken. Für Krankenakten, Bankdaten oder Staatsgeheimnisse ist das ein echtes Problem.

Rauschen als Schutzschild

Die meisten Gitterverfahren beruhen auf einer Aufgabe mit dem Namen „Learning with Errors“. Man stellt sich ein großes Gleichungssystem vor, wie man es aus der Schule kennt, nur mit tausenden Unbekannten. Ohne Störung wäre es leicht zu lösen. Bei der Verschlüsselung wird aber auf jede Zeile ein kleiner, zufälliger Fehler addiert. Dieses absichtliche Rauschen macht das System praktisch unlösbar, solange man den geheimen Schlüssel nicht kennt.

Der geheime Schlüssel ist eine besonders günstige Beschreibung des Gitters, aus kurzen und übersichtlichen Richtungsvektoren. Wer sie besitzt, findet den nächsten Gitterpunkt sofort und rechnet das Rauschen wieder heraus. Der öffentliche Schlüssel beschreibt dasselbe Gitter, aber mit lang und schief gewählten Richtungen. Damit kann jeder verschlüsseln, doch niemand kommt zurück. Das ist der Unterschied zwischen einem Stadtplan mit Straßennamen und einer Liste willkürlich verdrehter Wegbeschreibungen.

Ein häufiger Irrtum ist, dass Gitterverfahren beweisbar sicher seien. Bewiesen ist nur ein Zusammenhang: Wer das Verfahren bricht, könnte auch das allgemeine Gitterproblem lösen. Dass dieses Problem wirklich schwer ist, bleibt eine gut geprüfte Annahme. Praktisch fallen dabei größere Schlüssel an als bei den alten Verfahren, oft einige Kilobyte statt einiger hundert Byte. Dafür ist das Rechnen selbst schnell, weil überwiegend addiert und multipliziert wird.

Kyber steckt schon in deinem Browser

Die Umstellung läuft bereits, meist unsichtbar. Google Chrome und Firefox bauen beim Aufruf einer Webseite eine Verbindung auf, die Kyber mit einem klassischen Verfahren kombiniert. Apple hat 2024 für iMessage einen gitterbasierten Schlüsselaustausch eingeführt, Signal ebenfalls. Man kombiniert alt und neu absichtlich: Falls in einem der beiden Verfahren eine Schwäche gefunden wird, schützt das andere weiter.

In Wirtschaftsnachrichten begegnet dir das Thema unter Schlagwörtern wie Post-Quanten-Migration oder Krypto-Agilität. Banken, Cloud-Anbieter und Chiphersteller schätzen den Aufwand auf Jahre, weil Verschlüsselung in unzähligen Geräten fest verbaut ist. Behörden setzen Fristen: Die USA wollen kritische Systeme bis etwa 2035 umgestellt haben. Für Firmen entsteht daraus ein Markt für Beratung, Prüfwerkzeuge und neue Hardware.

Wichtig zur Abgrenzung: Gitterkryptographie ist keine Quantentechnologie. Sie läuft auf ganz normalen Computern und Smartphones. Verwechselt wird sie oft mit Quantenkryptographie, die Lichtteilchen über Glasfaser nutzt und spezielle Geräte braucht. Gitterverfahren sind der praktische Weg, Quantenschlüsselverteilung eher ein Nischenprodukt.