Niemand weiß, wann das sein wird, aber die Quantenmaschinen für die Krypto-Verschlüsselung werden kommen. Hier erfahren Sie, wie Forscher die Quantenmechanik nutzen, um in der asymmetrischen Kryptografie lange Ganzzahlen zu knacken. [...]
Die Quanteninformatik bewegt sich nach wie vor in einem nebulösen Bereich zwischen praktischer Anwendung und theoretischer Spekulation, aber sie nähert sich immer mehr der realen [weiterführende Artikel in Englisch] Anwendung. Einer der interessantesten Anwendungsfälle für Quantencomputer ist die moderne Internet-Kryptografie.
Quantencomputer und Qubits
Der Name Quantencomputer beruht auf der Tatsache, dass er sich auf die Eigenschaften subatomarer Teilchen stützt, die Gesetzen unterliegen, die für uns, die wir in der Makrowelt verwurzelt sind, seltsam erscheinen. Insbesondere verwenden Quantencomputer Qubits (Quantenbits) anstelle der binären Ziffern (Bits), die wir von herkömmlichen Computersystemen kennen.
Qubits sind von Natur aus probabilistisch, während Bits deterministisch sind. Ein Bit ist letztlich ein physikalischer Schalter – wenn auch ein sehr kleiner, gemessen in einer Handvoll Nanometer. Bits sind binär: entweder an oder aus, wahr oder falsch, 0 oder 1.
Nicht so bei Qubits.
Die physikalische Grundlage eines Qubits können zahlreiche Phänomene sein, wie zum Beispiel der Drehpunkt eines Elektrons oder die Polarisation von Photonen. Dies ist ein faszinierendes Thema: das Reich der linearen Gleichungen, die eine Brücke zwischen Vorstellung und Realität schlagen. Die Quantenmechanik gilt als Interpretation einer zugrunde liegenden Realität und nicht als Beschreibung, und sie ist mit einem hohen Rechenaufwand verbunden.
Der Zustand eines Qubits wird als eine lineare Überlagerung der beiden möglichen Zustände beschrieben. Einmal beobachtet, wird der Zustand in wahr oder falsch aufgelöst. Die gleiche Eingabe führt jedoch nicht notwendigerweise zur gleichen Ausgabe, und der unbeobachtete Zustand kann nur mit Wahrscheinlichkeitsannahmen beschrieben werden.
Aus Sicht der klassischen Physik ist es sogar noch erstaunlicher, dass Qubits in einem Quantencomputer mehrere Zustände gleichzeitig annehmen können. Wenn ein Computer ein Qubit für seinen Zustand abtastet, löst es sich in ein einziges Entweder-Oder auf (bekannt als Kollaps der Wellenfunktion).
Quantencomputing in der Kryptographie
All dies ist aus wissenschaftlicher und philosophischer Sicht recht interessant. Die Funktionsweise von Quantencomputern beweist zum Beispiel die Wirkung von Beobachtungen auf Teilchen. Hier geht es jedoch um die praktischen Aspekte der zunehmenden Kapazität von Quantencomputern für unser tägliches Leben. In den kommenden Jahren werden die tiefgreifendsten Auswirkungen wahrscheinlich in der Kryptographie zu spüren sein.
Der bekannteste Weg vom Quantencomputing zur Kryptographie ist ein theoretischer Durchbruch aus dem Jahr 1994: der Shor-Algorithmus. Theoretisch zeigte dieser Algorithmus, dass eine Quanten-Turing-Maschine in der Lage ist, eine Klasse von Problemen effizient zu lösen, die mit herkömmlichen Computern unlösbar waren: die Faktorisierung großer ganzer Zahlen.
Wenn Sie mit den Algorithmen asymmetrischer Kryptosysteme wie Diffie-Hellman und RSA vertraut sind, wissen Sie, dass sie auf der Problematik der Lösung von Faktoren für große Zahlen beruhen. Aber was passiert, wenn das Quantencomputing diese Aufgabe löst?
Große ganze Zahlen mit Quantenmechanik knacken
Shors Algorithmus und eine Handvoll anderer Algorithmen nutzen die Quantenmechanik, um die Einwegfunktionen zu knacken, die den Kern der asymmetrischen Kryptographie bilden. Die adiabatische Quantenberechnung wurde außerdem verwendet, um die Faktorisierung anzugreifen.
Die Algorithmen von Shor und anderen beruhen auf der Fähigkeit des Quantencomputers, dank der Qubits eine Vielzahl von Zuständen einzunehmen. Diese Qubits werden dann in einer Weise abgetastet (wodurch ihr Zustand kollabiert), die ein hohes Maß an Wahrscheinlichkeit bei der Abtastung ermöglicht. Im Wesentlichen geben wir die Frage „Was sind die Faktoren für eine gegebene Zahl?“ an die geheimnisvolle Welt des Unsichtbaren weiter, in der die Teilcheneigenschaften in mehreren Zuständen existieren können. Dann fragen wir diese Eigenschaften ab, um die wahrscheinlichste Antwort zu finden. (Ja, das funktioniert tatsächlich.)
Die größte Zahl, die bisher mit Shors Algorithmus faktorisiert wurde, ist 21. Die adiabatische Quantenberechnung hat 143 erfolgreich faktorisiert.
Diese Algorithmen sind ausgeklügelt und beeindruckend, aber bisher sind ihre Zahlen eher bescheiden. Der derzeitige Standard für RSA beträgt 2048 Bits, das sind 617 Ziffern! Beim Angriff auf die Zahl 143 entdeckten die Forscher jedoch unwissentlich einen Ansatz, der zumindest theoretisch noch größere Zahlen ermöglicht. Ein Beispiel ist 56.153, was immer noch eine relativ kleine Zahl im Vergleich zu dem ist, was erforderlich wäre, um reale Kryptosysteme zu kompromittieren. Sie hängt auch von einem reduktiven Trick ab, der nicht für alle Zahlen verwendet werden kann.
Die Bedrohung der Web-Sicherheitsinfrastruktur
Was wir derzeit wissen, ist, dass die grundlegenden Aspekte des Quantenangriffs auf asymmetrische Algorithmen ausgefeilt werden. Wie schnell wird die Technologie so weit fortgeschritten sein, dass sie sich deutlich größeren Zahlen nähern kann?
Interessanterweise sind die symmetrischen Algorithmen, die wir tagtäglich verwenden (wie AES), nicht sonderlich anfällig für Quantenalgorithmen. Der Algorithmus von Grover ist derjenige, der Anwendung findet. Er ist selbst in der Theorie nicht in der Lage, die für einen Angriff auf diese Algorithmen benötigte Zeit wesentlich weiter zu verkürzen als klassische Algorithmen, sofern 256-Bit-Schlüssel verwendet werden.
Der Großteil der symmetrisch gesicherten Kommunikation stellt seine Schlüssel jedoch über einen asymmetrischen Austausch her. Daher ist der meiste Webverkehr heute anfällig für fortgeschrittene Quantencomputer-Angriffe. Wenn ein Angreifer den zu Beginn einer Interaktion festgelegten Schlüssel herausfinden kann, nützt jede noch so gute symmetrische Verschlüsselung nichts.
Die Bedrohung für die Web-Sicherheitsinfrastruktur ist also real. Lassen Sie uns einen Moment über die Dynamik nachdenken, die hier im Spiel ist. Als erstes müssen wir die wirtschaftlichen Aspekte und den Zugang berücksichtigen. Im Moment können es sich nur Unternehmen leisten, die in Geld schwimmen, an solchen Dingen herumzubasteln. IBM, Google und Forscher in China wetteifern um die Führung bei der Entwicklung brauchbarer Systeme, ebenso wie eine Reihe von Universitäten. Hinter den Kulissen sind Regierungsbehörden wie die Nationale Sicherheitsbehörde der USA sicherlich nicht untätig. Die NSA hat sogar ihre eigene Meinung zum Thema öffentliche Kryptografie und Quantencomputer.
Zukunftsweisender Schutz vor Quantencomputern
Es ist unwahrscheinlich, dass kleine Akteure Quantencomputing-Fähigkeiten erreichen, die ausreichen, um moderne asymmetrische Schlüssel anzugreifen, bis lange nachdem große Institutionen dies getan haben. Das bedeutet, dass wir uns in einem langen Zeitraum befinden, in dem sich die Sicherheitsinfrastruktur in Reaktion auf die Dynamik des Quantencomputings weiterentwickeln kann.
Niemand weiß, wann es wirklich krypto-taugliche Quantencomputer geben wird, aber es scheint wahrscheinlich, dass es dazu kommen wird. Zwei Maßstäbe, um diese Frage zu beantworten, sind die Anzahl der Qubits in einem System und die Langlebigkeit dieser Qubits.
Qubits sind der so genannten Dekohärenz unterworfen. Die Entropie ist ständig dabei, die empfindlichen Ensembles aus Elektronen und Photonen zu zerstören. Das Problem ist, dass sowohl die Anzahl als auch die Lebensdauer von Qubits schwer zu quantifizieren sind. Wie viele Qubits sind für einen praktischen, reproduzierbaren Angriff auf einen RSA-2048-Schlüssel erforderlich? Einige sagen Dutzende, andere sagen Millionen. Wie viel Kohärenz ist erforderlich? Manche sagen Hunderte von Nanosekunden, manche sagen Minuten.
Und all dies kann durch Techniken wie die bereits erwähnte knifflige Verwendung von Vorverarbeitungsalgorithmen umgestoßen werden. Wer weiß, welcher geniale Student sich gerade einen neuen Ansatz ausdenkt. Die Leute, die 143 auf einer Quantenmaschine berechnet haben, merkten erst zwei Jahre später, dass sie auch 56.153 geknackt hatten.
Post-Quantum-Kryptographie
Alle Wege führen in eine Post-Quantum-Welt, und viele Menschen arbeiten bereits intensiv daran. Das US National Institute of Standards and Technology veranstaltet derzeit Wettbewerbe zur Entwicklung quantenresistenter Algorithmen. Einige dieser Bemühungen führen bereits zu Ergebnissen.
Letztendlich können wir sagen, dass die Quantenbedrohung für die Kryptografie real ist, und zwar auf der Grundlage von immer mehr Ergebnissen aus der Praxis. Aber im Moment wird sie durch Gegenkräfte mehr als ausgeglichen. Vielleicht müssen wir uns irgendwann von einigen unserer geliebten Algorithmen verabschieden, aber neue werden ihren Platz einnehmen.
Es wird ein interessanter Tanz sein, den wir im nächsten Jahrzehnt beobachten werden.
*Matthew Tyson ist Mitbegründer der Dark Horse Group, Inc. Er glaubt an Technologie, bei der der Mensch an erster Stelle steht. Wenn er nicht gerade Gitarre spielt, erkundet Matt das Hinterland und die philosophischen Gefilde. Er schreibt seit 2007 für JavaWorld.
Be the first to comment