Moderne Methoden der Ver-Ent-schlüsselung

Inhalt

1 Einführung: Evolution einer Unbekannten
1.1 Literaturbericht
1.2 Begriffsklärung

2 Zeitenwende: Monoalphabetische Chiffrierung versus Häufigkeitsanalyse
2.1 Monoalphabetische Verschlüsselungsmethoden
2.1.1 Cäsar-Verschiebung
2.1.2 Atbash-Chiffrierung
2.1.3 Allgemeine monoalphabetische Chiffrierung
2.2 Häufigkeitsanalyse
2.3 Homophone Verschlüsselung

3 Alphabet im Quadrat: Viginère versus Babbage, Kasiski und Friedman
3.1 Polyalphabetische Verschlüsselung: Das Viginère-Quadrat
3.2 Babbage und Kasiski
3.3 Friedman-Test

4 Kriegsgeflüster: Verschlüsselung zwischen 1918 und 1945
4.1 ADFGVX
4.2 Navajo
4.3 Exkurs: Enigma

5 Das Ende der Moderne: Wegwerfschlüssel und Public Key
5.1 One Time Pads
5.2 Asymmetrische Verschlüsselung

6 Ausblick

7 Bibliographie

8 Abbildungsverzeichnis

Anhang Buchstaben-Normalverteilung im Deutschen und Englischen

Vigenère-Quadrat

Navajo-Codes

1 Einführung

1.1 Entwicklung einer Unbekannten

„Seit es Menschen gibt, haben sie versucht, Worte und Taten zu verbergen“^[1] - der Wunsch, eine Nachricht vor ungewolltem Zugriff zu schützen, ist mitnichten ein exklusives Charakteristikum moderner Informationsgesellschaften. Zwar konnte die Kryptographie mit der weltweiten elektronischen Vernetzung ein nie gekanntes Interesse von Seiten einer breiten Öffentlichkeit an sich ziehen. Die Wissenschaft selbst aber existierte in ihren Grundsätzen bereits in frühen Hochkulturen wie Ägypten oder Indien^[2]. Ob ein vertraulicher Manöverplan oder eine verbotene Liebesbekundung – schon immer konkurrierten Geheimhaltungsbestrebungen mit Aufdeckungsinteressen, lieferten sich Kryptographie und Kryptoanalyse ein Rennen um die Informationshoheit. Dabei in ständiger Gefahr: Der Schlüssel zum Geheimtext. In ständigem Wechsel: die Oberhand über diesen Schlüssel. Und in ständiger Weiterentwicklung: Die Kryptographie. Schritt für Schritt wurde so aus einer dunklen Disziplin ein komplexer Fachbereich – und aus einer streng abgeschirmten, außerhalb von Hof und Militär oft unbekannten Geheimwaffe ein universitäres Seminarthema.

Die vorliegende Arbeit möchte zentrale Eckpunkte in der neueren und neuesten Entwicklung dieser Wissenschaft herausarbeiten und die jeweiligen „Etappensiege“ von Code-Ingenieuren und Codebrechern in ihrem einander antreibenden Wechselbezug verfolgen. Dabei wird ein zeitlicher Rahmen von etwa 1500 bis zum Ende des Zweiten Weltkriegs zugrunde gelegt, der aus zwei Gründen gerechtfertigt erscheint: Zum einen brachte der Beginn der Neuzeit in Europa einen plötzlichen Entwicklungsschub auch in der Verschlüsselungstechnik mit sich, nachdem noch bis in das späte Mittelalter hinein Verfahren dominierten, die bereits in der frühen Kaiserzeit entwickelt worden waren. Zum anderen schlug die Entwicklung des Computers nach dem Zweiten Weltkrieg ihrerseits ein völlig neues Kapitel auf: Mit seiner algorithmischen Überlegenheit und der Entwicklung der asymmetrischen Verschlüsselung stempelte der PC – fast – alle bekannten Verfahren hinfällig und läutete damit gewissermaßen die „Postmoderne“ der Chiffrierung ein.

1.1 Literaturbericht

