Das Forschungszentrum Jülich nimmt einen 5.000-Qubit-Quantencomputer in Betrieb. Geht von ihm eine Gefahr für Bitcoin aus?

Das Forschungszentrum Jülich nimmt einen neuen Quantencomputer in Betrieb, der erstaunliche 5.000 Qubits verbindet. Erwächst daraus eine Gefahr für Bitcoin und dessen Signaturalgorithmus ECDSA? Neue Forschungen zum Thema geben darauf eine ziemlich deutliche Antwort.

Quentencomputer gelten seit jeher als potenzielle Gefahr für Bitcoin. Denn ein Quantencomputer ist, potenziell, in der Lage, Signaturalgorithmen wie ECDSA zu brechen. Und da ECDSA-Signaturen Bitcoins schützen, könnte so ein Quantencomputer irgendwann Wallets ausräumen.

Bisher war diese Gefahr aber noch nicht mal sichtbar. Denn die bisher existierenden Quantencomputer sind viel zu leistungsschwach. Sie haben, wenn überhaupt, wenige hundert Qubits, während eine Gefahr für ECDSA frühestens ab 1.500 bis 2.000 Qubits entstehen würde.

Nun aber stellt das Forschungszentrum Jülich ein neues Quantensystem mit satten 5.000 Qubits vor: „Europas erster Quantencomputer mit mehr als 5000 Qubits in Jülich gestartet“ titelt das Forschungszentrum in einer Pressemitteilung.

Das System wurde von D-Wave erbaut, einem der führenden Hersteller von Quantencomputer; das Modell in Supercomputer-Zentrum Jülich ist das erste „Advantage System“ außerhalb des D-Wave-Firmensitzes in Kanada. „Das ermöglicht den Jülicher Experten, Erfahrungen mit dem Betrieb und der Wartung eines solchen Geräts zu sammeln – und führt zu einem erheblichen Wissenstransfer nach Deutschland. Darüber hinaus wird der Zugang zu diesem System unter deutscher Gesetzgebung und Kontrolle erfolgen“, erklärt die Pressemitteilung.

Bitcoins stehlen mit Shor’s Algorithmus

5.000 Qubits klingt nach einem fast zu großen Sprung, um wahr zu sein. Wenn der Quantencomputer tatsächlich 5.000 Qubits hätte, könnte daraus für Bitcoin zumindest eine gewisse Gefahrensituation entstehen, die vielleicht noch nicht handfest ist, aber sehr viel realitätsnäher als alls, worüber wir bisher nachgedacht haben.

Denn Quantencomputer können manche Aufgaben um Dimensionen schneller ausführen als traditionelle Computer. Diese „Quanten-Überlegenheit“ hat Google bereits 2019 bewiesen, als sie mit einem Quantensystem in wenigen Minuten Berechnungen abgeschlossen haben, die auf klassischen Computern 10.000 Jahre brauchen würden.

Ein Beispiel für die Quantenüberlegenheit ist, zumindest in der Theorie, Shor’s Algorithmus. Dieser Algorithmus kann moderne Arten von Kryptographie brechen, darunter auch Signaturen mit ECDSA. Für normale Computer ist es physikalisch quasi unmöglich, eine ECDSA-Signatur zu erzeugen, ohne den zugehörigen privaten Schlüssel zu kennen bzw. aus Kenntnis des öffentlichen Schlüssels den privaten zu berechnen (nichts anderes bedeutet es, eine Signatur zu „brechen“). Man bräuchte Energie in einer Größenordnung, die Sonnen verbrennt.

Aber ein Quantencomputer könnte, wenn er genügend Qubits koordiniert, mithilfe von Shor’s Algorithmus Signaturen sehr viel schneller brechen. Schon ab 1.500 oder 2.000 Qubits rückt das Fälschen einer Signatur in den Bereich des Möglichen.

Ist es nun mit dem System in Jülich möglich?

Die Antwort lautet, aus gleich zwei Gründen, sehr eindeutig nein. NEIN. Kein „eher nicht“, kein bedingtes Nein, kein „noch nicht“. Sondern ein sehr klares, sehr festes, und sehr nachhaltiges NEIN.

