Streng geheim

Von jeher hatten die Menschen Geheimnisse, die sie vor einem Teil ihrer Umgebung verbergen und an andere weitergeben wollten. Chiffren dienten Liebenden, die ihr Verhältnis geheim halten wollten, Kommandanten benutzten sie zur Durchgabe von Befehlen, und Spione schickten an ihre Auftraggeber Berichte, die niemand ohne den richtigen Schlüssel entziffern konnte. In unserer Zeit ist die Verschlüsselung wichtiger denn je: Fast jede Internet-Aktivität ist mit einer Verschlüsselung verbunden, von der Eingabe eines Passworts über die Versendung einer Chat-Nachricht bis zur Bezahlung per Kreditkarte. Für all das müssen wir ein System haben, das gewährleistet, dass nur der Absender und der Empfänger der Nachricht die darin enthaltene Botschaft lesen können. Bei dieser Aufgabe ist die hohe Rechenleistung des Computers ein wichtiger Verbündeter – aber auch manchmal ein Feind.

Eine kurze Geschichte der Verschlüsselung

Die ersten Chiffren traten schon vor Jahrtausenden auf, als Menschen relativ einfache Methoden verwendeten, um einen Text in einen anderen umzuwandeln. Zum Beispiel tauschten sie jeden Buchstaben gegen einen anderen Buchstaben aus, der in einem bestimmten Abstand von ihm im Alphabet steht, oder sie vereinbarten einen Schlüssel, der festlegte, welcher Buchstabe durch welchen ersetzt würde.

Diese Methoden waren bequem mit Bleistift und Papier zu verwenden, und der Chiffrierer und der Entzifferer konnten sie sich leicht einprägen, sodass sie weit verbreitet waren, doch vor rund 1100 Jahren fand der arabische Gelehrte Jussuf Al-Kindi einen sehr einfachen Weg, um sie zu knacken. Die Methode, die Häufigkeitsanalyse genannt wird, nutzt eine bedeutende Schwäche dieser Verschlüsselungssysteme: Auch wenn wir jeden Buchstaben durch ein anderes Zeichen ersetzen, bleibt doch die Häufigkeit jedes Buchstaben in der Sprache erhalten.

So ist das E der häufigste Buchstabe in der deutschen Sprache. Wenn wir also wissen, dass wir einen Text vor uns haben, in dem jeder Buchstabe durch einen bestimmten anderen Buchstaben ersetzt wurde, und wenn der häufigste Buchstabe in dem verschlüsselten Text das G ist, dann gibt es Grund zur Annahme, dass das G im verschlüsselten Text für das E im ursprünglichen Text steht. Auch wenn die Häufigkeit der Buchstaben im verschlüsselten Text ein wenig von der für die Sprache charakteristischen Norm abweicht, kann angenommen werden, dass zumindest der zweit- oder dritthäufigste Buchstabe im Text für das E steht. Mithilfe weiterer derartiger Verfahren und einiger geschickter Rateversuche werden wir kurze Wörter identifizieren und am Ende den ganzen Schlüssel knacken, also entdecken, welchen Buchstaben jedes Symbol in dem verschlüsselten Text repräsentiert. Die Prozedur wird natürlich immer einfacher, je mehr Buchstaben wir schon entziffert haben.

Eine leichte Methode zum Knacken einfacher Verschlüsselungen: Häufigkeitsanalyse von bestimmten Buchstaben, in diesem Fall in der englischen Sprache. Illustration: Nandhp, Wikipedia, gemeinfrei

Im Laufe der Jahre wurden immer komplexere Verschlüsselungen entwickelt, aber alle konnten mit Bleistift und Papier produziert und entziffert werden. Im 20. Jahrhundert wurde es schwieriger, als man begann, mechanische Verschlüsselungsmaschinen zu bauen, deren Produkte ohne eine ähnliche Maschine nicht entziffert werden konnten. Die berühmteste war ohne Zweifel die Enigma, die die deutsche Wehrmacht in den 30er Jahren und während des Zweiten Weltkriegs verwendete. Die Polen, und in ihrem Gefolge die Briten mithilfe eines Teams, das zahlreiche Mathematiker unter der Führung des Computerwissenschafts-Pioniers Alan Turing umfasste, konnten Schwächen im raffinierten Mechanismus der Maschine ausmachen und den Code brechen. Der so gewonnene Zugang zu vielen geheimen deutschen Funksprüchen dürfte viel zum Sieg der Alliierten beigetragen haben.

