Technische Bewertung

In unseren Artikeln zum RVB-Algorithmus haben wir schon einiges zur möglichen Realität eines Quantencomputers gesagt. Aus unserer Sicht, die von verschiedenen Seiten außer den Kryptologen geteilt wird, ist die Wahrscheinlichkeit für den erfolgreichen Angriff auf die derzeitigen Verschlüsselungssysteme auch langfristig äußerst gering. Verschiedene Indizien sprechen dafür, dass auch Quantencomputer bereits in Parameter-Bereichen, die bereits heute von misstrauischen Leuten verwendet werden, vermutlich genau wie klassische Verfahren nicht mehr skalieren.

Diese Einleitung zu unserem Algorithmus hat dazu geführt, dass sich die Kryptografen, die sich mit unserem Algorithmus beschäftigen sollten, fragten, wieso jemand eigentlich einen Algorithmus gegen einen Angriff entwickelt, den er nicht als realisierbar einschätzt. Aus Sicht des Praktikers ist die Frage wohl berechtigt, aus Sicht des Wissenschaftlers nicht, denn das Problem hat gleichwohl seinen theoretischen Reiz. Allerdings wurde die Frage auch dazu benutzt, mit dem Weiterlesen aufzuhören, was nun selbst aus praktischer Sicht Unfug ist, denn selbst wenn die Einleitung nicht die eigene Meinung widerspiegelt, sollte man sich mit einem Thema mindestens so lange beschäftigen, bis klar ist, ob was dran ist oder nicht.

Wir bringen hier die wesentlichen belastbaren Fakten zu Quantencomputern in Form eines FAQ - Kataloges (oder eines fiktiven Interviews, wenn man so will). Unter den Stichworten kann sich jeder im Internet (wikipedia oder secupedia und andere) weitere Informationen beschaffen.

Gibt es DEN Quantencomputer als Modell ?

Nein. Es existieren 3 unterschiedliche Quantencomputermodelle: der adiabatische Quantencomputer, der algorithmische Quantencomputer und der Einwegquantencomputer.

Wie sind die aktuellen Entwicklungsstadien ?

Am weitesten ist der adiabatische QC, der inzwischen die 1.000 Qbit-Grenze erreicht haben dürfte. Der algorithmische QC liegt je nach Interpretation bei 4-12 Qbit, der Einweg-QC ist noch theoretisches Modell. [1]

Ist jeder QC geeignet, Verschlüsselungstechniken anzugreifen ?

Nein. Nur der algorithmische QC besitzt nach übereinstimmender Meinung der Experten das Potential dazu. Der adiabatische QC wird auf anderen Gebieten eingesetzt, kann aber Verschlüsselungsprobleme nach der derzeitigen Meinung grundsätzlich nicht knacken.

Kann man mit einem QC alles machen, was ein klassischer Computer auch kann ?

Grundsätzlich ja, allerdings gibt es nur wenige Algorithmen, die tatsächlich quantenmechanische Effekte nutzen können. Bei allen anderen arbeitet der QC wie ein klassischer Computer.

Ist ein QC grundsätzlich schneller als ein klassischer Computer ?

Nein. Er ist langsamer, da ein klassischer Computer benötigt wird, um ihn zu steuern, und zusätzliche Operationen notwendig sind.

Rechnet ein QC auch mit Bits oder mit anderen Größen ?

Das Pendant zum Bit ist das Qbit. Es kann bei Messungen wie das Bit die Werte 0 oder 1 ausweisen. Insofern unterscheidet sich das Ergebnis nicht von dem eines klassischen Computers.

Was unterscheidet ein Qbit dann von einem Bit ?

Ein Qbit kann unter Nutzung quantenmechanischer Effekte während der Rechnung gewissermaßen “Zwischenwerte” zwischen 0 und 1 aufweisen. Erst eine Messung “zwingt” es, den Wert 0 oder 1 mit einer bestimmten Wahrscheinlichkeit anzunehmen. Dadurch wird der Zwischenwert beseitigt und die Rechnung ist damit beendet.

