Partner von
Partner von

Kryptografie

Die einen wollen Geheimnisse bewahren, die anderen wollen sie lüften. Der Kampf zwischen Ver- und Entschlüsselern tobt seit Beginn unserer Zivilisation. Eine kleine Historie der Kryptografie.





• Die Ägypter bemalten die Wände der Pharaonen-Gräber mit Fantasie-Hieroglyphen, als kleine Rätsel für Besucher. Das Kamasutra empfahl Frauen, Geheimschriften zu lernen, um ihre Affären zu verbergen. Und Herodot berichtete im 5. Jahrhundert vor unserer Zeitrechnung vom Kampf der Griechen gegen Persien. Ein Bote überbrachte den Griechen eine leere Schreibtafel. Erst als sie das Wachs von der Tafel kratzten, kam die Nachricht zutage. Ein anderes Mal rasierte man den Kopf des Kuriers, brannte eine Nachricht in die Kopfhaut und wartete, bis die Haare nachgewachsen waren. Offenbar hatte man damals Zeit.

Wird eine Nachricht so versteckt, dass man sie nicht sieht, nennt man das Steganografie (altgriechisch steganos = bedeckt). Zeitgleich entstand die Kryptografie (altgriechisch kyptos = verborgen). Nicht die Botschaft wurde verborgen, sondern ihr Sinn.

Caesar-Verschiebung

Julius Caesar benutzte das sogenannte Substitutionsverfahren. Dabei ersetzte er jeden Buchstaben einer Nachricht durch den Buchstaben, der zum Beispiel eine Stelle weiter im Alphabet folgt. Man nennt dieses Verfahren heute eine Caesar-Verschiebung.

siehe Beispiel Bild 1

Unsere Überschrift lautet also: Die Kunst des Verbergens. Die Caesar-Verschiebung ist eine monoalphabetische Verschlüsselung, weil dem Text nur ein einziges Geheimalphabet zugrunde liegt. Das Verfahren ist einfach – aber auch leicht zu knacken.

Häufigkeitsanalyse

Theologische Schulen im Orient waren die Ersten, denen das gelang – mit der Häufigkeitsanalyse. Sie stellten fest, dass manche Wörter und Buchstaben öfter vorkommen als andere. Dies kann als Schlüssel benutzt werden, um Geheimschriften zu entziffern. Die ersten Beschreibungen stammen aus dem 9. Jahrhundert.

Im Deutschen kommt der Buchstabe E am häufigsten vor, dann folgen das N und das I. Beim Entschlüsseln sucht man auch im Geheimtext nach den meistwiederholten Zeichen und ersetzt sie. Einer der ersten großen europäischen Codeknacker war Giovanni Soro, ab 1506 Geheimsekretär Venedigs. Befreundete Staaten schickten ihm abgefangene Botschaften, die er mithilfe der Häufigkeitsanalyse entzifferte. Die monoalphabetischen Verschlüsselungen waren damit eigentlich überholt.

Vigenère-Verschlüsselung

Der Florentiner Universalgelehrte Leon Battista Alberti schlug bereits im 15. Jahrhundert vor, mehrere Geheimtextalphabete zu benutzen, aber erst der französische Diplomat Blaise de Vigenère machte daraus eine Methode. Die Vigenère-Verschlüsselung besteht aus 26 verschiedenen Geheimtextalphabeten, die als Zeilen eines Quadrats dargestellt werden, und arbeitet zusätzlich mit einem Schlüsselwort (siehe Bild auf der nächsten Seite). So wird in unserem Beispiel der erste Buchstabe d mit e übersetzt. Denn der erste Buchstabe des Schlüsselwortes brandeins, b, gibt die Zeile an, mit der verschlüsselt wird. Es ist die, die mit b beginnt. In dieser Zeile entspricht das gesuchte d einem e.

siehe Beispiel Bild 2

Eine solche polyalphabetische Verschlüsselung ist mit der Häufigkeitsanalyse allein nicht mehr zu lösen. Trotzdem fand sie zunächst wenig Beachtung, weil sie mühsam war.

Erst Ende des 16. und Anfang des 17. Jahrhunderts wurde die Kryptoanalyse zu einem richtigen Gewerbe. Alle europäischen Mächte richteten damals sogenannte Schwarze Kammern ein. Die schlagkräftigste war die Geheime Kabinettskanzlei Wien, in die sämtliche Diplomatenpost umgeleitet wurde. Dort folgte man einem strengen Tagesplan: Die Briefe kamen um sieben Uhr morgens an, Sekretäre schmolzen die Siegel, Stenografen fertigten Abschriften, innerhalb von drei Stunden steckte man die Briefe wieder in die Umschläge, versiegelte sie und lieferte sie zurück zum Hauptpostamt, von wo aus sie zugestellt wurden. Die erlangten Informationen wurden auch an fremde Mächte verkauft. Die Professionali-tät der Kammern machte die monoalphabetische Verschlüsselung endgültig wertlos. Wer vertraulich kommunizieren wollte, war nun gezwungen, die Vigenère-Verschlüsselung zu nutzen.