Die berühmteste Verschlüsselungsmaschine von allen. Die Enigma der deutschen Wehrmacht | Foto: SCIENCE PHOTO LIBRARY / MARK WILLIAMSON

Heute gelten die Bleistift-und Papier-Verschlüsselungen nicht als sicher, und sie können alle mithilfe eines Computers relativ leicht geknackt werden. Die einzige Ausnahme ist ein Einmalverschlüsselung genanntes System, für das mathematisch bewiesen wurde, dass es sicher gegen jeden Entzifferungsversuch ist. Es hat aber den Nachteil, dass es einen zufällig gewählten Schlüssel benötigt, der genau so lang wie der zu verschlüsselnde Text sein muss, wobei jeder Schlüssel nur ein Mal verwendet werden darf. Das System erfordert also die laufende Erzeugung und Weitergabe von absolut zufälligen und sehr langen Schlüsseln. Deshalb gilt es als in der Praxis nicht einsetzbar und wird heute fast nicht mehr benutzt.

Unpraktische Verschlüsselung. Einmaltabelle zur Verschlüsselung bei der amerikanischen Nationalen Sicherheitsbehörde (NSA) | Quelle: Wikipedia, gemeinfrei

Verschlüsselung im Computer-Zeitalter

Wie sieht das heute aus, im Computer-Zeitalter? Zunächst einmal muss jede Nachricht, die verschlüsselt werden soll, in Zahlen umgewandelt werden, da die Daten im Speicher des Computers als binäre Zahlen aufbewahrt sind, die nur aus Ziffern mit den Werten eins und null bestehen. Man muss also jeden Buchstaben und jedes Zeichen in der Nachricht durch eine Zahl ersetzen. So wird die Nachricht, die versendet werden soll, zu einer Ziffernfolge, die sehr leicht zu entziffern ist. Nun muss ein Weg gefunden werden, um diese Ziffern einem anderen Menschen so zuzusenden, dass er die Nachricht lesen kann, ohne dass aber jemand, der sie abfängt, ihren ursprünglichen Inhalt erschließen könnte.

In den 60er Jahren des 20. Jahrhunderts tauchten erste Codes auf, die der Verschlüsselung elektronischer Kommunikation dienten. Diese Codes erfordern zahlreiche Berechnungen, und deshalb wäre eine Anwendung mit Bleistift und Papier allein nicht praktikabel. Sie basierten auf einem Schlüssel – einer Art geheimes Codewort, das nur dem Absender und dem Empfänger der Nachricht bekannt ist. Der Schlüssel dient der Herstellung einer verschlüsselten Nachricht und danach der Entzifferung des verschlüsselten Codes.

Die relativ alten Codes dieser Art, zum Beispiel DES, gelten nicht mehr als ausreichend sicher, weil die heute existierenden leistungsfähigen Rechner sie relativ leicht knacken können, indem sie systematisch fast alle möglichen Lösungen durchprobieren. An ihre Stelle sind moderne Codes getreten, die als sehr sicher gelten, wie etwa AES.

Die nächste Phase: asymmetrische Verschlüsselung

Alle Methoden, über die wir bis jetzt gesprochen haben, von den einfachen alten Austauschcodes über die Enigma bis zu den verbreiteten Computerverschlüsselungen, haben ein gemeinsames Problem: Damit ich jemandem eine verschlüsselte Nachricht schicken kann, brauchen wir beide den Schlüssel. Aber wie kann ich der anderen Seite zunächst einmal den Schlüssel überhaupt zukommen lassen? Wenn wir über einen gesicherten Kommunikationskanal verfügen, dann können wir ihn gleich zur Übermittlung der Nachricht verwenden, ohne dass eine Verschlüsselung notwendig wäre; und ohne einen solchen Kanal wird der Schüssel für jeden sichtbar sein, der Zugang zu dem Zustellungsweg hat.

