Seit Jahren warnen IT-Experten vor dem nahenden D-Day: dem Tag, an dem Quantencomputer leistungsfähig genug sind, um unsere bisherigen Verschlüsselungen zu knacken. Haben wir die digitale Infrastruktur bis dahin nicht auf andere Sicherheitssysteme umgestellt, sind all unsere Daten ungeschützt – von Krankenakten und E-Mails bis hin zu Konto- und Handydaten. Grund dafür ist der Shor-Algorithmus, ein Programm, das die Besonderheiten von Quantensystemen nutzt, um die zwei am weitesten verbreiteten kryptografischen Verfahren auszuhebeln: das RSA-Kryptosystem (benannt nach seinen Entwicklern Ron Rivest, Adi Shamir und Leonard Adleman) und die elliptische Kurvenkryptografie.

Für kryptografische Verfahren braucht man eine mathematische Funktion, die einfach zu berechnen und schwer umzukehren ist: Zum Verschlüsseln einer Nachricht wendet man die Funktion an (einfach); möchte man sie aber ohne Schlüssel wieder entschlüsseln (die Umkehrfunktion berechnen), ist das extrem schwer. Das RSA-Verfahren nutzt dafür die Primfaktorzerlegung. Vereinfacht kann man sich den RSA-Algorithmus so vorstellen: Zum Verschlüsseln einer Nachricht nutzt man aus, dass es sehr einfach ist, zwei große Primzahlen miteinander zu multiplizieren – und codiert die Nachricht mit diesem Produkt. Um die Nachricht wieder zu entschlüsseln, braucht man die beiden ursprünglichen Primzahlen. Die Primteiler einer sehr großen Zahl zu berechnen, gestaltet sich selbst mit Supercomputern als unmöglich: Die benötigte Rechenzeit beträgt teilweise etliche Jahrtausende.

Ähnlich verhält es sich mit der elliptischen Kurvenkryptografie – für gewöhnliche Computer ist es bisher unmöglich, sie zu knacken. Denn man kennt keinen effektiven Weg, die dazugehörigen mathematischen Probleme zu lösen. Damit sind unsere Daten vor unbefugtem Zugriff sicher – zumindest dachte man das bis 1994. Denn in jenem Jahr stellte der Mathematiker Peter Shor fest, dass beide Verfahren durch Quantencomputer angreifbar sind.

Eine Anleitung zum Berechnen von Primteilern

Der Shor-Algorithmus lässt sich am besten für die Primfaktorzerlegung erklären. Damit Quantencomputer diese Aufgabe meistern können, muss man das Problem allerdings etwas umformulieren. Denn der Quantenalgorithmus stützt sich auf eine Anleitung zum Faktorisieren von Zahlen, die aus den 1970er Jahren stammt. Damals fand man heraus, dass nur vier Schritte nötig sind, um die Primfaktoren p und q einer Zahl N = p·q zu berechnen.

1. Wähle eine zufällige Zahl a < N.
2. Finde die Periodenlänge r von a Modulo N.
3. Stelle sicher, dass r eine gerade Zahl ist und dass (a^r/2 + 1) nicht durch N teilbar ist.
4. Dann ist p der größte gemeinsame Teiler von a^r/2 − 1 und N. Der andere Primteiler q ist entsprechend der größte gemeinsame Teiler von a^r/2 + 1 und N.

Ich gebe zu: Als ich diese Vorschriften das erste Mal gesehen habe, habe ich kaum etwas verstanden. Aber wenn man sie Schritt für Schritt durchgeht, wirkt das Ganze gar nicht mehr so kompliziert. Besonders hilfreich ist es, die Punkte an einem konkreten Beispiel durchzuspielen: Wir werden auf diese Weise die Zahl N = 35 in ihre Primteiler zerlegen.

Der erste Schritt ist noch einfach: Man soll eine Zahl wählen, die kleiner ist als 35, also zum Beispiel 8. Nun könnte man prüfen, ob die 8 vielleicht gemeinsame Teiler mit 35 hat – denn dann wären wir schon fertig mit der Primfaktorzerlegung. Um herauszufinden, ob beide Zahlen gemeinsame Teiler haben, kann man den »euklidischen Algorithmus« benutzen, der den größten gemeinsamen Teiler zweier Zahlen liefert. Ist das Ergebnis größer als 1 und kleiner als a (in unserem Fall ist a = 8), hat man schon einen Primteiler gefunden! Bei großen Zahlen ist es jedoch unwahrscheinlich, zufällig a so gewählt zu haben, daher wird der größte gemeinsame Teiler höchstwahrscheinlich 1 sein. Das heißt, a und N (in unserem Beispiel 8 und 35) sind mit hoher Wahrscheinlichkeit teilerfremd.