Geradezu zwingend betreibt eine Arbeit, die zentrale Entwicklungspunkte der Kryptographie chronologisch nachzeichnen möchte, einen beständigen Schulterblick zu Simon Singhs Werk „Geheime Botschaften“ als einer Art „Nachfolgekompendium“ von David Kahns „The Codebreakers“. Gegenüber anderen Abhandlungen, wie etwa Friedrich L. Bauers „Entzifferte Geheimnisse“ oder Albrecht Beutelspachers „Kryptologie“, ihrerseits primär stellenweise empfehlenswert, vermag Singhs Buch, sich auch den mathematischen Ästen der Disziplin ausnahmslos allgemeinverständlich zu nähern. Zugleich konnte das Internet – entgegen bisheriger Recherche-Erfahrungen zu anderen Themen – als reiche Informationsquelle überzeugen. Sicherlich muss in diesem Zusammenhang eingestanden werden, dass die Verlässlichkeit einer Information im virtuellen Raum erst einmal nicht verifiziert werden kann; auch hinter offiziell anmutenden Angeboten mag sich beizeiten private Scharlatanerie verbergen. Soweit möglich, wurden daher stets mehrere Quellen für bestimmte Informationen herangezogen.

1.2 Begriffsklärung

Die Kryptographie unterscheidet grundsätzlich zwischen zwei Verschlüsselungsverfahren: Der Transposition und der Substitution von Schriftzeichen. Im ersten Fall bleiben die Klartextzeichen erhalten, verändern aber ihre Position im Text. Im zweiten Fall hingegen behalten Buchstaben oder Worte ihre Stellung bei, werden jedoch durch Geheimtextäquivalente ersetzt. Bei diesen Äquivalenten handelt es sich entweder um einzelne Zeichen, die für ganze Worte stehen (Codierung), oder um Symbole, die den Klartext schriftzeichenweise substituieren (Chiffrierung). Verfügt dabei jeder Buchstabe des Klartexts über eine konstante Entsprechung in einem Geheimtextalphabet, wird monoalphabetisch chiffriert. Stehen dem Klartext indes mehrere Geheimtextalphabete gegenüber, auf die abwechselnd zurückgegriffen wird, vollzieht sich die Verschlüsselung polyalphabetisch.

Eine Vermengung von Transposition und Substitution ist möglich, erhöht aber nicht zwingend die Verschlüsselungssicherheit. Ein eindrucksvolles Beispiel hierfür liefert die ADFGVX-Chiffrierung im Ersten Weltkrieg, die den Kryptoanalytikern kaum drei Monate lang standhalten konnte (vgl. Kap. 4.1).

Nachbardisziplin der Kryptographie ist die Steganographie, die hier nur erwähnt werden soll, nachdem sie nicht darauf abzielt, eine Nachricht zu verschlüsseln, sondern sie materiell zu verstecken. Zu den Methoden der Steganographie zählen etwa chemische Verfahren der Unsichtbarmachung („unsichtbare Tinte“), der Einsatz von Mikropunkten in Klartextbriefen oder auch die bitweise Manipulation digitaler Bilder.

2 Zeitenwende: Monoalphabetische Chiffrierung versus Häufigkeitsanalyse

Bis in das 15. Jahrhundert^[3] regierte bei den Kryptographen im europäischen Raum die monoalphabetische Verschlüsselung nach dem Vorbild der Cäsar-Verschiebung. Dabei handelt es sich um ein einfaches Substitutionsverfahren, das in seinen Grundsätzen bereits ab etwa 50 v.Chr.^[4] von Cäsar (100-44 v. Chr.) entwickelt und angewandt worden war. Seinen jahrhundertelangen Erfolg hatte das System zum einen sicherlich seinem simplen Algorithmus sowie seinem kurzen – und damit leicht übertragbaren – Schlüssel zu verdanken, zum anderen aber auch der späten Gewahrwerdung der westlichen Kryptographen eines im arabischen Kulturkreis des neunten Jahrhunderts wurzelnden (und den Kryptoanalytikern bereits früher vertrauten) Codebrechers: Der Häufigkeitsanalyse.

2.1 Monoalphabetische Verschlüsselungsmethoden

2.1.1 Cäsar-Verschiebung

Abbildung in dieser Leseprobe nicht enthalten

