Code-knackende Quantencomputer kommen näher

Bislang ging man davon aus, dass verbreitete Verschlüsselungen noch mehrere Jahrzehnte lang vor Quantencomputern sicher seien. Nach neuen Erkenntnissen könnte es aber schon viel früher so weit sein.

Lesezeit: 3 Min.
In Pocket speichern
vorlesen Druckansicht Kommentare lesen 8 Beiträge
Code-knackende Quantencomputer kommen näher

(Bild: "Quantum Supremacy" / Steve Jurvetson / cc-by-2.0)

Von
  • TR Online

Viele Menschen haben die Sorge, dass Quantencomputer in der Lage sein werden, bestimmte Verschlüsselungen zu knacken, mit denen heute sichere Nachrichten verschickt werden. Diese Codes verschlüsseln Daten mit Hilfe von mathematischen "Falltür"-Funktionen, die in eine Richtung gut funktionieren, in die andere aber nicht. Dies erleichtert das Verschlüsseln von Daten, während das Entschlüsseln ohne den richtigen Schlüssel extrem schwierig ist.

Vollkommen sicher waren diese Verschlüsselungssysteme nie. Stattdessen basiert ihre Sicherheit auf der Tatsache, dass klassische Computer enorm viel Zeit brauchen würden, um sie zu knacken. Moderne Methoden der Verschlüsselung wurden gezielt darauf ausgelegt, die Entschlüsselung zu aufwendig dafür zu machen.

Mit Quantencomputern aber könnte sich das ändern. Diese Maschinen sind weitaus leistungsfähiger als klassische Computer und dürften grundsätzlich auch Verschlüsselungen problemlos knacken können. Das wirft eine bedeutende Frage auf: Wann werden Quantencomputer so stark sein, dass das tatsächlich möglich ist? Anschließend wäre davon auszugehen, dass jegliche mit heutiger Verschlüsselung gesicherten Daten nicht mehr sicher sind.

Vor diesem Hintergrund haben Informatiker versucht zu berechnen, welche Ressourcen und wie viel Zeit solche Quantencomputer benötigen würden, und zu bestimmen, wie lange es dauern würde, bis derartige Rechner gebaut werden können. Bislang hatte das Ergebnis stets "mehrere Jahrzehnte" gelautet.

Jetzt aber wird man in dieser Hinsicht umdenken müssen. Verantwortlich dafür sind Craig Gidney bei Google in Santa Barbara und Martin Ekera am KTH Royal Institute of Technology in Stockholm: Die Forscher haben eine Methode gefunden, mit der Quantencomputer Berechnungen zur Entschlüsselung effizienter vornehmen können; der Ressourcen-Aufwand dafür ist um mehrere Größenordnungen kleiner.

Damit sind Code-knackende Quantencomputer bereits näher an der Realität, als irgendjemand vermutet hätte. Dieses Ergebnis ist beunruhigend für Regierungen, Militär und Sicherheitsbehörden sowie Banken und jeden anderen, der Daten 25 Jahre oder länger sicher halten möchte.

Zur Einordnung: Im Jahr 1994 entdeckte der US-Mathematiker Peter Shor einen Quanten-Algorithmus, der sein klassisches Pendant übertraf. Dieser Algorithmus zerlegt große Zahlen in ihre Primfaktoren und ist damit ein entscheidendes Element beim Knacken von Codes, die mit Falltür-Funktionen realisiert wurden.

Falltür-Funktionen basieren auf dem Prozess der Multiplikation, der in eine Richtung leicht funktioniert, aber sehr viel schwieriger umzukehren ist. So bereitet es kein Problem, zwei Zahlen miteinander zu multiplizieren – 593 mal 829 ist 491.597. Wesentlich schwieriger aber ist es, ausgehend von 491.597 herauszufinden, welche beiden Primzahlen für dieses Ergebnis multipliziert werden müssen.

Und weil die verwendeten Zahlen immer größer werden, steigt auch der Rechenaufwand immer weiter. Tatsächlich gilt es als praktisch unmöglich, dass ein klassischer Computer Zahlen faktorisieren könnte, die länger als 2048 Bit sind. Diese Länge bildet die Basis für die am häufigsten eingesetzte Form der RSA-Verschlüsselung.