Kasiski-Test

Der britische Exzentriker Charles Babbage war es, der schließlich auch die Vigenère-Methode entzauberte. Zuerst suchte er im Geheimtext nach Buchstabenfolgen, die sich wiederholten. Dann schloss er aus den Abständen zwischen den Wiederholungen auf die Länge des Schlüsselwortes. Das Schlüsselwort brandeins hat beispielsweise neun Buchstaben. Im Vigenère-Quadrat entspricht das neun Zeilen, also auch neun monoalphabetischen Verschlüsselungen. Und diese können wiederum mit der Häufigkeitsanalyse gelöst werden.

Charles Babbage gelang diese Entdeckung um 1854. Sie wurde aber nie veröffentlicht. Erst in seinem Nachlass fanden sich entsprechende Unterlagen. 1863 gelangte aber der pensionierte preußische Offizier Friedrich Wilhelm Kasiski zu denselben Schlüssen – seither ist das Verfahren als Kasiski-Test bekannt.

Die Kryptoanalytiker hatten damit wieder die Oberhand und setzten die Gegenseite unter Druck. Der Telegraf war bereits erfunden, drahtlose Funkgeräte sollten folgen. Beide konnten problemlos abgehört werden. Im Ersten Weltkrieg fingen allein die Franzosen rund 100 Millionen Wörter der Deutschen ab. Sie hatten das stärkste Codebrecher-Team in ganz Europa.

One Time Pad

Gegen Ende des Ersten Weltkriegs entwickelten amerikanische Kryptografen auf Basis der Vigenère-Verschlüsselung das One Time Pad. Statt eines sich wiederholenden Schlüsselwortes nutzten sie völlig zufällige Buchstabenfolgen, die so lang waren wie die Nachricht selbst. Davon musste eine ungeheure Menge erzeugt und gleichzeitig an alle Funker verteilt werden. Das Verfahren erforderte jeweils Hunderte Blatt Papier. In der Praxis war die Methode unbrauchbar.

Enigma

Der Deutsche Arthur Scherbius gründete 1918 eine Firma für allerlei Erfindungen. In seiner Werkstatt entstand die gefürchtetste Chiffriermaschine der Geschichte: die Enigma. Sie bestand aus einer Tastatur und rotierenden Walzen, die Buchstaben ver- und entschlüsseln konnten. Entscheidend war die genaue Ausgangsposition der Walzen. Wer eine Botschaft entschlüsseln wollte, musste die ursprüngliche Position der Walzen kennen. Es gab zunächst 17 576 Stellungen und, nach weiteren Verbesserungen durch Scherbius, schließlich mehr als zehn Billiarden mögliche Schlüssel. Zu viele, um sie alle zu testen.

Das deutsche Militär entwickelte daraus das sicherste Verschlüsselungssystem der Welt. Je mehr Geräte eingesetzt wurden, desto weniger Nachrichten konnten Briten, Franzosen und Amerikaner entziffern. Zudem ließ ihre Motivation nach. Deutschland war nach dem Ersten Weltkrieg scheinbar keine Bedrohung mehr. Das sahen allerdings die Polen ganz anders. Geografisch zwischen Deutschland und der Sowjetunion eingekeilt, fühlten sie sich weiterhin bedroht und richteten einen neuen Dechiffrierdienst ein.

Das Biuro Szyfrów

Der polnische Statistiker Marian Rejewski suchte dort nach der Schwachstelle der Enigma. Er bemerkte, dass die Deutschen vor jeder Botschaft einen Schlüsselcode sendeten und diesen zur Sicherheit einmal wiederholten. Zum Beispiel LCG LCG. In der chiffrierten Version (zum Beispiel EPF NAS) war die Wiederholung innerhalb der Buchstabenfolge nicht zu sehen. Aber Rejewski wusste, dass der erste und vierte, zweite und fünfte, dritte und sechste Buchstabe im Klartext identisch sein mussten. Hatte er genug Funksprüche gesammelt, konnte er sogenannte Beziehungsketten aufstellen: E und N standen in Verbindung, N und A, A und E. Eine Kette mit drei Verknüpfungen. Diese, so Rejewskis Vermutung, waren Ausdruck der Walzenstellung.

Seine Mitarbeiter probierten alle Walzenkonfigurationen aus und fassten die Verknüpfungen in einem Katalog zusammen. Es dauerte ein ganzes Jahr. Nun konnte Rejewski bei jedem abgefangenen Funkspruch die Zahl der Verknüpfungen herausfinden, mit dem Katalog vergleichen und die Walzenstellung ermitteln. Ein schöner Erfolg, aber da die Deutschen die Enigma immer weiter verfeinerten, bedurfte es ständiger weiterer Nachforschungen. Für die fehlte den Polen das Geld. Und so gaben sie ihre Erkenntnisse im Juli 1939 an die Briten und die Franzosen weiter.

Bletchley Park

