Die Zukunft der Kryptographie mit öffentlichen Schlüsseln im Zeitalter des Quantencomputers

(Di Mario Satin)
27/07/20

In den letzten Jahren haben die akademische, industrielle und staatliche Welt Energie und Ressourcen in den Bereich des Quantencomputings investiert, in Computer, die die Phänomene der Quantenmechanik nutzen, um mathematische Probleme zu lösen, die für herkömmliche Computer schwierig oder undurchführbar sind.

Wenn die Massenproduktion von Quantencomputern jemals in Gang kommt, werden sie in der Lage sein, viele der derzeit verwendeten kryptografischen Systeme mit öffentlichem Schlüssel (oder asymmetrisch) zu knacken. Dies würde die Privatsphäre und Integrität der digitalen Kommunikation im Internet und anderswo ernsthaft gefährden.

In diesem Zusammenhang das Ziel der Verschlüsselung postquantum (o quantensicher) besteht darin, Chiffren zu entwickeln, die sowohl vor mit Quantencomputern durchgeführten als auch klassischen Kryptoanalyse-Angriffen sicher sind und gleichzeitig mit bestehenden Kommunikationsnetzwerken und -protokollen interagieren können.

Während einerseits die Public-Key-Kryptographie mit doppelten Schlüsseln zur Ver-/Entschlüsselung durch das Aufkommen von Quantencomputern ernsthaft gefährdet sein könnte, basieren symmetrische (oder private) Verschlüsselung und Hash-Funktionen auf Quantenalgorithmen. Unter ihnen ist die größte Bedrohung für symmetrische Chiffren dieGrovers Algorithmus (erstellt von Lov Grover 1996 bei i Bell Labs1). Dieser auf einem Quantencomputer ausgeführte Algorithmus ermöglicht die Suche nach einem Element in einer ungeordneten Liste der Länge N in einer Zeit, die proportional zur Quadratwurzel von N ist. Im Gegensatz dazu wäre die Zeit auf einem klassischen Computer proportional zu N. Das heißt Um das gleiche Maß an Sicherheit zu erreichen, muss die Länge des Schlüssels verdoppelt werden.

Unter den symmetrischen Schlüsselalgorithmen ist derAdvanced Encryption Standard (AES), die Kugelfisch, dann Twofish oder Schlange, mit einer Schlüssellänge größer oder gleich 256 Bit und unter geeigneten Bedingungen, werden sich bewähren können quantensicher.

Im Bereich der asymmetrischen Kryptographie sind die Aussichten jedoch weniger zuversichtlich. Kryptosysteme mit öffentlichen Schlüsseln werden hauptsächlich für zwei grundlegende Aufgaben verwendet: den sicheren Austausch von Schlüsseln für deren anschließende Verwendung mit symmetrischen Verschlüsselungsverfahren und die digitale Signatur.

Zu den bekanntesten Public-Key-Verschlüsselungen, die derzeit verwendet werden, gehören:

  • RSA, basierend auf dem Ganzzahlfaktorisierungsproblem;
  • Kryptografie mit elliptischen Kurven, deren Sicherheit auf der Schwierigkeit beruht, bestimmte Operationen an den Punkten dieses Kurventyps durchzuführen;
  • Diffie-Hellman konzentrierte sich auf die Schwierigkeit, den diskreten Logarithmus für einige zyklische Gruppen zu berechnen.

Gegen jeden von ihnen ist es leicht möglich, einen kryptoanalytischen Angriff durchzuführen, bei dem die Informationen ohne Verwendung des Schlüssels entschlüsselt werdenShors Algorithmus (erstellt von Peter Shor im Jahr 19942), die auf einem Quantencomputer läuft. Der Grund, warum Shors Algorithmus in der Lage ist, kryptografische Systeme mit öffentlichen Schlüsseln zu „brechen“, ist die Folge der Tatsache, dass sie auf Problemen mit nicht-polynomialer Rechenkomplexität basieren, die von einem Quantencomputer in polynomieller Zeit gelöst werden können. Insbesondere wenn eine ganze Zahl N gegeben ist, faktorisiert Shors Algorithmus diese in die Polynomzeit in log(N), während auf einem klassischen Computer die Zeit in N exponentiell ist.

Motiviert durch diese Überlegungen hat der Amerikaner National Institute of Standards and Technology (NIST) übernahm die Auswahl der kryptografischen Algorithmen mit öffentlichem Schlüssel quantensicher am Ende einer öffentlichen Ausschreibung, die während der PQCrypto-Konferenz 2016 angekündigt und im Dezember desselben Jahres gestartet wurde.
Im Rahmen der Ausschreibung wurden 82 Kandidatenalgorithmen zusammengetragen, die durch Peer-Review-Prozesse und Auswahlrunden das Feld einschränkten, um voraussichtlich bis 2024 mit der Veröffentlichung eines Standards ein Ende zu finden. 

Die neuen Chiffren werden von den Vereinigten Staaten ähnlich wie frühere Bemühungen zur Einführung übernommen Datenverschlüsselungsstandard (DES) und die AES.

