Die Presse über uns

Bedrohen Quantencomputer die heutige Verschl├╝sselung?

Elektronik - 20/2003
11.10.2003

Die Quantenmechanik eröffnet völlig neue Möglichkeiten bei der Konstruktion von Rechenmaschinen. Der Übergang ist etwa so drastisch wie beim Wechsel von Relais zum Transistor. Sollten solche Computer jemals Realität werden, dann sind die mit den heute üblichen Methoden verschlüsselten Daten plötzlich nicht mehr sicher. Zwar sind Quantencomputer von einer praktischen Realisierung noch weit entfernt, doch Forscher halten die Behauptung, dass Quantencomputer nicht realisierbar seien, für unseriös.

"Wie sicher ist Kryptographie?" war das Thema eines Workshops im Fraunhofer-Institut für Graphische Datenverarbeitung in Darmstadt. Einen ganzen Tag lang referierten Fachleute über die Sicherheit heutiger und zukünftiger Verschlüsselung, über adäquate Schlüssellängen, die Sicherheit neuer Algorithmen und die möglichen Konsequenzen der Einführung von Quantencomputern.

Kryptographie war stets der dauernde Wettbewerb zwischen Verschlüsselung und Analyse. Schon im fünften Jahrhundert v. Chr. hatten die Spartaner ein Verfahren, in dem die Buchstaben des Klartextes anders angeordnet werden. Auch von Julius Cäsar ist ein Verschlüsselungsverfahren bekannt, in dem jeder Klartextbuchstabe durch einen festen, anderen Buchstaben ersetzt wird. Cäsar verschlüsselte durch eine einfache Schiebeoperation. Der Schlüssel war eine ganze Zahl, die angab, um wie viele Buchstaben der Klartext verschoben wird. Ist der Schlüssel z.B. "3", dann wird A zu D, B wird zu E, C zu F usw. Solche Schiebeoperationen sind durch Häufigkeitsanalysen sehr einfach zu entschlüsseln. Der Angreifer muss dazu nur wissen, in welcher Sprache das verschlüsselte Dokument abgefasst ist. In der deutschen Sprache ist E der mit Abstand am häufigsten vorkommende Buchstabe: durchschnittlich 17 Prozent der Buchstaben eines deutschen Dokuments sind E. Der zweithäufigste Buchstabe ist das N usw. Bei einer Substitution verschiebt sich dieses Häufigkeitsmuster einfach und so kann die Verschlüsselung durch Rückverschiebung entschlüsselt werden.

Dieser Zusammenhang kostete auch Maria Stuart im 16. Jahrhundert den Kopf. Die schottische Königin war von den Engländern eingekerkert worden, weil man ihr den Vorwurf machte, sie wolle die englische Krone vom Thron stürzen. Allerdings fehlten dazu noch die Beweise. Maria Stuart tauschte jedoch mit ihren Helfern außerhalb der Gefängnismauern geheime Nachrichten aus, die mit einer erweiterten monoalphabetischen Substitution verschlüsselt waren. Im Unterschied zur Cäsar-Verschlüsselung existierten dabei noch zusätzliche Symbole für häufig vorkommende Worte wie "wenn", "mein", "dein", "dort", "dies", "und" usw. Maria Stuart übergab ihre Botschaften einem Boten, der als Doppelspion für beide Seiten tätig war und die verschlüsselten Nachrichten auch an die Engländer übergab. Es gelang ihnen, den Code zu entschlüsseln und so kamen sie in den Besitz der Beweise, die letztlich zur Hinrichtung von Maria Stuart führten.

Heute sind im Wesentlichen zwei Verfahren der Verschlüsselung verbreitet: die symmetrische und die asymmetrische Verschlüsselung. Beim symmetrischen Verfahren wird der gleiche Schlüssel zum Ver- und Entschlüsseln verwendet. Die Schwachstelle dieses Verfahrens liegt also in der Übermittlung des Schlüssels. Die Geheimnummer der EC-Karte ist z.B. ein solcher Schlüssel. Es gibt zwei Schwachstellen, an denen ein Angreifer in den Besitz von EC-Karten und Geheimzahl kommen kann: im Rechenzentrum der Bank, wo die Geheimzahl ausgedruckt wird, und im Briefkasten des Empfängers, wo der Brief abgefangen werden kann. Der Angreifer kann den Magnetstreifen der EC-Karte kopieren und dann mit der Geheimzahl frei über das Konto verfügen. Die gebräuchlisten symmetrischen Verschlüsselungsverfahren sind DES (Data Encryption Standard), die Erweiterung Triple-DES und AES (Advanced Encryption Standard).