Bei der Cäsar-Verschiebung sind Klar- und Geheimtextalphabet um eine konstante Buchstabenzahl gegeneinander verschoben. Cäsar selbst etwa substituierte Klartext- durch Buchstaben, die im Alphabet jeweils drei Stellen weiter links lagen, wobei „A“, „B“ und „C“ durch die letzten drei Buchstaben des Alphabets ersetzt wurden. Augustus verschob das Alphabet gar nur um eine Stelle nach rechts^[5]. Der Schlüssel ist bei dieser Methode denkbar kurz: Er besteht aus der Angabe über die gewählte Anzahl der zwischen Klar- und Geheimtext liegenden Buchstaben sowie der Laufrichtung. Damit ergibt sich allerdings zugleich auch ein äußerst geringer Entschlüsselungsaufwand: Bei einem x Buchstaben umgreifenden Alphabet stehen nur x-1 Möglichkeiten der Verschiebung zur Verfügung^[6]. Ein Cäsar-Geheimtext muss also nur um einen, zwei usw. – höchstens x-1 – Buchstaben versetzt bis hin zu einem stimmigen Klartext „rückübersetzt“ werden. Zusätzlich beschleunigt wurde die Dechiffrierung durch eine im Jahr 1470 von Leon Battista Alberti (1404-1472) entwickelte Maschine^[7] aus zwei gegeneinander drehbaren Scheiben, auf denen jeweils das Alphabet abgedruckt ist. Über die Drehung einer der Scheiben lässt sich jedem Geheimtextalphabet schnell dessen Klartextentsprechung gegenüberstellen.

2.1.2 Atbash-Chiffrierung

Mit der Cäsar-Verschiebung verwandt ist die Atbash-Verschlüsselung: Bei diesem System jüdischen Ursprungs handelt es sich um eine starre monoalphabetische Chiffrierung, bei der der erste Buchstabe des Alphabets mit dem letzten Buchstaben verschlüsselt wird, der zweite mit dem vorletzten usw. Über diese konstante, d.h. nicht durch einen Schlüssel modifizierbare Zuordnung von Klar- und Geheimtextbuchstaben ist die Atbash-Verschlüsselung noch einfacher zu dechiffrieren als die Cäsar-Verschiebung. Der Häufigkeitsanalyse steht die Methode, mit der in der Bibel stellenweise etwa das Wort „Babylon“^[8] verschlüsselt wurde, freilich ebenso machtlos gegenüber.

2.1.3 Allgemeine monoalphabetische Chiffrierung

Ob ihrer Entschlüsselungsanfälligkeit setzte sich im ersten Jahrtausend^[9] eine verfeinerte Variante der Cäsar-Verschiebung durch, die allgemeine monoalphabetische Chiffrierung. Hier besteht der Schlüssel aus einem oder mehreren natürlichen Worten, mit deren Buchstaben das Geheimtextalphabet beginnt^[10]. Die sodann noch unbesetzt gebliebenen Gegenparts zum Klartextalphabet werden in alphabetischer Buchstabenreihenfolge, beginnend mit dem Buchstaben, der auf den „höchsten“ Buchstaben im Schlüsselwort folgt, „aufgefüllt“. Mit dieser Methode wird die Starre des Cäsar-Modells deutlich aufgebrochen: Ein „A“ wird nun nicht mehr zwingend etwa zum „B“, ein „B“ nicht mehr analog zum „C“ gewandelt – und die gebotene Dechiffrierungsleistung ist mit herkömmlichen Methoden entsprechend nicht mehr zu erbringen: Kann jeder Klartext- in einen beliebigen Geheimtextbuchstaben eines x-stelligen Alphabets umgewandelt worden sein^[11], so ergeben sich für den ersten Klartextbuchstaben x Möglichkeiten, im Geheimtext repräsentiert zu werden, für den zweiten x-1 Möglichkeiten etc., so dass etwa im Deutschen pro abgefangenem Text 26! potenzielle Geheimtextalphabete^[12] auf ihre Klartextplausibilität hin überprüft werden müssten – hätte nicht der arabische Gelehrte al-Kindi im neunten Jahrhundert^[13] die Häufigkeitsanalyse erdacht.

Eine über zwei Jahrhunderte lang trotz al-Kindis Erbe als nicht dechiffrierbar erachtete Variante der allgemeinen monoalphabetischen Verschlüsselung ist die „ Große Chiffre “, die im 17. Jahrhundert am Hof Ludwigs XIV von Antoine und Bonaventure Rossignol entwickelt wurde. Hier werden teils Silben, teils einzelne Buchstaben des Klartextes mit jeweils mehrstelligen Zahlen chiffriert. Erst im letzten Jahrzehnt des 19. Jahrhunderts gelang dem französischen Kryptoanalytiker Etienne Bazeries die Entschlüsselung.

