Original-URL des Artikels: https://www.golem.de/news/quantencomputer-das-ende-von-rsa-und-co-1401-103697.html    Veröffentlicht: 06.01.2014 09:14    Kurz-URL: https://glm.io/103697

Quantencomputer

Das Ende von RSA und Co.

Quantencomputer könnten heute gängige Verschlüsselungs- und Signaturverfahren brechen. Laut den jüngsten Snowden-Enthüllungen forscht die NSA an derartigen Technologien. Wir haben die wichtigsten Hintergründe zusammengefasst.

Laut einem Bericht der Washington Post forscht die NSA im Geheimen an der Entwicklung eines Quantencomputers. Das ergab die Auswertung von Dokumenten des Whistleblowers Edward Snowden. Quantencomputer könnten einen Großteil der heute verwendeten Kryptographie brechen, daher sind die Bemühungen der NSA wenig überraschend. Bislang sieht es jedoch so aus, dass der US-Geheimdienst dabei wenig Fortschritte erzielen konnte und nicht mehr erreicht hat als die öffentlich bekannte Wissenschaft.

Was ist ein Quantencomputer und was leistet er?

Abgesehen von einigen Experimenten mit wenigen Bit existieren Quantencomputer bislang nur als theoretisches Modell. Sie nutzen die Gesetze der Quantenmechanik, um bestimmte, sehr spezielle mathematische Berechnungen deutlich schneller durchzuführen. Dazu rechnen Quantencomputer mit sogenannten verschränkten Teilchen. Die Idee, mit Hilfe verschränkter Quantenzustände zu rechnen, geht auf den Physiker und Nobelpreisträger Richard Feynman zurück, der bereits 1982 ein entsprechendes Konzept publizierte.

Für die Kryptographie sind Quantencomputer vor allem deswegen interessant, weil sie die mathematischen Probleme, die hinter den wichtigsten Public-Key-Verfahren stehen, deutlich schneller lösen können. Peter Shor konnte 1994 zeigen, dass die Faktorisierung großer Zahlen und das diskrete Logarithmusproblem mit einem Quantencomputer effizient berechnet werden können. Später konnte auch gezeigt werden, dass dasselbe für das diskrete Logarithmusproblem in elliptischen Kurven gilt.

Welche kryptographischen Verfahren sind betroffen?

Der Algorithmus von Shor gefährdet die Sicherheit praktisch aller heute verwendeten Public-Key-Verfahren für Verschlüsselung und digitale Signaturen, also solche Verfahren, die mit einem öffentlichen und einem privaten Schlüssel arbeiten. Auch Schlüsselaustauschverfahren sind betroffen. Durch Quantencomputer gefährdet sind das RSA-Verfahren, das ElGamal-Verfahren und damit auch DSA, der Diffie-Helmann-Schlüsselaustausch und sämtliche Verfahren auf Basis elliptischer Kurven.

Von Shors Algorithmus nicht betroffen sind symmetrische Verfahren wie AES und Hash-Funktionen. Allerdings gibt es den Quantenalgorithmus von Grover, mit dem sich - theoretisch - die Komplexität eines Angriffs bei symmetrischen Verfahren auf die Quadratwurzel reduzieren lässt. Konkret würde das etwa bedeuten, dass eine Verschlüsselung mit 256 Bit nur noch eine Stärke von 128 Bit hat. Damit könnte man annehmen, dass ein Verfahren mit 128 Bit gefährdet ist, denn es hätte nur noch eine Sicherheit von 64 Bit. 64 Bit ist im Bereich dessen, was sich schon heute - genügend Geld und Ressourcen vorausgesetzt - mit klassischen Computern angreifen lässt. Allerdings: Hierfür bräuchte man massiv parallel arbeitende Spezialhardware in großer Zahl. Selbst wenn es Quantencomputer irgendwann geben sollte, ist ein Angriff auf ein derartiges Problem immer noch unwahrscheinlich, denn man bräuchte nicht nur einen Quantencomputer, man bräuchte sehr viele davon.

Verschlüsselungsverfahren mit 256 Bit und Hash-Verfahren mit 512 Bit sind selbst bei massiven Fortschritten bei der Entwicklung von Quantencomputern vermutlich weiterhin sicher.

Warum ist der Bau von Quantencomputern so schwer?