Was bedeutet “durch eine Messung wird die Rechnung beendet ?

Bei einem klassischen Computer kann man Zwischenergebnisse abfragen und dann weiterrechnen. Beispielsweise kann man so in einer IF-Verzweigung eine Entscheidung treffen. Der QC kann das nicht, wenn Quanteneffekte verwendet werden. Es gibt nur ein Endergebnis, da eine Abfrage von Zwischenergebnissen (= Messung) die Quanteneffekte aufhebt.

Liefert ein QC dann das gleiche Ergebnis wie ein klassischer Computer ?

Nein. Er liefert bei einer Messung eines der möglichen Ergebnisse. Die Kunst besteht darin, die Wahrscheinlichkeiten der möglichen Ergebnisse so zu steuern, dass das gesuchte Ergebnis mit möglichst hoher Wahrscheinlichkeit auftritt. Die Steuerung kann bewirken, dass das Ergebnis völlig anders aussieht als das des klassischen Computers und anschließend erst sehr aufwändig mit einem klassischen Computer untersucht werden muss, ob es sich um das gesuchte Ergebnis handelt.

Was sind Quanteneffekt ?

Es gibt 2 Quanteneffekte: die Superposition und die Verschränkung. Durch eine Superposition wird ein Qbit auf einen Zwischenwert gebracht. Beispielsweise kann man ein Qbit so einstellen, dass es bei 10 Messungen (jeweils nach erneuter Einstellung) 3 Mal eine 0 und 7 Mal eine 1 anzeigt.

Durch eine Verschränkung werden zwei Qbit miteinander verbunden. Im obigen Beispiel kann man dafür sorgen, dass eine Messung am Qbit 1 jeweils die Statistik erfüllt, Qbit 2 aber immer genau den gleichen Wert wie Qbit 1 zeigt.

Wie erreicht man Superposition und Verschränkung ?

Als Qbits werden Elektronen oder Atomkerne, genauer deren Spins (= magnetisches Moment) verwendet. Ein Qbit ist vereinfacht ein kleiner Magnet, der in einem Magnetfeld nach Norden oder nach Süden zeigen kann.

Bei einer Superposition führt man dem Qbit elektromagnetische Strahlung zu, die es ihm ermöglich, gewissermaßen den Zwischenwert anzunehmen, der energetische ungünstiger ist als ein reiner Wert.

Bei einer Verschränkung passiert im Grunde das Gleiche, wobei sich allerdings die Qbits “einigen” müssen, wer die Strahlungsenergie und zusätzlich noch etwas Energie des Partners aufnimmt. Das erfordert, dass man die beiden Qbits räumlich so nahe zusammenbringt, dass sie sich gegenseitig spüren, etwa wie zwei Magnete, die man zusammenschiebt. Dieser Schritt - das Zusammenführen der Qbits für einen Verschränkungsschritt - ist das Hauptproblem für die Konstruktion eines Quantencomputers.

Das Magnetbild ist zwar stark vereinfacht, beschreibt aber schon recht gut das Prinzip, mit dem man es zu tun hat.

Kann ein QC mehrere Rechnungen gleichzeitig ausführen ?

Nein. Er kann nur einen vorgegebenen Algorithmus ohne Verzweigungen ausführen, aber aufgrund der Superposition und Verschränkung mit einer Überlagerung aller möglichen Eingabewerte. Er rechnet gewissermaßen mit vielen Werten gleichzeitig, wenn dieses Bild die Angelegenheit auch nicht sehr korrekt beschreibt. Er liefert zum Schluss aber nur EIN Ergebnis, als hätte er von vornherein mit dem dazu gehörenden Eingabewert gerechnet.

Welche speziellen Quantenalgorithmen existieren ?

