Implementierung einer Bibliothek von Quantenalgorithmen zur Kryptoanalyse, Simon Kalytta

Simon Kalytta

Kurzfassung

In den vergangenen Jahren haben sich in der Entwicklung von Quantencomputern bedeutsame Fortschritte ergeben. Aufgrund dieser Fortschritte erwarten Prognosen, dass in absehbarer Zukunft Quantencomputer mit kryptografisch relevanter Rechenleistung existieren könnten. Derzeit existieren bereits konzeptuelle Quantenalgorithmen, die in der Lage sind, bestimmte mathematische Probleme effizient zu lösen. Diese mathematischen Probleme spielen aufgrund ihrer Komplexität eine grundlegende Rolle in bestimmten Kryptosystemen. Da bisher keine Quantencomputer mit ausreichender Rechenleistung existieren, gibt es auch wenige konkrete Implementierungen dieser Quantenalgorithmen. In dieser Arbeit wird der Shor-Algorithmus zusammen mit verschiedenen Optimierungen auf der Abstraktionsebene von Quantenschaltkreisen implementiert. Mithilfe dieses Quantenalgorithmus ist es möglich, die Primfaktorzerlegung mit einem vertretbaren Laufzeitaufwand zu berechnen. Alle bisher bekannten konventionellen klassischen Algorithmen zeigen bei dieser Berechnung eine exponentielle Laufzeitsteigerung, wobei das Wachstum der Laufzeit von der Größe der zu faktorisierenden Zahl abhängt. Dementsprechend ist die Sicherheit von Kryptosystemen wie beispielsweise dem RSA-Verfahren, die auf der Schwierigkeit der Primfaktorzerlegung basieren, durch den Shor-Algorithmus gefährdet. Die in dieser Arbeit durchgeführte Implementierung des Shor-Algorithmus wird um mehrere Optimierungen erweitert, die in unterschiedlichen Kombinationen verschiedene Varianten des Quantenalgorithmus ergeben. DesWeiteren wird ein klassischer Algorithmus zur Nachberechnung entwickelt, der die Erfolgsrate des Quantenalgorithmus erhöht. In einer Analyse werden die Laufzeiten und der Ressourcenbedarf der implementierten Varianten anhand von Kriterien für kryptografische Angriffe durch Quantenalgorithmen bewertet. In einem Vergleich mit den Ergebnissen vergleichbarer Arbeiten zeigt sich, dass eine der implementierten Varianten sowohl einen geringeren Ressourcenbedarf als auch eine kürzere Laufzeit aufweist. Dennoch erfüllt keine der Varianten die Kriterien in Bezug auf die Laufzeit, um als effiziente Methode für empfohlene aktuelle Schlüssellängen betrachtet zu werden.

Schlagwörter: Shor-Algorithus,Quanten-Computing, Qiskit, RSA, Primfaktorzerlegung

Abstract

In recent years, significant progress has been made in the development of quantum computers. These advancements have led to predictions that quantum computers with cryptographically relevant computational power could exist in the foreseeable future. Currently, there are already conceptual quantum algorithms capable of efficiently solving certain mathematical problems. Due to their complexity, these mathematical problems play a fundamental role in certain cryptographic systems. However, as of now, there are few concrete implementations of these quantum algorithms due to the lack of quantum computers with sufficient computational power. In this thesis, the Shor algorithm, along with various optimizations at the abstraction level of quantum circuits, is implemented. Using this quantum algorithm, it becomes feasible to compute prime factorization with reasonable computational time. All known conventional classical algorithms exhibit exponential runtime growth in this computation, with the runtime growth depending on the size of the number to be factored. Consequently, the security of cryptographic systems, such as the RSA algorithm, which relies on the difficulty of prime factorization, is compromised by the Shor algorithm. The implementation of the Shor algorithm in this work is extended with several optimizations that result in different variants of the quantum algorithm when combined in various ways. Furthermore, a classical post-processing algorithm is developed to increase the success rate of the quantum algorithm. An analysis evaluates the runtimes and resource requirements of the implemented variants based on criteria for cryptographic attacks by quantum algorithms. A comparison with the results of similar works reveals that one of the implemented variants exhibits both lower resource requirements and shorter runtime. However, none of the variants meet the criteria regarding runtime to be considered an efficient method for recommended current key lengths.

Keywords: Shor-Algorithm,Quantum-Computing, Qiskit, RSA, Prime factorization