Zu den Klassen von Algorithmen postquantum Zu den vielversprechendsten zählen die Algorithmen, die auf „fehlerkorrigierenden Codes“ (Code-basierte Kryptographie) basieren und 1978 vom Amerikaner Robert McEliece eingeführt wurden3 Bei der Public-Key-Kryptografie hatten sie aufgrund der übermäßigen Schlüsselgröße nicht viel Erfolg. Ebenso gibt es heute Varianten, die deutlich reduzierte und konkurrenzfähige Schlüsselgrößen bieten können. Diese Algorithmen basieren auf der Schwierigkeit, innerhalb einer riesigen, ungeordneten Menge von Zahlen zu suchen. Es wurde auch theoretisch bewiesen, dass sie zur Klasse der sogenannten NP-Probleme (nicht deterministische Polynome) gehören, die einer Quantenberechnung widerstehen könnten.

eine zweite Klasse, Multivariate Kryptographie4, basiert auf der Schwierigkeit, Systeme quadratischer algebraischer Gleichungen in vielen Variablen (NP-) zu lösen.Härte).

Eine dritte Klasse basiert auf dem algebraischen Konzept des „Gitters“ (Gitterbasierte Kryptographie), einschließlich Varianten, die auf dem Problem des „Lernens mit Fehlern“ basieren, das in der Rekonstruktion einer Funktion aus einigen ihrer ungenauen Bewertungen besteht5. Diese Formulierung hat es ermöglicht, einige innovative Algorithmen für die asymmetrische Kryptographie zu definieren, begleitet von strengen Sicherheitsdemonstrationen.

Die Implementierung neuer Public-Key-Verschlüsselungen quantensicher heute stellt eine unvermeidbare Anstrengung dar. Der allgegenwärtige Einsatz aktueller Public-Key-Algorithmen wirkt sich auf das tägliche Leben aller aus, vom sicheren Surfen im Internet bis hin zu Banksicherheitssystemen, von digitalen Signaturen bis hin zu Kryptowährungen.

Für die einen ein Wettlauf mit der Zeit, für andere wird es noch einige Zeit dauern, bis die Rechenleistung eines Quantencomputers das nötige Niveau erreicht, um aktuelle Standards obsolet zu machen.

Mittlerweile führen jedoch im privaten Sektor Giganten wie Google und IBM Experimente durch, die darauf abzielen, die sogenannte „Quantenüberlegenheit“ zu erlangen, und fordern sich gegenseitig bei der Erzielung neuer und immer anspruchsvoller werdender Rechenrekorde heraus. Darüber hinaus tätigen Supermächte wie die Vereinigten Staaten und China sowie die Europäische Union mit dem gleichen Ziel im internationalen Bereich immer größere Investitionen in die Entwicklung von Forschungsplänen auf diesem Gebiet Quantencomputing. China beispielsweise gab kürzlich bekannt, dass es bis 2020 in Hefei ein nationales Labor für Quanteninformationswissenschaften errichten wolle, wofür ein mehrjähriges Budget von zehn Milliarden Dollar vorgesehen sei.6.

Gleichzeitig hat sich im europäischen Bereich die neue Präsidentin der Europäischen Kommission, Ursula von der Leyen, zu diesem Thema geäußert und erklärt, dass die Quantencomputing ist eine der Prioritäten der Union und zeigt ihre Bereitschaft, Entwicklungsinitiativen in diesem Bereich zu unterstützen und durch die auch europäische Rechenressourcen für die akademische Welt und die Forschungswelt verfügbar zu machen Cloud. Dafür stellt die Union eine Milliarde Dollar zur Verfügung, die innerhalb der nächsten zehn Jahre verwendet werden soll7, für die Entwicklung bestimmter bereits identifizierter Projekte.

In diesem Zusammenhang liegt der Grund für den krampfhaften „Wettlauf“ staatlicher und privater Akteure, der darauf abzielt, die oben genannte Vormachtstellung auf diesem Gebiet zu erreichen Quantencomputing, lässt sich an den Worten von Mike McCaul erkennen8, nordamerikanischer Politiker und Mitglied des American Enterprise Institute, äußerte sich 2018 zum Wettbewerb im Bereich Quantencomputing der USA mit globalen Gegnern wie China, Russland, Nordkorea und Iran: „Ich glaube, dass jede Supermacht, die dieses Ziel vor den anderen erreicht, sich mit der ersten digitalen Atombombe ausrüsten würde.“.

1 Grover, „Ein schneller quantenmechanischer Algorithmus für die Datenbanksuche“, Proceedings, 28. jährliches ACM-Symposium zur Theorie des Rechnens, S. 212, 1996.

2 Shor, „Algorithms for Quantum Computation: Discrete Log and Factoring“, in Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, Santa Fe, IEEE Computer Society Press, S. 124-134, 1994.

3 McEliece, „Public-Key System Based on Algebraic Coding Theory“, DSN Progress Report 44, S. 114-116, 1978.

4 Matsumoto, Imai, „Eine Klasse asymmetrischer Kryptosysteme basierend auf Polynomen über endlichen Ringen“, IEEE International Symposium on Information Theory, Abstract of Papers, S. 131-132, 1983.

5 Goldreich, Goldwasser, Halevi, „Public-Key-Kryptosystem aus dem Problem der Gitterreduktion“, in Proc. of Crypto '97, Band 1294 von LNCS, S. 112-131, IACR, Springer-Verlag, 1997.

6https://itbrief.com.au/story/apac-jumps-on-quantum-computing-bandwagon

7https://www.ilsole24ore.com/art/la-cina-l-occidente-e-sfida-globale-big-...

8https://fedmanager.com/news/congressman-quantum-computing-equivalent-to-...

Foto: IBM