Fieberhaft wird derzeit an der Entwicklung von Quantenrechnern gearbeitet. Unter anderem unter Beteiligung des IBM-Forschungslabors in Rüschlikon bei Zürich werden entsprechende Computer mit immer mehr Leistung bereitgestellt. Aktuell ist ein System mit 127 Quantenbits, kurz Qubits, im Einsatz. Bis Ende Jahr will IBM Research einen Rechner mit 433 Qubits in Betrieb nehmen. In den nächsten Jahren soll sich diese Zahl verzehnfachen. 2025 wird dann mit Kookaburra ein Quantencomputer mit 4148 Qubits an den Start gehen, sofern alles nach Plan läuft.

Das ist eine atemberaubende Entwicklung, wenn man bedenkt, dass jedes zusätzliche einzelne Qubit für eine Verdoppelung der Rechenleistung steht und damit das Mooresche Gesetz aus der klassischen Computertechnik alt aussehen lässt. Dieses besagt nämlich, dass jede Verdoppelung der Transistoren auf einem Chip eine Verdoppelung der Leistungsfähigkeit darstellt.

Quantencomputer werden somit sehr schnell sehr leistungsfähig. Das hat riesige Vorteile. So wird von den Rechnern erwartet, dass sie bislang unlösbare oder sehr aufwendige Berechnungen wie beispielsweise in der Bioinformatik bald lösen können. Andererseits heisst das fast grenzenlose Potenzial auch, dass heute verwendete Verschlüsselungsverfahren dann im Nu geknackt werden könnten.

Entsprechende Algorithmen wurden bereits vorgelegt. So zeigte Lov Grover, dass mit Quantenrechnern der Aufwand für die Suche nach einem Schlüssel in symmetrischen Verschlüsselungsverfahren stark reduziert werden kann. Für asymmetrische Kryptografieverfahren hat Peter Shor 1994 demonstriert, dass Quantenrechner die hier verwendeten Produkte aus grossen Primzahlen effizient faktorisieren können.

Wann dies genau der Fall sein wird, wann also ein solcher Quantencomputer zur Verfügung stehen wird, ist allerdings noch ungewiss. Wie Rolf Opplinger vom Nationalen Forschungszentrum für Cybersicherheit NCSC in einer «Technologiebetrachtung» zum Thema darlegt, «benötigt man für den Algorithmus von Shor selbst unter idealen Bedingungen eine Anzahl Qubits, die linear mit der Bitlänge der entsprechenden Schlüssel wächst, das heisst typischerweise ein paar Tausend». Doch das ist offenbar rein theoretisch. «Unter realen Bedingungen werden zudem noch Fehlerkorrekturverfahren benötigt, sodass die Zahl der benötigten Qubits in die Millionen gehen könnte», führt er weiter aus.

Das bedeutet allerdings nicht, dass das «Ablaufdatum» heutiger Kryptografieverfahren in ferner Zukunft liegt und wir dadurch eine gewisse Verschnaufpause erhalten. Denn einerseits besteht die Chance, dass effizientere Algorithmen für die Primzahlenzerlegung gefunden werden könnten, andererseits ist bekannt, dass vor allem Geheimdienste die Strategie des «harvest now, decrypt later» verfolgen, dass also auf Vorrat verschlüsselte Daten abgegriffen werden, um diese dann zu entschlüsseln, wenn die Quantenrechnerei genügend Fortschritte gemacht hat.

So gesehen bleibt wenig Zeit, um sogenannte Post-Quanten-Kryptografie-Verfahren (PQK) zu etablieren. Aber auch hier läuft die Entwicklung entsprechender Methoden auf Hochtouren und hat sich diesen Sommer konkretisiert. Denn vor Kurzem hat das US-amerikanische National Institute of Standards and Technology (NIST) jene Algorithmen bekannt gegeben, die dereinst den PQK-Standard ausmachen sollen. Auch die vom NIST auserkorenen Verfahren wurden zu guten Stücken unter Beteiligung der IBM-Forscher in Rüschlikon entwickelt.

Im Zentrum stehen die beiden Haupt-Algorithmen Crystals-Kyber für die Verschlüsselung und Crystals-Dilithium für digitale Signaturen, wobei Crystals für «Crypto­graphic Suite for Algebraic Lattices» steht. Bei beiden Verfahren stehen somit Gittervektorprobleme (Lattice-based) im Zentrum. Konkret handelt es sich bei Kyber um ein Schlüsselkapselungsverfahren (Key Encapsulation Mechanism; KEM), dessen Sicherheit auf der Schwierigkeit beruht, das Problem des Lernens mit Fehlern (Learning-with-Errors) zu lösen. Die Herausforderung besteht darin, mehrere Punkte als Stichprobe aus einem Gitter zu nehmen, wobei einige dieser Punkte auch falsch platziert sein könnten, und daraus die Funktion zu bestimmen oder zu «erlernen», die sie erzeugt hat. Das Verfahren scheint schwierig zu sein und vor allem auch verschieden genug, sodass es keine bekannten Quantenalgorithmen gibt, die es schnell lösen könnten.

Neben den beiden Crystals-Algorithmen hat das NIST auch die für digitale Signaturen verwendbare Verfahren «Falcon» und «Sphincs+» für den PQK-Standard vorgeschlagen. Auch diese beiden sind «Lattice-based» und sollen in Sachen Verwendungszweck die Haupt-Algorithmen ergänzen. So weist Falcon kleinere Parameter auf, während Dilithium einfacher einzusetzen und zu verteilen ist. Sphincs+ wiederum könnte als Backup-Algorithmus dienen, falls die anderen doch geknackt werden könnten.

Dass ein solcher Hack durchaus auch geschehen könnte, hat das Signaturverfahren «Rainbow» gezeigt. Dieses hatte es auch in die NIST-Endauswahl geschafft. Doch dem Kryptografen Ward Beullens war es gelungen, den privaten Schlüssel in Rainbow mit seinem Notebook innert 53 Stunden zu knacken.

Neben der PQK können auch quantenmechanische Systeme zum Einsatz kommen, um Daten vor der Dechiffrierung mit Quantenrechnern zu schützen. Derzeit gelingt dies hauptsächlich bei der sogenannten Schlüsselvereinbarung. Allerdings sind solche Systeme noch sehr beschränkt verwendbar, etwa nur über relativ kurze Strecken von wenigen Hundert Kilometern und über dedizierte Kanäle. Dennoch ist auch hier die Schweiz an vorderster Front mit Angeboten präsent, etwa durch die in Genf beheimatete Firma ID Quantique.

Ein Fazit rund um quantenresistente Verschlüsselung könnte lauten, dass Firmen besonders schützenswerte Daten schon heute vor künftigen Quantencomputer-Hackern schützen können. Denn die Bedrohung für symmetrische Kryptoverfahren ist geringer als für assymetrische Methoden. So reicht hier schon der Einsatz eines doppelt so langen Schlüssels aus. Die kryptologische Fachstelle des Bundes (FUB Kryptologie) empfiehlt daher den Behörden, als geheim klassifizierte Informationen ausschliesslich mit einem symmetrischen Verfahren und einer Schlüssellänge von mindestens 256 Bit zu verwenden. Die Verwendung beispielsweise von AES-256 (Advanced Encryption Standard) statt AES-128 darf somit auch als eine empfehlenswerte Praxis für Firmen angesehen werden.

Dieser Artikel ist im Rahmen der «Top 500»-Sonderausgabe von Computerworld erschienen. Das Heft einschliesslich Ranking lässt sich auf dieser Seite bestellen.