Sie wollen mehr?
Weitere Artikel im Archiv
RSA mit einem Quantencomputer angreifen
Die Attacke auf RSA mithilfe eines Quantencomputers beschreibt man am besten, indem man sich die Bauteile der Attacke anschaut.
Das Verschlüsselungsprotokoll RSA, benannt nach seinen Autoren Rivest, Shamir und Adleman, ist eines der meistgenutzten Verschlüsselungsverfahren der heutigen Zeit. Es wird unter anderem bei TLS zum sicheren Austausch von Schlüsseln zwischen Webserver und Client verwendet und schützt somit den Austausch zwischen Webseiten wie E-Banking und Endgeräten.
Bei RSA handelt es sich um ein asymmetrisches Kryptographieverfahren. Das bedeutet, dass für die Ver- und Entschlüsselung zwei verschiedene Schlüssel verwendet werden. Der Schlüssel zur Verschlüsselung der Daten wird öffentlicher Schlüssel genannt. Der öffentliche Schlüssel ist, wie der Name schon sagt, öffentlich und kann an alle Parteien versendet werden, mit denen man kommunizieren möchte. Es wird angenommen, dass auch ein Angreifer den öffentlichen Schlüssel kennt.
Der Schlüssel zur Entschlüsselung der Daten wird privater Schlüssel genannt. Der private Schlüssel muss geheim gehalten werden und darf nicht in die Hände des Angreifers gelangen oder von diesem berechnet werden können.
Die Sicherheit des RSA-Protokolls basiert auf der Vermutung, dass es schwer ist, eine Zahl N = p * q, die das Produkt von zwei Primzahlen p und q ist, wieder in diese zwei Faktoren zu zerlegen. Der schnellste bekannte Algorithmus auf klassischen Computern braucht dazu
O(2∛n)
Zeiteinheiten, wobei n die Anzahl Bits der Zahl N ist. Die Laufzeit des klassischen Algorithmus der als Input die Zahl N bekommt und die beiden Faktoren p und q findet und ausgibt ist also exponentiell in der Anzahl Bits n.
Eines der wichtigsten Bauteile des Shor-Algorithmus ist das Quantenprogramm, welches die Periode r einer periodischen Funktion
ƒ(x) = ƒ(x + r)
berechnet. Das Programm berechnet also den Abstand r nachdem sich die Ausgabe der Funktion wiederholt.
Das Quantenprogramm berechnet die Periode r mithilfe der Quanten-Fourier-Transformation. Die Quanten-Fourier-Transformation ist das quantentechnische Pendant zu der diskreten Fourier-Transformation, schafft diese Operation jedoch exponentiell viel schneller als es klassische Computer können. Dies ist der entscheidende Zeitvorteil, welcher es uns später erlauben wird, RSA in nützlicher Zeit zu knacken.
Mit dem euklidischen Algorithmus lässt sich der grösste gemeinsame Teiler ggT von zwei Zahlen effizient berechnen.
Wir wollen nun diese Programme nutzen, um einen Algorithmus zu konstruieren, der uns die Zahl N in polynomieller (sprich sub-exponentieller) Zeit in die geheimen Faktoren p und q zerlegt. Der amerikanische Mathematiker Peter Shor hat einen solchen Algorithmus im Jahre 1994 entwickelt, welcher nun auch nach ihm benannt ist – der Shor-Algorithmus.
Wir wählen eine Zahl a welche keine gemeinsamen Teiler mit N hat. Dies lässt sich leicht mit dem euklidischen Algorithmus feststellen, da in diesem Fall der grösste gemeinsame Teiler von a und N eins sein muss.
ggT(a, N) = 1
Wenn wir einen geeigneten Kandidaten a gefunden haben, definieren wir zwei Dinge:
ar mod N = 1
ƒa(x) = ax mod N
Nun stellen wir fest, dass ƒa folgende Eigenschaften hat:
ƒa( r ) = ar mod N = 1
ƒa(x+y) = ax+y mod N = ax * ay mod N = ƒa(x) * ƒa(y) mod N
Die entscheidende Schlussfolgerung von all diesen Definitionen ist nun, dass ƒa eine periodische Funktion mit der Periode r ist:
ƒa(x+r) = ƒa(x) * ƒa( r ) = ƒa(x) * 1 = ƒa(x)
Wir können nun mithilfe des oben genannten Quantenprogramms die Periode r von ƒa in polynomieller Zeit berechnen. Wenn die Periode r mithilfe des Quantencomputers bestimmt wurde, benutzen wir klassische Algorithmen, um r zu verarbeiten und die Faktoren von N zu bestimmen.
Mit einer Wahrscheinlichkeit von mindestens 50 Prozent, erhalten wir von dem Quantencomputer ein r welche folgende zwei Eigenschaften hat:
Wenn diese zwei Eigenschaften erfüllt sind, können wir die Primfaktoren von N bestimmen. Ansonsten lassen wir den Quantencomputer ein neues r berechnen, indem wir einen anderen Wert für a wählen. Da die Chance ein nützliches r zu finden mindestens 50 Prozent ist, können wir mit hoher Wahrscheinlichkeit und in schneller Zeit ein solches r finden.
Mit einem r, das die obigen Eigenschaften hat, machen wir die folgende Beobachtung:
ar mod N = 1
⇔ (ar/2)2 mod N = 1
⇔ (ar/2)2 – 1 mod N = 0
⇔ (ar/2 – 1)(ar/2 + 1) mod N = 0
Da weder ar/2 + 1 noch ar/2 – 1 ein Vielfaches von N sind, müssen diese Zahlen einen nicht-trivialen Faktor mit N teilen. Dieser Faktor lässt sich mit dem euklidischen Algorithmus finden.
x = ggT(ar/2 – 1, N) = p oder q
Der zweite Faktor lässt sich durch Teilen von N mit dem Faktor x bestimmen.
Wir konnten nun also mithilfe des Shor-Algorithmus in polynomieller Zeit
O(poly(n))
die beiden geheimen Primfaktoren p und q bestimmen. Dies erlaubt einem Angreifer den privaten Schlüssel so zu berechnen, wie es der ursprüngliche Besitzer des privaten Schlüssels tat. Der private Schlüssel ist somit in den Händen des Angreifers und wir haben RSA geknackt!
Nun stellt sich die Frage, ob denn auch andere Protokolle durch die Präsenz von Quantencomputer geschwächt werden. Dabei spielt es eine Rolle, ob diese Protokolle symmetrisch oder asymmetrisch sind.
Symmetrische Kryptosysteme sind vor dem Shor-Algorithmus sicher, da diese auf anderen Problemen aufbauen als die, die ein Quantencomputer exponentiell schneller lösen können als klassische Computer. Dies ist jedoch eine Momentaufnahme und bedeutet lediglich, dass zurzeit noch kein Algorithmus gefunden wurde, der diese Probleme effizient löst. Ob es einen solchen Algorithmus gibt, ist ein offenes Forschungsproblem.
Der Shor-Algorithmus kann erweitert werden, sodass er alle Probleme des Hidden Subgroup Problem für endliche abelsche Gruppen löst. Dazu gehört das Problem den diskreten Logarithmus zu berechnen, worauf der Diffie-Hellman Schlüsselaustausch und auch Elliptische-Kurven-Kryptographie aufbauen. Es ist also keines der heute häufig verwendeten asymmetrischen Protokolle sicher.
Auch wenn es noch mindestens einige Jahre dauern wird, bis ein Quantencomputer existiert, der genügend viele und genaue Qubits besitzt, um die heutigen Problemgrössen von RSA und co. zu knacken, so ist der jetzige Zustand doch unbefriedigend. Abhilfe könnten zwei Ansätze schaffen.
Die Post-Quanten-Kryptographie, also die Kryptographie, die nach der Ära von Quantencomputern sicher sein soll, beschäftigt sich mit der Entwicklung klassischer asymmetrischer Verschlüsselungsverfahren welche weder von klassischen noch von Quantenalgorithmen geknackt werden können. Zurzeit läuft ein Zertifizierungsverfahren von NIST, welches einige der neuen Verfahren standardisieren möchte.
Der Quantenschlüsselaustausch nutzt die Quantenphysik, um Schlüssel auszutauschen, deren Sicherheit durch physikalische Gesetze und nicht durch Annahmen über die Leistung von Computern garantiert wird. Somit ist es auch einem Angreifer mit einem Quantencomputer nicht möglich den ausgetauschten Schlüssel wiederherzustellen. Die Nachteile des Quantenschlüsselaustausch sind die beschränkte Übertragungsdistanz und -geschwindigkeit, sowie die nötige Anschaffung neuer Hardware.
Die Attacke auf RSA zeigt, dass falls wir in ein Zeitalter kommen, indem Quantencomputer mit genügend Qubits existieren, wir uns um neue Arten der asymmetrischen Verschlüsselung bemühen müssen. Ansonsten ist die sichere Kommunikation, die wir uns heute gewöhnt sind nicht mehr möglich. Es existieren Alternativen zu dem quantentechnisch unsicheren Status quo, diese müssen jedoch noch weiter entwickelt werden damit sie praktikabel sind.
Leser, die sich gerne mehr mit Quantencomputer und deren Algorithmen auseinandersetzen möchten, werden sowohl im Textbook von Qiskit als auch in dem Buch Quantum Computation and Quantum Information von Nielsen und Chuang fündig.
Haftungsausschluss: Da sich dieser Artikel an ein breites Publikum wendet, wurden einige mathematische Aussagen vereinfacht und sollten nicht in der hier präsentierten Form verwendet werden, um weitere Aussagen herzuleiten.
Unsere Spezialisten kontaktieren Sie gern!
Ian Boschung
Yann Santschi
Michèle Trebo
Ralph Meier
Unsere Spezialisten kontaktieren Sie gern!