Man stelle sich das folgende Szenario vor: Du kaufst ein Produkt im Internet und möchtest dem Site deine Kreditkartendaten schicken. Du möchtest sie natürlich verschlüsseln, sonst könnten sie bei der Übertragung gestohlen werden, und jemand könnte sie benutzen, um auf deine Kosten etwas zu kaufen. Aber wie kannst du mit dem Site einen gemeinsamen Schlüssel produzieren? Wenn der Seite dir einen Schlüssel zuschickt, dann kann er abgefangen werden, und Hacker könnten dann wiederum die verschlüsselten Kreditdaten entziffern. Methoden, mit denen solche Probleme in der Vergangenheit gelöst wurden, etwa die Verwendung von vertrauenswürdigen Kurieren, die den Schlüssel von Person zu Person überbringen, sind für so einen Fall natürlich irrelevant.

Der Durchbruch gelang 1977 mit der Entwicklung der ersten asymmetrischen Verschlüsselungsmethode RSA, die nach ihren Erfindern benannt wurde: Ron Rivest, Adi Shamir (heute am Weizmann-Institut tätig) und Leonard Adleman. Bis zu dieser Methode wurde jede Verschlüsselung symmetrisch vorgenommen, das heißt, der Vorgang bei der Entzifferung der Nachricht war die Umkehrung von jenem bei der Verschlüsselung. Bei der asymmetrischen Verschlüsselung hingegen gibt es zwei Schlüssel: einen für die Verschlüsselung der Nachricht und einen für die Entzifferung. Daher kann man den Schlüssel der Verschlüsselung nicht für die Entzifferung verwenden.

Unter diesen Umständen kann der Internet-Site seinen Schlüssel veröffentlichen, und jeder kann seine Kreditkartendaten verschlüsseln und sie an den Site senden. Doch der Entzifferungs-Schlüssel, der deshalb privater Schlüssel genannt wird, ist nur dem Site bekannt, und nur dieser kann die Information entschlüsseln. Somit kann nicht bloß niemand, der die Nachricht abgefangen hat, an die verschlüsselten Daten kommen, sondern sogar der Absender selbst kann den Vorgang nicht umkehren – denn beiden fehlt der Entzifferungs-Schlüssel. So ergibt sich ein System, das die Verschlüsselung leicht macht, während die Entzifferung sehr schwierig ist, wenn man den privaten Schlüssel nicht kennt, und leicht, wenn man ihn kennt.

Jeder kann eine Nachricht verschlüsseln, aber nicht jeder kann sie lesen. Adi Shamir, einer der Entwickler der RSA-Methode | Foto: Erik Tews, Wikipedia

Gesucht: ein Beweis

 Die Idee klingt ja gut, aber kann so ein System gefunden werden? Es gibt bis heute keinen mathematischen Beweis dafür, dass ein derartiges System wirklich existiert, obwohl das angenommen wird. In der Praxis gibt es jedenfalls Systeme, die die Voraussetzungen erfüllen: Mit ihnen ist die Verschlüsselung leicht, anhand des Schlüssels kann die Nachricht leicht entziffert werden, und man kennt keine Methode, um sie ohne den Schlüssel zu entziffern. Nicht bewiesen ist aber bisher, dass auch wirklich niemals ein leichter Weg gefunden werden kann, um den Code zu knacken und die Nachricht ohne den privaten Schlüssel zu entziffern. Die heute verbreiteten asymmetrischen Verschlüsselungsmethoden, allen voran RSA, stützen sich auf Algorithmen, von denen man annimmt, dass sie die Bedingung erfüllen, und in den vielen Jahrzehnten, seitdem sie präsentiert wurden, wurden keine Abkürzungen oder etwaige andere Schwachstellen in der Verschlüsselung gefunden.

Auch das berühmte mathematische „P=NP?“-Problem, eines der sieben im Jahr 2000 aufgelisteten Millenniumsprobleme der Mathematik, ist mit dem Thema verbunden: Auf die genaue Aussage können wir hier nicht eingehen, aber wenn bewiesen werden kann, dass P=NP, dann bedeutet das, dass es zumindest in der Theorie einen schnellen Weg gibt, jede asymmetrische Verschlüsselung zu knacken, wenn auch nicht unbedingt in der Praxis. Fast alle, die sich heute mit Computerwissenschaften befassen, halten es für sehr unwahrscheinlich, dass der Beweis gelingt. Und selbst wenn er gelingt, ist nicht anzunehmen, dass sich daraus ein praktischer Weg ergibt, um asymmetrische Verschlüsselungen rasch zu entziffern. Sogar wenn wir einen Algorithmus fänden, der der mathematischen Definition von „leicht“ entspräche, könnte er immer noch für alle praktischen Zwecke zu langsam sein.