Bislang sind zwei Quantenalgorithmen bekannt/entwickelt:

Der Quanten-Suchalgorithmus durchsucht eine ungeordnete Liste nach einem bestimmten Wert. Beispielsweise kann er eine Superposition aller AES-Schlüssel dahingehend prüfen, ob eine gegebene Eingabe eine ebenfalls gegebene Ausgabe erzeugt.

Ein klassischer Computer würde bei N möglichen Schlüsseln nach diesem Durchlauf eine Prüfung durchführen und im Mittel nach N/2 Versuchen das Ergebnis ermittelt haben. Man könnte die Prüfung auch unterbrechen und am nächsten Tag fortsetzen oder die Aufgabe auf viele Computer verteilen, die unterschiedliche Schlüssel untersuchen.

Der Quantencomputer würde ähnlich vorgehen, müsste jedoch OHNE Unterbrechung die Rechnung sqrt(N) -fach durchführen. Nach sqrt(N) Schritten würde das Ergebnis mit hoher Wahrscheinlichkeit angezeigt werden.

Würde man beispielsweise 128 Bit-AES angreifen, benötigt ein klassischer Computer 2^127 = 1,7 * 10^38 Schritte, ein QC 2^64 = 1,8 * 10^19 Schritte. Der QC ist damit formal erheblich effektiver als ein klassischer Computer, allerdings nur bei unsortierten Listen. In sortierten Liste ist ein klassischer Computer mit ld(2^128) = 128 Schritten kaum zu schlagen. Aber AES entspricht eben einer unsortierten Liste.

Der Shor-Algorithmus ist ein weiterer Algorithmus, der nach sich wiederholenden Ereignissen sucht und die Wiederholfrequenz anzeigt. In der Mathematik asymmetrischer Verschlüsselungssysteme wie RSA gibt es solche Wiederholungen, die zum Bruch ausgenutzt werden können. Formal genügt dazu das einmalige Durchlaufen des Algorithmus, was ihn zu einem gefährlichen Gegner der klassischen Verschlüsselung macht. Die benötigt nämlich hierfür größenordnungsmäßig (?) Schritte, so dass man ihr entkommen kann, wenn man N nur groß genug macht, d.h. genügend Bit für die Zahl spendiert.

Ist der Suchalgorithmus ein geeigneter Kandidat für Angriffe ?

Nein. Die Qbits sind instabil und verlieren ihre Werte durch Wechselwirkungen mit der Umgebung. Wenn man einen Vergleich sucht, denke man an ein Bild aus Styropor-Kügelchen, die die Qbits symbolisieren. Wenn man eine unvorsichtige Bewegung macht, reicht die Luftbewegung, um sie zu bewegen, und das Bild ist zerstört. Qbits besitzen ähnlich radioaktiven Elementen gewissermaßen eine Halbwertszeit, nach der die Hälfte aller Qbits nicht mehr korrekt sind. Das gewünschte Ergebnis kann man dann natürlich vergessen.

Theoretisch rechnet man je nach System mit einer Obergrenze von 10⁴ - 10¹⁴ Operationen, die ohne Fehler durchführbar sind, und auch das muss technisch erst einmal erreicht werden. Im günstigsten Fall klafft in der Theorie zwischen Möglichkeit und Notwendigkeit beim 128 Bit-AES eine Lücke von 5 Zehnerpotenzen, die ohne Probleme fast beliebig vergrößert werden kann.

Anders ausgedrückt: ein QC läuft einfach nicht lange genug, um eine solche Verschlüsselung angreifen zu können.

Gibt es keinen Ausweg aus der Zerfallslücke ?

Doch. Es gibt Quantenkorrekturverfahren. Vereinfacht ausgedrückt, verdreifacht man die Anzahl der Qbits, verschränkt jeweils 3 Qbits und führt dann den Algorithmus gewissermaßen in 3 Parallelversionen durch. Ist die Obergrenze der Operationen erreicht, ist möglichweise eines der 3 Qbits bereits zerstört, und man würde ein falsches Endergebnis erhalten.

