Shor-Algorithmus zur Quantenkryptoanalyse von RSA und Co.

Bitte beachten Sie die Abgrenzungen zwischen Quantenkryptologie, Quantenkryptografie, Quantenkryptoanalyse und Post-Quanten-Kryptografie, wie sie auf der Index-Seite nachzulesen ist.

Dieser Beitrag gehört zum Thema Quantenkryptoanalyse. Quantenkryptoanalyse ist das, was man gemeinhin unter Kryptoanalyse, also das Knacken von Chiffren, versteht, nur halt mit Quantencomputern statt mit herkömmlichen Computern.

Sie sollten vorher den Beitrag Quantencomputer und wie sie funktionieren und die Einleitung zur Quantenkryptoanalyse gelesen haben, um die hier verwendeten Grundbegriffe zu verstehen.

Der Shor Algorithmus ist nach Peter W. Shor benannt, der diesen in seiner Arbeit Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer ⁽¹⁾ 1995 vorstellte, die folgendermaßen zusammengefasst werden kann:

Ein digitaler Computer gilt im Allgemeinen als effizientes universelles Rechengerät, d. h. er ist in der Lage, jedes beliebige physikalische Rechengerät zu simulieren, wobei die Rechenzeit höchstens um einen Polynomialfaktor zunimmt. Dies gilt jedoch nicht, wenn die Quantenmechanik in Betracht gezogen wird. In diesem Beitrag werden die Faktorisierung ganzer Zahlen und die Bestimmung diskreter Logarithmen betrachtet, zwei Probleme, die auf einem klassischen Computer als schwierig gelten und als Grundlage für mehrere vorgeschlagene Kryptosysteme verwendet wurden. Es werden effiziente randomisierte Algorithmen für diese beiden Probleme auf einem hypothetischen Quantencomputer angegeben. Diese Algorithmen benötigen eine Anzahl von Schritten, die polynomial zur Größe der Eingabe ist, z.B. die Anzahl der Ziffern der zu faktorisierenden ganzen Zahl.

Kurz gesagt werden in der Arbeit Algorithmen beschrieben, die das Problem der Primzahlenfaktorisierung mithilfe von Quantenalgorithmen extrem beschleunigen. Das Problem der Primzahlenfaktorisierung ist die Einwegfunktion einiger asymmetrischer Verschlüsselungsverfahren, ganz vorne weg von RSA.

Bei der dort eingesetzten Einbahnfunktion wird ausgenutzt, dass zwei Primzahlen schnell miteinander multipliziert werden können, es aber ein fast unlösbares Problem darstellt, große Primzahlen in seine Faktoren zu zerlegen, solange man nicht über einen der benutzten Faktoren verfügt.

Dies gilt aber nur für Berechnung per Hand oder mit einem herkömmlichen Computer. Shors Algorithmus stellt nun aber eine wesentliche schnellere Möglichkeit unter Zuhilfenahme von Quantencomputern zur Verfügung und ist deswegen kryptologisch relevant, zumindest erst einmal theoretisch.

Denn Quantencomputer sind 2025 in der Praxis noch sehr aufwändig und teuer zu bauen und Shors Algorithmus ist relativ komplex. Dies erfordert komplexe Quantencomputer, die aber derzeit noch sehr schwierig zu bauen sind. Bisher gelang nur die Faktorisierung kleiner Zahlen wie 15 oder 21, während RSA Primzahlen mit hunderten von Dezimalstellen benutzt.

Mit der Zeit und dem Fortschritt werden auch komplexere Quantencomputer möglich werden; bis allerdings die Komplexität erreicht ist, damit solch große Primzahlen, wie sie RSA benutzt, faktorisiert werden können, wird es sicher noch einige Zeit dauern. Wie lange das sein mag, darüber kann man nur spekulieren. Siehe auch den Abschnitt Wann bricht die Kryptokalypse aus? in der Einleitung zur Quantenkryptoanalyse.

Wie funktioniert der Shor-Algorithmus?

Beim Knacken des RSA-Algorithmus arbeiten Quanten- und herkömmliche Computer zusammen. Nur die Teile des Codes, die eine hohe Laufzeit auf dem herkömmlichen Computer haben und Geschwindigkeitsvorteile auf Quantencomputern bieten, werden auf letztere ausgelagert. Besonders das Suchen nach passenden Perioden für die Primzahlenfaktorisierung ist eine solche Funktion, bei der der Quantencomputer punkten kann.

Der Ablauf ist dabei der Folgende:

Zufallszahl wählen: Der Algorithmus beginnt damit, eine zufällige Zahl a auszuwählen, die kleiner als die Zahl N ist, die wir faktorisieren wollen.

Periodizität finden: Man betrachtet die Funktion f(x)=a^x mod N. Diese Funktion wiederholt sich irgendwann, sie ist periodisch. Die Länge dieser Periode (nennen wir sie r) ist gesucht. Mit Hilfe eines Quantencomputers und der Quanten-Fourier-Transformation kann man diese Periode sehr schnell bestimmen. Die Quanten-Fourier-Transformation kann man mithilfe von Quantengattern realisieren. Es sind Hadamard-Gatter und Phasengatter nötig. ⁽³⁾

Faktoren ableiten: Sobald man die Periode r gefunden hat, kann man unter bestimmten Bedingungen (zum Beispiel, wenn r gerade ist) mathematisch die Faktoren von N berechnen. Konkret rechnet man dann beispielsweise den größten gemeinsamen Teiler (ggT) von a^r/2 ± 1 und N, was oft einen der Primfaktoren ergibt.

Während klassische Algorithmen exponentiell langsamer werden, wenn N groß ist, bietet der Shor-Algorithmus eine exponentielle Beschleunigung.

Quellen, Literaturverweise und weiterführende Links