In einem Quantencomputer müssen alle Registerbits aus physikalischen Teilchen bestehen, die sich kontrolliert in einem verschränkten Zustand befinden. Das Problem: Die Teilchen müssen dabei von anderen Teilchen aus der Umgebung isoliert werden. Der Zustand eines Quantencomputers ist also höchst instabil. Um Verschlüsselungsverfahren anzugreifen, müsste ein Quantencomputer Hunderte oder Tausende von Teilchen in verschränktem Zustand halten, da sich der gesamte Schlüssel im Speicher des Quantencomputers befinden muss. Dieser Vorgang lässt sich auch nicht parallelisieren. Zwei 512-Bit-Quantencomputer würden also nicht ausreichen, um einen 1.024-Bit-RSA-Schlüssel zu brechen. Man bräuchte hierfür einen 1.024-Bit-Quantencomputer.

Da die Bitlänge eine entscheidende Hürde beim Bau von Quantencomputern ist, wäre eine erste Möglichkeit, sich vor Angriffen zu schützen, die Erhöhung der Schlüssellänge. Ein Bau eines 1.024-Bit-Quantencomputers erscheint unwahrscheinlich, ein 4.096-Bit-Quantencomputer ist aber mit Sicherheit noch deutlich schwieriger zu betreiben. Die Bedrohung durch Quantencomputer ist somit auch ein Argument gegen die Nutzung von Kryptographie auf Basis elliptischer Kurven und spricht für klassische Verfahren wie RSA. Denn bei der Kryptographie mit elliptischen Kurven kommen deutlich kürzere Schlüssel zum Einsatz. Während bei RSA und bei Verfahren auf Basis des diskreten Logarithmusproblems Schlüssellängen zwischen 1.024 und 4.096 Bit üblich sind, nutzen Verfahren auf Basis elliptischer Kurven üblicherweise Schlüssellängen im Bereich von 200 bis 500 Bit.

Wie weit ist die Forschung?

2001 gelang es Forschern von IBM, die Zahl 15 auf einem 7-Bit-Quantencomputer zu faktorisieren. Zehn Jahre später, 2011, gelang es einem Forscherteam der Universität Innsbruck, diesen Rekord zu brechen und 14 Quantenbits in einem kontrollierten Zustand zu halten.

Viele Wissenschaftler gehen davon aus, dass der Bau eines Quantencomputers in relevanter Größenordnung nahezu unmöglich ist. Das hält sie jedoch nicht davon ab, daran zu forschen. 2012 ging der Nobelpreis der Physik an die beiden Wissenschaftler David Wineland und Serge Haroche. Das Nobelpreiskomitee begründete seine Entscheidung damit, dass ihre Forschung dazu beitragen könne, in Zukunft Quantencomputer zu bauen.

Gibt es Public-Key-Verfahren, die vor Quantencomputern sicher sind?

Vermutlich ja, aber die Forschung steht hier erst am Anfang. Es gibt einige experimentelle Public-Key-Algorithmen, bei denen Kryptographen annehmen, dass sie sich mit Quantencomputern nicht angreifen lassen. Ein möglicher Kandidat sind sogenannte gitterbasierte Verfahren, am weitesten entwickelt ist hier der Algorithmus NTRU, für den es bereits Implementierungen und Entwürfe für Standards gibt. NTRU ist allerdings patentiert und kommt somit etwa für den breiten Einsatz in Internetprotokollen vermutlich nicht infrage. Für sämtliche Algorithmen und ihre mathematischen Grundlagen gilt allerdings: Hier handelt es sich um frühe Forschung.

Für alle Public-Key-Verfahren gilt, dass sich ihre Sicherheit - zumindest mit heutigen mathematischen Methoden - nicht beweisen lässt. RSA, Diffie Hellman oder die Kryptographie mit elliptischen Kurven gelten nur deshalb als sicher, weil die Algorithmen über Jahrzehnte von den besten Kryptographen der Welt umfangreich untersucht wurden. Die Hoffnung: Gäbe es große Schwächen in den Verfahren, so hätte man diese bereits gefunden. Für die experimentellen Algorithmen, die möglicherweise Sicherheit vor Quantencomputern bieten, gilt dies nicht, denn sie wurden längst nicht so intensiv untersucht wie die bekannten Public-Key-Verfahren.

Generell gilt, dass die Entwicklung von Public-Key-Verfahren sehr schwierig ist. Nur wenige mathematische Probleme eignen sich, um daraus Public-Key-Verfahren zu konstruieren. Viele Verfahren, die in der Vergangenheit vorgeschlagen wurden, erwiesen sich bei näherer Betrachtung als unsicher. Ein Beispiel für ein solches Verfahren ist der Signaturalgorithmus SFLASH. Er galt als möglicher Kandidat für ein Verfahren, welches Sicherheit gegen Quantencomputer bietet. Doch nach einer Untersuchung durch ein Team des RSA-Erfinders Adi Shamir zeigte sich: SFLASH ist unsicher und lässt sich brechen - auch ganz ohne Quantencomputer.