Berechnungen im Uhrzeit-Zahlenraum

Damit ist der erste Schritt abgehakt. Der zweite ist etwas komplizierter, denn dafür braucht man die Modulo-Operation, die man in der Schule meist nicht lernt. Doch tatsächlich führen wir solche Berechnungen tagtäglich durch, ohne es zu merken – und zwar jedes Mal, wenn wir auf die Uhr schauen.

Das Rechnen mit Modulo (kurz: mod) wird deshalb gelegentlich als Uhrzeit-Arithmetik bezeichnet. Bei solchen Berechnungen schränkt man den Zahlenraum ein, man betrachtet nur noch Zahlen von 0 bis zu einer oberen Grenze n − 1. Allerdings setzt sich der Zahlenraum periodisch fort, auf n − 1 folgt also wieder die Null, dann die Eins und so weiter: 0, 1, 2, 3, …, n − 1, 0, 1, 2, 3, …, N − 1, 0, 1, 2, 3 … Das Prinzip ist dasselbe wie bei einer Uhr: Sie springt von 23.59 auf 00.00. Damit lässt sich auch rechnen: Wenn es 15 Uhr ist und man in 20 Stunden verabredet ist, dann trifft man sich nicht um 35 Uhr, sondern um 11 Uhr am nächsten Tag. Das heißt, 35 mod 24 ist 11. Möchte man generell eine Zahl a mod b berechnen, muss man a durch b dividieren und das Ergebnis ist der ganzzahlige Rest der Division.

Damit wissen wir, wie man den Ausdruck a mod N im zweiten Schritt berechnet. Allerdings soll man die Periodenlänge r davon bestimmen. Diese ergibt sich durch eine spannende Eigenschaft, die auftaucht, wenn man Zahlen im Modulo-Raum potenziert: Sie bilden periodische Folgen. Das sieht man zum Beispiel, wenn man die Werte von 3^k mod 10 für verschiedene k berechnet:

Dasselbe kann man für andere Zahlen wiederholen, zum Beispiel 2^k mod 7:

Die Einträge in den zweiten Spalten der Tabellen wiederholen sich. Wie sich herausstellt, gilt das für alle a^k mod N, solange a und N teilerfremd sind (das ist bei 8 und 35 zum Beispiel der Fall). Das heißt, die Folge a⁰ mod N, a¹ mod N, a² mod N, a³ mod N, … ist periodisch. Zudem wird jede Periode durch die Zahl 1 eingeleitet und beendet (da a⁰ = 1). Die gesuchte Periodenlänge r ist durch die Anzahl der Terme bestimmt, bis sich die Folge wiederholt. Im ersten Beispiel betrug die Periodenlänge r = 4, im zweiten r = 3. Für a = 8 und N = 35 erhalten wir die Folge: 1, 8, 29, 22, 1, 8, 29, …, also r = 4.

Diese Periodizität kann man für die Primfaktorzerlegung nutzen. Denn wenn man r für einen allgemeinen Ausdruck a^k mod N bestimmt, kann man daraus sofort ableiten: a^r = 1 mod N, auf unser Beispiel übertragen: 8⁴ = 4096 Mod 35 = 1. Und nicht nur das: r ist die kleinstmögliche Zahl (abseits von null natürlich), für die das Ergebnis 1 ist.

Ein wenig Algebra führt schließlich zum Ziel

Diese Gleichung muss man nun in eine geeignete Form packen, um mit ihr weiterzuarbeiten. Dafür sind jetzt ein paar Umformungsschritte nötig. Zunächst subtrahiert man die 1 auf der rechten Seite: a^r − 1 = 0 mod N. Dann kommt ein entscheidender Schritt, der es erlaubt, den Modulo-Zahlenraum wieder zu verlassen und zu den gewöhnlichen Zahlen zurückzukehren. Denn wenn ein Ausdruck x mod N null ergibt, dann ist x ein ganzzahliges Vielfaches von N: N·n = x. Damit erhält man die neue Gleichung: a^r − 1 = N·n. Für das konkrete Beispiel mit N = 35 und a = 8 folgt also: 8⁴ − 1 = 4095 = 117·35, also ist n in diesem Fall 117.

