Waffengleichheit mit dem Quantencomputer

12.08.2015

Künftige Quantencomputer und einfallsreiche Angreifer bedrohen gängige Verschlüsselungsmethoden. Microsoft behauptet nun, ein Kraut dagegen zu haben

"Ein gigantisches Desaster" für die Datensicherheit drohe, sobald es eine potente Version eines Quantencomputers gibt, warnt Johannes Buchmann von der Technischen Universität Darmstadt. Denn der würde die Vertrauensbasis des Internets obsolet machen: das Verschlüsselungsverfahren RSA1.

"Es gäbe keine sichere Verbindung zu eBay oder Amazon mehr", sagt der Mathematiker. Digitale Signaturen, täglich millionenfach genutzt, könnten leicht gefälscht werden, fügt Buchmann hinzu. "Jemand könnte ein Update von Microsoft vorgaukeln und Milliarden Festplatten löschen", schildert der IT-Sicherheitsexperte.

Aber leistungsstarke Quantencomputer wird es nach Expertenmeinung frühestens in einem Jahrzehnt geben, will man einwerfen. Auch der von seinem Hersteller D-Wave-Systems als Quantencomputer bezeichnete Rechner jedenfalls kann keine Codes knacken, denn dafür ist er nicht konstruiert. Er nutzt zwar quantenphysikalische Phänomene, aber nicht jene, die ein Code knackender Quantencomputer benötigt (Rechnen 1000 Qubits schneller?).

Ist Buchmanns Szenario also überhaupt relevant? Wie lange sollen digitale Grundbucheinträge oder elektronische Steuererklärungen geschützt sein, fragt das Urgestein der Kryptographie rhetorisch zurück. 10 Jahre? 20? Oder vielleicht 100? Immer mehr langfristig schützenswerte Information wandere ins Internet, sagt Buchmann, nach dem ein inzwischen gebrochenes Verschlüsselungsverfahren aus den 1980er Jahren benannt ist. Zu Beginn der elektronischen Kommunikation sei es hauptsächlich um den Schutz kurzfristig relevanter Informationen gegangen, wie den momentanen Aufenthaltsort eines Politikers. In Zukunft werde "langfristige Datensicherheit uns immer mehr beschäftigen", sagt Buchmann.

Der Quantencomputer allein ist es nicht, der dauerhaften Schutz für Digitales bedroht. Das "Verfallsdatum" der heutigen Verschlüsselungsmethoden liege bei 20 Jahren, sagt Buchmann. Immer stärkere Rechner und immer smartere Methoden von Mathematikern nagen ständig an den etablierten Verschlüsselungs- und Signaturverfahren wie RSA. Alte digitale Signaturen und Verschlüsselungen werden daher mit der Zeit unwirksam.

Der Grund dafür: Methoden wie RSA basieren auf, wenn auch schwer lösbaren, mathematischen Problemen - und die sind eben berechenbar, wenn auch mit großem Aufwand. Ähnlich wie Einbrecher im Prinzip jede Wohnungstür knacken können, es ist nur eine Frage des Zeitaufwands und ihres Könnens. Gut geschützte Wohnungen werden sie daher meiden.

Bei RSA ist die Verschlüsselung dadurch geschützt, dass sich eine ca. 300-stellige-Zahl nur äußerst schwer in Primzahlen zerlegen lässt. Ein heutiger Rechner braucht dafür Jahrmilliarden. Ein Quantencomputer hingegen könnte die Aufgabe im Handumdrehen lösen. Es geht also darum, Daten für möglichst lange Zeit zu sichern und da sollte der Quantencomputer als Möglichkeit mitgedacht werden, meint Buchmann.

Ist ein Gitter quantensicher?

Ein Team von Microsoft, dem Chiphersteller NXP und der Queensland University of Technology hat nun ein neues Verschlüsselungsverfahren entwickelt, das angeblich dem Angriff eines Quantencomputers standhält. Es ist konzipiert für den Einbau in das Verschlüsselungsprotokoll TLS (Abkürzung für Transport Layer Security), das zur sicheren Datenübertragung im Internet dient und derzeit auf mathematischen Problemen basiert, die ein Quantencomputer schnell knacken können wird.

Dass dies möglich ist, liegt am begrenzten Können eines Quantencomputers. Es gibt eben auch knifflige Aufgaben, an denen er sich ohne schnelles Ergebnis abarbeiten wird. Dies, so glauben Experten, sind Probleme, denen eine bestimmte mathematische Struktur fehlt. Beim Zerlegen von Zahlen in Primfaktoren kommt es darauf an, Wiederholungen in extrem langen Zahlenfolgen zu finden. Die Frage lautet: Nach wie vielen Zahlen wiederholt sich die Sequenz?