Wie Shor gezeigt hat, würde die Entschlüsselung dieses Codes einem hinreichend leistungsfähigen Quantencomputer keine Probleme bereiten. Diese Erkenntnis sendete seinerzeit Schockwellen durch die IT-Sicherheitsbranche.

Und seit dieser Zeit hat die Rechenleistung von Quantencomputern immer weiter zugenommen. 2012 nutzten Physiker einen Rechner mit 4 Qubits, um die Zahl 143 zu faktorisieren. Im Jahr 2014 gelang ihnen das mit einer ähnlichen Maschine schon bei der Zahl 56.153.

Bei diesem Fortschrittstempo könnte man glauben, Quantencomputer würden schon bald die besten klassischen Rechner übertreffen. Doch wie sich zeigt, macht Quanten-Faktorisierung in der Praxis mehr Probleme als erwartet. Denn bei großen Quantencomputern werden Störungen zu einem erheblichen Problem. Die beste Gegenmaßnahme dagegen sind bislang Fehlerkorrektur-Codes, die aber selbst eine große Zahl zusätzlicher Qubits benötigen.

Das bedeutet, dass für die Faktorisierung von 2048 Bit langen Zahlen wesentlich mehr Ressourcen benötigt werden. 2015 schätzten Forscher, dass ein Quantencomputer für zuverlässige Ergebnisse Milliarden von Qubits brauchen würde. Das ist weitaus mehr als die 70 Qubits, die in den besten aktuellen Quantencomputern zur Verfügung stehen. Damit konnte man scheinbar davon ausgehen, dass es tatsächlich noch Jahrzehnte dauern würde, bis sich RSA mit 2048 Bit von einem Quantenrechner knacken lässt.

Gidney und Ekera haben jetzt allerdings gezeigt, wie ein Quantencomputer die nötigen Berechnungen mit nur 20 Millionen Qubits erledigen könnte – nach ihren Angaben würde er dafür nur 8 Stunden brauchen. "Im Ergebnis ist die Worst-Case-Schätzung dafür, wie viele Qubits zur Faktorisierung von RSA-Zahlen mit 2048 Bit gebraucht werden, um fast zwei Größenordnungen gesunken", schreiben die Forscher.

Ihre Arbeit konzentriert sich auf eine effizientere Methode für einen mathematischen Prozess namens modulares Potenzieren. Dabei wird der Rest festgestellt, der verbleibt, wenn eine Zahl mit einem bestimmten Wert potenziert und dann durch eine andere Zahl geteilt wird.

Dies ist der Schritt im Algorithmus von Shor, der den höchsten Rechenaufwand erfordert – und Gidney und Ekera haben unterschiedliche Möglichkeiten zu seiner Optimierung gefunden, die den Ressourcen-Bedarf für den Algorithmus deutlich reduzieren.

Die Arbeit dürfte große Bedeutung für jede Organisation und Person haben, die Informationen für die Zukunft speichern möchte. Ein Quantencomputer mit 20 Millionen Qubits erscheint heute noch wie ein weit entfernter Traum. Die Frage aber ist, ob ein solches Gerät möglicherweise noch im Lauf der nächsten 25 Jahre verfügbar wird. Wenn dem so wäre, würde für lange Datensicherung eine andere Art der Verschlüsselung gebraucht.

Mehr Infos

Tatsächlich haben Sicherheitsforscher schon Codes für die Quantencomputer-Ära entwickelt. Also ist es bereits heute möglich, Daten vor zukünftigen Angriffen mit Quantencomputern zu schützen. Standardmäßig werden die neuen Verfahren aber noch nicht eingesetzt.

Für normale Menschen ist das Risiko gering. Die meisten arbeiten mit 2048-Bit-Verschlüsselung oder ähnlichen Codes, wenn sie beispielsweise Kreditkartendaten über das Internet schicken. Wenn diese Informationen heute aufgezeichnet und dann in 25 Jahren entschlüsselt werden, wäre nicht viel verloren.

Bei Regierungen allerdings steht mehr auf dem Spiel. Von ihnen heute verschickte Nachrichten – beispielsweise an Botschaften oder das Militär – könnten auch in vielen Jahren noch Geheimhaltung erfordern. Wenn sie derzeit noch mit 2048-Bit-RSA oder ähnlich verschlüsseln, müssten sich staatliche Organisationen also etwas einfallen lassen – und zwar rasch.

()