Nun kommt der dritte Schritt: Man muss sicherstellen, dass r eine gerade Zahl ist. Wenn das der Fall ist, kann man nämlich a^r − 1 in zwei Faktoren aufteilen: (a^r/2 − 1)·(a^r/2 + 1). Gleichzeitig wissen wir, dass sich auch N durch zwei Faktoren ausdrücken lässt, nämlich den gesuchten Primteilern p·q. Damit erhält man letztlich folgende Formel: (a^r/2 − 1)·(a^r/2 + 1) = n·p·q. Für das Beispiel mit N = 35, a = 8 und r = 4, ergibt sich: (8² − 1)·(8² + 1) = 63·65 = 4095 = n·p·q.

Nun sind wir fast am Ziel! Denn die Gleichung besagt, dass einer der beiden Faktoren (a^r/2 − 1) und (a^r/2 + 1) durch p und einer durch q teilbar ist. Man fühlt sich dazu verleitet, p dem einen und q dem anderen Faktor zuzuordnen. Doch ganz so einfach ist es dann doch nicht. Schließlich könnte einer der beiden Faktoren, etwa (a^r/2 − 1), sowohl durch p als auch durch q (also insgesamt durch N) teilbar sein. Das schließt jedoch die Bedingung a^r − 1 = 0 mod N aus. Denn k = r ist die kleinste Zahl, für die a^k mod N eins ergibt. Und da r/2 kleiner ist als r, kann a^r/2 − 1 Mod N nicht null ergeben – und damit ist a^r/2 − 1 nicht durch N teilbar. Um sicherzustellen, dass auch der zweite Faktor a^r/2 + 1 nicht durch N teilbar ist, schließt der dritte Schritt diesen Fall explizit aus. Die anfangs gewählte Zufallszahl a muss folgende Bedingung erfüllen: a^r/2 + 1 ≠ 0 mod N. Wenn das nicht der Fall ist, muss man ein anderes a wählen und alle Schritte von vorne beginnen. Glücklicherweise ist das für unser Beispiel mit N = 35 und a = 8 nicht der Fall, denn: 8² + 1 = 65 = 30 mod 35.

Wie man in vier Schritten eine Zahl in ihre Primteiler zerlegt

Nach den vier Schritten ist man fertig und kann die zwei Primfaktoren p und q mit Hilfe des euklidischen Algorithmus berechnen: p ist der größte gemeinsame Teiler von a^r/2 − 1 und N; und q ist entsprechend der größte gemeinsame Teiler von a^r/2 + 1 und N.

In Kurzform lauten die vier Schritte für das Beispiel mit N = 35:

1. Wähle ein a < 35, zum Beispiel 8.
2. Bestimme die Periodenlänge r von 8 mod 35: 8⁰ mod 35 = 1, 8¹ mod 35 = 8, 8² mod 35 = 29, 8³ mod 35 = 22, 8⁴ mod 35 = 1, 8⁵ mod 35 = 8 und so weiter. Also ist r = 4.
3. Stelle sicher, dass r gerade ist (ist es). Prüfe, ob (8² + 1) = 65≠ 0 mod 35.
4. Nun kann man die beiden Primfaktoren berechnen: p ist der größte gemeinsame Teiler von 8² − 1 = 63 und 35. Das heißt p = 7. q ist entsprechend der größte gemeinsame Teiler von 8² + 1 = 65 und 35, daher ist q = 5.

Mit diesem Algorithmus lassen sich also die Primteiler einer Zahl bestimmen. Allerdings tun sich gewöhnliche Rechner mit dem zweiten Schritt extrem schwer: der Berechnung der Periodenlänge r. Denn für große Werte von N kann r ähnlich groß werden. Tatsächlich sind für klassische Computer mehr Rechenschritte zur Berechnung von r nötig, als direkt alle Primzahlen durchzugehen, die kleiner sind als N, um die Primteiler von N zu bestimmen.

Der Shor-Algorithmus nutzt einen Quantenvorteil

Bei Quantencomputern ist das anders. Auch sie sind nicht besonders gut darin, einen Primteiler zu erraten – sie schneiden dabei nicht wirklich besser ab als klassische Computer. Sobald es aber um periodische Probleme geht, sind Quantencomputer unschlagbar.