Kein Computer, sondern ein Annealer

Der erste Grund liegt in der Art des Systems. Im Forschungszentrum in Jülich ging kein reinrassiger Quantencomputer in Betrieb, sondern ein „Quantenannealer“. Dieser ist „besonders geeignet für die Lösung von schwierigen Optimierungsproblemen, die insbesondere auch für die Industrie von großem Interesse sind – etwa um Verkehrsflüsse effizient zu steuern oder um künstliche neuronale Netze für Anwendungen der Künstlichen Intelligenz zu trainieren.“

Ein Quantenannealer ist sozusagen ein hochspezialisierter Quantencomputer. Soweit ich es verstehe – und das bedeutet leider nicht sehr viel – bringt ein solcher Annealer die Quantenbits in eine Superposition, die das Problem, das der Annealer zu lösen hat, bereits enthält. Aus diesem Grund ist ein Quantenannealer gut geeignet, bestimmte, stark eingeschränkte Operationen auszuführen – aber nicht, um Algorithmen wie Shor’s zu kalkulieren.

Die Quantencomputer, auf die es ankommt, erreichen noch bei weitem keine 5.000 Qubits. Der derzeit leistungsstärkste Quantencomputer, IBMs new Eagle, erreicht 127 Qubits. Das ist der Stand von November 2021. Damit sind Quantencomputer weiterhin sehr weit davon entfernt, die 1.500 bis 2.000 Qubits zu verbinden, ab denen ECDSA bedroht sein könnte.

Allerdings kündigt IBM an, man hoffe, schon in diesem Jahr, also 2022, einen 400-Qubit-Prozessor zu veröffentlichen, und im darauf folgenden Jahr einen Prozessor, der die 1.000-Qubit-Marke durchbricht. Selbst wenn IBM hier allzu optimistisch ist, scheint der Forschritt in der kommenden Dekade unaufhaltbar zu sein.

Der CEO von Alphabet („Google“), Sundar Pichai, hat 2020 das Weltwirtschaftsforum in Davos gewarnt, dass Quantencomputer im Lauf der nächsten fünf Jahre in der Lage sein werden, gängige kryptographische Algorithmen zu brechen. Es sei wichtig, sich darauf durch stärkere und quantensichere Verschlüsselungsverfahren vorzubereiten.

Ist es also nur eine Frage der Zeit, bis Quantencomputer Bitcoin brechen?

Warum Bitcoin-Adressen quantensicherer sind als ECDSA-Signaturen

Nein, ist es nicht. Damit wären wir bei „zweitens“: Der Art, welche Signaturen Bitcoin wie verwendet. Dafür müssen wir für einen kurzen Moment etwas ausholen.

Wie alle Signaturalgorithmen arbeitet der von Bitcoin verwendete – ECDSA – mit öffentlichen und privaten Schlüsseln. Wenn man nun eine Nachricht signiert, etwa eine Bitcoin-Transaktion, dann kalkuliert der Computer die Signatur durch zwei Zutaten: Erstens durch die zu signierte Nachricht (bzw. deren Hash), und zweitens durch den geheimen Schlüssel.

Um zu prüfen, ob eine Signatur korrekt ist, braucht der Empfänger der Nachricht, ebenfalls zwei Zutaten: Er muss den Signaturalgorithmus sowie den öffentlichen Schlüssel kennen.

Es ist derzeit unmöglich, aus dem öffentlichen Schlüssel den privaten Schlüssel abzuleiten. Aber selbst wenn es möglich wäre, würde dies einem Angreifer keinen uneingeschränkten Zugriff auf alle Bitcoins geben.

Denn man überweist Bitcoins in der Regel nicht an einen öffentlichen Schlüssel, sondern an eine Adresse. Eine Adresse ist eine durch Hashes generierte Ableitung aus dem öffentlichen Schlüssel. Es ist nicht möglich, aus ihr den öffentlichen Schlüssel auszulesen. Erst dann, wenn jemand eine Transaktion von einer Adresse aus sendet, enthüllt er den öffentlichen Schlüssel.

