RSA ist eine der meistgenutzten Verschlüsselungstechniken der heutigen Zeit und schützt verschiedene Applikation von den neugierigen Augen der Angreifer – ausser diese Angreifer besitzen einen Quantencomputer. Die Sicherheit von RSA basiert darauf, dass Computer eine gewisse Zeit brauchen, um ein hartes Problem zu lösen. Quantencomputer können einige dieser Probleme so viel effizienter lösen als klassische Computer, dass es ihnen in nützlicher Zeit gelingt RSA zu knacken.

Benötigte Bausteine

Die Attacke auf RSA mithilfe eines Quantencomputers beschreibt man am besten, indem man sich die Bauteile der Attacke anschaut.

RSA

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.

Periode einer Funktion mit einem Quantenprogramm berechnen

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.

Euklidischer Algorithmus

Mit dem euklidischen Algorithmus lässt sich der grösste gemeinsame Teiler ggT von zwei Zahlen effizient berechnen.

Zusammensetzen der Bausteine – Der Shor-Algorithmus

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.

Quantenteil

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:

1. Die Ordnung von a modulo N nennen wir r und ist definiert als die Potenz von a modulo N welche eins ergibt:
   

   a^r mod N = 1

2. Wir definieren die Funktion ƒ_a als
   

   ƒ_a(x) = a^x mod N

Nun stellen wir fest, dass ƒ_a folgende Eigenschaften hat:

ƒ_a( r ) = a^r mod N = 1

ƒ_a(x+y) = a^x+y mod N = a^x * a^y 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.

Klassischer Teil

Mit einer Wahrscheinlichkeit von mindestens 50 Prozent, erhalten wir von dem Quantencomputer ein r welche folgende zwei Eigenschaften hat:

1. r ist eine gerade Zahl.
2. Weder a^r/2 + 1 noch a^r/2 – 1 ist ein Vielfaches von N.

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:

a^r mod N = 1

⇔ (a^r/2)² mod N = 1

⇔ (a^r/2)² – 1 mod N = 0

⇔ (a^r/2 – 1)(a^r/2 + 1) mod N = 0

Da weder a^r/2 + 1 noch a^r/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(a^r/2 – 1, N) = p oder q

Der zweite Faktor lässt sich durch Teilen von N mit dem Faktor x bestimmen.

Zack, RSA geknackt!

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!

Sind andere Protokolle sicher?

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

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.

Asymmetrische Kryptosysteme

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.

Post-Quanten-Kryptographie

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.

Quantenschlüsselaustausch

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.

Zusammenfassung

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.

Zusätzliches Material

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.

Über den Autor

Noah Berner schloss sein Studium an der ETH Zürich mit einem Bachelor of Science in Informatik und einem Master of Science in Quantum Engineering ab. Neben der Informationssicherheit in komplexen Datenverarbeitungssystemen gehören Quantum-Key-Distribution-Protokolle und physische Quantencomputer-Architekturen zu seinen Forschungsinteressen. (ORCID 0000-0003-4320-097X)

Links

• https://apps.dtic.mil/sti/pdfs/ADA606588.pdf
• https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.5183&rep=rep1&type=pdf
• https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions
• https://michaelnielsen.org/qcqi/QINFO-book-nielsen-and-chuang-toc-and-chapter1-nov00-acro5.pdf
• https://qiskit.org/textbook/preface.html