Die Bedrohung für die klassische Kryptographie
Die Bedrohung des Quantenrechnens für die klassische Kryptographie beschränkt sich weitgehend auf asymmetrische Verschlüsselungsverfahren. Obwohl Grovers Algorithmus symmetrische Chiffren brechen kann, wurde argumentiert, dass eine Erhöhung der Schlüsselgröße solche Angriffe effektiv abwehren kann. Shors Algorithmus (und seine Varianten) hingegen kann alle drei schwierigen mathematischen Probleme lösen, auf die sich die aktuellen asymmetrischen Verschlüsselungsverfahren für ihre Sicherheit stützen, von denen eines die Primfaktorzerlegung ist.5
RSA ist das prominenteste Beispiel für ein asymmetrisches Verschlüsselungsverfahren, das die Primfaktorzerlegung verwendet. Einfach formuliert: Im RSA-Verschlüsselungsverfahren wird der private Schlüssel aus einem Paar von Primzahlen konstruiert, die zufällig ausgewählt werden und die als Produkt eine Halbprimzahl ergeben. Der entsprechende öffentliche Schlüssel wird von dieser Halbprimzahl abgeleitet. Bei der Übertragung einer Nachricht verwendet der Sender den öffentlichen Schlüssel, den er vom beabsichtigten Empfänger erhalten hat, um die Verschlüsselung durchzuführen. Nach dem Empfang der verschlüsselten Nachricht verwendet der Empfänger den privaten Schlüssel, der aus den Primzahlen generiert wurde, um die Entschlüsselung durchzuführen.
Der RSA-Verschlüsselungsschlüssel kann gebrochen werden, indem die Halbprimzahl, hier als N bezeichnet, faktorisiert wird, d. h. indem die (einzigen) beiden Primzahlen gefunden werden, aus denen N das Produkt ist. Zur Veranschaulichung nehmen wir an, dass N gleich 35 ist. Die Faktorisierung von 35 ist einfach, da sie sofort als Produkt von 5 und 7 erkannt wird, den (einzigen) beiden Primzahlen, die die Halbprimzahl 35 erzeugen.
Moderne Implementierungen von RSA-Chiffren verwenden Primzahlen, die Hunderte von Ziffern lang sind. Zum Beispiel hat die RSA-Zahl des 2048-Bit-RSA-Protokolls, das für die RSA Factoring Challenge generiert wurde, die 1991 gestartet wurde, 617 Dezimalstellen. Es gibt keinen bekannten Algorithmus, der es klassischen Rechnern ermöglicht, in einer praktikablen Zeitspanne die Primfaktoren von so großen Zahlen zu bestimmen.6 Dennoch hat Shors Algorithmus, der 1994 eingeführt wurde, die Fähigkeit demonstriert, das Faktorisierungsproblem in polynomialer Zeit mithilfe des Quantenrechnens zu lösen und damit die theoretische Grundlage für das Brechen von RSA zu liefern.7
Die Implementierung von Shors Algorithmus stellt eine gewaltige physikalische Herausforderung dar. Dies liegt daran, dass die heutigen (physikalischen) Qubits mit Fehlern behaftet sind, die mit Hardware-Beschränkungen und Störungen aus der Umgebung zusammenhängen.8 Eine experimentelle Studie von 2019 über Shors Faktorisierungsalgorithmus auf einem IBM-Q-Quantenrechner berichtet von einer exzellenten Leistung bei der Faktorisierung der Zahl 15 (3x5), während Abweichungen von den theoretischen Ergebnissen deutlicher werden für 21 (3x7) und die Faktorisierung der Zahl 35 (5x7) aufgrund sich häufender Fehler fehlschlägt.9
Bemerkenswert ist, dass die Halbprimzahl 35 nur aus zwei Dezimalstellen besteht, weit entfernt von der 617 Dezimalstellen langen RSA-Zahl, die für die RSA Factoring Challenge mit dem 2048-Bit-Protokoll generiert wurde. Obwohl Quantenrechner erfolgreich größere Zahlen mit alternativen Algorithmen faktorisiert haben, ähneln diese Methoden klassischen Brute-Force-Methoden zur Faktorzerlegung. Im Gegensatz zu Shors Algorithmus wird nicht erwartet, dass diese Ansätze die Leistung von klassischen Faktorisierungsalgorithmen übertreffen.10
Das Brechen eines ausreichend starken RSA-Verschlüsselungsschlüssels mit Shors Algorithmus mag noch viele Jahre entfernt sein.11 Quantenrechnen in großem Maßstab erfordert Techniken, die verhindern, dass sich die von (physikalischen) Qubits erzeugten Fehler vervielfachen und ausbreiten. Aktuelle Fehlerkorrekturmethoden konzentrieren sich auf die Kodierung von Informationen in mehrere physikalische Qubits, die zu logischen Qubits gruppiert werden.12
Post-Quanten-Kryptographie (PQK)
Im Jahr 2016 rief das National Institute of Standards and Technology (NIST) die globale Gemeinschaft der Kryptographen auf, Verschlüsselungsmethoden zu entwickeln und zu bewerten, die in der Lage sind, Angriffen von fortgeschrittenen Quantenrechnern zu widerstehen, die die Leistungsfähigkeit der heutigen begrenzten Maschinen übertreffen. Bis 2022 hatte NIST die erste Reihe von Verschlüsselungsalgorithmen ausgewählt, die darauf ausgelegt sind, Angriffen von zukünftigen Quanten- und klassischen Rechnern gleichermaßen standzuhalten. Diese vier ausgewählten Verschlüsselungsalgorithmen sind auf dem Weg, ein integraler Bestandteil des Post-Quanten-Kryptographie-Standards von NIST zu werden, der voraussichtlich im Jahr 2024 eingeführt werden wird.13
Bemerkenswert ist, dass nur ein Kandidat für den Schlüsselaustausch vorgeschlagen wurde, während die anderen drei Algorithmen digitale Signaturverfahren sind. Die Sicherheit des Öffentlicher-Schlüssel-Verschlüsselungsalgorithmus CRYSTALS-Kyber basiert auf einem schwer zu lösenden Problem, das als Kürzester-Vektor-Problem (Shortest Vector Problem, SVP) bekannt ist. Die Lösung einer großen SVP-Instanz zur Wiederherstellung des privaten Schlüssels gilt selbst für Quantenrechner als nicht machbar.14
Fazit
Das NIST hält die Möglichkeit für plausibel, dass in den nächsten zwei Jahrzehnten Quantenrechner eine Leistungsfähigkeit erreichen, bei der sie potenziell alle derzeit verwendeten öffentlichen Schlüsselverschlüsselungsmethoden kompromittieren könnten. Das gemeinsame Faktenblatt zur Quantenbereitschaft fordert Organisationen auf, frühzeitig mit der Erstellung eines Quantenbereitschaftsfahrplans, der Durchführung von Risikobewertungen und der Einbindung von Technologieanbietern zu beginnen. Dies ist wesentlich, weil Daten, die heute von Bedrohungsakteuren ins Visier genommen werden, möglicherweise auch in Zukunft noch Schutz benötigen.
Dieser Blog wurde von Frank Schmid verfasst und spiegelt seine Gedanken wider; er wurde jedoch vor der redaktionellen und rechtlichen Prüfung durch Gen Re mithilfe generativer KI verbessert.