Zuletzt aktualisiert am 11. April 2019 durch Jürgen Voskuhl
Sicher hat der eine oder andere Leser schon mal vom "Moore'schen Gesetz" gehört. Dieses besagt, dass sich die Komplexität integrierter Schaltkreise – und damit die Leistungsfähigkeit von Computern – innerhalb von zwölf bis 24 Monaten verdoppelt. Umgekehrt proportional verhält sich zwangsläufig die Zeit, die man für das Knacken von Passwörtern mittels Brute-Force-Angriff benötigt.
Dieser Sachverhalt erscheint zunächst nicht besonders bedrohlich, benötigt man doch hierfür mit heute verfügbarer Rechenleistung mehrere tausend Jahre.
Aktuell betreten allerdings neue Spieler das Feld, nämlich sogenannte Quantencomputer. Laut Arvind Krishna, Direktor von IBM Research, werden Quantencomputer in etwa fünf Jahren in der Lage sein, die stärksten heute gebräuchlichen Verschlüsselungsalgorithmen mühelos zu knacken.
Was sind eigentlich Quantencomputer und wie ist der aktuelle Stand der Technik? Wird Verschlüsselung zum Schutz der Privatsphäre in Zukunft sinnlos sein? Werden digitale Signaturen wertlos?
Quantencomputer: Die Grundlagen
Beschäftigen wir uns zunächst mit den wesentlichen Grundlagen eines Quantencomputers.
Ein klassischer Computer verarbeitet sogenannte Bits. Ein Bit kann den Zustand 0 oder 1 annehmen.
Im Gegensatz dazu arbeitet ein Quantencomputer mit Quanten-Bits, oder auch Qubits. Qubits können zusätzlich sogenannte "Superpositionen" annehmen, welche durch eine komplexe Zahl repräsentiert werden. Wenn sich N Qubits in einer Superposition befinden, wird dadurch eine Kombination von 2 hoch N Zuständen kreiert.
Ein klassischer Computer nimmt zu jedem bestimmten Zeitpunkt genau einen dieser Zustände an. Ein Quantencomputer kann dagegen parallel Berechnungen über alle Superpositionen durchführen.
Allerdings liefert ein Quantencomputer kein exaktes Ergebnis, er berechnet Ergebnisse mit einer Wahrscheinlichkeitsangabe. Ein Beispiel: Die Rechenoperation 1.000 + 1.000 liefert auf einem konventionellen Computer das exakte Ergebnis 2.000. Die Antwort eines Quantencomputers könnte dagegen beispielsweise "1997,4 mit einer Wahrscheinlichkeit von 98,3%" lauten. Diese Antwort liefert er dafür schnell. Sehr schnell: So haben Google und die NASA herausgefunden, das ein bestimmter Quantencomputer des Herstellers D‑Wave die Berechnung eines Optimierungsproblems über 3.600 mal schneller anstellen kann als heute existierende Supercomputer.
Umgekehrt ausgedrückt:
Mit einem klassischen Computer kann man alles berechnen, was man auch mit einem Quantencomputer berechnen kann.
Ein Quantencomputer mit wenigen Qubits kann jedoch manche Aufgaben elegant und vor allem in kürzester Zeit lösen, für die ein konventioneller Computer wegen dem explodierenden Rechenaufwand ewig brauchen würde.
Praktische Anwendungen für Quantencomputer
Präzise Mathematik ist die Stärke heutiger Standard-Computer. Dagegen werden Quantencomputer für Spezialanwendungen verwendet, nicht für Textverarbeitung. In der Praxis werden sich wohl Tandem-Systeme durchsetzen, in denen beide Komponenten ihre Stärken einbringen können.
Stand heute sind bereits drei praktische Anwendungsbereiche für Quantencomputer identifiziert:
- Die schnelle Suche in großen, ungeordneten Datenbanken
- Die Primfaktorzerlegung (wird im weiteren Verlauf des Artikels erläutert)
- Die Simulation, beziehungsweise detaillierte Berechnung beliebiger Quantensysteme
Hierbei geht es um schwer zugängliche Quanteneigenschaften von Festkörpern, Flüssigkeiten, Gasen oder andere Vielteilchensysteme
Quantencomputer: Wer fördert, wer baut?
Die Bundesregierung fördert die Quantentechnologie in der aktuellen Legislaturperiode mit der stolzen Summe von 650 Mio. Euro. Und erwartungsgemäß forscht auch die amerikanische NSA zu dem Thema.
Google betreibt seit Anfang 2018 Bristlecone, einen 72-Qubit-Quantencomputer. Erst im Januar diesen Jahres, also quasi "gerade eben" hat IBM den ersten kommerziellen Quantencomputer vorgestellt, mit einer Kapazität von 50 Qubit. Auch Microsoft und Intel sind beim Thema Quantencomputer "am Ball". Ferner existieren einige Startups, wie zum Beispiel die Firmen D‑Wave und Rigetti.
Technische Herausforderungen
Ein Problem von Quantencomputern ist die sogenannte Dekohärenz. Mit Dekohärenz ist der Verlust der Superpositionseigenschaften eines Quantenzustands gemeint.
Am einfachsten zu verstehen ist dies, wenn man ein Qubit mit einer Münze vergleicht. Die Zustände Kopf, beziehungsweise Zahl repräsentieren hierbei die Zustände 0 und 1 herkömmlicher Bits. Während sich die Münze auf einem Tisch dreht, befindet sie sich in einer Superposition. Irgendwann wird sie aber einen der beiden Zustände 0 oder 1 (beziehungsweise Kopf oder Zahl) einnehmen. Stößt jemand an den Tisch, während sich die Münze dreht, läuft dieser Vorgang vermutlich schneller ab. Geräusche, Temperaturwechsel, elektrische Leitung, Vibration – all diese Dinge stören die Qubits!
Will man einen Quantencomputer bauen, so muss man Dekohärenz verhindern – und das schaffen die Forscher derzeit nur für Bruchteile von Sekunden. Diese Herausforderung wächst zudem mit der Anzahl der Qubits.
Ein Weg, um Dekohärenz entgegenzuwirken, ist Kälte. Viel Kälte! So wird etwa der Quantencomputer von Google bei ‑70 Grad C betrieben. IBM betreibt im Labor einen Quantencomputer sogar bei einer Temperatur nahe dem absoluten Nullpunkt.
Ein weiteres Problem stellt die Software dar: Zum jetzigen Zeitpunkt ist lediglich eine Handvoll Algorithmen bekannt, welche die Geschwindigkeit eines Quantencomputers ausnutzen können. Vermutlich existieren mehr Algorithmen, diese sind aber schwierig zu finden: man kann einen existierenden Algorithmus für einen konventionellen Computer nicht einfach "quantisieren", um ihn auf einem Quantencomputer lauffähig zu machen.
Kryptographie heute
Aber was haben Quantencomputer denn nun eigentlich mit Verschlüsselung zu tun? Zur Beantwortung dieser Frage schauen wir uns zunächst mal die aktuell verwendeten Verschlüsselungsverfahren und die dafür verwendeten Algorithmen an. Diese lassen sich grob in zwei Gruppen einteilen:
Bei den symmetrischen Verfahren wird zum Ver- und Entschlüsseln dasselbe Passwort verwendet. Demzufolge muss auch der zu Grunde liegende Algorithmus symmetrisch sein. Der heute gebräuchlichste Algorithmus ist der Advanced Encryption Standard (AES).
Dem gegenüber stehen die asymmetrischen Verfahren. Hierbei werden jeweils Schlüsselpaare verwendet: Der Sender einer Information beschafft sich zunächst den öffentlichen Schlüssel des Empfängers. Damit wird die zu übertragende Information verschlüsselt und an den Empfänger gesendet. Der Empfänger kann die verschlüsselte Information dann wiederum mit seinem privaten Schlüssel entschlüsseln.
Eine Zusatzfunktion ist die digitale Signatur. Hierbei "unterschreibt" der Sender die Nachricht zusätzlich mit seinen privaten Schlüssel. Mit dem öffentlichen Schlüssel des Senders kann der Empfänger verifizieren, dass die Information auch tatsächlich vom Absender stammt und nicht verändert wurde.
Zu den bekannteren Verfahren, in denen entsprechende Algorithmen wie beispielsweise RSA zum Einsatz kommen, gehören PGP (Pretty Good Privacy) und S/MIME, welche unter anderem zum Verschlüsseln und Signieren von E‑Mails eingesetzt werden.
AES widersteht Quantencomputern
Inwiefern beeinträchtigen Quantencomputer die beschriebenen Verschlüsselungsalgorithmen? Hierbei sind vor allem zwei Algorithmen relevant, die speziell für Quantencomputer entwickelt wurden.
Der Grover-Algorithmus ist ein Quantenalgorithmus zur Suche in einer unsortierten Datenbank. Er wurde von Lov Grover im Jahre 1996 veröffentlicht. Das zugrunde liegende mathematische Problem ist vergleichbar mit einem Brute-Force-Angriff auf einen symmetrische Verschlüsselungsalgorithmus.
Auf einem klassischen Computer ist der prinzipiell schnellstmögliche Suchalgorithmus in einer unsortierten Datenbank die lineare Suche, also quasi das Ausprobieren aller in Frage kommenden Möglichkeiten. Nehmen wir als Beispiel ein Telefonbuch mit N Einträgen, in dem wir eine bestimmte Rufnummer finden wollen. Im besten Fall benötigen wir einen Versuch (der erste Versuch liefert bereits die gesuchte Nummer), im schlechtesten Fall benötigen wir N Versuche (wir finden die gesuchte Nummer erst beim letzten Eintrag). Statistisch betrachtet benötigen wir also N/2 Versuche, um die Lösung zu finden. Der Mathematiker schreibt dafür 
Ein Quantencomputer, der mit dem Grover-Algorithmus rechnet, benötigt dagegen nur
Schritte, was einer quadratischen Beschleunigung entspricht.
Offensichtlich ist also der Verschlüsselungsalgorithmus AES durch den Grover-Algorithmus und der sich daraus ergebenden Beschleunigung bedroht. Dieser Beschleunigung kann man jedoch problemlos mit längeren Schlüsseln entgegenwirken.
Quantencomputer haben also nur wenig Einfluss auf die Sicherheit des AES-Verschlüsselungsalgorithmus – vorausgesetzt, man verwendet genügend lange Schlüssel. In der Praxis wird heute eine Schlüssellänge von mindestens 192 Bit empfohlen, besser sind 256 Bit.
Die Krux mit den asymmetrischen Verfahren
Den asymmetrischen Verfahren ist gemein, das sie auf mathematisch aufwändigen Problemen basieren. Dazu gehört etwa das Problem der Primfaktorzerlegung: Jede natürliche Zahl lässt sich als Produkt von Primzahlen darstellen. Es ist vergleichsweise einfach, eine Multiplikation von Primzahlen durchzuführen. Beispielsweise ergibt 113 x 139 den Wert 15,707. Umgekehrt ist es mathematisch sehr aufwändig, unser Ergebnis 15,707 wieder in die beiden Primfaktoren 113 und 139 zu zerlegen. Der Schwierigkeitsgrad nimmt offensichtlich mit der Größe der zu zerlegenden Zahl exponentiell zu. In der Praxis werden natürliche Zahlen mit mehr als 1000 Dezimalstellen verwendet. Ein konventioneller Computer würde Jahrmilliarden benötigen, bis er zufällig richtig rät.
Bereits 1994 hat der Mathematiker Peter Shor in seinem Papier "Algorithms for Quantum Computation: Discrete Logarithms and Factoring” bewiesen, dass die Faktorisierung großer Ganzzahlen sich mit Quantencomputern fundamental verändern wird: Ein leistungsstarker Quantencomputer könnte das beschriebene Problem binnen Minuten lösen!
Damit ist klar:
Alle heute gebräuchlichen kryptographischen Verfahren zur asymmetrischen Verschlüsselung sind in naher Zukunft obsolet!
Die nachfolgende Tabelle vermittelt einen Überblick auf den Einfluss von Quantencomputern im Hinblick auf die heute gebräuchlichen Kryptographieverfahren:
| Kryptographischer Algorithmus |
Art | Anwendung | Einfluss durch Quantencomputer |
| AES-256 | Symmetrischer Schlüssel | Verschlüsselung | Sicher |
| AES-128 | Symmetrischer Schlüssel | Verschlüsselung | Nicht mehr sicher |
| SHA-256, SHA‑3 | - | Hash-Funktionen | Sicher |
| RSA | Schlüsselpaar (öffentlich/privat) | Signaturen | Nicht mehr sicher |
| ECDSA, ECDH (elliptische Kurven) | Schlüsselpaar (öffentlich/privat) | Signaturen, Schlüsselaustausch | Nicht mehr sicher |
| DSA (Finite Felder) | Schlüsselpaar (öffentlich/privat) | Signaturen, Schlüsselaustausch | Nicht mehr sicher |
Die Zukunft der Verschlüsselung
Eine Diskussion, ob Quantencomputer mit einer brauchbaren Anzahl von Qubits in drei, fünf oder erst in zehn Jahren verbreitet sein werden, ist recht müssig: Es ist sehr wahrscheinlich, das es früher oder später passiert. Im Hinblick auf diesen Tag gibt es nur eine Lösung:
Neue kryptographische Verfahren müssen her, die selbst unter Verwendung von Quantencomputern praktisch nicht zu entschlüsseln sind!
Etabliert hat sich hierfür inzwischen der Begriff "Post-Quanten-Kryptographie". Zur Erforschung entsprechender Algorithmen hat beispielsweise das NIST (National Institute of Standards and Technology) bereits 2016 einen entsprechenden Wettbewerb gestartet. Anfang diesen Jahres wurden die 26 "Halbfinalisten" verkündet. Somit existieren bereits verschiedene, zum Teil vielversprechende Algorithmen.
Auch andere Organisationen wie die IRTF (Internet Research Task Force) sind in diesem Bereich aktiv: Der Internet-Standard RFC 8391 ist der erste veröffentliche Standard zu Post-Quantum-Signaturen. Das Hash-basierte Verfahren wurde von einem Forscherteam der Technischen Universität (TU) Darmstadt und des deutschen IT-Security-Anbieters Genua unter der Leitung des Kryptographie-Experten Prof. Johannes Buchmann entwickelt.
Letztendlich gilt es also nur noch abzuwarten, bis sich verschiedene Algorithmen etabliert haben und ebenfalls als Standard verabschiedet werden.
Fazit
- Vor allem die Dekohärenz verhindert aktuell den breiten Einsatz von Quantencomputern.
- Kurfristig sind aktuellen Verschlüsselungsverfahren daher nicht bedroht.
- Die symmetrische Verschlüsselung mittels AES wird auch im Hinblick auf Quantencomputer sicher sein, sofern ausreichend lange Schlüssel (192 oder 256 Bit) verwendet werden.
- Die heutigen Public-Key-Verfahren wie zum Beispiel RSA sind mittelfristig durch Quantencomputer bedroht und sollten durch neue Verschlüsselungsverfahren ersetzt werden, sobald entsprechende Verfahren standardisiert sind.
Selbstverständlich halten wir für unsere Kunden Augen und Ohren offen und werden ihnen rechtzeitig geeignete Handlungsempfehlungen zukommen lassen.
Weiterführende Links
Vasileios Mavroeidis, Kamer Vishi, Mateusz D. Zych, Audun Jøsang: The Impact of Quantum Computing on Present Cryptography
Bundesministerium für Bildung und Forschung: Quantentechnologien
Gustav Böhm: Quantencomputer – „the next big thing“?
Karen Martin: Waiting for quantum computing: Why encryption has nothing to worry about