Ein Quantencomputer wird gut darin sein, solche Muster in einer riesigen Zahlenmenge zu finden. Wenn aber derartige Muster nicht vorhanden sind, wird er sich ebenso schwer tun wie normale Computer. So lautet zumindest die derzeitige Annahme.

Ein Favorit für so ein quantensicheres Problem: Man setze sich mitten in ein regelmäßiges Gitter, einem Schachbrett vergleichbar, und suche den nächstgelegenen Gitterpunkt. Das ist nur dann simpel, wenn das Gitter zwei oder drei Dimensionen hat, wie eben ein Schachbrett oder das Metallgerüst eines Hochhauses. Einem virtuellen, nur im Computer existierenden Gitter kann man jedoch Tausende von Dimensionen geben. So entsteht ein enormer Wirrwarr, dem die Muster fehlen, die ein Quantenrechner nutzen könnte. Auch für jeden anderen Computer ist es äußerst schwierig, in dem Tohuwabohu von Gitterpunkten den nächstgelegen zu finden. Auf Basis dieses Problems lassen sich also veritable Verschlüsselungsverfahren entwickeln.

Buchmanns Team arbeitet gerade daran, solche gitterbasierten Verfahren reif für den Einsatz zu machen. Ein Problem besteht darin, die Verfahren so zu verschlanken, dass sie schnell genug für den quirligen Internetalltag sind. Das Team um Joppe W. Bos von NXP will das nun geschafft haben. Es nutzt eine Variante der gitterbasierten Verfahren namens "Ring Learning With Errors", kurz: RLWE (Erklärung).

Das neue Verfahren wird derzeit getestet. Dabei zeigte sich, dass es die Datenübertragung gegenüber heute genutzten Methoden nicht sehr stark, nämlich um 21 Prozent, bremst. Johannes Buchmann schränkt ein, vollständig quantensicher sei das neue Verfahren nicht, da die Zertifikate noch auf die übliche Weise signiert würden. Die digitale Signatur stellt die Urheberschaft einer verschlüsselten Nachricht sicher. Es sei zudem noch Forschung nötig, um zu zeigen, dass das RLWE-Verfahren tatsächlich quantensicher sei.

Einen Beweis, dass die gitterbasierten Verfahren tatsächlich Quantencomputern widerstehen werden gibt es nicht. Buchmann zeigt sich jedoch zuversichtlich: "Gitter haben sich bis jetzt jedem Versuch widersetzt, Quantenalgorithmen zuzulassen". Mit Quantenalgorithmus meint er ein speziell für künftige Quantencomputer entwickeltes Rechenverfahren, das die gitterbasierten Methoden schnell knackt.

Der Berliner Datenschützer Ulrich Vollmer ist skeptischer: Es gebe noch keine hinreichenden Indizien, dass die diskutierten Alternativ-Verfahren quantencomputer-resistent seien. Mit gitterbasierten Verfahren habe man zu wenige Erfahrungen, um ihnen zu vertrauen.

Cover

Christian J. Meier
Eine kurze Geschichte des Quantencomputers
Wie bizarre Quantenphysik eine neue Technologie erschafft
Als Buch bei Telepolis erschienen

x
Fehler melden
Telepolis zitieren
Vielen Dank!
Anzeige
Hellwach mit Telepolis
Anzeige
Cafe
Telepolis-Cafe

Hochwertiger Kaffee und Espresso aus Costa Rica: Die Telepolis-Edition für unsere Leser

Anzeige
Anzeige

Auf der Suche nach Planet 9

Hinweise auf einen neunten Planeten am Rand des Sonnensystems

Vom Datum zum Dossier Das gekaufte Web 9/11 - Der Kampf um die Wahrheit
bilder

seen.by

Mit dem Schalter am linken Rand des Suchfelds lässt sich zwischen der klassischen Suche mit der Heise-Suchmaschine und einer voreingestellten Suche bei Google wählen.

Tastenkürzel:

ctrl-Taste:
Zum Wechseln zwischen Heise- und Google-Suche

esc-Taste:
Verlassen und Zurücksetzen des Eingabe-Felds

Buchstaben-Taste F
Direkt zur Suche springen

SUCHEN

Mit dem Schalter am linken Rand des Suchfelds lässt sich zwischen der klassischen Suche mit der Heise-Suchmaschine und einer voreingestellten Suche bei Google wählen.

SUCHEN

.
.