Den Briten kam die Unterstützung gerade recht. Hatten sie doch bereits eine neue Zentrale für die Kryptoanalyse errichtet, den Bletchley Park, ein Gelände auf dem erst 200, später bis zu 7000 Menschen arbeiteten. Der bekannteste von ihnen war Alan Turing. Er analysierte alle deutschen Funksprüche und stellte fest, dass sie einer strengen Ordnung folgten. Jeden Morgen um sechs Uhr sendeten die Deutschen einen Wetterbericht, in dem immer das Wort Wetter vorkam. Turing konnte sogar ziemlich genau die Position des Begriffs vorhersagen. Er entwarf eine Apparatur mit drei hintereinandergeschalteten Enigma-Kopien und führte Tests durch. Die britische Armee erbeutete zudem einige Schlüsselbücher, die den Mitarbeitern in Bletchley Park bei der Aufklärung halfen. Aufbauend auf den Erkenntnissen der polnischen Kollegen, führten sie schließlich zum Erfolg. Enigma wurde entschlüsselt und der Krieg, so sehen es Historiker, maßgeblich verkürzt.

Das Ende des Kriegs bedeutete nicht das Ende für die Enigma. Die Briten erbeuteten viele Geräte, gaben sie an die Regierungen ihrer einstigen Kolonien weiter, die sie so belauschten.

RSA

Mit dem Ende des Zweiten Weltkriegs begann der Siegeszug des Computers. Nun wollten auch Unternehmen ihre Daten verschlüsseln. Dazu brauchte es einen Verschlüsselungsstandard.

Der erste hieß Lucifer, ein IBM-Produkt, entwickelt von dem emigrierten Deutschen Horst Feistel. Die Chiffrierung war so stark, dass der US-Nachrichtendienst NSA Feistel unter Druck setzte. Zweimal musste er seine Forschung unterbrechen, schließlich drängte die NSA ihn, die Zahl der Schlüssel zu begrenzen, sodass sie in der Lage war, mit ihren schnellen Computern in den Nachrichtenverkehr einzubrechen. 1976 wurde Lucifer unter dem Namen Data Encryption Standard (DES) als Verschlüsselungsstandard von den USA und später weltweit eingeführt.

Ein Problem blieb: die Schlüsselverteilung. Kuriere und Boten fuhren mit Aktenkoffern durch das Land. Ein unhaltbarer Zustand. Whitfield Diffie war Anfang der Siebzigerjahre einer der wenigen wirklich unabhängigen Sicherheitsexperten. Zusammen mit Martin Hellman, Professor in Stanford, untersuchte er das scheinbar unlösbare Problem: Wenn zwei Menschen sich ein Geheimnis, also eine verschlüsselte Botschaft, mitteilen wollten, mussten sie sich zuvor bereits ein Geheimnis, nämlich den Schlüssel, mitgeteilt haben. Oder doch nicht?

Ein Gedankenexperiment widersprach dem: Alice will Bob eine Nachricht schicken, legt sie in eine kleine Kiste und sichert sie mit einem Vorhängeschloss. Dann schickt sie die Kiste los. Bob kann die Kiste nicht öffnen. Er hängt seinerseits ein Vorhängeschloss an die Kiste und schickt sie zurück an Alice. Alice entfernt ihr Schloss und schickt die Kiste wieder zu Bob. Der entfernt sein eigenes Schloss und öffnet die Kiste. Diffie entwickelte daraus die Idee eines zweigeteilten Schlüssels. Ein Teil ist öffentlich und bekannt. Er dient der Verschlüsselung. Der zweite Teil ist privat und geheim und ermöglicht die Entschlüsselung. Diffie nannte dies einen asymmetrischen Schlüssel.

Ron Rivest, Adi Shamir und Leonard Adleman vom MIT-Labor für Computerwissenschaften lasen von der Idee und entwickelten daraus das nach ihren Nachnamen benannte RSA-Verfahren. Der US-Computerwissenschaftler Phil Zimmermann machte RSA schließlich einer breiten Öffentlichkeit zugänglich. Er entwarf ein Programm mit benutzerfreundlicher Oberfläche, das auch Laien bedienen konnten: PGP – Pretty Good Privacy.

1991 veröffentlichte Zimmermann das Programm im Internet, bekam Dankesschreiben von Menschen aus der ganzen Welt – und Besuch vom FBI. Der Vorwurf: Illegaler Waffenexport, denn Verschlüsselungs-Software gilt in den USA als Rüstungsgut. Der Friedensaktivist Zimmermann war plötzlich ein Waffenhändler. Nach drei Jahren wurden die Vorwürfe fallen gelassen. Das Exportverbot für starke Verschlüsselung besteht aber noch heute.

In Zukunft könnte ein Quantencomputer alle heutigen Verschlüsselungen hinfällig machen. Er kann theoretisch beliebig viele Rechnungen gleichzeitig vornehmen. Das erste Programm für einen Quantencomputer wurde 1994 in den AT&T Bell Laboratories entwickelt. Es konnte eine astronomisch hohe Zahl in ihre Faktoren zerlegen – genau das, was man braucht, um RSA-Verschlüsselungen zu knacken. ---
Vigenère-Verschlüsselung
Verschlüsselt, praktisch, gut: das Vigenère-Quadrat