Sehr lange Zahlen

Wir wollen hier nicht in allen Einzelheiten auf die RSA-Methode eingehen, sondern nur das Grundprinzip erklären. Zunächst wählt der Empfänger der Nachricht zwei große Primzahlen, jede von ihnen mit wenigstens einigen hundert Ziffern. Dann multipliziert er sie miteinander und gibt das Produkt für die Benutzung durch die Absender bekannt. Für die Verschlüsselung reicht die Kenntnis des Produkts. Mit seiner Hilfe erzeugt man aus der ursprünglichen Nachricht, die wie gesagt aus einer binären Zahl besteht, eine neue Zahl, die die verschlüsselte Nachricht ist.

Der private Schlüssel ergibt sich aus den Primfaktoren der Zahl, und mit ihrer Hilfe stellt man aus der verschlüsselten Nachricht die ursprüngliche Nachricht wieder her. Das Problem ist, dass man keinen einfachen Weg kennt, um eine derart große Zahl in ihre Primfaktoren zu zerlegen, also um aus dem Produkt leicht die beiden Primzahlen zurückzuerhalten, die wir miteinander multipliziert haben. Und wenn das nicht geht, können wir eben die verschlüsselte Nachricht nicht leicht entziffern.Es ist theoretisch möglich, den Code auch ohne Primfaktorzerlegung zu brechen, doch in den 44 Jahren, die seit der Erfindung der RSA-Methode vergangen sind, ist kein leichterer Weg gefunden worden, um sie zu knacken. 

Es wird angenommen, dass es keinen raschen und einfachen Weg gibt, um sehr große Zahlen in ihre Primfaktoren zu zerlegen, auch wenn das bisher mathematisch nicht bewiesen wurde. Wie schwierig ist die Primfaktorzerlegung? Das hängt hauptsächlich von der Größe der Zahl ab. Ein PC kann heute alle Primfaktoren einer 60-stelligen Zahl in einigen Sekunden finden, aber bei 80 Stellen wird er schon viele Minuten brauchen. Es gibt heute Webanwendungen, die es ermöglichen, mit Zahlen verschiedener Größen zu spielen und zu sehen, wieviel Zeit zu ihrer Zerlegung in Primfaktoren nötig ist. Um eine Zahl mit 200 Stellen vielleicht in ihre Faktoren zu zerlegen, sind schon gewaltige Rechenressourcen erforderlich, während Zahlen mit 400 Stellen alle Kapazitäten übersteigen, sogar jene von Geheimdiensten mit ihren Supercomputern.  

Vertrauenswürdige Signatur

 Die RSA-Methode hat einen weiteren wichtigen Vorteil: Sie erlaubt es, Nachrichten auf zuverlässige Weise zu signieren.

Die Verschlüsselungsmethode wirkt in beide Richtungen. Sie ermöglicht es nicht nur, einen Text zu verschlüsseln und ihn dann zu entziffern, sondern auch umgekehrt. Wenn wir versuchen, einen echten Text zu „entziffern“, also auf ihn den Entzifferungsalgorithmus anwenden und dann das Ergebnis verschlüsseln, dann erhalten wir am Ende wieder den Originaltext.

Wenn wir einen Text verschlüsseln, erzeugen wir einen Code, der nur für denjenigen lesbar ist, der den privaten Schlüssel hat. Wenn wir einen echten Text „entziffern“, erhalten wir einen Text, der für jeden lesbar ist, denn jeder kann ihn mithilfe des öffentlichen Schlüssels verschlüsseln, doch nur ein einziger Mensch konnte ihn erzeugen – derjenige, der den privaten Schlüssel hat. So kann man  zuverlässig eine Unterschrift erzeugen, die unfälschbar ist.

