Kryptographie nach dem Quantencomputer

04. November 2012 Hanno Böck

Quantencomputer würden große Teile der heute verwendeten Kryptographiesysteme unbrauchbar machen. Alternativen gibt es, von einem Praxiseinsatz sind sie aber noch weit entfernt

Der folgende Beitrag ist vor 2021 erschienen. Unsere Redaktion hat seither ein neues Leitbild und redaktionelle Standards. Weitere Informationen finden Sie hier.

Die beiden Physik-Nobelpreisträger Serge Haroche und David Wineland haben mit ihrer Forschung dazu beigetragen, den Grundstein für künftige Quantencomputer zu legen. So begründet das Nobelpreiskomitee seine diesjährige Auszeichnung. Es lenkt damit Aufmerksamkeit auf ein Thema, das manchem Kryptographen Kopfzerbrechen bereitet. Denn Quantencomputer würden viele heute verwendete Verschlüsselungs- und Signaturverfahren unbrauchbar machen. Deshalb forschen Wissenschaftler bereits heute daran, welche Algorithmen gegen Angriffsversuche durch Quantencomputer resistent sind.

Ein wichtiger Baustein von sicheren Internetverbindungen - ganz praktisch etwa der Aufruf einer Webseite über https oder der Versand einer verschlüsselten E-Mail - sind sogenannte Public-Key-Algorithmen. Deren Eigenschaft: Verschlüsselt wird mit einem sogenannten öffentlichen Schlüssel, entschlüsselt mit einem privaten Schlüssel. Geheim gehalten wird nur der private Schlüssel. Auch für digitale Signaturen gibt es Public-Key-Verfahren, hier läuft es genau andersrum. Eine Signatur wird mit einem privaten Schlüssel erstellt, überprüft werden kann sie wiederum mit einem öffentlichen Schlüssel.

Die Public-Key-Kryptographie ist aus dem heutigen Internet kaum wegzudenken. Denn die alternative, sogenannte symmetrische Verschlüsselungsverfahren wie AES, bei denen Sender und Empfänger denselben Schlüssel verwenden, würde in der Praxis zu großen Problemen führen. Vor der Nutzung müsste eine sichere Übertragung der Schlüssel, etwa durch ein persönliches Treffen, stattfinden.

Das bekannteste und mit Abstand am häufigsten eingesetzte Public-Key-Verfahren ist RSA, das sowohl für Signaturen als auch für Verschlüsselung genutzt werden kann. Entwickelt wurde es im Jahr 1978 und ist nach seinen Erfindern Ron Rivest, Adi Shamir und Leonard Adelman benannt. Das RSA-Verfahren basiert auf dem Faktorisierungsproblem großer Zahlen. Faktorisierung bedeutet, eine Zahl als Produkt von Primzahlen darzustellen. Ein einfaches Beispiel: Die Faktorisierung von 15 ist 3*5. Die Faktorisierung sehr großer Zahlen lässt sich nur mit riesigem Aufwand durchführen - und darauf basiert die Sicherheit von RSA. Selbst mit den besten heute verfügbaren Supercomputern wäre das Brechen eines langen RSA-Schlüssels (2048 Bit gelten heute als sicher) innerhalb der Lebenszeit eines Menschen nicht durchführbar.

Theorie und Praxis

1994 gelang es dem Mathematiker Peter Shor zu zeigen, dass sich dies mit einem Quantencomputer fundamental ändern würde. Ein von Shor entwickelter Algorithmus wäre in der Lage, eine Faktorisierung großer Zahlen in kurzer Zeit durchzuführen - allerdings konnte zu diesem Zeitpunkt niemand diesen Algorithmus praktisch nutzen, da Quantencomputer nur als theoretisches Konzept existierten.

Quantencomputer sind in der Lage, in überlagerten Zuständen zu rechnen. Grob vereinfacht bedeutet das: Sie können eine Rechenoperation nicht nur für eine bestimmte Zahl, sondern für alle möglichen Zahlen mit einer bestimmten Länge gleichzeitig durchführen und somit die Geschwindigkeit radikal erhöhen. Allerdings ist das tatsächlich nur eine grob vereinfachte Darstellung. In der Praxis lassen sich nur sehr spezielle Probleme mit einem Quantencomputer lösen. Sie würden somit keineswegs, wie oft fälschlicherweise behauptet wird, das Ende aller Verschlüsselungsverfahren einläuten.