Um das zu verhindern, misst man eines der 3 Qbits, wobei man 0 oder 1 als Ergebnis erhält, was aber völlig uninteressant ist. Weicht der Zustand eines Qbits von dem der beiden anderen ab, kann man durch einige Tricks erreichen, dass die beiden verbleibenden im gleichen Zustand sind und durch die Messung gewissermaßen nur das “falsche” Qbit zerstört wird. Sind noch alle ok, entfernt man ein gutes Qbit, ohne die anderen zu stören. Liegen schon mehrere Fehler vor, ist allerdings nichts mehr zu retten.

Theoretisch kann man so die Anzahl der möglichen Operationen verdoppeln. Praktisch muss man die Zeiten allerdings so klein wählen, dass die Anzahl der Fehler klein im Vergleich zur Anzahl der Qbits bleibt, damit die Wahrscheinlichkeit, dass 2 Qbits in einem 3er-Paket zerfallen sind, klein bleibt.

Da verschiedene Fehler möglich sind, können pro solchem Korrekturschritt bis zu 9 Qbits notwendig werden, und wenn mehrere Korrekurschritte notwendig werden, steigt die Anzahl der Qbits weiter an. Für den Suchalgorithmus sind solche Korrekturen aber nicht ausreichend, was leicht nachzurechnen ist.

... und für den Shor-Algorithmus ?

Der Shor-Algorithmus benötigt für ein RSA-Modul von n Bit größenordnungsmäßig 3*n Qbits und n³ Operationen. Rein theoretisch wäre damit selbst ein 16.384 Bit-RSA-Modul unter optimalen Bedingungen zu knacken. In der Praxis sind sich alle Fachleute allerdings einig, dass es ohne Quantenkorrektur nicht geht. Rein rechnerisch landet man dann bei QC, die zwischen 500.000 und einigen Millionen Qbits aufweisen müssten, um diese Rechnung durchzuführen (bei 2.048 Bit RSA mindesten 50.000). Diese Zahlen beziehen sich allerdings immer auf theoretisch optimale Bedingungen.

Das sieht doch schlecht für RSA & Co aus. Wo ist der Knackpunkt in der Rechnung ?

Der Knackpunkt ist eindeutig die Verschränkung. Pro Schritt des Algorithmus kommt man nicht darum herum, Verschränkungsoperationen durchzuführen, und dazu muss man die Qbits miteinander in Kontakt bekommen und diesen auch wieder ausschalten können. Ein QC mit 50.000 Qbit muss in der Lage sein, jedes dieser Qbits mit jedem beliebigen anderen verschränken zu können, und das ist ein ernstes logistisches Problem, das auch Auswirkungen weitere denkbare Optimierungen hat. Beispielsweise könnte man auf 2 Qbit-Päärchen gleichzeitig eine Verschränkung wirken lassen, aber dazu dürfen sie sich bei der Kontaktaufnahme nicht in den Weg kommen. Außerdem kostet der Kontakt um so mehr Zeit, je weiter die Qbits voneinander entfernt sind, und Zeit ist das große Problem des QC.

Was ist der Stand der Technik ?

Wenn man von experimentellen Laborsystemen absieht, ist von IBM ein 4 Qbit-Chip entwickelt worden, an dem man auch die Korrektur ausprobieren kann. Man kann den Chip natürlich vervielfachen, aber das Problem der Verschränkung bleibt ungelöst, da eben immer nur 4 Qbit nahe genug aneinander sind. Derzeit ist uns kein technischer Ansatz bekannt, der dieses Problem lösen könnte, um auf die erforderlichen Qbit-Anzahlen im MQbit-Bereich zu kommen.

