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

(Di Mario Raso)
27

In den letzten Jahren hat die akademische, industrielle und staatliche Welt Energien und Ressourcen auf dem Gebiet des Quantencomputers investiert, in Computer, die die Phänomene der Quantenmechanik nutzen, um schwierige oder unpraktische mathematische Probleme für herkömmliche Computer zu lösen.

Sollte die Produktion von Quantencomputern in großem Maßstab jemals beginnen, können sie viele der derzeit verwendeten (oder asymmetrischen) Kryptografiesysteme mit öffentlichem Schlüssel zerstören. Dies würde die Vertraulichkeit und Integrität der digitalen Kommunikation im Internet und anderswo ernsthaft gefährden.

In diesem Zusammenhang das Ziel der Kryptographie postquantum (o quantensicher) soll Chiffren entwickeln, die sowohl vor Kryptoanalyse-Angriffen mit Quantencomputern als auch vor klassischen Angriffen sicher sind und gleichzeitig mit vorhandenen Protokollen und Kommunikationsnetzwerken interagieren können.

Während die Kryptografie mit öffentlichem Schlüssel und zwei Schlüsseln für die Entschlüsselung / Entschlüsselung durch das Aufkommen von Quantencomputern ernsthaft gefährdet werden kann, basieren symmetrische (oder private) Kryptografie- und Hash-Funktionen auf Quantenalgorithmen. Unter diesen ist die größte Bedrohung für symmetrische Chiffren dargestellt durchGrovers Algorithmus (1996 von Lov Grover bei i Bell Labs1). Dieser Algorithmus, der auf einem Quantencomputer ausgeführt wird, ermöglicht es Ihnen, nach einem Element in einer ungeordneten Liste der Länge N in einer Zeit zu suchen, die proportional zur Quadratwurzel von N ist. Im Gegensatz dazu wäre auf einem klassischen Computer die Zeit proportional zu N. Dies bedeutet, dass die Länge des Schlüssels verdoppelt werden muss, um das gleiche Sicherheitsniveau zu erreichen.

Unter den symmetrischen Schlüsselalgorithmen ist dieAdvanced Encryption Standard (AES), die Kugelfischdas Twofish oder Schlangemit einer Schlüssellänge größer oder gleich 256 Bit und unter geeigneten Bedingungen kann sich dies bewähren quantensicher.

In Bezug auf die asymmetrische Kryptographie ist die Aussicht jedoch weniger beruhigend. Kryptosysteme mit öffentlichen Schlüsseln werden hauptsächlich verwendet, um zwei grundlegende Aufgaben auszuführen, den sicheren Austausch von Schlüsseln für ihre spätere Verwendung mit symmetrischen Chiffren und die digitale Signatur.

Zu den bekanntesten und derzeit verwendeten Verschlüsselungen für öffentliche Schlüssel gehören:

  • RSA, basierend auf dem Problem der Faktorisierung ganzer Zahlen;
  • Kryptographie 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.

Für jeden von ihnen ist es möglich, einen Kryptoanalyse-Angriff durchzuführen, bei dem die Informationen ohne Verwendung des Schlüssels mit dem Schlüssel entschlüsselt werdenShors Algorithmus (1994 von Peter Shor konzipiert2) läuft auf einem Quantencomputer. Der Grund, warum Shors Algorithmus in der Lage ist, kryptografische Systeme mit öffentlichem Schlüssel zu "brechen", ist die Folge der Tatsache, dass sie auf Problemen mit nichtpolynomieller Rechenkomplexität beruhen, die von einem Quantencomputer in einer Polynomzeit gelöst werden können. Insbesondere bei einer gegebenen ganzen Zahl N faktorisiert der Shor-Algorithmus sie in eine Polynomzeit in log (N), während auf einem klassischen Computer die Zeit in N exponentiell ist.

Motiviert durch diese Überlegungen, der Amerikaner National Institute of Standards and Technology (NIST) hat die Auswahl von kryptografischen Algorithmen mit öffentlichem Schlüssel vorgenommen quantensicher am Ende eines öffentlichen Aufrufs, der während der PQCrypto-Konferenz 2016 angekündigt und im Dezember desselben Jahres gestartet wurde.
Die Einladung sammelte 82 Kandidatenalgorithmen, die durch Peer-Review-Prozesse und Auswahlrunden das Feld einschränkten, um das Ende zu erreichen, vermutlich bis 2024, mit der Veröffentlichung eines Standards.

Die neuen Chiffren werden von den Vereinigten Staaten in Analogie zu früheren Initiativen zur Einführung der Datenverschlüsselungsstandard (DES) und AES.