So faszinierend Quantencomputer in der Theorie sind, in der Praxis stehen sie vor kaum überwindbaren Problemen. Die einzelnen Speicherbausteine, die sogenannten Qubits, müssen in einem verschränkten Zustand gehalten werden. Genutzt werden können hierfür im Prinzip alle physikalischen Teilchen, doch müssen diese isoliert vom Einfluss anderer Teilchen gehalten werden, sonst würde die Verschränkung sofort zusammenbrechen. Deswegen sind Forschungen wie die von Wineland und Haroche so entscheidend. Sie haben Methoden entwickelt, einzelne Teilchen unter kontrollierten Bedingungen zu beobachten. Für einen Quantencomputer, der heutige Verschlüsselungsverfahren bricht, müssten aber mehrere tausend Teilchen in einem verschränkten Zustand gehalten werden.

Viele Physiker zweifeln daran, dass Quantencomputer mit einer nennenswerten Rechenleistung jemals gebaut werden. Als Durchbruch galt bereits, dass IBM im Jahr 2001 einen Quantencomputer mit 7 Quantenbits erfolgreich nutzen konnte, um die Zahl 15 zu faktorisieren. Aus theoretischer Sicht ist dies sicher sehr spannend, denn hier wurde Shors Algorithmus zum ersten Mal in der Praxis eingesetzt. Doch es ist offensichtlich: Ein solcher Quantencomputer ist für den Praxiseinsatz komplett nutzlos.

Eine Ankündigung der kanadischen Firma D-Wave, sie habe einen Quantencomputer mit 128 Qubits für den Praxiseinsatz entwickelt, wurde von der Wissenschaft skeptisch aufgenommen. Für die Kryptographie ist der D-Wave-Computer jedoch, selbst wenn er funktioniert, weitgehend uninteressant: Es handelt sich nicht um einen universellen Quantencomputer und zur Ausführung von Shors Algorithmus wäre er nicht in der Lage.

Shors Algorithmus bricht alle heute genutzten Verfahren

Doch trotz dieser Aussichten: Vollständig ausschließen, dass ein großer Quantencomputer gebaut wird, kann heute auch niemand. Daher beschäftigen sich Kryptographen seit einigen Jahren mit der Frage, welche Perspektiven die Kryptographie nach dem Quantencomputer hätte. Vordenker dieser sogenannten Post-Quanten-Kryptographie ist der US-amerikanische Professor Daniel J. Bernstein. Zwar sagt auch Bernstein, dass es unklar sei, ob große Quantencomputer je Realität werden. Doch trotzdem sei es notwendig, sich für den Fall der Fälle vorzubereiten und Kryptographiesysteme für eine mögliche Zukunft mit Quantencomputern zu entwickeln.

Für symmetrische Verfahren wären Quantencomputer nur eine geringe Bedrohung. Shors Algorithmus spielt hier keine Rolle, es gibt jedoch den Quantenalgorithmus von Grover , der die Geschwindigkeit eines Angriffs auf die Quadratwurzel reduzieren würde. In der Praxis hieße das: Ein Schlüssel mit einer Länge von 128 Bit hätte nur noch eine Sicherheit von 64 Bit. Als sicher gelten etwa 80 Bit. Der weit verbreitete Standard AES kann mit Schlüssellängen von 128 Bit oder 256 Bit genutzt werden, wer Angst vor Quantencomputern hat, sollte also auf die kürzere Variante verzichten. Generell gilt: Für symmetrische Verfahren und auch für sogenannte Hash-Funktionen, die in der Kryptographie oft eine wichtige Rolle spielen, ließe sich das Problem Quantencomputer durch mehr Bits aus der Welt schaffen.