Die Kombination dieser beiden Eigenschaften ermöglicht es, eine Nachricht zu erzeugen, die sowohl verschlüsselt als auch signiert ist: Man verschlüsselt sie mithilfe des öffentlichen Schlüssels und entziffert die erhaltenen Nachricht mithilfe des privaten Schlüssels. So entsteht ein Text, den nur der Adressat lesen kann, und er kann auch mit Sicherheit wissen, dass seine Quelle vertrauenswürdig ist. In der Praxis ist das Verfahren etwas komplizierter als hier beschrieben, und es gibt noch andere Methoden des digitalen Signierens, aber die Möglichkeit des Signierens ist jedenfalls ein wichtiges Charakteristikum der RSA-Methode.

Die asymmetrische Verschlüsselung ist immer noch nicht die ultimative Lösung für das Verschlüsselungsproblem, denn sie hat einen bedeutenden Nachteil – die Notwendigkeit, mit sehr großen Zahlen zu hantieren. Arithmetische Berechnungen von Schlüsseln mit hunderten Stellen können den Computer erheblich verlangsamen, besonders bei kleinen Prozessoren mit beschränkten Speichern wie jene von einfachen Mobiltelefonen.

Eine verbreitete Abhilfe für diese Schwierigkeit ist die Verwendung einer asymmetrischen Verschlüsselung, um gesichert viel kürzere Schlüssel für eine gewöhnliche symmetrische Verschlüsselung zu versenden. Damit können dann alle Mitteilungen verschlüsselt werden. So löst man das Problem der Weitergabe der Schlüssel und kann trotzdem effizient und rasch Nachrichten verschlüsseln.

Ein Beispiel für einen Fall, in dem die symmetrische Verschlüsselung wegen der beschränkten Rechnerkapazität einen klaren Vorteil bringt. Smartcards von Mobiltelefonen | Quelle: Hywel Clatworthy, Wikipedia

Prima Zahlen

Das Finden von großen Primzahlen für die RSA-Verschlüsselung stellt keine besonders große Herausforderung dar. Nehmen wir an, dass wir zwei Primzahlen mit jeweils 300 Stellen finden wollen. Wenn wir 1500 Zahlen dieser Größe zufällig wählen, dann ergibt sich aus dem Primzahlsatz eine hohe Wahrscheinlichkeit dafür, dass zwei davon Primzahlen sind, denn ungefähr 1 von 700 Zahlen dieser Länge ist eine Primzahl.

Die Prüfung, ob eine Zahl eine Primzahl ist, geht sehr rasch, auch wenn es sich um Zahlen mit Hunderten von Stellen handelt, und dauert auf einem PC weniger als eine Sekunde. Wenn die Zahl keine Primzahl ist, wird unsere Prüfung uns nicht die Primfaktoren liefern, denn wir haben ja schon gesehen, dass die Primfaktorzerlegung von großen Zahlen eine sehr schwierige Aufgabe ist. Doch man kann beweisen, dass eine Zahl teilbar ist, auch ohne ihre Teiler zu finden.

Die raffinierten Algorithmen, die das bewerkstelligen, sind viel schneller als jene, die der Primfaktorzerlegung dienen. Um das zu verdeutlichen, können wir etwa zwei Primzahlen mit je 300 Ziffern nehmen. Wenn wir sie miteinander multiplizieren, hat das Ergebnis 600 Ziffern. Es kann im Nu bewiesen werden, dass diese Zahl keine Primzahl ist, doch die Primfaktorzerlegung würde mit den besten Methoden, über die wir heute verfügen, Millionen Jahre dauern, auch wenn wir dafür alle Computer der Welt zusammenspannen könnten.

Auch Supercomputer würden Millionen Jahre brauchen, um eine moderne Verschlüsselung zu entziffern. Der Supercomputer „Intrepid“ von IBM | Foto: Argonne National Laboratory, Wikipedia

Die Zukunft: Quantencomputer?

Die wichtigste Neuerung, die heute auf dem Gebiet der Verschlüsselung zu erwarten ist, ist die Entwicklung von Quantencomputern. Die Arbeitsweise dieser Rechner unterscheidet sich stark von jener der existierenden digitalen Rechner, und es ist bewiesen, dass sie die RSA-Verschlüsselung knacken können werden, denn sie werden imstande sein, relativ rasch Primfaktorzerlegungen durchzuführen.