Für sichere symmetrische Verschlüsselung ist je ein Schlüssel für je eine Kommunikationsbeziehung notwendig. Wenn n die Anzahl der Kommunikationsbeziehungen ist, werden n(n-1)/2 Schlüssel gebraucht, damit alle Teilnehmer verschlüsselt Nachrichten austauschen können. Bei derzeit 300 Mio. Internetnutzern waären das 45 x 1015 Schlüssel. Das ist nicht handhabbar. Dieses Problem glaubte man, durch die asymmetrische Verschlüsselung aus der Welt geschafft zu haben. Dabei kommen unterschiedliche Schlüssel beim Ver- und Entschlüsseln zum Einsatz. Jeder Kommunikationsteilnehmer hat einen privaten und einen öffentlichen Schlüssel. Der Sender verschlüsselt mit seinem privaten Schlüssel und dem öffentlichen Schlüssel des Empfängers. Der Empfänger entschlüsselt mit dem öffentlichen Schlüssel des Senders und seinem eigenen privaten Schlüssel. Da die öffentlichen Schlüssel kein Geheimnis sind, können sie beliebig ausgetauscht werden. Das Problem der Schlüsselverteilung ist damit gelöst.

Der bekannteste asymmetrische Algorithmus RSA ist nach seinen Erfindern Ron Rivest, Adi Shamir und Leonard Adleman benannt. Die Analyse des RSA-Algorithmus kann auf eine Primfaktorzerlegung reduziert werden - ein extrem rechenaufwendiger Vorgang. Im April 2003 gelang es erstmals, eine RSA-Verschlüsselung mit 160 bit Schlüssellänge zu analysieren. Allerdings betrug der dazu nötige Rechenaufwand mehrere 100 Computerjahre. Da die Komplexität der Analyse exponentiell mit der Schlüssellänge wächst, gilt der RSA-Algorithmus mit einer entsprechenden Schlüssellänge (192 bit und mehr) jedoch nach wie vor als sicher.

Sicherheit für hundert Jahre

Das Problem der Kryptoanalyse muss jedoch im langfristigen Rahmen gesehen werden. Gerhard Schabhüser vom Bundesamt für Sicherheit in der Informationstechnik und zuständig für die Bewertung von kryptographischen Methoden u.a. bei der Bundeswehr sagte auf dem Fraunhofer-Workshop in Darmstadt: "Für Verschlüsselung bei der Bundeswehr müssen wir garantieren, dass die Dokumente nach Ende der Einsatzphase eines Verschlüsselungssystems noch dreißig Jahre sicher geschützt sind. Die heute bei der Nato im Einsatz befindlichen Geräte wurden in den sechziger Jahren entwickelt und sind nicht kaputt zu kriegen. Da kann man mit dem Panzer drüberfahren - die funktionieren immer weiter, noch mindestens zwanzig Jahre. Und wenn die Dokumente dann noch weitere dreißig Jahre sicher sein sollen, dann sprechen wir hier von einem Zeitraum von rund hundert Jahren Schutz."

Die Sorge, dass Quantencomputer heutige kryptographische Methoden brechen könnten, ist also keineswegs unberechtigt, auch wenn ihre Realisierung noch lange nicht bevorsteht. Fast alle kryptographischen Verfahren wurden in der Vergangenheit gebrochen. Es gibt keinen Grund zu der Annahme, das dies in Zukunft anders sein wird. Die Schätzungen, wann Quantencomputer realisierbar sein werden, reichen von fünf bis zweihundert Jahre in die Zukunft. Die Theorie der Quantenphysik und der Quantenalgorithmen ist sehr gut abgesichert, doch in der Praxis gibt es noch große, fundamentale Probleme. So begrenzt z.B. die Dekohärenz die Dauerhaftigkeit von Quantenspeichern und die Reichweite der Kommunikation. Auch die Verarbeitung von Quantenbits führt aufgrund ihrer Natur zu Fehlern, die sich akkumulieren. Doch für alle diese Probleme existieren bereits theoretische Lösungen. Es scheint eher eine Frage zu sein, wann die Realisierungsprobleme gelöst werden können, weniger ob sie gelöst werden. "Bewertungen, die Quantencomputer für unrealisierbar halten oder die Realisierung in die beliebig ferne Zukunft verschieben, sind unseriös", sagt Dr. Andreas Schmidt vom Fraunhofer-Institut für Sichere Telekooperation.

Wenn es soweit ist und Quantencomputer eines Tages existieren, dann sind alle Algorithmen bedroht, die auf Primfaktorzerlegung beruhen - und dazu zählt auch der populäre RSA-Algorithmus. Quantencomputer zeichnen sich durch eine massive Parallelität aus - sie können Operationen mit allen Registerwerten gleichzeitig ablaufen lassen. Diese Fähigkeit führt insbesondere zu einer sehr schnellen Fouriertransformation, die die Grundlage des Faktorisierungsalgorithmus ist. Der DES-Algorithmus ist weniger stark betroffen, da der Analyseaufwand hier durch Quantencomputer nur halbiert würde. Eine Verdopplung der Schlüssellänge könnte dieses Sicherheitsdefizit wieder ausgleichen. Algorithmen auf Basis von elliptischen Kurven, die zwar seit ca. zehn Jahren diskutiert werden, aber erst seit rund einem Jahr in praktische Anwendungen eindringen, sind nach heutigem Wissensstand durch die Dechiffrierung mittels Quantencomputer gefährdet. jk