Zwischen Klassen von Algorithmen postquantum Am vielversprechendsten erweisen sich die Algorithmen, die auf der "Code-basierten Kryptographie" basieren und 1978 vom Amerikaner Robert McEliece eingeführt wurden3 Für die Kryptographie mit öffentlichen Schlüsseln hatten sie aufgrund der übermäßigen Größe des Schlüssels nicht viel Glück. Dieselben haben heute Varianten, die in der Lage sind, deutlich reduzierte und wettbewerbsfähige Schlüsselgrößen anzubieten. Diese Algorithmen basieren auf der Schwierigkeit, innerhalb eines riesigen ungeordneten Satzes von Zahlen zu suchen. Es wurde auch theoretisch bewiesen, dass sie zur Klasse der sogenannten NP-Probleme (Non-Deterministic Polynomial) gehören, die einer Quantenberechnung widerstehen könnten.

Eine zweite Klasse, Multivariate Kryptographie4basiert auf der Schwierigkeit, Systeme quadratischer algebraischer Gleichungen in vielen Variablen zu lösen (NP-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" beruhen und darin bestehen, eine Funktion aus einigen ihrer ungenauen Bewertungen zu rekonstruieren5. Diese Formulierung ermöglichte es, einige innovative Algorithmen für die asymmetrische Kryptographie zu definieren, die von strengen Sicherheitsdemonstrationen begleitet wurden.

Die Implementierung neuer Public-Key-Chiffren quantensicher Heute ist eine unvermeidliche Anstrengung. Die allgegenwärtige Verwendung aktueller Algorithmen für öffentliche Schlüssel 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.

Ein Wettlauf gegen die Zeit für einige, während es für andere noch einige Zeit dauern wird, bis die Rechenleistung eines Quantencomputers das Niveau erreicht, das erforderlich ist, um aktuelle Standards überflüssig zu machen.

In der Zwischenzeit führen jedoch Giganten wie Google und IBM im privaten Sektor Experimente durch, um die sogenannte "Quantenüberlegenheit" zu erlangen, und fordern sich gegenseitig heraus, neue und zunehmend ehrgeizige Rechenaufzeichnungen zu erzielen. Mit dem gleichen Ziel tätigen Supermächte wie die Vereinigten Staaten und China sowie die Europäische Union im internationalen Bereich immer größere Investitionen in die Entwicklung von Forschungsplänen im Bereich Quantencomputing. So hat China kürzlich angekündigt, bis 2020 in Hefei ein nationales Labor für Quanteninformationswissenschaften zu errichten, dem ein mehrjähriges Budget von zehn Milliarden Dollar zugewiesen wird.6.

Gleichzeitig hat die neue Präsidentin der Europäischen Kommission, Ursula von der Leyen, im europäischen Kontext zu dem Thema erklärt, dass die Quantencomputing Es ist eine der Prioritäten der Union und bringt ihren Willen zum Ausdruck, Entwicklungsinitiativen in diesem Bereich zu unterstützen und über die EU auch europäische Rechenressourcen für Wissenschaft und Forschung verfügbar zu machen Wolke. Zu diesem Zweck hat die Union eine Milliarde Dollar zur Verfügung gestellt, die innerhalb der nächsten zehn Jahre verwendet werden sollen7für die Entwicklung bestimmter bereits identifizierter Projekte.

In diesem Zusammenhang war der Grund für die krampfhafte "Rasse" staatlicher und privater Akteure, die darauf abzielte, die oben erwähnte Vormachtstellung auf dem Gebiet der Quantencomputing, findet sich in den Worten, dass Mike McCaul8, Nordamerikanischer Politiker und Mitglied des American Enterprise Institute, äußerte sich 2018 zum Wettbewerb auf dem Gebiet der Quantencomputing der Vereinigten Staaten mit globalen Gegnern wie China, Russland, Nordkorea und Iran: "Ich glaube, dass jede Supermacht, die diesen Meilenstein vor den anderen erreicht, die erste digitale Atombombe haben würde.".

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

2 Shor, "Algorithmen für die Quantenberechnung: Diskretes Log und Factoring", in Proceedings des 35. jährlichen Symposiums über die Grundlagen der Informatik, Santa Fe, IEEE Computer Society Press, pp. 124-134, 1994.

3 McEliece, "Public-Key-System basierend auf algebraischer Codierungstheorie", DSN Progress Report 44, pp. 114-116, 1978.

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

5 Goldreich, Goldwasser, Halevi, "Kryptosystem mit öffentlichem Schlüssel aus Gitterreduktionsproblemen", in Proc. Of Crypto '97, Band 1294 von LNCS pp. 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