2.2 Häufigkeitsanalyse

Die Häufigkeits-, statistische oder Frequenzanalyse fußt auf al-Kindis Beobachtung, dass in jeder Sprache einige Buchstaben häufiger auftreten als andere; so ist im Deutschen etwa gut jeder sechste Buchstabe ein „e“, wohingegen das „q“ nur 0,2 Prozent aller verwendeten Buchstaben ausmacht^[14]. In einem monoalphabetisch chiffrierten Text finden sich entsprechend einige Geheimtextzeichen öfter als andere. Gleiches gilt für Bi-^[15] und Trigramme^[16]. Bei der statistischen Analyse werden die Häufigkeiten, die diese Buchstaben, Bi- und Trigramme in einer Sprache durchschnittlich aufweisen, mit der Häufigkeit bestimmter Buchstaben, Bi- und Trigramme im Geheimtext verglichen. Zudem können Statistiken zu charakteristischen Häufigkeiten von Vokalabständen sowie zu typischen Häufigkeiten eines Buchstaben in Abhängigkeit von seiner Position in einem Wort herangezogen werden.

Noch vor dem Rückgriff auf die statistische Analyse muss der Kryptoanalytiker allerdings wissen, welche natürliche Sprache sich hinter dem Geheimtext verbirgt: Je nach Sprache nämlich differieren die Häufigkeiten, mit der bestimmte Buchstaben auftreten, zum Teil deutlich (vgl. Anhang 1 zu den Unterschieden bei der Normalverteilung im Deutschen und Englischen). Als besonders effektiv erweist sich die statistische Analyse im Allgemeinen bei langen Texten, da hier die Häufigkeitsverteilung der Buchstaben mit zunehmender Textlänge ihrer Normalverteilung entspricht. Weniger verlässlich präsentiert sich die Methode hingegen bei Texten, die über weniger als 100 Buchstaben verfügen^[17], sowie bei Texten, deren Buchstabenverteilung signifikant „untypisch“ für eine Sprache ist („In Ulm und um Ulm und um Ulm herum“).

[...]

^[1] Beutelspacher, Albrecht: Geheimsprachen: Geschichte und Techniken. München: Beck, 2000. S.14.

^[2] Vgl. www.siemens-akademie.de/0226.html. S.3.

^[3] Vgl. www.siemens-akademie.de/0226.html. S.4.

^[4] Ibid.

^[5] Allerdings ersetzte er „Z“ durch „AA“. Vgl. Attenberger, Birgit. Verschlüsselungen und Geheimschriften in der Antike. Universität Passau: Hauptseminar „Die geheime Nachricht“, 2001. (Thesenpapier)

^[6] Bei einer Verschiebung um x Stellen wären Klar- und Geheimtext wieder identisch.

^[7] Vgl. www.siemens-akademie.de/0226.html. S.5.

^[8] Vgl. http://philologos.org/bpr/files/Misc_Studies/ms046.htm

^[9] Vgl. Singh, Simon: Geheime Botschaften. München: Carl Hanser Verlag, 2000. 29.

^[10] Dabei werden Leerzeichen ignoriert und mehrmals auftretende Buchstaben nur bei ihrem ersten Vorkommen berücksichtigt. Vgl. Bsp. in Singh, S.29: Das Schlüsselwort JULIUS CAESAR wird zu JULISCAER verkürzt. Nächster Geheimtextbuchstabe ist dann das „T“, sodann „U“ usw.

^[11] Bei natürlichen Worten ist zwar nicht jede Buchstabenfolge zulässig, gleichwohl bleiben die zu überprüfenden möglichen Klartextalphabete bei einem herkömmlichen Dechiffrierungsversuch unrealistisch hoch.

^[12] Die Anzahl der Möglichkeiten beläuft sich auf 26*25*24*...*1= 26! = 403291461126605635584000000.

^[13] Vgl. Singh, S.33.

^[14] Vgl. Singh, S.36 und Beutelspacher, Albrecht: Kryptologie. Braunschweig: Vieweg, 1997. 18.

^[15] Die häufigsten Bigramme im Deutschen sind „en“, „er“ und „ch“ (Vgl. Beutelspacher, S.27, und http://www.gasperonline.de/krypto/geheim/haeufig.html)

^[16] Häufigstes Trigramm im Deutschen ist „ein“.

^[17] Vgl. Singh, S.37.