Für die absolute Mehrheit von Bitcoins gilt also: Erst wenn man von einer Adresse aus eine Transaktion bildet, öffnet sich ein Zeitfenster von einigen Minuten bis zur Bestätigung dieser Transaktion, in welcher ein Quantenangreifer die Kenntnis des öffentlichen Schlüssels nutzen kann, um den privaten zu berechnen.

Ein Quantenangreifer bräuchte also nicht allein einen Quantencomputer, der in der Lage ist, ECDSA zu brechen – sondern einen Quantencomputer, der dies in wenigen Minuten schafft.

13 x 10⁶ Qubits

Bisher war genau dies immer die für mich offene Frage bei Quantencomputern. Selbst wenn sie ECDSA brechen können – wie lange bräuchten sie dafür? Einige Minuten – oder Jahrzehnte (selbst wenn ein Quantencomputer 20 Jahre bräuchte, wäre dies ein revolutionärer Durchbruch)?

Vor kurzem haben einige Forscher versucht, diese Frage zu beantworten. Die Wissenschaftler, die vor allem an der Uni Sussex forschern, haben gefragt, wie viele Qubits ein Quantencomputer bräuchte, um ECDSA in zehn Minuten, einer Stunde oder einem Tag zu brechen. Ihre Antwort ist diese:

„Es würde 317 x 10⁶ physikalische Quibits brauchen, um die Kryptographie in einer Stunde zu brechen […] Um sie in einem Tag zu brechen, bräuchte es 13 x 10⁶ physikalische Qubits.“

Um ECDSA in einem Tag zu knacken, bräuchte man also 13 Millionen Qubits, und 317 Millionen, um es in einer Stunde zu brechen. Von zehn Minuten ist gar nicht die Rede. Dabei gehen die Forscher übrigens noch von relativ optimistischen Geschwindigkeiten der Code-Zyklen aus, wie sie heute noch nicht gegeben sind, und von denen auch fraglich ist, ob man sie auf Systeme mit vielen Qubits skalieren können wird.

Selbst wenn IBM also im nächsten Jahr die 1.000-Qubits-Marke durchbricht, ist das nur 1/13.000 der notwendigen Qubits, durch die ein Angriff gelingen könnte, wenn eine Bitcoin-Transaktion einen ganzen Tag braucht, um bestätigt zu werden – was ein extrem unrealistisches Szenario ist.

Inwieweit die Angaben der Forscher korrekt sind, kann ich natürlich nicht beurteilen. Sie nennen eine weitere Studie, von Gidney und Ekerå, laut der man 20 Millionen Qubits bräuchte, um ECDSA in acht Stunden zu brechen. Diese Studie geht aber von relativ optimistischen Rechenzyklen und Fehlerkorrekturen aus. Mit anderen Parametern bräuchte ein Quantemcomputer wohl 2 Milliarden Qubits und immer noch 110 Tage. Das scheint zumindest zu bestätigen, dass sich das hier besprochene Paper in der richtigen Größenordnung bewegt.

Auch wenn sich noch vieles ändern kann – sowohl der Aufbau als auch Betrieb eines Quantencomputers – scheint es derzeit so gut wie ausgeschlossen zu sein, dass Quantencomputer jemals auch nur zu einer geringen Gefahr für unbedarfte Bitcoin-User werden. In jedem Fall nicht auf absehbare Zeit.

---

Das Bitcoinblog wird von Bitcoin.de gesponsort, ist inhaltlich aber unabhängig und gibt die Meinung des Redakteurs Christoph Bergmann wieder

Christoph hat vor kurzem sein zweites Buch veröffentlicht: „Das Bitcoin-Kompendium: Netzwerk und Technologie“. Es ist eine überarbeitete Auslese seiner besten Artikel für dieses Blog. Ihr könnt das Kompendium direkt auf der Webseite Bitcoin-Buch.org bestellen – natürlich auch mit Bitcoin – oder auch per Amazon.

Tipps für Stories sind an christoph.bergmann@mailbox.org immer erwünscht. Für verschlüsselte Nachrichten nutzt bitte meinen PGP-Schlüssel — Auf Telegram! könnt ihr unsere News abonnieren.