Mit der Erforschung von Public-Key-Verfahren, die sich durch Quantencomputer nicht angreifen lassen, beschäftigt sich die Post-Quanten-Kryptographie. Seit 2008 finden in unregelmäßigen Abständen Fachkonferenzen statt, auf denen sich Kryptographen und Physiker über die neuesten Erkenntnisse austauschen. Im Oktober wird sich die Forschergemeinde das nächste Mal im kanadischen Waterloo treffen. Eine Herausforderung ist der notwendigerweise interdisziplinäre Ansatz. Kryptographen sind meist Mathematiker oder theoretische Informatiker und haben oft wenig Kenntnisse in der Quantenmechanik.

Quantenkryptographie, D-Wave und Fazit

Was haben Quantencomputer mit Quantenkryptographie zu tun? Kurz gesagt: überhaupt nichts.

Bei der Quantenverschlüsselung handelt es sich um Verfahren, die nicht in erster Linie auf Mathematik, sondern auf physikalischen Effekten basieren, um Daten verschlüsselt zu übertragen. Theoretisch sind derartige Systeme nach den Gesetzen der Physik absolut sicher und können nicht abgehört werden. In der Praxis gibt es jedoch zahlreiche Probleme. So muss für erfolgreiche Quantenkryptographie ein einzelnes Teilchen - etwa ein Photon - ungestört und in kontrollierter Weise vom Absender zum Empfänger übertragen werden. Die in der Praxis eingesetzten Systeme, die man teilweise bereits kaufen kann, übertragen hier in der Regel mehr als ein Teilchen. Damit geht allerdings die absolute Sicherheit verloren.

Was hat es mit den Quantencomputern der Firma D-Wave auf sich?

Die kanadische Firma D-Wave forscht seit einiger Zeit an Quantencomputern, die angeblich bereits mit 128 Bit rechnen, und verkauft diese auch. D-Wave hat dabei einige namhafte Partner für sich gewinnen können, darunter Google, die Nasa und die Firma Lockheed Martin. Der MIT-Professor Scott Aaronson bezeichnet sich als "Chefkritiker von D-Wave" und hat große Zweifel an den Forschungsergebnissen von D-Wave. Er schreibt darüber regelmäßig in seinem Blog.

Für die Kryptographie ist die Entwicklung von D-Wave allerdings uninteressant, denn das System von D-Wave - selbst wenn es funktioniert - ist kein universeller Quantencomputer. Der Algorithmus von Shor, der Public-Key-Verfahren angreifen kann, lässt sich auf den Systemen von D-Wave nicht ausführen.

Fazit

Die NSA forscht an Quantencomputern, was kaum jemanden überraschen kann. Sie steht dabei allerdings vor denselben Problemen wie die Forschung an Universitäten und anderen öffentlichen Forschungseinrichtungen: Der Bau eines großen Quantencomputers ist eine enorm schwierige Angelegenheit. So schwierig, dass niemand weiß, ob es jemals einen Quantencomputer geben wird, der in der Praxis eingesetzte Verschlüsselungsverfahren angreifen kann. Sollte es jemals gelingen, so werden bis dahin vermutlich noch Jahrzehnte vergehen. Es ist nicht anzunehmen, dass es der NSA - oder irgendeiner anderen Institution - gelingt, einen Quantencomputer zu bauen, ohne dass die entsprechenden Fortschritte in der Forschung öffentlich bekanntwerden.

Die Forschung an Algorithmen, die Sicherheit vor Quantencomputern bieten, ist sinnvoll und sollte mehr Aufmerksamkeit erfahren. Sie ist aber noch weit davon entfernt, praktisch einsetzbare Technologien zu liefern, die ähnlich vertrauenswürdig sind wie die heute eingesetzten Public-Key-Verfahren.  (hab)


Verwandte Artikel:
Microsoft Quantum: Q# kommt für MacOS, Linux und mit Python-Unterstützung   
(27.02.2018, https://glm.io/133020 )
Materialforschung: Stanen - ein neues Wundermaterial?   
(14.02.2018, https://glm.io/132599 )
Donald Trump: Die Mauer ist wichtiger als sauberer Strom   
(13.02.2018, https://glm.io/132740 )
Computerforschung: Quantencomputer aus Silizium werden realistisch   
(08.01.2018, https://glm.io/131946 )
IBM Q: IBMs Quantencomputer klingt wie ein dampfbetriebenes Uhrwerk   
(02.01.2018, https://glm.io/131927 )

© 1997–2021 Golem.de, https://www.golem.de/