Theoretisch denkbar sind vermittelnde Verschränkungen, d.h. eine Verschränkung zwischen zwei Qbit wird durch eine Kette von Hilfsqbits weitergereicht. Das würde das physikalische Transportproblem für die betreffenden Qbits vermindern, erhöht jedoch gleichzeitig die Anzahl der notwendigen Qbits und die Rechenzeit. Man tauscht also durch solche Modelle den Teufel durch Beelzebub aus und muss erst einmal klären, wohin das theoretisch führt - von der technischen Praxis einmal ganz abgesehen.

Aber der Shor-Algorithmus wurde doch bereits in die Praxis umgesetzt

Ja und nein. Der Trick des Nachweises wurde an einem Molekülmodell durchgeführt. In dem Modell ist die Verschränkung zwischen den Qbits zwangsweise immer eingeschaltet und entspricht in etwa dem Vermittlungsmodell. Man kann es aber nicht abschalten und reine Superpositionsoperationen durchführen. Dieser experimentelle QC war daher nicht in der Lage, tatsächlich das RSA-Problem zu lösen, aber man kann theoretisch durchrechnen, welches Ergebnis er liefert, wenn die Shor-Theorie stimmt. Und genau dieses Ergebnis lieferte das Experiment. Es handelt sich mithin um einen indirekten Beweis.

Und eure Schlussfolgerung aus dem Ganzen ?

Seit 1990 ist man bis zum Jahr 2015, also in 25 Jahren, in den Bereich von ca. 12 Qbit im rein experimentellen Laborbereich, der nur für Grundlagenforschung geeignet ist, vorgestoßen, im praktischen Bereich mit dem IBM-Chip bis zu 4 Qbit. Um RSA zu gefährden, muss man die heute Technik mindestens ver-25.000-fachen für alte Verschlüsselung, ver-250.000-fachen für bereits derzeit problemlose Möglichkeiten. Diffie-Hellman-Verschlüsselung oder EC-Verschlüsselung (elliptische Kurven) haben wir dabei noch gar nicht betrachtet. Theoretisch sind diese auch angreifbar, praktisch sind aber zusätzliche Randbedingungen zu beachten, die die Probleme vergrößern.

Mit modernen Chiptechniken mag das Erreichen solcher Größenordnungen möglich erscheinen, wobei das Verschränkungsproblem aber oberhalb der 4 Qbit-Grenze noch nicht einmal ansatzweise betrachtet wurde. 20-40 Qbit mögen denkbar sein, wenn man IBM-Pressemitteilungen glauben möchte, aber in der Realität sind ganz andere Größenordnungen zu knacken. Um es einmal bildlich zu formulieren: von einem Pickup mit 1,5 to Ladefähigkeit kann man mit ein wenig Mühe auf einen LKW mit 90 to Tragfähigkeit hochrechnen, benötigt wird allerdings einer mit 125.000 to, und an der Stelle würde wohl jeder Automobiltechniker aussteigen.

Das in 10 - 15 Jahren erreichen zu wollen, halten wir angesichts der weder in der Theorie noch in der Praxis angefassten Probleme für eine Illusion. Es ist nicht auszuschließen, dass in einigen Jahrzehnten die technische Entwicklung tatsächlich QC hervorbringt, die einfache RSA-Versionen angreifen können, es ist aber auch durchaus möglich, dass sich herausstellt, dass QC in dem Bereich, in dem Angriffe durchzuführen sind, genauso wenig skalieren wie klassische Computer.

Wichtig

Im Gegensatz zur allgemeinen Panikmache halten wir RSA noch für längere Zeit für eine sichere Verschlüsselungsangelegenheit. Sollten wir mit dieser Einschätzung Unrecht haben, sind wir allerdings mit unserem RVB-Algorithmus trotzdem auf der sicheren Seite.

[1]Im Juni 2016 ist eine Verschränkung von mehr als 200 Qbit beschrieben worden, die man als Vorstufe eines Einweg-QC betrachten kann.