Von Hieroglyphen und Quantencomputern
Der Wettlauf zwischen Kryptographie und Kryptanalyse
Simon Singh, Autor eines überaus erfolgreichen allgemeinverständlichen Buches über das letzte Problem von Fermat, hat seinem internationalen Bestseller nun das «Code Book» folgen lassen. Es beschreibt auf spannende Weise den evolutionären Wettlauf zwischen Kryptographie und Kryptanalyse von den frühesten Methoden bis zu den modernsten Verschlüsselungsverfahren.
MM5P7)-8F-,HÄJOF1C//L . . .: Diese anscheinend sinnlose Abfolge von Buchstaben ist Teil einer längeren sinnlosen Abfolge von Buchstaben, hinter der sich ein Codewort verbirgt. Schon seit alten Zeiten gibt es das Bedürfnis, Nachrichten zu senden, deren Inhalt unbefugten Augen vorenthalten werden sollte. Dem General im Feld musste mitgeteilt werden, wo und wann der Angriff stattfinden soll oder dass Nachschub auf dem Weg sei; der Diplomat musste Abmachungen nach Hause melden; der Liebhaber musste seine Angebetete verständigen, wo er sie zu einem Schäferstündchen treffen wolle.
Die «Caesar-Verschiebung»
Die früheste Methode, Nachrichten zu verschlüsseln, bestand darin, jeden Buchstaben durch einen im Alphabet weiter unten stehenden zu ersetzen. Zu Ehren von Julius Caesar, der dieses Verfahren benutzte, wird es «Caesar-Verschiebung» genannt. Allerdings ist es ein leichtes, solcherart verschlüsselte Nachrichten zu dechiffrieren. Da die Frequenz der Buchstaben in einer Sprache bekannt ist, kann der Schlüssel durch einen einfachen Vergleich der Buchstabenhäufigkeit gefunden werden. Zum Beispiel tritt der Buchstabe «e» im Deutschen mit einer Häufigkeit von etwa 17,5 Prozent auf. Wenn also im verschlüsselten Text der Buchstabe «m» ähnlich häufig vorkommt, darf angenommen werden, dass «m» das ursprüngliche «e» darstellt. Die einzige Voraussetzung zur Dechiffrierung ist das Vorliegen eines genügend langen Textes.
Die «Caesar-Verschiebung» ist eine sogenannte monoalphabetische Substitution. Die Verschlüsselung kann komplexer gemacht werden, indem zur Chiffrierung mehrere Schlüssel gleichzeitig benützt werden. Bei solchen polyalphabetischen Substitutionen wird der erste Buchstabe einer Nachricht mit dem ersten Schlüssel chiffriert, der zweite mit einem anderen und so weiter. Da ein «e» nun durch verschiedene Buchstaben ersetzt wird, hilft die simple Frequenzanalyse nicht sofort weiter. Aber auch die polyalphabetische Methode, von der lange angenommen wurde, dass sie nicht zu enträtseln sei, konnte den Angriffen von Kryptanalysten nicht standhalten.
Enigma an allen Fronten
Nach dem Ersten Weltkrieg konstruierte der deutsche Ingenieur Arthur Scherbius eine simple Chiffriermaschine, die eine Decodierung fast unmöglich machte und überdies Bleistift und Papier überflüssig werden liess. Die Betonung liegt auf «fast», denn brillanten polnischen und britischen Mathematikern gelang es schliesslich doch, den Code zu brechen. Die unter dem Namen Enigma bekannt gewordene Chiffriermaschine besass drei Walzen und eine Steckerplatte, die zwölf Buchstaben vertauschte. Die Verschlüsselung durch die Steckerplatte allein wäre eine triviale monoaphabetische Substitution gewesen. Doch die drei Walzen verunmöglichten eine Frequenzanalyse, da sie andauernd ihre Stellungen veränderten. Somit wurde der gleiche Buchstabe jedesmal anders chiffriert. Die Anfangspositionen der Walzen sowie die Steckerplätze wurden laut einem Codebuch jeden Tag geändert. Den neuartigen Chiffriermaschinen wurde zuerst kein kommerzieller Erfolg zuteil, doch im Zweiten Weltkrieg kamen bei den deutschen Truppen an allen Fronten, zu Wasser und zu Lande, schätzungsweise 30 000 Enigma-Geräte zum Einsatz.
Da die Enigma-Verschlüsselung als absolut robust galt, sandten die sich in Sicherheit wiegenden Deutschen Unmengen von codierten Nachrichten über den Äther. Doch auf die Dauer konnte auch Enigma den Anstrengungen der Kryptanalysten nicht standhalten. Der erste Durchbruch gelang dem polnischen Mathematiker Marian Rejewski. Damit nicht zu viele Meldungen mit der gleichen Encodierung gesendet würden, benützten die Deutschen nicht durchgehend den für diesen Tag geltenden «Tagesschlüssel», sondern für jede Nachricht einen separaten Code. Dieser nachrichtenspezifische Code, der die Stellungen der drei Rotoren zur Entschlüsselung dieser Meldung festsetzte (zum Beispiel OLM) wurde mit dem «Tageschlüssel» chiffriert und am Anfang der Sendung durchgegeben. Der Rest der Sendung wurde dann mit dem nachrichtenspezifischen Code chiffriert.
Gefährliche Höflichkeitsfloskeln
Dabei begingen die Deutschen einen fatalen Fehler: der nachrichtenspezifische Code wurde, um Irrtümer wegen Übertragungsstörungen zu vermeiden, doppelt durchgegeben: OLMOLM. Obwohl zwar jeder der sechs Buchstaben auf verschiedene Weise chiffriert wurde, was zum Beispiel WCTJOD ergab, wusste der polnische Kryptanalyst, dass das «W» und das «J» den gleichen Buchstaben darstellten, wie auch «C» und «O» und «T» und «D». Dass die Deutschen – Ordnung muss sein – ihre Nachrichten meist mit Standardformulierungen begannen und beendeten und jeden Tag genau um sechs Uhr früh den Wetterbericht durchgaben, half den Entschlüsselungsexperten ebenfalls weiter, wie auch die Nachlässigkeit der Operateure, die Nachrichtenschlüssel oft aus Faulheit mit simplen Kombinationen wie GGG, HHH oder ABC versahen. Nachdem das polnische «Biuro Szyfrow» die alliierten Kollegen über die Entdeckungen informiert hatte, wurde die Arbeit im legendären Bletchley Park von englischen Kryptanalysten – unter ihnen der geniale Mathematiker und Computerpionier Alan Turing – weitergeführt. Churchill wusste die Arbeit der Leute in Bletchley Park sehr zu schätzen, und Historiker sind heute der Meinung, dass die Entschlüsselung der Enigma-Meldungen viel zur Niederlage Hitlers beigetragen habe.
Aber nicht nur brillante Mathematiker, Schachspieler, Philologen und Kreuzworträtselspezialisten hatten Anteil an den Entschlüsselungserfolgen. Bei der Versenkung von Kriegsschiffen fiel so manches Codebuch in die Hände des Feindes, und bisweilen wurden zum Ergattern von Chiffrierschlüsseln Kollaborateure angeworben. Dies verweist auf eine offenbar unvermeidliche Schwierigkeit aller bis dahin verwendeten Chiffriermethoden: Die Schlüssel zur Decodierung, das heisst die Codebücher, mussten allen Operateuren in irgend einer Form physisch übergeben oder elektronisch übersandt werden.
Schlüsseltransaktion als Schwachstelle
Diese Schwachstelle wurde Mitte der siebziger Jahre durch die DES (Data Encryption Standard) genannte Methode ausgemerzt (vgl. Artikel auf der folgenden Seite). Die von Whitfield Diffie, Martin Hellman und Ralph Merkle konzipierte Technik machte die physische Übergabe eines Schlüssels unnötig. Simon Singh 1 vergleicht DES mit dem folgenden Szenario: Nehmen wir an, die beiden Liebhaber Alice und Bob wollen sich chiffrierte Nachrichten zukommen lassen, befürchten aber, dass der Schlüssel in die falschen Hände fallen könnte. Wenn die Zeit nicht eilt, können sie die Gefahr folgendermassen umgehen: Alice steckt ihre Nachricht in eine mit einem Vorhängeschloss versehene Schachtel und sendet sie an Bob. Nach Erhalt der Schachtel versieht Bob die Schachtel zusätzlich mit einem eigenen Vorhängeschloss und sendet das ganze an Alice zurück. Diese entfernt ihr Schloss und retourniert die einfach verschlossene Schachtel an Bob, der nun nur sein eigenes Schloss öffnen muss, um die Schachtel zu öffnen. Während der Transaktionen musste kein Schlüssel transferiert werden, es bestand so nie eine Gefahr, dass er in falsche Hände geraten würde.
DES kann mit simplen arithmetischen Operationen veranschaulicht werden. Sagen wir, dass Alice die aus der Zahl «6» bestehende Nachricht an Bob senden wolle. Alice verschlüsselt die Nachricht, indem sie die Zahl mit 12 multipliziert, und sendet das Resultat, «72», an Bob. Bob, der keine Ahnung hat, was «72» bedeutet, verschlüsselt die erhaltene Meldung seinerseits, indem er sie durch 18 dividiert. Das Resultat, «4», retourniert er an Alice. Sie entfernt ihren Schlüssel, indem sie die Nachricht nun durch 12 dividiert. Das Resultat, « 1/3», sendet sie wieder an Bob. Bob entschlüsselt die Meldung, indem er die Zahl mit 18 multipliziert, und hält die ursprüngliche Nachricht, «6», in Händen. Aussenstehende können aus eventuell abgefangenen Meldungen – 72, 4, 1/3 – nichts herauslesen, aber weder Alice noch Bob brauchten den Schlüssel ihrer Partner zu kennen. In Wirklichkeit ist die DES-Verschlüsselung viel komplizierter und benutzt nicht Multiplikation und Division sondern die Potenzierung in der sogenannte Modulo-Arithmetik.
Das DES-System löst das Problem mit der physischen Übergabe des Schlüssels, hat aber immer noch einen Nachteil: wegen des Hin und Hers der Nachrichten müssen die Korrespondenten jeweils warten, bis die chiffrierte Meldung eingetroffen ist, bevor sie ihre eigene Ver- und Entschlüsselungen vornehmen können. Um auch diese Hürde aus dem Weg zu räumen, begann die Suche nach einem sogenannten asymmetrischen System, das die zeitgleiche Präsenz der Korrespondenten nicht voraussetzte.
Die Suche fand 1977 ein Ende, als Ronald Rivest, Adi Shamir und Leonard Adleman die «Public Key Cryptography» vorstellten. Die nach den Anfangsbuchstaben ihrer Namen benannte RSA-Methode erlaubt auch dann den Versand codierter Nachrichten ohne Schlüsseltransaktion, wenn der Adressat zur Zeit der Sendung nicht präsent ist. Der Empfänger kann die Nachricht dann zu einem beliebigen späteren Zeitpunkt mit seinem privaten Schlüssel entziffern. Zur Ver- und Entschlüsselung werden zwei sehr grosse Primzahlen und ihr Produkt verwendet. Das Geheimnis besteht darin, dass die Faktorierung einer solchen Zahl eindeutig, aber überaus zeitaufwendig ist. Das Produkt zweier Primzahlen kann nämlich durch keine andern Zahlen als durch die beiden Primfaktoren selber geteilt werden. Zum Beispiel kann 175 828 273 nur durch die beiden Primzahlen 17 159 und 10 247 geteilt werden. Wenn aber nur das Produkt bekannt ist, müssen Unmengen von Zahlen ausprobiert werden, um die beiden Faktoren zu finden.
Das Produkt der beiden Primzahlen, der sogenannte öffentliche Schlüssel, wird bekanntgegeben und dient zur Chiffrierung. Aber nur der legitime Empfänger, der die beiden Primfaktoren kennt – den sogenannten privaten Schlüssel –, kann die Meldung auch dechiffrieren. Ohne dass der private Schlüssel dem Empfänger physisch oder elektronisch übergeben werden muss, kann die Nachricht somit von jedermann verschlüsselt, aber von keinem unbefugten Lauscher gelesen werden. Elektronische Geldtransaktionen werden heute von Banken routinemässig mit je über 150 Ziffern langen Primzahlen verschlüsselt. Auch die stärksten Computer brauchten Jahrhunderte, um die Primfaktoren einer solch immensen Zahl zu finden. Übrigens stellte sich erst vor kurzem heraus, dass dieselbe Methode schon mindestens fünf Jahre vor RSA von dem Engländer James Ellis entwickelt worden war, der aber als Geheimdienstmann der Schweigepflicht unterlag.
Vom Nachteil des «u» nach dem «q»
Simon Singhs «Code Book» liest sich trotz dem technischen Thema wie ein Kriminalroman. Die Schilderungen reichen von Geheimmeldungen Mary Stuarts, der tragischen Königin von Schottland, über Navajo-Indianer, die im Zweiten Weltkrieg amerikanischen Truppen im Feld zugeteilt wurden und in ihrer völlig unerforschten Sprache kommunizierten, bis zu der noch sehr spekulativen Diskussion über die zukünftige Rolle von Quantencomputern bei der Chiffrierung. Dabei macht Singh faszinierende Abstecher zu der Entzifferung vergessener Sprachen und Schriften, wie zum Beispiel zu Champollions Enträtselung der Hieroglyphen – allerdings sind die sogenannten Cartouches mit den Namen ägyptischer Pharaonen zumindest im englischen Text seitenverkehrt wiedergegeben – oder zum Expertenstreit über die bei Ausgrabungen in Kreta gefundene Schrift «Linear B» aus dem zweiten vorchristlichen Jahrtausend.
Der Leser erfährt bei Singh Tips, die Generationen von unberechtigten Lauschern das Leben schwermachten, wie die, dass das «u» nach dem «q» unbedingt ausgelassen werden muss, oder dass eine schlecht empfangene Nachricht nie ein zweites Mal verschlüsselt und gesendet werden darf. Anhand von einfachen Beispielen wird der Leser sozusagen an der Hand genommen und Schritt für Schritt durch die Analyse chiffrierter Nachrichten geführt. Nebenbei erfährt man, wie Altertumsforscher aus den dünnsten Anhaltspunkten ganze Theoriengebäude erstellen. Technische Erklärungen sind in die Anhänge verwiesen, und nach der Lektüre des Buches kann sich der Leser gleich als Kryptanalyst versuchen. Singh schrieb nämlich einen Dechiffrier-Wettbewerb aus, auf dessen Lösung eine Preissumme von 10 000 Pfund steht. Die Rangliste führt zurzeit ein Mathematiker aus Cambridge an, der Mitte Januar den achten von zehn Texten entschlüsseln konnte. Die anscheinend sinnlose Abfolge von Buchstaben zu Beginn dieser Rezension sind Teil der letzten noch ungelösten Aufgabe des Preisausschreibens. (Der Wettbewerb kann im Internet 2 mitverfolgt werden.)
Allerdings beschränkt sich Singhs Buch auf das Allgemeinverständliche. Wer sich weitergehend über Kryptographie und Kryptanalyse informieren möchte und eine mathematische Schreibweise nicht scheut, nimmt mit Vorteil das soeben in zweiter Auflage neu herausgegebene Buch von Friedrich L. Bauer «Decrypted Secrets» 3 zur Hand. Die Lektüre setzt bloss elementare Mathematik voraus, diese aber in hohen Dosen. Doch der Text behandelt keineswegs nur trockene Theorie, er ist durchsetzt von Anekdoten, die Singhs Chronik vervollständigen. Bauers Buch ist sowohl für Spezialisten als auch für interessierte Laien gedacht, und angehende Kryptographen, Mathematik- und Informatikstudenten können es als Einführung in ein neues Gebiet benützen. Allerdings ist die Lektüre manchmal etwas mühsam, vor allem wegen einer etwas schwerfälligen Sprache und der für den Spezialisten gedachten Querverweise.
Georg Szpiro
1 Simon Singh: The Code Book. The science of secrecy from ancient Egypt to quantum cryptography. Fourth Estate Ltd., London 1999. 402 S.
2 www.4thestate.co.uk/cipherchallenge
3 Friedrich L. Bauer: Decrypted Secrets. Methods and maxims of cryptology. Second edition. Springer-Verlag, Heidelberg 2000. 448 S.
