Am 23. Oktober 2019 gab Google bekannt, dass es seinem Quantenprozessor Sycamore gelungen ist, ein Problem in 3 Minuten zu lösen, das für einen Supercomputer mehr als 10.000 Jahre Rechenleistung erfordert hätte. Es war der erste erklärte Fall von Quantenüberlegenheit.
Diese Technologie verspricht, das Feld der Möglichkeiten in vielen Bereichen zu eröffnen. Sie stellt jedoch auch ein neues Risiko für die moderne Kryptografie dar, deren Sicherheit auf mathematischen Problemen beruht, die schwer zu lösen sind. Was passiert, wenn diese Berechnungsschwierigkeit kein Hindernis mehr darstellt?
In dieser neuen Artikelserie untersuchen wir das Potenzial von Quantencomputern und analysieren seine möglichen Auswirkungen auf Bitcoin.
Was ist ein Quantencomputer?
Beim Durchsuchen dieses Artikels verwenden Sie wahrscheinlich einen normalen Computer oder vielleicht ein Smartphone. Diese Geräte können Rechenoperationen ausführen, obwohl sie Einschränkungen aufweisen. In der Tat müsste die Maschine angesichts bestimmter komplexer Berechnungen Millionen von Jahren laufen, bevor eine Lösung gefunden wird. Der Vorteil eines Quantencomputers besteht darin, dass er bestimmte spezifische Berechnungen viel schneller durchführen kann als ein klassischer Computer.
Um dieses Ergebnis zu erzielen, hat der Betrieb des Quantencomputers absolut nichts mit der Funktionsweise des klassischen Computers zu tun. Der traditionelle Computer manipuliert Bits, die zwei verschiedene Zustände verkörpern können - 0 oder 1 — und das kombiniert, um Code zu erstellen und Aufgaben zu erledigen. Klassisches Rechnen basiert daher auf den Grundprinzipien der Elektrizität, während Quantencomputer auf den Prinzipien der Quantenphysik basieren.
Anstatt Informationen mit Bits zu verarbeiten, verwenden Quantencomputer Quantenbits, auch bekannt als „Qubits“. Diese Qubits können entweder 0 oder 1 oder eine Überlagerung von 0 und 1 sein. Durch die Verwendung dieser Überlagerung von Zuständen mit anderen Quantenphänomenen wie Verschränkung und Quanteninterferenz kann ein Quantencomputer Rechenaufgaben parallelisieren und daher bestimmte Probleme viel schneller lösen.
Die Herausforderung besteht darin, dass die Kryptografie auf mathematischen Problemen basiert, die von herkömmlichen Computern als unlösbar angesehen werden. Es ist jedoch möglich, dass diese mathematischen Probleme in Zukunft in einer akzeptablen Zeit von Quantencomputern gelöst werden könnten, was unsere aktuellen kryptografischen Standards verletzen würde.
Was sind die Risiken der Kryptografie?
Bisher gibt es hauptsächlich zwei Quantenalgorithmen, die einige moderne kryptografische Primitive bedrohen könnten. Dies sind die Algorithmen von Shor (1994) und Grover (1996).
Der Shor-Algorithmus wurde entwickelt, um ganze Zahlen in Polynomzeit in ihre Primfaktoren zu zerlegen. Dies bedeutet, dass die benötigte Berechnungszeit in akzeptabler Weise mit der Größe der zu faktorisierenden Zahl zunimmt. Im Gegensatz dazu weisen die effizientesten klassischen Algorithmen auf diesem Gebiet eine Komplexität auf, die als „subexponentiell“ beschrieben wird.
Einige der weltweit am häufigsten verwendeten kryptografischen Methoden sind jedoch genau auf dieses Problem der Faktorisierung großer Ganzzahlen zugeschnitten. Dies ist beispielsweise beim RSA-Algorithmus der Fall.
Einfacher ausgedrückt: Wenn es herkömmlichen Computern gelingt, die RSA-Chiffre zu knacken, ist es möglich, die Sicherheit des Algorithmus wiederherzustellen, indem die Größe der verwendeten Schlüssel erhöht wird. Dann schweigen wir für einen Moment, da die Komplexität mit der Größe des Schlüssels subexponentiell zunimmt. Durch den Einsatz des Quantenalgorithmus von Shor nimmt diese Komplexität jedoch viel weniger schnell zu, was letztlich die sichere Verwendung von Verschlüsselungsmethoden wie RSA gefährden könnte.
Dieser Shor-Algorithmus kann modifiziert werden, um auch das Problem des diskreten Logarithmus in Polynomzeit zu lösen. Dies ist das mathematische Problem, das im Zusammenhang mit Diffie-Hellman oder der Kryptographie auf elliptischen Kurven verwendet wird.
Der Grover-Algorithmus kann dagegen verwendet werden, um unstrukturierte Suchprobleme zu lösen. Mit anderen Worten, er wurde entwickelt, um in einer unorganisierten Datenbank nach einem bestimmten Objekt zu suchen, und das viel schneller als ein herkömmlicher Algorithmus. Insbesondere kann es nützlich sein, um Kollisionen mit einer Hash-Funktion zu finden.
Grover und Shor sind zwei Algorithmen, die einige moderne kryptografische Primitive untergraben könnten. Obwohl sie schon lange existieren, ist es bis heute immer noch unmöglich, sie auf einem Quantencomputer auszuführen.
Die Gründe für diese Unmöglichkeit sind vielfältig. Zuallererst müssten wir in der Lage sein, einen Quantencomputer mit einer sehr großen Anzahl von Qubits zu haben. Dann sollten diese Qubits eine minimale Fehlerrate haben. Techniken zur Fehlerkorrektur befinden sich derzeit jedoch noch in der Entwicklung. Um solch komplexe Berechnungen durchführen zu können, müssen Qubits schließlich in der Lage sein, ihren Quantenzustand lange genug aufrechtzuerhalten. Die aktuellen Zeiten sind zu kurz und die Informationen gehen verloren, bevor alle erforderlichen Operationen ausgeführt werden können.
Kurz- und mittelfristig scheint daher keine Bedrohung für Krypto zu bestehen. In jedem Fall ging dies aus den Meinungen von Experten hervor, wie eine 2022 unter 40 Fachleuten der Branche durchgeführte EvolutionQ-Umfrage zeigt.
In dieser Studie wurden sie gefragt, mit welcher Wahrscheinlichkeit ein Quantencomputer in der Lage ist, einen 2.048-Bit-RSA-Schlüssel innerhalb von 24 Stunden zu knacken, verglichen mit anderen Zeithorizonten ab dem Jahr 2022. Innerhalb von 5 Jahren schätzt ein einziger Experte, dass die Wahrscheinlichkeit, dass die beschriebene Situation eintritt, bei über 50% liegt. Innerhalb von 15 Jahren gehen mehr als die Hälfte der Experten davon aus, dass die Wahrscheinlichkeit bei über 50% liegt. Mit 30 Jahren sind sich fast alle einig, und fast ein Drittel glaubt sogar, dass eine Wahrscheinlichkeit von 99% besteht, dass ein RSA-Schlüssel kaputt geht.
Quelle: globalriskinstitute.org
Diese Umfrage zeigt uns, dass die Bedrohungen, die Quantencomputer für die Kryptografie darstellen könnten, kurz- und mittelfristig für Experten wenig besorgniserregend sind. Auf der anderen Seite sind sie auf lange Sicht viel pessimistischer.
Fazit
In diesem ersten Kapitel haben Sie herausgefunden, warum Quantencomputer ein Risiko für die Kryptografie darstellen. Die Hauptbedrohungen sind die Algorithmen von Shor und Grover. Wir sind jedoch noch weit davon entfernt, sie erfolgreich auf einer Maschine ausführen zu können. Das liegt einfach daran, dass wir noch keinen Quantencomputer haben, der ausreichend stabil und leistungsstark ist.
Experten in diesem Sektor zufolge muss diese Bedrohung ernst genommen werden. Es handelt sich jedoch um ein Risiko, das erst in mehreren Jahren oder sogar mehreren Jahrzehnten auftreten sollte.
Im zweiten Kapitel dieser Serie werden wir uns genauer mit den Risiken befassen, die das Bitcoin-Protokoll belasten. Wir werden sehen, ob Quantencomputer einen Einfluss auf die Erfindung von Satoshi Nakamoto haben können.
.png)