Grund dafür ist die Funktionsweise der Geräte. Anstatt mit herkömmlichen Bits zu arbeiten, bestehen die Quanteninformationseinheiten (Qubits) aus überlagerten Zuständen. Das heißt, Qubits können sich in mehreren Zuständen (zum Beispiel rot, grün und blau) gleichzeitig befinden. Manchmal wird daher die Analogie verwendet, dass Quantencomputer wie mehrere parallel arbeitende Rechner funktionieren. Doch das stimmt so nicht: Während der Berechnungen befinden sich die Qubits zwar in einem überlagerten Zustand (sowohl rot als auch grün als auch blau) und können damit viele Rechenoperationen gleichzeitig ausführen – sobald der Quantencomputer ein Ergebnis liefert, nimmt er allerdings eine Messung vor. Der überlagerte Quantenzustand kollabiert und es bleibt das Ergebnis einer einzigen Rechenoperation übrig. Welches Ergebnis ausgespuckt wird, kann man nicht vorhersagen – man kann bloß eine Wahrscheinlichkeit dafür angeben.

Anstatt sich die Quantenzustände als Farben vorzustellen, kann man ihnen die Werte a^x mod N für unterschiedliche x zuweisen, also einen Zustand konstruieren: (a¹ mod N) + (a² mod N) + (a³ mod N) + … Wie wir bereits wissen, ergeben die Werte ein periodisches Muster. Man kann sich also vorstellen, dass dieser überlagerte Zustand eine Art Welle darstellt, deren Frequenz f mit der gesuchten Periodenlänge r zusammenhängt: f = 1/r.

Die Periodenlänge zu bestimmen, ähnelt damit der Aufgabe, einen Klang in seine Obertöne zu zerlegen. Dafür nutzt man die so genannte Fourier-Transformation: Sie wandelt ein aufgenommenes akustisches Signal in ein Frequenzspektrum um. Man kann daraus ablesen, aus welchen Wellen mit welcher Frequenz sich das Signal zusammensetzt. Im Quantencomputer hat man es jedoch nicht mit einem akustischen Signal zu tun, sondern einer quantenmechanischen Wellenfunktion. Glücklicherweise gibt es eine Quanten-Fourier-Transformation, die im Grunde genauso funktioniert wie ihr klassisches Analogon: Man zerlegt den überlagerten Quantenzustand gewissermaßen in seine Obertöne – und erhält damit die gesuchte Frequenz f = 1/r.

Und wie sich herausstellt, braucht ein Quantencomputer dafür erheblich weniger Zeit als ein klassischer Computer. Möchte man eine Zahl mit d Ziffern faktorisieren, braucht der schnellste Algorithmus dafür etwa exp(konst.·∛d) Rechenoperationen (die Anzahl wächst also exponentiell), während ein Quantencomputer nur konst.·d³ Rechenschritte benötigt.

Damit sind Quantencomputer in der Lage, selbst große Zahlen innerhalb von kurzer Zeit in ihre Primteiler zu zerlegen – und können somit RSA-Verschlüsselungen knacken. Schlimmer noch: Der Shor-Algorithmus lässt sich auch auf ein anderes mathematisches Problem anwenden und kann damit die inzwischen viel weiter verbreitete elliptische Kurvenkryptografie lösen.

Doch keine Angst: Bisherige Quantencomputer konnten lediglich zweistellige Zahlen mit dem Shor-Algorithmus faktorisieren. Um Zahlen in ihre Primteiler zu zerlegen, die in aktuellen Verschlüsselungssystemen auftauchen, braucht man mehrere tausend Qubits, die sich in einem gemeinsamen überlagerten Zustand befinden. Der aktuell größte Quantencomputer hat bisher etwas mehr als 400 Qubits, die sich jedoch nicht alle gemeinsam in einen überlagerten Zustand für so komplexe Rechenoperationen wie den Shor-Algorithmus bringen lassen.

Damit liegt der D-Day glücklicherweise noch einige Jahre in der Zukunft. Dennoch tüfteln IT-Experten an neuen Verschlüsselungssystemen, denen Quantencomputer nichts anhaben können – und damit unsere Daten auch für die Zukunft sichern.

​​Was ist euer Lieblingsmathetheorem? Schreibt es gerne in die Kommentare – und vielleicht ist es schon bald das Thema dieser Kolumne!