Bis jetzt wurde das in der Praxis noch mit keiner für eine Verschlüsselung verwendete Primzahl gemacht, weil die bisher gebauten experimentellen Quantencomputer nicht stark genug sind. Man schätzt, dass Quantencomputer schon in wenigen Jahren stark genug sein werden, um Zahlen mit Tausenden von Stellen rasch zu zerlegen. Das wird zugleich das Ende der RSA-Methode sein. Auch die wichtigste andere Methode der asymmetrischen Verschlüsselung, die „Verschlüsselung mit elliptischen Kurven“, wird mit Quantencomputern geknackt werden.

Wir können die Funktionsweise von Quantencomputern hier nicht ausführlich erklären. Wir können dazu nur sagen, dass ihr Erfolgsgeheimnis darin liegt, dass die physikalischen Grundsätze, auf denen ihre elementaren Bestandteile beruhen, beim Quantencomputer ganz andere sind als bei einem herkömmlichen Computer und es den Quantencomputern erlauben, gewisse Operationen viel schneller auszuführen. Nach jetzigem Stand wird die Entwicklung starker Quantencomputer durch erhebliche physikalische Herausforderungen erschwert, und alle Quantencomputer, die bisher gebaut wurden, waren sehr klein und eingeschränkt.

Vorläufig sind ihre Kapazitäten noch sehr eingeschränkt. Der Quantencomputer „Sycamore“ von Google | Foto: Rocco Ceselin

Wie wird sich das Erscheinen von Quantencomputern auf die Verschlüsselung auswirken? Schon jetzt befasst man sich mit der Entwicklung neuer Verschlüsselungsmethoden, die auch gegen solche Computer sicher sein sollen. Man spricht dabei von Post-Quanten-Verschlüsselung. Die vorgeschlagenen Lösungen können in zwei Zugänge unterteilt werden. Der erste ist die Verwendung von asymmetrischen Algorithmen, die gegen Quantencomputer sicher sind. Man kennt einige solche Algorithmen, wie etwa NTRU, doch sie gelten als nicht so gut wie RSA oder die elliptischen Kurven, oder es wurde mit ihnen noch nicht genug Erfahrung gesammelt. Wenn sie weiter ausgebaut und verbessert werden, könnten sie die meisten existierenden Verschlüsselungsmethoden verdrängen. Man bemüht sich auch um die Festlegung eines neuen Standards für Verschlüsselungen, der gegen Quantencomputer sicher sein soll.

Der zweite Zugang wird manchmal Quantenverschlüsselung genannt, obwohl die Bezeichnung etwas irreführend ist, weil das Verfahren überhaupt nichts mit Quantencomputern zu tun hat. Die Idee besteht darin, Phänomene der Quantenmechanik zu nutzen, um Kommunikationskanäle zu schaffen, die nicht angezapft werden können. Damit ist gemeint, dass die beiden kommunizierenden Seiten es merken würden, wenn ein Dritter auf die in dem Kommunikationskanal übertragene Information zugreift. In dem Moment, da sie wissen, dass niemand sie belauscht, können sie den Kanal benutzen, um Schlüssel für eine Einmaltabellen-Verschlüsselung zu übertragen, die auch gegen die Rechenkapazität von Quantencomputern sicher sein soll.

Die Quantenverschlüsselung ist eine sicherere Methode als der oben erwähnte erste Zugang, aber auch kostspieliger und schwerfällig. Zum Unterschied zum ersten Zugang wurde sie bisher auch nicht auf breiter Basis angewendet, sondern nur experimentell, und für ihre Entwicklung werden einige physikalische Herausforderungen zu bewältigen sein.

Die Verschlüsselung ist ein Gebiet, auf dem die Forschung nie stillsteht, eben so wenig wie die Akteure, die versuchen, die Codes zu knacken. Es ist ein Gebiet, das die Menschen seit Jahrtausenden beschäftigt und das die Forschung noch für viele weitere Jahrtausende vor neue Aufgaben stellen wird. Wo das hinführt? Wir wissen es nicht. Aber sicher ist: Es bleibt spannend.