Bei den Public Key-Verfahren sieht die Situation jedoch deutlich schlechter aus: Praktisch alle heute verwendeten Verfahren basieren auf zwei mathematischen Problemen: Die oben bereits erwähnte Faktorisierung (RSA) und die Berechnung sogenannter diskreter Logarithmen (DSA-Signaturen und ElGamal-Verschlüsselung). Beide sind von der mathematischen Struktur her ähnlich und lassen sich mit Shors Algorithmus in kürzester Zeit brechen. Die in jüngerer Zeit häufiger eingesetzten Algorithmen auf Basis elliptischer Kurven (etwa ECDSA) nutzen eine Abwandlung des diskreten Logarithmusproblems und bieten ebenfalls keinen Schutz gegen Quantencomputer.

Viele Algorithmen scheiterten

Dass die Zahl der Algorithmen in der Public-Key-Kryptographie so übersichtlich ist, hat einen Grund: Es gab in der Vergangenheit nicht wenige Vorschläge für neue Verfahren, die sich später als unsicher herausstellten. Darunter auch solche, die als aussichtsreiche Kandidaten für Post-Quanten-Kryptographie galten.

Das EU-Forschungsprojekt NESSIE gab im Jahr 2003 eine Liste kryptographischer Algorithmen heraus und empfahl für digitale Signaturen drei Verfahren, darunter den Algorithmus SFLASH. Keine gute Empfehlung: Im Jahr 2007 konnte ein Team um den Kryptographen Adi Shamir (das "S" in RSA) zeigen, dass SFLASH ganz ohne Quantencomputer mit geringem Aufwand vollständig gebrochen werden kann.

Die Geschichte von SFLASH ist keineswegs einzigartig. Viele Vorschläge für Public-Key-Verfahren erweisen sich nach näherer Untersuchung als unsicher. Lange Zeit etwa galt das relativ alte McEliece-Verfahren (1978 - ein Jahr nach RSA - präsentiert) als Möglichkeit, Quantencomputern Paroli zu bieten. Es galt zwar als unpraktikabel, da seine Schlüssel mehrere hundert Kilobytes groß sind, doch einige exotische Anwendungen nutzten es trotzdem, darunter etwa das (inzwischen eingestellte) Privacy-Netzwerk Entropy. Daniel Bernstein beendete die Hoffnungen auf McEliece im Jahr 2008 und präsentierte auch hier einen Angriff mit Hilfe klassischer Computertechnik.

Als aussichtsreicher Kandidat für die Post-Quanten-Kryptographie gelten momentan sogenannte Gitter-basierte Algorithmen. Das Public Key-Verfahren NTRU, welches für Verschlüsselung und Signaturen eingesetzt werden kann, ist hierbei am weitesten entwickelt. Ein Nachteil für die Praxis: NTRU ist patentiert. Damit ist ein Einsatz etwa im Rahmen von https momentan kaum denkbar. Die Patente laufen jedoch 2016 aus.

Bei der Frage nach künftigen Public Key-Algorithmen muss man sich vergegenwärtigen, wie Vertrauen in kryptographische Verfahren entsteht: Es ist mit heutigen Mitteln kaum möglich, die Sicherheit eines Verfahrens mathematisch zu beweisen. Eine Ausnahme bilden dabei nur einige wenige in der Praxis untaugliche Algorithmen wie One-Time-Pads. Ein Verfahren gilt daher dann als besonders sicher, wenn es über einen längeren Zeitraum umfangreich von Experten untersucht wurde. Hier zeigt sich die Stärke von RSA: Seit 35 Jahren befassen sich Kryptographen hiermit. Zwar wurden die Angriffsmethoden besser und kurze RSA-Schlüssel, die früher zum Einsatz kamen, gelten heute als unsicher. Doch bislang scheiterten alle Versuche, einen Angriff gegen RSA mit langen Schlüsseln durchzuführen.

Hier zeigt sich auch das Problem von Alternativen wie NTRU. Zwar widersetzt es sich bislang erfolgreich allen Versuchen, seine Sicherheit zu erschüttern. Doch da NTRU bisher allenfalls in Nischenanwendungen zum Einsatz kommt, steht es weit weniger im Rampenlicht als RSA. Ein Angriff auf RSA oder einen anderen häufig eingesetzten Algorithmus wäre eine Sensation, der Anreiz für Wissenschaftler ist groß, sich damit zu beschäftigen. Ein Angriff auf NTRU dürfte höchstens als Fußnote in die Wissenschaftsgeschichte eingehen.