Kryptoanalyse mit dem Geocacher-Team haensel+gretel - Teil I - von CÄSAR bis Playfair - einfache Verfahren

Letztmalig dran rumgefummelt: 19.12.16 07:52:20

	Kurz paar Worte vorweg zu unserem kleinen Seminar. So was hab ich letztes Jahr schon mal mit paar Cacherkollegen gemacht und das hat ganz gut funktioniert. Allerdings waren das nur vier Leute, die natürlich etwas einfacher unter einen Hut zu bekommen sind als unsere jetzige Truppe mit elf Leuten. Aber wir werden das schon hinbekommen. Da ich keine Ahnung habe, auf welchem Kenntnisstand ihr seid und wie viel Zeit ihr für diese Aktion erübrigen könnt, schlage ich vor, dass ich einfach mal bei Adam und Eva, also ganz am Anfang mit den Basics beginne - auch auf die Gefahr hin, dass sich manche vielleicht langweilen werden. Ich teile den Stoff in einzelne Mails auf und schicke jeweils ein Häppchen ungefähr einmal pro Woche rum. Falls jemand nicht genügend Zeit dafür hat, einfach die Bremse rein hauen, dann machen wir etwas langsamer. Kann auch sein, dass es bei mir mal zeitlich hakt, weil ich beruflich doch ziemlich eingespannt bin. Wir können auch mal eine Weile aussetzen. Wenn irgendwas unklar ist, einfach fragen. Und wenn euch die Lust verlässt oder das Ganze eure Erwartungen nicht erfüllt, dann können wir es auch ad acta legen. Ich werde es keinem verdenken, wenn ihm das zu trocken oder zu öde wird. Denn seid gewarnt: Es wird gerade am Anfang trocken und theoretisch werden. Ich werd mich zwar bemühen, mich auf das zu beschränken, was für den Cacher nützlich ist und mich nicht zu sehr in die Theorie und die Feinheiten versteigen. Dennoch kommen wir natürlich um die Grundlagen nicht herum. Ihr kennt das ja. Ist bei jedem Thema das Gleiche, da kann man nichts machen. Ich versuche, das Ganze möglichst praktisch zu gestalten und mit Beispielen zu illustrieren. Außerdem schick ich zur praktischen Anwendung immer mal wieder ein kleines Tool mit. Ich bastle diese Tools in einer älteren Excel-Version (XP), die auf älteren und neueren Win- und Mac-Systemen problemlos laufen sollte. Für Linux hab ich leider noch nichts. Die Mails verfasse ich als reinen ASCII-Text ohne HTML oder anderen Schnickschnack, dann ist das auf jeden Fall mit allem kompatibel. Da gelegentlich Listen und Tabellen erforderlich werden, deren Darstellung in ASCII aber nur recht eingeschränkt möglich ist, wäre es sinnvoll, wenn ihr zur Anzeige eine nichtproportionale Schrift verwenden würdet, also eine, bei der jedes Zeichen die gleiche Breite einnimmt, z.B. Courier. Darauf stimme ich die Texte ab. Sonst verrutscht der ganze Kram mitunter bis zur Unkenntlichkeit. Beispiel: Bei der folgenden Liste sollten die Buchstaben der beiden Zeilen genau untereinander stehen.  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Z Y X W V U T S R Q P O N M L K J I H G F E D C B A  Noch gschwind zum geplanten Inhalt. Wir werden mit wenigen Ausnahmen nur die klassischen Verfahren besprechen. Dabei wird es nur um die gängigsten Varianten gehen, Spezialfälle und exotischere Verfahren können wir später besprechen, falls Interesse daran besteht. Neuere und insbesondere asymmetrische Verfahren werden keine Rolle spielen (die sind beim Cachen normal auch unwichtig). Zunächst wird es um die Substitutionsverfahren gehen - zunächst die monoalphabetische Substitution. Vermutlich kennen das die meisten bereits (z.B. ROT13, Caesar), aber für alle Fälle gehen wir das trotzdem kurz durch. Dann folgt die polyalphabetische Substitution (z.B. von Vigenère haben die meisten wahrscheinlich zumindest schon mal was gehört). Anschließend kommt dann die Transposition dran (z.B. Spaltentransposition, Palisade, Sägezahn). Schließlich streifen wir kurz die beim Cachen wichtigsten Codes (z.B. ASCII, CCITT2, Kenny-Code). Wenn es euch dann immer noch nicht zu viel geworden ist, können wir uns speziellen Systemen wie den bipartiten Substitutionsverfahren (z.B. Polybios oder Playfair), den kombinierten Verfahren (z.B. ADFGVX oder Sorge-Chiffre), den Spezialfällen wie Rastersystemen (z.B. Fleißner) oder auch der Steganographie zuwenden. Gelegentlich, wenn auch selten, begegnet man diesen Dingen beim Cachen. Werden wir ja sehen. Hört sich jetzt wahrscheinlich auch erst mal wilder an, als es eigentlich ist. Wenn das so weit ok für euch ist, dann werd ich irgendwann die nächsten Tage loslegen und die erste Mail rumschicken. Falls ihr Einwände, Anregungen oder Fragen habt, lasst es mich wissen. Und noch was Formales: "Kryptographie" schreibe ich hier mit "ph", auch wenn man nach neuer deutscher Rechtschreibung "f" verwenden müsste. Beginnender Altersstarrsinn vielleicht oder ein altphilologisches Kindheitstrauma, keine Ahnung.
	1. Basic BASICS 2. Monoalphabetische Substitution 3. CRYPTOOL 4. Systematik bei der Kryptoanalyse einer monoalphabetischen Substitution 5.Systematik bei der Kryptoanalyse einer polyalphabetischen Substitution 6. Dechiffrierprojekt Vigenère-Code Informatik-Kurs 2006/07 7. Web-Links zum Thema Vigenère und Polyalphabetischer Chiffre 8. Aufgaben zum Thema Kasiski-Test 9. Verwandte Themen
	Kryptoanalyse Logo des Geocacher-Teams haensel+gretel angemeldet bei GEOCACHING zu erreichen unter: http://www.geocaching.com/profile/?guid=abaf5959-6316-4277-aad9-d4cbe3a1b10e&wid=28326ff8-97af-4eb8-838c-fae643736efb&ds=2 begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: KRYPTOLOGIE - eine Einführung in die Wissenschaft vom verschlüsseln, Verbergen und Verheimlichen Seite 34 Die Welt der geheimen Zeichen -  die faszinierende Geschichte der Verschlüsselung Seite 216 ff.
	universeller Codewandler von 2016 direkt ausführbar universeller Codewandler von 2016 - hier komplett komfortabler kleiner Codewandler komfortabler kleiner Codewandler

1. Basic BASICS - also die Grundlagen der Grundlagen

Also jetzt aber los. Die Kryptologie gliedert sich in die Kryptographie (also das Verschlüsseln) und die Kryptoanalyse (also das Brechen von Krypttexten, was nichts anderes bedeutet als ein Entziffern, ohne dass man zunächst den Schlüssel hat). Uns interessiert hier natürlich vornehmlich die Kryptoanalyse.

Das Brechen eines Krypttextes besteht immer aus vier Schritten: 1. verwendete Sprache identifizieren 2. verwendetes Verfahren identifizieren 3. Schlüssel ermitteln 4. Krypttext entziffern Dabei kann man die Schritte nicht immer streng nacheinander abarbeiten. Häufig muss man hin- und zurückspringen, vor allem am Schluss zwischen Schritt 3 und 4. Die ersten beiden Schritte aber müssen immer am Anfang stehen. Ohne das Verfahren zumindest grob zu kennen (Schritt 2), bleibt die Sache ein reines Glücksspiel. Den ersten Punkt können wir in der Regel überspringen und einfach von deutschen Texten ausgehen. Beim Identifizieren des verwendeten Verfahrens wird es schon wesentlich schwieriger - das ist meist der Hauptknackpunkt. Darauf werden wir später noch ausführlicher zu sprechen kommen müssen. Es gibt eine unübersehbare Vielfalt von Verschlüsselungsverfahren. Ganz grob unterscheidet man die klassischen Verfahren von den modernen. Die klassischen kann man im Prinzip mit Papier und Bleistift durchführen, die modernen basieren auf der digitalen Datenverarbeitung und erfordern Computerunterstützung. Dennoch ist der Computer natürlich auch bei den klassischen Verfahren eine große Hilfe und erspart einem viel mühevolle Handarbeit. Wir werden uns hier nahezu ausschließlich mit den klassischen Verfahren beschäftigen. Ganz grundsätzlich kann man bei diesen Verfahren neben diversen Sonderformen zwei Grundtypen unterscheiden: Substitution Transposition An dieser Stelle nur eine ganz kurze Erklärung, später mehr dazu: Bei der Substitution werden die Klarzeichen durch Kryptzeichen ersetzt. Die Zeichen behalten also ihren Platz in der Zeichenkette, werden aber zu anderen Zeichen. Bei der Transposition verändert man die Position der Zeichen in der Zeichenkette, die Zeichen an sich bleiben aber unverändert erhalten. Sie sind eben nur anders angeordnet. Beispiel: Wenn man beim Wort "HAUS" jedes Zeichen um eine Stelle im Alphabet nach hinten verschiebt, also jedes Zeichen durch seinen nachfolgenden Nachbarn ersetzt, erhält man "IBVT". Das ist eine Substitution. Jeder Buchstabe wurde durch einen anderen ersetzt, behält aber seine Position in der Zeichenkette. Tauscht man dagegen die Plätze der Buchstaben, indem man das Wort z. B. einfach von hinten nach vorne aufschreibt, erhält man "SUAH". Das ist eine Transposition. Jeder Buchstabe bleibt unverändert erhalten, verändert aber seine Position in der Zeichenkette.

2. Monoalphabetische Substitution

	Zunächst beschäftigen wir uns mit der Substitution. Bei der Substitution ersetzt man wie gesehen die Klarzeichen durch andere Zeichen. Ich sage hier bewusst "Zeichen" und nicht "Buchstaben", weil man prinzipiell natürlich jedes nur erdenkliche Zeichen verwenden kann (z.B. Freimaurer-Code, Morsezeichen, Blindenschrift, beliebige Symbole) - am üblichsten sind aber freilich Buchstaben. Nehmen wir uns zunächst die monoalphabetische Substitution vor. Was das genau bedeutet, besprechen wir später.
	Klassischer CAESAR Der Klassiker der Substitution und gleichzeitig das einfachste aller Substitutionsverfahren ist der Caesar-Code. Das ist die wohl jedem Cacher wohlbekannte ROT-Geschichte. Das antike Caesar-Verfahren im engeren Sinne ist ROT3 (Verschiebung um drei Zeichen, aus "A" wird also "D" etc.). Für die Hints beim Cachen ist dagegen wie bekannt ROT13 üblich (Verschiebung um 13 Zeichen, aus "A" wird also "N" etc.). Beim Caesar-Verfahren wird jedes Klarzeichen also durch ein ganz bestimmtes Kryptzeichen ersetzt, und zwar durch eines, das sich um eine bestimmte Anzahl an Stellen weiter hinten im Alphabet befindet. Beträgt die Verschiebung z. B. vier Stellen, wird "A" auf "E" abgebildet, rutscht also im Alphabet einfach vier Stellen weiter nach hinten. "A" wird zu "E", "B" zu "F", "C" zu "G" etc. Zum Decodieren rutschen wir die Kryptzeichen wieder vier Stellen im Alphabet nach links und schon haben wir den Klartext. Mathematisch also (p=Klartext [plain], c=Krypt [cipher], k=Schlüssel [key]): Verschlüsselung: c = p + k Entschlüsselung: p = c - k Alles ganz einfach. Wobei die Mathematik hierbei für unsere Zwecke nicht ganz so wichtig ist. Wer damit also auf Kriegsfuß steht, überliest es einfach. Eine kleine Sache fehlt aber noch: Wenn man bei der Rechnung das Alphabet verlässt, steigt man vorne (bzw. hinten) wieder ein. Soll "Y" beim Verschlüsseln um vier Stellen nach rechts verschoben werden, landet man natürlich hinter dem "Z". Man springt nach dem "Z" einfach wieder zum "A". Bei einer Verschiebung um vier Stellen wird aus "Y" also "C". Man denkt sich das Alphabet praktisch als ringförmige, endlose Zeichenkette. Mathematisch gesprochen führt man eine Modulo-Rechnung durch. Wenn man wie früher mit Papier und Bleistift arbeitet, ist es nicht besonders praktisch, ständig rechnen zu müssen. Daher bastelt man sich eine kleine Tabelle, die die Zuordnung von Klarzeichen und Kryptzeichen deutlich macht. Für den echten Caesar, also ROT 3, sieht das dann so aus: p A B C D E F G H I J K L M N O P Q R S T U V W X Y Z c D E F G H I J K L M N O P Q R S T U V W X Y Z A B C p ist hier also das Klartextalphabet, c nennt man das Tauschalphabet. Aus "A" wird beim Verschlüsseln "D", aus "B" wird "E" etc. Die beiden Alphabete sind beim Caesar einfach gegeneinander verschoben. Für das bekannte ROT13 sieht die Sache so aus: p A B C D E F G H I J K L M N O P Q R S T U V W X Y Z c N O P Q R S T U V W X Y Z A B C D E F G H I J K L M In diesem Fall beginnt das Tauschalphabet mit "N". Aus "A" wird also "N", aus "B" wird "O" etc. An dieser Stelle eine kurze Randbemerkung: ROT 13 weist eine Besonderheit auf, aufgrund derer es auch so populär ist. Es ist involutorisch. Das bedeutet, dass jede Ersetzung in beide Richtungen funktioniert oder anders ausgedrückt: Führt man eine Ersetzung doppelt aus, landet man wieder beim Ausgangszustand. Beispiel: Bei ROT3 wird aus "A" ein "D", aus "D" wird ein "G". Bei ROT13 dagegen wird "A" ein "N" und aus "N" wird wieder ein "A". Bei Rot13 ist es also egal, ob man von oben nach unten oder von unten nach oben geht - es kommt immer dasselbe dabei heraus. Daher genügt es auch, wie in den GC-Listings üblich, nur die halbe Tabelle aufzuschreiben: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Beim Caesar-Verfahren ergeben sich aufgrund seines sehr einfachen Aufbaus ein paar Besonderheiten, die für uns sehr interessant sind: der Abstand zwischen Klarzeichen und Kryptzeichen im Alphabet ist immer gleich (klar, es wird stur immer der Faktor k addiert, also jedes Zeichen um den gleichen Betrag verschoben. das bedeutet aber gleichzeitig, dass jedes Klarzeichen immer durch das gleiche Kryptzeichen ersetzt wird, also jedes "A" wird z.B. zu "E" und nichts anderem. aus Letzterem ergibt sich wiederum, dass der Zeichenvorrat des Klartextes exakt gleich groß ist wie derjenige des Krypttextes. Wenn also im Klartext zwölf verschiedene Zeichen vorkamen, besteht auch der Krypttext aus genau zwölf verschiedenen Zeichen. Hieraus ergeben sich nun diverse Schlussfolgerungen: Aus dem ersten Umstand ergibt sich, dass bei nur einer einzigen bekannten Zuordnung von Klarzeichen zu Kryptzeichen alles klar ist. Logisch, wurde das eine Zeichen um k Stellen verschoben, gilt das für alle anderen Zeichen gleichermaßen. Zum Entschlüsseln muss man also alle Zeichen im Krypttext um den gleichen Betrag im Alphabet zurückschieben, also k subtrahieren. Bingo. Wissen wir also, dass im Krypttext "G" für "E" steht, können wir den gesamten Krypttext entziffern, indem wir einfach jedes Zeichen um zwei Stellen im Alphabet zurückrücken. Wenn "G" für "E" steht, dass muss "F" für "D" stehen, "E" für "C" etc. Aber wie bekommen wir im Einzelfall raus, um wie viele Stellen wir die Zeichen verschieben müssen? Nun, dabei hilft uns die Tatsache, dass jedes Klarzeichen immer durch das gleiche Kryptzeichen ersetzt wird. Da ein bestimmtes Klarzeichen immer auf das gleiche Kryptzeichen abgebildet wird, entspricht die Häufigkeit der einzelnen Kryptzeichen natürlich immer noch derjenigen der Klarzeichen. War im Klartext z.B. "E" am häufigsten, dann wird im Krypttext das Kryptzeichen von "E" am häufigsten sein. Wurde das "E" des Klartexts also z.B. immer durch "G" ersetzt, dann ist im Krypttext natürlich "G" am häufigsten. Das ist schön für uns, denn wenn wir die Normalverteilung der Buchstabenhäufigkeiten der zugrundeliegenden Sprache kennen, können wir die Klarzeichen meist recht problemlos identifizieren. Im Deutschen ist das mit Abstand häufigste Zeichen das "E". Daher geht man bei einem Caesar-Code einfach her und zählt die Anzahl aller im Krypttext vorkommenden Zeichen. Man hat bei einem halbwegs normalen Text gute Chancen, dass das häufigste Kryptzeichen dann dem Klarzeichen "E" entspricht. Damit ist aber auch die Verschiebung bekannt und der Krypttext so gut wie geknackt. Beispiel: Nehmen wir an, unser Krypttext lautet "MJZYJNXYJNSXHMTJSJWYFL" und wir haben Grund zu der Annahme, dass es sich um einen Caesar handelt. Wir zählen zunächst die Zeichen aus: F 1 H 1 J 5 L 1 M 2 N 2 S 2 T 1 W 1 X 2 Y 3 Z 1 "J" kommt fünfmal vor und ist damit am häufigsten - vermutlich entspricht es also dem Klarzeichen "E". "E" ist der fünfte Buchstabe im Alphabet, "J" ist die Nummer zehn. Die Verschiebung beträgt also 10 - 5 = 5 Stellen. Rücken wir von "J" aus fünf Stellen im Alphabet zurück, erhalten wir "E". Rücken wir also mal zum Entziffern alle Buchstaben im Krypttext fünf Stellen zurück. Aus "M" wird "h", aus "J" wird "e" aus "Z" wird "u" etc. Schließlich erhalten wir den Klartext "heuteisteinschoenertag" oder etwas lesefreundlicher "Heute ist ein schöner Tag". Na also, geht doch ganz einfach. Doch es geht noch viel einfacher. Dazu kommen wir beim nächsten Mal. An dieser Stelle eine kurze Randbemerkung: In der Kryptologie schreibt man Krypttext immer in Großbuchstaben, Klartext dagegen immer in Kleinbuchstaben. So kann es keine Verwechslungen geben. Außerdem lässt man in der Regel beim Verschlüsseln Leerzeichen und Satzzeichen weg und wandelt Umlaute in normale Buchstaben um (ä = ae, ö = oe, ü = ue, ß = ss). Oft wird der Krypttext dann noch in Fünfergruppen geteilt (hat historische Gründe und ist für die Funker übersichtlicher), sodass unser Beispieltext von eben dann also so aussähe: MJZYJ NXYJN SXHMT JSJWY FL Ist die letzte Fünfergruppe unvollständig, wird sie mitunter mit Füllzeichen aufgefüllt. In diesem Fall wären das also drei zu ergänzende Zeichen. Kryptologen nehmen zum Füllen irgendwelche zufälligen Zeichen, also hier z.B. "GWQ" oder "FLZ" oder so - Ahnungslose nehmen oft "XXX", was dem Kryptoanalytiker aber in die Hände spielt. Ein Caesar ist sehr einfach zu brechen, wie wir gesehen haben. Es genügt, ein einziges Kryptzeichen richtig zu seinem Klarzeichen zuzuordnen, der Rest ist reine Formsache. Zumindest für das "e" wird man die korrekte Zuordnung meist problemlos hinbekommen und das genügt ja auch schon. Daher ist es kein Wunder, dass dieses Verfahren längst aus der Mode gekommen ist (außer bei kryptologisch ahnungslosen Cachern). Wobei man erstaunt anmerken muss, dass das Verfahren in der russischen Armee doch tatsächlich noch bis 1915 in Gebrauch war, weil man den Funkern nach Meinung der russischen Generalität nichts Komplizierteres zumuten konnte. Der Grund für die Unsicherheit des Caesar-Verfahrens liegt auf der Hand: Der Schlüssel besteht aus einer einzigen Zahl, nämlich dem Verschiebefaktor, den man auch als Buchstabe ausdrücken kann. Doch aufgepasst: Das ist etwas verwirrend, weil als Schlüsselbuchstabe derjenige angegeben wird, auf den "a" abgebildet wird. So entspricht z.B. eine Verschiebung um drei Stellen dem Schlüssel "D", da dann aus "a" ein "D" wird. Die Vorschrift für einen Caesar kann man also folgendermaßen ausdrücken:  ROT0 = Verschiebung um  0 = Schlüssel "A": a=A, b=B ... z=Z  ROT1 = Verschiebung um  1 = Schlüssel "B": a=B, b=C ... z=A  ROT2 = Verschiebung um  2 = Schlüssel "C": a=C, b=D ... z=B  ROT3 = Verschiebung um  3 = Schlüssel "D": a=D, b=E ... z=C ... ROT24 = Verschiebung um 24 = Schlüssel "Y": a=Y, b=Z ... z=X ROT25 = Verschiebung um 25 = Schlüssel "Z": a=Z, b=A ... z=Y Obacht: Man liest im Web und in allerlei Tools gelegentlich auch andere Angaben (z.B. beim "De-/Encrypter" von cacheblogger, der einer Verschiebung von 1 den Schlüssel "A" zuordnet). Das ist aber falsch. Zu kryptologischen Themen wird überhaupt einiges an Unfug, Halbwissen und Fehlerhaftem verbreitet. Davon darf man sich nicht verwirren lassen. Für den Verschiebfaktor gibt es nur 25 Möglichkeiten, denn bei einer Verschiebung um 26 Stellen wird jedes Zeichen wieder auf sich selbst abgebildet (entspricht also einer Verschiebung von 0), eine Verschiebung um 27 Stellen entspricht derjenigen um eine Stelle etc. Es gibt also nur 25 verschiedene Schlüssel, nämlich 1 bis 25 (bzw. "B" bis "Z"). Lächerlich und überhaupt kein Problem, die einfach mal alle durchzuprobieren. Man muss also gar nicht mal unbedingt die Zeichen zählen, das häufigste Zeichen ermitteln und den Schlüssel, also den Verschiebefaktor, errechnen. Es genügt, die 25 Möglichkeiten durchzuprobieren - bei einer davon muss sich zwangsläufig der Klartext ergeben. Mit dem Computer eine Sache von grade mal einem Augenblick. Im Anhang findet ihr diesmal ein einfaches, kleines Caesar-Tool. Zu den Tools, die ich mitunter mitschicke, eine kurze Anmerkung: Eingabezellen sind immer gelb, Zellen für optionale Eingaben sind hellgelb, grün sind Ergebnisfelder Im Hintergrund befinden sich mitunter Hilfszellen oder Matrixformeln. Passt also etwas auf, wo ihr hinklickt. Will man auf Nummer sicher gehen, lässt man alles außer den gelben Feldern in Ruhe. Am besten arbeitet man eh immer in einer Kopie der Datei, sodass man wieder auf die Originaldatei zurückgreifen kann, falls mal was schiefgeht. Alles ist offen und frei zugänglich. Es gibt keine Passwortsperren oder geschützten Zellen. So kann jeder alles nachvollziehen und ggf. für seine Bedürfnisse anpassen. Auch die Fehlerbehandlung ist nur rudimentär angelegt. Kann also schon mal sein, dass irgendein Makro mit einer Fehlermeldung aussteigt. Jetzt probiert mal unseren Beispieltext vom letzten Mal aus (MJZYJNXYJNSXHMTJSJWYFL). Kopiert ihn also hier aus dem Text raus und fügt ihn in das gelb markierte Eingabefeld ins Caesar-Tool ein. Am besten fügt ihr übrigens nicht direkt in die Eingabezelle selbst ein, sondern klickt nur auf die Zelle, um sie zu aktivieren, fügt den Text aber in das Formeleingabefeld im Menüblock ein (mit "fx" gekennzeichnet). Dann wird nämlich nur der Text ohne jede Formatierung in die Zelle eingetragen. Andernfalls kann es die Formatierung der Zelle verhauen (Schriftart, Farbe, Rahmen). Eine andere sichere Möglichkeit ist das Einfügen über Kontextmenü bzw. Bearbeiten/ Inhalte einfügen/ Text. Das Tool spielt nun für die ersten 50 Zeichen des Krypttextes alle 25 möglichen Verschiebungen auf einen Blick durch. Somit kann man leicht erkennen, bei welcher Verschiebung sich ein sinnvoller Text ergibt. Diese Verschiebung kann man dann unten im Feld "ROT" einstellen und bekommt den gesamten Klartext ausgegeben. Makros müssen natürlich aktiviert sein, sonst funktioniert der zweite Teil der Geschichte nicht. Der erste Teil, das Durchspielen der 25 Möglichkeiten geht auch ohne Makros, da es sich hierbei um reine Tabellenblattfunktionen handelt. Probiert es einfach mal aus und spielt bisschen damit rum. Weiteres Übungsmaterial gibt es z.B. beim Mystery "Bin's Zentrum ..."  (www.coord.info/GC1MHHT) aus der nett gemachten Krypto-Serie von saxony315, auf die wir noch öfter zurückkommen werden. Das Caesar-Tool eignet sich also gut dazu, bei einem Caesar schnell den Klartext zu erhalten - aber auch dazu, bei einem unklaren Text einen Caesar fix auszuschließen. Ergibt sich bei keiner der 25 möglichen Verschiebungen sinnvoller Text, handelt es sich definitiv nicht um einen Caesar (wobei man aber bedenken muss, dass der Text z.B. auch wortweise oder insgesamt rückwärts geschrieben sein kann, also auch darauf achten).
	allgemeine monoalphabetische Substitution Die nächste Stufe der Substitution nach dem Caesar ist die allgemeine monoalphabetische Substitution, die allerdings bereits seit den Sumerern bekannt ist. Hierbei verschiebt man nicht jedes Zeichen um den gleichen, festen Betrag, sondern ordnet jedem Buchstaben frei ein Ersatzzeichen zu. Beispielsweise kann man für "a" den Ersatz "K" wählen, für "b" nimmt man "W", für "c" setzt man "F" etc. Auf diese Weise erstellt man also ein ungeordnetes Tauschalphabet. Wichtig ist dabei nur, dass jedes Klarzeichen ein anderes Kryptzeichen erhält, sonst ist eine Entschlüsselung nicht eindeutig möglich. Es gilt also wie beim Caesar, dass der Zeichenvorrat von Klartext und Krypttext genau gleich groß ist. Für unser eben genanntes Beispiel sieht der Anfang der Ersetzungstabelle also so aus: p a b c ... c K W F ... Das ist schon mal um einiges sicherer als ein Caesar, aber es gibt dennoch ein paar Probleme damit. Erstens kann man sich nicht mehr so gut merken, wie man den Krypttext zurück in einen Klartext bringt, denn man muss ja 26 Zuordnungen kennen. Wohl kaum einer kann sich zuverlässig ein völlig chaotisches Alphabet merken. OK, dieses Problem löst man mit einem Schlüsselwort, das man sich besser merken kann als eine völlig willkürliche Zeichenfolge. Es gibt viele verschiedene und teils recht komplizierte Verfahren, wie man aus einem Schlüsselwort ein Tauschalphabet erzeugt. Eines der einfacheren und gängigsten Verfahren geht so: Man denkt sich ein beliebiges, nicht zu kurzes Schlüsselwort aus. Sagen wir mal "SONNTAGSSPAZIERGANG". Jeder Buchstabe darf im Tauschalphabet nur einmal vorkommen, also entfernt man die überzähligen - jeder Buchstabe bleibt nur bei seinem ersten Auftreten im Schlüsselwort stehen, alle weiteren streicht man. Damit erhalten wir "SONTAGPZIER". OK, war jetzt ein blödes Beispiel, weil der "GANG" komplett rausgefallen ist. Egal, weiter. Aus dem verstümmelten Schlüsselwort macht man jetzt das Tauschalphabet, indem man das ganze restliche Alphabet ohne die Buchstaben, die im Schlüsselstummel vorkommen, anhängt. Also: "SONTAGPZIERBCDFHJKLMQUVWXY". Darüber schreibt man das normale Alphabet und fertig ist die Laube. Ein wunderbares Tauschalphabet mit einem einfach und unverdächtig auszutauschenden und leicht zu merkenden Schlüssel. Das Ganze sieht dann also so aus: a b c d e f g h i j k l m n o p q r s t u v w x y z S O N T A G P Z I E R B C D F H J K L M Q U V W X Y "a" wird also durch "S" ersetzt, "b" durch "O", "c" durch "N" etc. Im Anhang findet ihr ein kleines Tool, das ein Tauschalphabet erstellt und damit auch gleich ver- und entschlüsselt. Zusätzlich erlaubt es, das Schlüsselwort beliebig im Tauschalphabet zu positionieren. Manchmal ist das notwendig. Wir werden noch ein solches Beispiel kennenlernen. Gut, dieses Problem wäre gelöst. Der nächste Haken bei der Sache ist, dass natürlich wie beim Caesar nach wie vor jedes Zeichen genau durch ein anderes Zeichen ersetzt wird. Und zwar immer das gleiche Zeichen. Bei unserem Beispiel mit dem Sonntagsspaziergang wird jedes "a" im Klartext zu einem "S" im Krypttext. Das ist das spezifische Merkmal der MONOALPHABETISCHEN Substitution. "Monoalphabetisch" bedeutet, dass es nur ein einziges Tauschalphabet gibt. Für jedes Klarzeichen gibt es also nur einen einzigen Austauschpartner und daher tritt auch immer genau das gleiche Kryptzeichen an die Stelle eines bestimmten Klarzeichens. Es gibt zwar - wie könnte es anders sein - eine Ausnahme von dieser Regel (homophone Substitution), aber dazu kommen wir erst später. Für die allgemeine monoalphabetische Substitution stimmt die Regel jedenfalls voll und ganz. Das bedeutet aber auch, dass die Häufigkeit der Klarzeichen auf die Kryptzeichen übergeht. Mit dem Zeichenzählen ist es also für uns ein Leichtes, das häufigste Zeichen herauszufinden und damit einen heißen Kandidaten für das Klarzeichen "e" zu ermitteln. Allerdings können wir nun nicht einfach wie beim Caesar alle anderen Zeichen ebenfalls um den gleichen Betrag verschieben, der zwischen "e" und seinem Tauschpartner liegt. Wir müssen uns also was anderes einfallen lassen, um die Zuordnung der anderen Buchstaben rauszubekommen. Dazu betrachten wir nächstes Mal die Normalverteilung etwas genauer.
	Normalverteilung   Häufigkeitsverteilung bei verschiedenen Chiffrierverfahren Häufigkeitsverteilung bei verschiedenen Chiffrierverfahren ... und hier schon einmal der Ciphertext vom GC1MHHT - "Bin's Zentrum ..." ABEQS HRASA HYYTE NQSHR ASAHY YMJRV RVAFR VAFBF GAHYY RVAFM JRVTE NQSHR ASSHR ASIVR EMJRV FVROR AKKKK CAESAR-Ciffrierung mit Verschiebefaktor Häufigkeitsverteilung bei verschiedenen Chiffrierverfahren PS: ...  die 13 liefert Klartext ... und hier schon einmal der Ciphertext vom GC1MHK3 - "Franzosenfriedhof" LEDUW HVLWL HPPXD RUIZV DRTYG QJVZV ZLFFZ VSVLE FGLHP PVZLF UDVZX DRULH PPWHV LWRTY GUDVZ FZVSV LKKKK Tauschchiffre mit Schlüsselwort Häufigkeitsverteilung bei verschiedenen Chiffrierverfahren Die Normalverteilung, also die "normale" Häufigkeit der einzelnen Buchstaben, ist bei der Kryptoanalyse ein ganz zentrales, allerdings auch etwas heikles Thema. In der Kryptoanalyse nennt man das Auszählen der Häufigkeiten der Zeichen eines Textes übrigens auch "Frequenzanalyse". Es gibt da ein paar kleine Gemeinheiten, die man niemals aus den Augen verlieren sollte. Zunächst einmal müssen wir die Sprache kennen, in der der Text verfasst wurde. Denn natürlich ist die Normalverteilung der Buchstaben in jeder Sprache anders. Ok, für uns wie besprochen geschenkt, weil wir praktisch immer von der deutschen Sprache ausgehen können. Die Normalverteilung einer Sprache zu ermitteln ist allerdings nicht ganz so einfach. Denn erstens verändert sich die Sprache mit der Zeit, sodass man die Statistik immer wieder aktualisieren muss, und zweitens kommt natürlich je nach Text eine etwas andere Häufigkeitsverteilung raus. Ein Roman wird andere Zahlen bringen als ein Fachartikel zur Quantenmechanik oder einer zur Normung von Stahlrohren. Meist gewinnt man die Normalverteilung aus Romanen oder Zeitungen oder einer Mischung aus beidem. Es gibt aber auch spezielle Zahlenwerke zu bestimmten Fachgebieten. Je länger ein Text ist, desto mehr nähern sich die Buchstabenhäufigkeiten einer idealen Normalverteilung an und desto mehr verschwimmen die Unterschiede zwischen verschiedenen Textarten. Ab etwa 1000 Zeichen bestehen auch zwischen verschiedenen Themengebieten kaum mehr statistische Unterschiede. Je kürzer und je spezieller der Text, desto stärker weicht aber seine Häufigkeitsverteilung von der Normalverteilung ab. Mit diesen Problemen haben wir beim Cachen ständig zu kämpfen, weil es sich hierbei in aller Regel eben nicht um normale deutsche Texte handelt. Oft haben wir es mit Texten zu tun, die nur aus Zahlwörtern bestehen oder die allenfalls noch paar Begriffe wie "Cache", "Final", "Koordinaten", "Grad" etc. beinhalten. Und natürlich haben wir meist keine Texte mit Hunderten oder gar Tausenden von Zeichen. Aus einem Text mit nur 20 Zeichen kann man aber nur schwerlich belastbare statistische Schlüsse ziehen. Ab 50 Zeichen geht aber schon ein bisschen was, ab 200 Zeichen sieht die Sache dann schon sehr gut aus, wenn wir Prosatext voraus setzen. Was nützt uns das jetzt zum Brechen einer allgemeinen monoalphabetischen Substitution? Das "e" bekommen relativ sicher raus. Aber wie geht es weiter? Eine ganz gute Idee wäre es vielleicht, wenn wir einfach den zweithäufigsten Buchstaben im Krypttext ermitteln und davon ausgehen, dass dieser dem zweithäufigsten Buchstaben der Normalverteilung entspricht. Im Prinzip keine schlechte Idee, doch das Problem ist, dass das "e" zwar wirklich mit Abstand der häufigste Buchstabe ist, dass sich aber zweit-, dritt- und vierthäufigster Buchstabe etc. nicht mehr so stark in ihrer Häufigkeit unterscheiden, dass man sie eindeutig identifizieren könnte. Beim zweithäufigsten, dem "n", gelingt das zwar nicht immer, aber doch noch recht häufig, danach aber verschwimmen die Grenzen endgültig, wie man in der Liste der durchschnittlichen Häufigkeiten ganz deutlich erkennt: E 17,48% N 9,84% I 7,73% R 7,54% S 6,83% A 6,47% T 6,13% D 4,83% H 4,23% U 4,17% L 3,49% G 3,06% O 2,98% C 2,68% M 2,58% B 1,93% F 1,65% W 1,48% K 1,46% Z 1,14% P 0,96% V 0,94% J 0,27% Y 0,08% X 0,04% Q 0,02% Solche Listen gibt es unterschiedliche in der Literatur. Klar, die Prozentzahlen fallen immer etwas unterschiedlich aus, je nachdem, welche Quelltexte man auswertet. Im Groben stimmen die Angaben aber überein. Zumindest eines ist praktisch immer gleich: "e" ist mit Abstand am häufigsten, dann folgt "n" und dann die Gruppe "irsat", bei der die Reihenfolge je nach Quelle aber etwas verschieden ist und z.B. auch mal "rista" oder "irsta" lauten kann. Auf jeden Fall sind diese genannten Buchstaben die "großen Sieben" im Deutschen, also die sieben häufigsten Buchstaben. Nach ihnen fällt die Häufigkeit deutlich ab. Angenommen, wir haben in einem Krypttext ein Zeichen mit einer Häufigkeit von 6,6%, so wissen wir zwar nicht sicher, welchem Klarzeichen es entspricht, können aber ziemlich sicher sein, dass es zu den großen Sieben gehört und nicht das "e" ist. Üblicherweise teilt man das Alphabet in fünf Gruppen. Die erste Gruppe besteht nur aus dem "e". Die zweite sind die restlichen Kandidaten der "großen Sieben", also "nisrat". Dann kommt die Gruppe der mittelhäufigen Buchstaben "dhulcgmo", gefolgt von den selteneren "bwfkz". Und zum Schluss bleiben die sehr seltenen Buchstaben "pvjyxq". Bei der Identifizierung sind natürlich die "großen Sieben" besonders wichtig (allein schon deshalb, weil sie einen Großteil des Textes ausmachen), aber auch gerade die sehr seltenen Buchstaben verdienen einige Aufmerksamkeit. Schwieriger zuzuordnen ist das Mittelfeld. Meist kann man anhand der Häufigkeit eines Zeichens bestimmen, zu welcher Gruppe es vermutlich gehört. Um das Zeichen tatsächlich zu identifizieren, bedarf es dann aber weiterer Überlegungen und mitunter auch einigen Herumprobierens. Die Buchstaben eines Textes auszuzählen ist natürlich eine ausgesprochen dröge und freudlose, je nach Konzentration auch fehlerträchtige Angelegenheit. Dennoch muss sie gemacht werden. Sie bildet die Grundlage der statistischen Kryptoanalyse. In Bletchley Park, der britischen Kryptoanalyse-Zentrale während des zweiten Weltkriegs, waren Tausende von Mitarbeitern Tag für Tag mit nichts anderem beschäftigt, als die Zeichen abgefangener Funksprüche auszuzählen. Grauenhaft. Zum Glück können wir uns diesen Job vom Rechenknecht abnehmen lassen. Dazu findet ihr mal wieder ein kleines Tool im Anhang. Das stellt das Ergebnis nicht nur als Zahlenwüste dar, sondern auch grafisch. Diese Darstellung nennt man in der Kryptologie "Häufigkeitsgebirge". Jede Sprache hat eine eigene charakteristische Abfolge von Gipfeln und Tälern. Die Normalverteilung im Deutschen wird in diesem Tool mit blauen Säulen dargestellt, die des aktuellen Krypttextes mit grünen Säulen. Auf das Häufigkeitsgebirge werden wir später noch einmal ausführlicher zurückkommen, denn es ist auch hilfreich, um Vermutungen über das verwendete Verschlüsselungsverfahren anzustellen. Außer den Zeichenhäufigkeiten gibt dieses Tool auch noch paar andere Eckdaten aus. Da ist zunächst mal die Gesamtzahl der im Krypttext enthaltenen Zeichen (ohne Leerzeichen). Dann die Anzahl der Vokale und Konsonanten sowie Art und Anzahl der vorkommenden Buchstaben und weiteren Zeichen. Als Buchstaben zählen hier ausschließlich Großbuchstaben. All diese Parameter können uns später mitunter bei der Analyse des verwendeten Verfahrens helfen. Ganz unten wird noch die Summe und die Quersumme der enthaltenen Buchstaben gebildet. Das ist cache-spezifisch, in der Kryptoanalyse braucht man das nicht. Damit kann man gschwind Buchstabensummen einzelner Wörter bilden, was beim Cachen ja gelegentlich ganz nützlich ist. Das ist natürlich eine sehr rudimentäre Auswertung, aber ich denke, für den Rahmen dieses Grundlagenseminars reicht das aus. Man muss bei der ganzen Auszählerei und Rechnerei auch immer bedenken, dass wir es hier mit Statistik zu tun haben, die von Natur aus immer mit erheblichen Schwankungen und Unschärfen behaftet ist - und dies umso stärker, je kleiner die Probenmenge ist - in unserem Fall also, je kürzer der Text ist, den wir analysieren.

3. CRYPTOOL

An dieser Stelle ein kleiner Exkurs, bei dem ich euch mit einem Werkzeug bekannt machen möchte, das wir künftig immer wieder brauchen werden. Es handelt sich um das CrypTool, das vielleicht einige schon kennen. Dieses wirklich starke Programm gibt es zum Runterladen http://www.cryptool.org/ct1download/SetupCrypTool_1_4_30_de.exe oder auch als Online-Version (http://www.cryptool-online.org/). Es ist das beste mir bekannte, frei erhältliche Werkzeug zur Kryptologie. Das Problem mit dem CrypTool ist allerdings, dass es zwar eine schöne Vielfalt von Verfahren beherrscht, und das in beide Richtungen - man kann jeweils Ver- und Entschlüsseln. Auch paar ganz nette Analysefunktionen stellt es bereit. Doch zum Brechen von Chiffren und Codes ist es nur sehr bedingt geeignet. Für die klassischen Verfahren gibt einige nützliche Funktionen, doch die Auswahl bleibt letztlich doch übersichtlich. Es gibt auch kaum die Möglichkeit, Parameter zu variieren oder hinter den Kulissen herumzuschrauben. Für die Transposition schließlich gibt es nur eine reine Entschlüsselungsroutine, die einem aber rein gar nichts nützt, wenn man den Schlüssel nicht hat.

Daher setze ich das CrypTool nur selten ein, sondern bevorzuge Excel-Lösungen. Das hat den Vorteil, dass alles sehr leicht und schnell zu modifizieren ist. Denn grade beim Cachen trifft man sehr häufig nicht auf die typischen klassischen Verfahren, sondern auf Dinge, die sich die Owner selbst haben einfallen lassen. Mitunter findet man auch im Prinzip klassische Verfahren, die die Owner aber - ob nun aufgrund von Unkenntnis, Missverständnissen oder bewusst - nicht ganz korrekt einsetzen. Da ist dann auch eine unkonventionelle Herangehensweise gefragt. Oft muss man eher mal etwas herumprobieren und basteln und rumspielen. Und das erfordert es, die Tools hierhin und dorthin zu modifizieren oder ein Teilergebnis von einem in ein anderes Modul zu übertragen. Dabei ist die Excel-Lösung natürlich flexibler als ein fixes Programm. Für den Rahmen, in dem wir uns mit unserem kleinen Seminar bewegen, eignet sich aber das CrypTool ohne größere Einschränkungen. Also ladet euch am besten mal das Programm runter und schaut euch darin etwas um. Die Version, auf die ich mich beziehen werde, ist die derzeit aktuelle, oben verlinkte Version 4.30. Das Häufigkeitsgebirge heißt im CrypTool übrigens "ASCII-Histogramm" und ist zu finden unter Analyse/ Werkzeuge zur Analyse/ Histogramm - und ihr werdet zugeben müssen, dass unsere Grafik viel schöner ist ;-), die Zeichenzählung befindet sich unter Analyse/ Werkzeuge zur Analyse/ N-Gramm. Einen einfachen Caesar als Übungsmaterial gibt es hier auch unter dem Menüpunkt "Kryptoanalyse" (http://www.cryptoolonline.org/index.php?option=com_content&view=article&id=55&Itemid=53&lang=de).  Den soll man zwar per Frequenzanalyse lösen, aber mit unserem Caesar-Tool sind wir natürlich schneller: CSORK LOXNS OFOBC MRVEO CCOVE XQOBP YVQBO SMRQO UXKMU DOCPY VQDXE XOSXD OHDEO LOBMB IZDYY VEWQO XEOQO XNJOS MROXP EOBOS XOUBI ZDYKX KVICO JEVSO POBXN KCZBY QBKWW MBIZD YYVSC DOSXP BOSOC OVOKB XSXQZ BYQBK WWPEO BGSXN YGCWS DNOWU BIZDY QBKZR SCMRO FOBPK RBOXK XQOGO XNODE XNKXK VICSO BDGOB NOXUY OXXOX NSOCO CYPDG KBOGS BNGOV DGOSD OSXQO CODJD NKLOS EXDOB CDEOD JDCSO OSXOW YNOBX OVORB OKXCM REVOX EXNRY MRCMR EVOXC YGSON SOCOX CSLSV SCSOB EXQFY XPSBW OXKXQ ORYOB SQOX So viel für den Moment - nächstes Mal knacken wir dann einen monoalphabetisch verschlüsselten Krypttext.

4. Systematik bei der Kryptoanalyse einer monoalphabetischen Substitution

	Wie angekündigt brechen wir heute eine monoalphabetische Substitution. Dazu kommt ein kleines, praktisches Werkzeug mit, das uns die Sache etwas komfortabler gestalten wird. Doch macht euch keine Illusionen: Krypttext vorne rein, Klartext hinten raus geht auch damit nicht. Es wird schon ein Stück Arbeit, bis wir den Klartext vor uns haben. Drum wird das diesmal auch eine etwas längere Abhandlung, weil ich das Praxisbeispiel am Stück durchziehen will. Das lässt sich nicht sinnvoll teilen. Nehmen wir uns zur Demonstration mal einen konkreten Fall vor, nämlich "Die Wiederkehr des Human Tasty Burgers" (www.coord.info/GC263FG). Der ist zwar inzwischen archiviert, aber ist ja wurscht.
	Zunächst mal sehen wir auf der "Speisekarte" nur wirres Zeug. Schaut man sich die Zeichen genauer an, wird schnell klar, dass es nicht allzu viele unterschiedliche sind. Es sind auch Leerzeichen erhalten. Das deutet doch recht deutlich auf eine simple Substitution hin. Jedes der merkwürdigen Zeichen steht also wohl für einen Buchstaben. Damit dürfte das kein all zu großes Problem werden. Randbemerkung: Die Sache ist im Grunde noch viel einfacher, weil es keine echte Substitution ist, sondern nur eine Codierung. Es wurde einfach statt des normalen ein anderer Zeichensatz verwendet. Dieser Zeichensatz heißt "Futurama" und ist im Web leicht zu finden. Aber zu Übungszwecken stellen wir uns erst mal dumm und gehen davon aus, die Sache ohne Kenntnis des Zeichensatzes lösen zu müssen. Zur Herkunft des Cache-Namens siehe http://www.kryptographiespielplatz.de/index.php?aG=3e19d3a084e42d6e4dcf3cd1d23254de039da751. Zunächst wandelt man in Handarbeit die merkwürdigen Zeichen in beliebige Buchstaben um. Gleiche Zeichen erhalten natürlich immer den gleichen Buchstaben. Das hab ich hier schon mal für euch erledigt. Das Ergebnis sieht so aus: AB CDE FABGE HGIHJ KALMDL NA OPECDE, BAII BGE EAL DHQGI RDPSDE. GTFHFA ECDLHOADEONPM BDHDL KDP NQDPAECGTFHNPM MLGC. UPDS IRGII QADEITFD PTF monoalphabetische Kryptoanalyse Häufigkeitsverteilung bei verschiedenen Chiffrierverfahren Kopiert diesen Krypttext in das Substitutions-Tool rüber. Schauen wir mal, was hier passiert. In der Tabelle links werden die ersten 60 Zeichen des Krypttextes als Liste ausgegeben. Diese Liste braucht man nur selten, aber hin und wieder ist es doch ganz praktisch, auch eine Auswertung auf Einzelzeichenbasis zu haben. Grade wenn irgendwelche Sonderzeichen Schwierigkeiten machen, kann man hier am besten die Spur zum Problem aufnehmen. In der Tabelle mit den -Button werden die Buchstaben des Krypttextes ausgezählt. Wir erhalten die absolute Anzahl und die prozentuale Häufigkeit der enthaltenen Zeichen. Mit den beiden -Knöpfen kann man diese Tabelle alphabetisch oder nach Häufigkeit sortieren lassen. Unten wird noch die Gesamtzahl der enthaltenen Buchstaben ausgegeben. Das Herz der ganzen Veranstaltung ist die Tabelle rechts daneben (daher auch fett umrandet). Die besteht aus zwei Spalten. In die linke, gelbe Spalte (und nur hier) gibt man diejenigen Kryptzeichen ein, die den Klarzeichen in der rechten Spalte dieser Tabelle entsprechen sollen. Wenn man hier was eingibt, zeigt der Block darunter das Ergebnis der Ersetzung. Die weißen und beigen Zeilen zeigen die Ersetzung schrittweise - also je Zeile die Ersetzung des hier in der linken blauen Spalte stehenden Klarzeichens und aller darüberstehenden. Hier muss man nur selten genauer hinsehen. Von entscheidender Bedeutung ist dagegen die grüne Zeile ganz oben auf dem Block . Das ist praktisch eine Zusammenfassung aller Zeilen darunter und zeigt das Ergebnis aller Ersetzungen zusammen. Da wir in die zentrale Ersetzungstabelle (die mit der gelben Spalte) noch nichts eingegeben haben, wird noch nichts ersetzt, sodass hier noch der unveränderte Krypttext steht. Zur leichteren Orientierung kann man hier die im Text noch nicht durch Klarzeichen ersetzten Kryptzeichen auch ausblenden. Jetzt, wo wir noch keine Ersetzungen haben, also ausschließlich Kryptzeichen zu sehen sind, werden logischerweise alle Zeichen ausgeblendet. Welche Kryptzeichen welchen Leerstellen im Klartext („-“) entsprechen, kann man in der Zeile drunter mit dem unveränderten Krypttext sehen . Die Zeichen stehen immer genau untereinander (u. a. deswegen Ausgabe in Schriftart Courier). Ganz rechts gibt es noch paar statistische Normalwerte, die mitunter nützlich sein können. Alles klar? OK, dann also los. Sortieren wir die Tabelle mit der Frequenzanalyse erst mal nach Häufigkeit (mit dem rechten -Knopf). Häufigstes Zeichen ist „D“ mit 15 Vorkommen. Dürfte also wohl „e“ entsprechen (ihr erinnert euch: Kryptzeichen immer groß, Klarzeichen immer klein). Das „e“ ist fast immer eindeutig und sicher zu bestimmen - Betonung auf „fast“, kann auch mal anders sein. Bei den nächsten der „großen Sieben" muss das nicht immer perfekt hinhauen. Zwar ist meist klar, wer zum Mitgliederkreis gehört, aber nicht ganz genau, wer auf welche Position innerhalb der Gruppe gehört. Die Farben in der Normalwerttabelle rechts neben den Substitutionstabellen deuten diese Gruppen an (deren Grenzen natürlich nicht als völlig statisch anzusehen sind). Also schauen wir doch einfach mal, ob wir vielleicht richtig viel Glück haben und der Text eine perfekte Häufigkeitsverteilung aufweist. Mit dem -Button links der Substitutionstabelle überträgt man die Buchstaben aus der Frequenzanalyse in die Substitutionstabelle, der Knopf mit dem Knubbel löscht die gelbe Spalte der Substitutionstabelle wieder. Da in der Frequenzanalyse die Klarzeichen jetzt nach Häufigkeit sortiert sind, stehen sie nach dem Übertragen natürlich auch in dieser Häufigkeitsreihenfolge in der Substitutionstabelle. Im günstigsten Fall könnte das eine perfekte Zuordnung sein. Denn die Klarzeichen in der Substitutionstabelle sind ebenfalls nach der Normalverteilung geordnet. Dann müsste sofort der Klartext erscheinen. Den Gefallen tut er uns natürlich nicht - schon klar, dass solche Glücksfälle sehr selten sind - zumal bei so kurzen Texten wie diesem. In unserem Fall erkennt man noch nicht mal ansatzweise irgendwelche Klartextfetzen. Hmm, also nicht sonderlich überzeugend. OK, dann also Handarbeit. Mal sehen, ob wir wenigstens bei den „großen Sieben" besser liegen. Also die gelben Substitutionszellen von „d“ bis „q“ (in diesem Fall also „F“ bis „Z“ bzw. die Zellen L17 bis L35) löschen (das gilt fast immer!!!). Aha, da passieren jetzt gleich mehrere Dinge. Die bereits einem Substituenten zugeordneten Klarzeichen in der Substitutionstabelle und die verwendeten Substituenten selbst in der Frequenztabelle sind etwas weggedimmt (also die Zeichen, die schon vergeben sind), die anderen sind fett auf blauem Hintergrund dargestellt. Außerdem hat sich der Text in der Klartextzeile verändert. Er enthält jetzt (sofern Kryptzeichen nicht ausgeblendet sind) Groß- und Kleinbuchstaben. Die Kleinen sind die Klarzeichen, die Kryptzeichen ersetzt haben, die Großen sind die noch nicht substituierten Kryptzeichen (also die, für die oben in der gelben Spalte noch nichts eingetragen ist). Die kann man wie schon gesehen auch ausblenden, was die Arbeit meist erheblich erleichtert. Also gleich mal den Haken setzen, falls er nicht schon drin ist. Na, das sieht doch gleich viel besser aus. Wenn man wie in diesem Fall im Text Leerzeichen hat, also die Wortgrenzen kennt, dann guckt man erst mal nach ganzen Wörtern. Es bieten sich kurze Wörter mit drei Buchstaben an, weil sich viele von ihnen aus den „großen Sieben" (plus „d“) rekrutieren (z.B. „ist“, „ein“, „den“, „die“, „der“, „das“, „und“, „sie“, „man“, ...). Gleich am Anfang sieht es gut aus: Das zweite Wort „CDE“ wird durch unsere Substitution zu „-en“ und könnte „den“ entsprechen. Für das neunte Wort ergibt sich aber leider ein Trigramm (Zeichenfolge aus drei Zeichen) „-sn“, was nicht sein kann - es gibt kein Wort im Deutschen, das aus drei Buchstaben besteht und bei dem zweiter und dritter Buchstabe „sn“ lauten (zumindest fällt mir keines ein). Sofern die Leerzeichen also tatsächlich die wahren Wortgrenzen bedeuten, haut unsere Substitutionsvorschrift noch nicht hin. Dieses „-sn“ ist entstanden aus „BGE“. Entweder ist die Zuordnung von „G“ für „s“ oder die von „E“ für „n“ falsch. „n“ am Ende könnte gut sein („den“, „wen“, „ein“, „von“, „man“, ...). Ein Trigramm mit „s“ in der Mitte könnte natürlich auch sein („ist“, „Ast“, „Ost“), ist aber doch seltener. Gegen das „s“ spricht auch das zweite Wort des Textes, das auf „-sn“ endet. Auch im weiteren Überblick wirkt das „s“ eher störend. Also hier würde ich jetzt den Substituenten von „s“ (also „G“) aus der Substitutionstabelle löschen. „CDE“ = „den“ ist so naheliegend, dass man das einfach probieren muss. Zumal „d“ ja noch gar nicht vergeben ist (in der Substitutionstabelle nicht gedimmt). Also in das gelbe Feld links neben „d“ ein „C“ eingeben. So, außer dem „den“ (zweites Wort) kann ich immer noch nichts Entscheidendes entdecken. Wenden wir uns mal dem achten Wort zu („BAII“). Ein Wort mit einem Doppelbuchstaben am Ende, das nach einem Komma steht. Könnte doch „dass“ sein, zumal „S“ der am häufigsten gedoppelte Buchstabe im Deutschen ist. Dazu müsste aber „I“ dem Klarzeichen „s“ entsprechen. Bislang ist „I“ aber schon an „r“ vergeben. Egal, tragen wir links neben „s“ mal „I“ ein. Unten in der Klartextzeile lautet das Wort jetzt „-iss“. In der Substitutionstabelle ist das „I“ nun rot. Das kommt daher, dass es doppelt vergeben ist, was natürlich nicht sein darf. Also werfen wir das „I“ bei „r“ raus. Wenn wir aus dem „-iss“ jetzt „dass" machen wollen, müssen wir aus dem „i“ ein „a“ machen und aus dem ersten Zeichen („B“) ein „d“. Aber Moment mal, für „d“ haben wir doch schon das „C“ vergeben. Wenn wir das ändern, ist es Essig mit unserem „den“ vom Anfang, das so plausibel aussieht. Hmm, überlegen, was gibt es noch für Möglichkeiten für ein Wort mit „ss“ am Schluss, das nicht mit „d“ anfängt? „Riss“, „Kuss“, „muss“, „Fass“, „nass“, „kess“ - mehr fällt mir dazu grade nicht ein. In solchen Fällen kann auch mal ein Kreuzworträtsel-Lexikon hilfreich sein, was es natürlich auch online gibt: http://www.kreuzwort-raetsel.net/suche.php?m=lueckentext Für den Moment erscheint mir „muss“ als am plausibelsten. Also mal links neben „m“ das „B“ eintragen und neben „u“ das „A“. Das „A“ ist doppelt, wie die rote Färbung zeigt, also das „A“ beim „i“ löschen. Na, das sieht doch schon gar nicht so schlecht aus. Als erstes Wort ergibt sich „um“, nicht unplausibel. Nach dem "muss“ kommt „m-n“. Könnte „man“ sein. Also für „a“ das „G“ statt dem „P“ eintragen. Ha, das sieht doch richtig gut aus. Es ergeben sich eine ganze Reihe von Ansatzpunkten, um weiterzukommen. Gleich am Anfang kann man vermuten, dass hier der Cache-Titel stehen muss: „um den human tasty burger“. Das 15. Wort „BDHDL“ sieht schwer nach „meter“ aus. Nach und nach ergibt sich eins aus dem anderen. Früher oder später gibt der Knoten nach. Steckt man mal fest, orientiert man sich an der Statistik von Buchstaben, Bigrammen und Trigrammen sowie den Sprachmerkmalen und der Paarung von Vokalen und Konsonanten. Das „e“ ist ja meist ziemlich eindeutig. Da ihm am häufigsten ein „n“ oder „r“ folgt (die ebenfalls beide zu den „großen Sieben“ gehören), kommt man damit oft weiter. Die Bigramme „ei“ und „ie“ sind relativ ähnlich häufig, während sich „ch“ und „hc“ in der Häufigkeit krass unterscheiden. Nach „c“ kommt fast immer ein „h“, selten ein „k“, sonst so gut wie nichts (OK, in Zeiten der Anglizismen stimmt das nicht mehr so ganz). Vor „ch“ oft ein „s“. Nach „q“ immer ein „u“ und ein weiterer Vokal ... Es würde jetzt zu weit führen, worauf man so alles achtet. Man bekommt mit der Zeit ein Gefühl dafür und jeder hat seinen eigenen Stil. Am schwierigsten ist immer der Anfang. Hat man erst mal die sechs oder sieben häufigsten Buchstaben korrekt zugeordnet, läuft es meist wie von selbst. Man muss ja bedenken, dann die zehn häufigsten Buchstaben im Deutschen rund 75% eines Textes ausmachen. Den Rest zu erraten sollte nicht schwer sein. Kopiert den Ausgangstext AB CDE FABGE HGIHJ KALMDL NA OPECDE, BAII BGE EAL DHQGI RDPSDE. GTFHFA ECDLHOADEONPM BDHDL KDP NQDPAECGTFHNPM MLGC. UPDS IRGII QADEITFD PTF in Zelle D4 rechter Sortierschalter ... (Frequenzanalyse) Substitution mit Pfeil-Taste komplett übernehmen „F“ bis „Z“ bzw. die Zellen L17 bis L35 löschen in das gelbe Feld links neben „d“ ein „C“ eingeben Egal, tragen wir links neben „s“ mal „I“ ein ... lso werfen wir das „I“ bei „r“ raus ... also mal links neben „m“ das „B“ eintragen neben „u“ das „A“ - das „A“ ist doppelt, wie die rote Färbung zeigt, also das „A“ beim „i“ löschen ... also für „a“ das „G“ statt dem „P“ eintragen ... das 15. Wort „BDHDL“ sieht schwer nach „meter“ aus Den Rest zu erraten sollte nicht schwer sein.   Wir haben den Text geknackt - auch ganz ohne Kenntnis des Zeichensatzes. Die statistische Methode funktioniert also nicht nur bei alphabetischen Krypttexten, sondern auch bei Zeichen, die nicht dem Alphabet entstammen wie eben z. B. dem Freimaurer-Code (z.B. www.coord.info/GC1A124) oder dem Moon-Alphabet (z.B. www.coord.info/GC296J2, www.coord.info/GC26G7B) oder was auch immer. Man ersetzt willkürlich jedes Kryptzeichen durch einen Buchstaben, macht eine Frequenzanalyse dieser Zeichenfolge und schon sollte einem Brechen des Krypttextes nichts mehr im Wege stehen. Klar ist es einfacher, wenn man den Code (bzw. den Zeichensatz) kennt, aber zur Not kommt man eben auch so weiter. Ein weiteres Beispiel eines exotischen Zeichensatzes ist der wirklich schön gemachte „Sonne, Mond und Sterne“ (www.coord.info/GCY6XR). Als weiteres Beispiel und Übungsmaterial sei wieder einer aus der sächsischen Krypto-Serie genannt, nämlich „Franzosenfriedhof“. (www.coord.info/GC1MHK3). Dies ist kein merkwürdiger Zeichensatz, sondern eine ganz gewöhnliche monoalphabetische Substitution mit Buchstaben. Beachtet hier auch die vier „K“ am Ende des Krypttextes. Klarer Fall von Füllzeichen (die zu allem Überfluss auch noch tatsächlich „X“ entsprechen). Zwar gibt der Owner hier den Schlüssel an, aber den brauchen wir eigentlich bei unserem Verfahren gar nicht. Klar, mit Schlüssel geht es natürlich schneller und einfacher, ist aber eigentlich auch witzlos - für diesen Weg könnt ihr das Tauschalphabet-Tool einsetzen: Krypttext in die gelbe Zelle „Krypttext“ kopieren (zur Erinnerung: am besten per Kontextmenü bzw. Bearbeiten/ Inhalte einfügen/ Text oder oben in die Formeleingabezeile), Schlüsselwort „NAPOLEON“ eingeben und Position auf 10 stellen). Voilá, schon erscheint der Klartext. Und noch eine Herausforderung: Eines der wohl bekanntesten kryptologischen Rätsel der Literaturgeschichte ist das Kryptogramm des Piraten Captain Kidd in der Erzählung „Der Goldkäfer” von Edgar Allan Poe, dessen Steckenpferd die Kryptologie war. Es soll die Position eines Schatzes beschreiben und lautet: 53‡‡†305))6*,4826)4‡.)4‡);806*;48†8p60))85;1‡(;:‡*8†83(88)5*†;46(;88*96*?;8)*‡(;485);5*†2:*‡(;4956*2(5*-4)8p8*;4069285);)6†8)4‡‡;1(‡9;48081;8:8‡1;48†85;4)485†528806*81(‡9;48;(88;4(‡?34;48)4‡;161;:188;‡?; Der Protagonist der Geschichte, William Legrand, der den Krypttext auch knackt, erklärt seinen Lösungsweg recht ausführlich - geradezu ein Lehrstück der Kryptoanalyse. Wen's interessiert, der kann es z.B. hier nachlesen: http://gutenberg.spiegel.de/buch/2271/1. Zum Abschluss der monoalphabetischen Substitution sei noch erwähnt, dass man natürlich auch Ziffern mit einem Schlüsselwort codieren kann. Dann ist das Tauschalphabet natürlich nur zehn Zeichen lang, weil es ja nur zehn Ziffern gibt. Ein relativ bekanntes Beispiel ist der Kaufmannscode, mit dem früher u. a. das Verpackungsdatum von Butter codiert wurde. Hierbei war das Codewort für die Ziffern von 1 bis 0 „MILCHPROBE“: 1 2 3 4 5 6 7 8 9 0 M I L C H P R O B E Butter mit der Kennzeichnung „ILME" wurde also am 23. Oktober verpackt. Ein weiteres und etwas pikanteres Beispiel, das auch durch die Presse ging, ist der „MAKEPROFIT-Code“ (http://www.manager-magazin.de/unternehmen/artikel/0,2828,464741,00.html). So, damit hätten wir die monoalphabetische Substitution durch und können uns nun gut gerüstet interessanteren Themen zuwenden. Nächstes Mal geht es dann los mit der polyalphabetischen Substitution, deren bekanntester Vertreter Vigenère ist.
	Übungsteil I Ciphertextbeispiel als Abbildung Ciphertextbeispiel im Word Format Achtung! Zur Kryptoanalyse nicht mehr als eine viertel Seite des Originals verwenden - die Rechenzeit steigt (logischerweise) sprunghaft an! Erstangriff - einfache Frequenzanalyse - hilft nicht wirklich!!!
	Übungsteil II - mit Demonstration zur Vorgehensweise GC3FFPW - Heimat - Die Blaue Welle zu Flöha der "Geheimtext" mit monoalphabetischer Verschlüsselung Zeichenzuordnung Statistische Häufigkeitsverteilung Text zusammensetzen ... bringt uns als Ergebnis N 50°51.070 E 13°04.781 ... hier die Datei im CorelDraw 10.0-Format
	Übungsteil III - hier nun bist Du dran GC1355Z - Schatz vom Pöhlberg ... der aufgefundene Code
	Bei der monoalphabetischen Substitution ist ja das Problem, dass wir mit einem einzigen Tauschalphabet arbeiten, sodass die sich die Zeichenhäufigkeiten vom Klartext auf den Krypttext übertragen. Damit aber ist der Krypttext mit statistischen Methoden sehr leicht angreifbar. Das ist im Prinzip auch schon lange bekannt. Bereits im 9. Jahrhundert veröffentlichte der arabische Philosoph al-Kindi in Bagdad das erste bekannte kryptoanalytische Werk überhaupt, in dem er die Frequenzanalyse vorstellte. Es dauerte allerdings eine kleine Ewigkeit, bis sich das auch in Europa rumgesprochen hatte. Und so galt hierzulande die monoalphabetische Substitution noch lange als sicher. Es sollte bis zur Renaissance dauern, bis dieses Problem angegangen wurde. Der Florentiner Leon Batista Alberti stellte 1466 in seinem Werk "De cifris" schließlich ein verbessertes Verfahren vor. Seine Idee war, statt mit nur einem Tauschalphabet mit zweien zu arbeiten, zwischen denen man nach jedem dritten oder vierten Wort wechselt. Damit bekommt jedes Klarzeichen zwei verschiedene Austauschpartner. Dies ist die einfachste Form der POLYALPHABETISCHEN Substitution, also einer Substitution, die mehr als nur ein Tauschalphabet verwendet. Beispiel: Setzen wir als Tauschalphabet mal unseren SONNTAGSSPAZIERGANG ein, im ersten Fall ab Position 1, im zweiten ab Position 10. Allerdings wechsle ich hier die Tauschalphabete nicht wie von Alberti vorgeschlagen nur alle paar Wörter, sondern nach jedem Klarzeichen: p  a b c d e f g h i j k l m n o p q r s t u v w x y z k1 S O N T A G P Z I E R B C D F H J K L M Q U V W X Y k2 K L M Q U V W X Y S O N T A G P Z I E R B C D F H J Da wird dann aus "Heute ist ein schöner Tag": p heute ist ein schoener tag c ZUQRA YLR AYD ENXFUDUK RSW Zur besseren Orientierung hab ich mal die Leerzeichen stehen lassen. Man sieht z.B. gleich im ersten Wort, dass das erste "e" zu "U" wurde, das zweite aber zu "A". Wenn wir uns die Frequenzanalyse anschauen, wird deutlich, dass es jetzt nicht mehr so ohne Weiteres möglich ist, einen Tauschkandidaten für "e" zu finden: A D E F K L N Q R S U W X Y Z 2 2 1 1 1 1 1 1 3 1 3 1 1 2 1 Die fünf "e" haben sich aufgeteilt auf zwei "A" und drei "U". Beim Caesar schwankten die Häufigkeiten beim gleichen kurzen Text zwischen einem und fünf Vorkommen, hier nun nur noch zwischen einem und drei. Das ist ein typisches und wichtiges Erkennungsmerkmal polyalphabetischer Verfahren: Die Höhe der Gipfel und die Tiefe der Täler im Häufigkeitsgebirge wird geringer, das gesamte Profil wird also gleichmäßiger und wirkt irgendwie eingeebnet. Wir kommen darauf später noch ausführlicher zurück. Gut, dieser Text ist auch ziemlich kurz. Bei längeren Texten würden die typischen Häufigkeiten doch wieder durchschimmern, wenn auch nicht mehr ganz so deutlich. Trotzdem kein Problem für einen gewieften Kryptoanalytiker.

5. Systematik bei der Kryptoanalyse einer polyalphabetischen Substitution - Vigeère-Chiffre

	Über mehrere Zwischenstufen hat sich die Sache dann weiterentwickelt. Bereits Ende des 15. Jahrhunderts hatte Trithemius eine Tafel mit 26 Tauschalphabeten entwickelt, die auf der simplen Caesar-Verschiebung basieren. Der Einsatz der Caesar-Verschiebung ermöglicht es, die benötigten Tauschalphabete ganz einfach und ohne Schlüssel oder sonst was aus dem Kopf aufzustellen. Dabei kommen alle 26 möglichen Varianten der Verschiebung zum Zug - also auch die Version, bei der jedes Zeichen auf sich selbst abgebildet wird (das A-Alphabet). Diese Tafel nannte er "tabula recta". 1553 schlug Giovanni Battista Belaso vor, mehr als zwei Tauschalphabete zu verwenden und sie anhand eines Schlüsselworts auszuwählen. Und schließlich kam Blaise de Vigenère mit einer Idee, die sich letztlich durchgesetzt hat (1586 veröffentlicht in "Traicté des Chiffres"). Er kombiniert die Tafel von Trithemius mit der Schlüsselwort-Technik von Belaso. Und das geht so: In der Kopfzeile haben wir im Vigenère-Quadrat die Klarzeichen, darunter stehen alle 26 Verschiebungen von 0 bis 25, also die Tauschalphabete A bis Z. Das Ganze entspricht also der tabula recta von Trithemius.
	a b c d e f g h i j k l m n o p q r s t u v w x y z A A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B B C D E F G H I J K L M N O P Q R S T U V W X Y Z A C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B D D E F G H I J K L M N O P Q R S T U V W X Y Z A B C E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D F F G H I J K L M N O P Q R S T U V W X Y Z A B C D E G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H J J K L M N O P Q R S T U V W X Y Z A B C D E F G H I K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K M M N O P Q R S T U V W X Y Z A B C D E F G H I J K L N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M O O P Q R S T U V W X Y Z A B C D E F G H I J K L M N P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Z Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Tithemius verwendet einfach alle Alphabete der Reihe nach. Der erste Klarbuchstabe wird mit dem A-Alphabet codiert, der zweite mit dem B-Alphabet etc. Nach dem Z-Alphabet geht es wieder mit dem A-Alphabet von vorne los. Das entspricht einem Verfahren, das man heute als "Caesar mit laufendem Schlüssel" bezeichnet (oder auf schlau: Verschiebechiffre mit inkrementiertem Vektor) und das doch relativ leicht zu durchschauen ist. Die Verbesserung von Vigenère besteht darin, dass er wie Belaso ein Schlüsselwort zur Auswahl der einzusetzenden Tauschalphabete verwendet. Zwei grundsätzliche Anforderungen an das Schlüsselwort gelten wie bei der monoalphabetischen Verschlüsselung: gut zu merken und nicht zu kurz. Sonst ist es egal, wie es lautet. Nur Doppelbuchstaben sollte man vermeiden - warum, das sehen wir gleich. Als Beispiel sei das Schlüsselwort mal "GARTEN". Dieses Schlüsselwort bestimmt, mit welchem der 26 Caesar-Tauschalphabete das jeweils aktuelle Klarzeichen codiert wird. Das Entschlüsseln geht genau andersrum, ist klar. Da "GARTEN" sechs verschiedene Buchstaben enthält, benötigen wir auch nur sechs Tauschalphabete des Vigenère-Quadrats, die wir der Reihe nach abwechselnd nutzen: a b c d e f g h i j k l m n o p q r s t u v w x y z G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F A A B C D E F G H I J K L M N O P Q R S T U V W X Y Z R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
	Beispiel: Der Klartext sei wieder unser "Heute ist ein schöner Tag". Für den ersten Buchstaben des Klartextes bestimmt der erste Buchstabe des Schlüsselworts das Tauschalphabet. Erstes Klarzeichen ist "h", das wird mit dem G-Tauschalphabet codiert, also wird aus dem "h" ein "N", denn im Schnittpunkt von Spalte h und Zeile G steht eben "N". Das zweite Klarzeichen "e" wird mit dem Tauschalphabet codiert, das dem zweiten Schlüsselbuchstaben entspricht, also dem A-Alphabet. Dieses bildet jeden Buchstaben auf sich selbst ab, das "e" wird also "E". Das dritte Klarzeichen ist "u", es wird mit dem Tauschalphabet des dritten Schlüsselbuchstabens codiert, also mit dem R-Alphabet. Schnell ein Blick ins Vigenère-Quadrat: Im Schnittpunkt von "u" und "R" steht unser drittes Kryptzeichen, und das ist "L". So geht das immer weiter. Das Prinzip ist klar, denke ich. Wenn man am Ende des Schlüsselworts angelangt ist, fängt man einfach wieder vorne bei ihm an: k G A R T E N G A R T E N G A R T E N G A R T p h e u t e i s t e i n s c h o e n e r t a g c N E L M I V Y T V B R F I H F X R R X T R Z Unser Krypttext lautet also: NELMI VYTVB RFIHF XRRXT RZ Jedes Klarzeichen hat jetzt potenziell so viele Austauschpartner, wie das Schlüsselwort unterschiedliche Buchstaben hat. Das versaut uns natürlich die Statistik ganz gehörig. Damit wird dann die Frequenzanalyse zu einem stumpfen Schwert in der Hand des Kryptoanalytikers - könnte man meinen. Weit gefehlt, es wird nur alles etwas komplizierter und strapaziöser. Zunächst konnte sich das als umständlich geltende Verfahren lange nicht durchsetzen. Schließlich aber war es doch in ganz Europa hoch geschätzt und galt als absolut sicher. Denn es ging geraume Zeit ins Land, bis die Kryptoanalytiker herausgefunden hatten, wie sie dieses gemeine Verfahren knacken konnten. Das als "Chiffre indéchiffrable" berühmte Verfahren blieb bis zum Ende des 19. Jahrhundert ungebrochen und das Standardverfahren der militärischen und diplomatischen Korrespondenz. Wie man einem Vigenère dennoch zu Leibe rücken kann, dazu kommen wir nächstes Mal. Vorher noch eine kurze Betrachtung zur Anzahl der Tauschalphabete. Wie viele unterschiedliche Tauschalphabete eingesetzt werden, hängt von der Anzahl unterschiedlicher Buchstaben im Schlüsselwort ab. Das bedeutet, dass ein längeres Wort mehr Tauschalphabete ins Spiel bringt. Aber eben nur, wenn es auch viele verschiedene Buchstaben enthält. Ein Schlüsselwort wie "POPELEO" oder "LOLLIPOP" bringt es grade mal auf vier Tauschalphabete - nicht besonders schlau gewählt. Außerdem bewirken Doppelbuchstaben, dass zwei Buchstaben hintereinander mit dem gleichen Tauschalphabet codiert werden, was dem Kryptoanalytiker einen zusätzlichen Ansatzpunkt für seine Brechstange liefern kann. Denn neben dem Verwischen der Zeichenhäufigkeiten muss der Kryptograph auch versuchen, die nachbarlichen Beziehungen zwischen den Buchstaben zu kaschieren. Bigraphische Analyseverfahren haben es nämlich genau darauf abgesehen. Man sieht also mal wieder: Ein Verfahren allein bringt noch keine Sicherheit, man muss es auch richtig bedienen. Selbst modernste Verfahren werden unsicher, wenn man sie nicht korrekt einsetzt. Daher ist es nie ein Fehler - auch abseits vom Cachen - zumindest ein wenig Ahnung von Kryptologie zu haben. Das Wichtigste aber ist, sich bewusst darüber zu sein, dass kein Verfahren der Welt absolute Sicherheit gewährleisten kann und dass die Sicherheit ganz maßgeblich von der richtigen Anwendung abhängt. Das gilt für den Vigenère gleichermaßen wie für die modernen Verschlüsselungen im Bankwesen, im WLAN oder beim "cloud computing". Gerade heute ist ein solches Wissen und Bewusstsein wichtiger denn je und wir werden später noch Fälle analysieren, die das mehr als deutlich belegen. Aber ich schweife ab. Im Anhang findet ihr diesmal ein kleines Vigenère-Tool zum Ver- und Entschlüsseln. Zeichen, die keine Buchstaben sind, ignoriert das Tool einfach und gibt sie unverändert aus. So was sollte aber eigentlich gar nicht vorkommen. Ich habe diesen Fall dennoch vorgesehen, weil manche Cacher Satzzeichen oder Umlaute gegen jede Regel und Gepflogenheit in Vigenère-Verschlüsselungen stehen lassen. Vigenère-Tool von haensel + gretel Ganz rechts gibt es noch die Funktion "Anzeige Zeichen". Das funktioniert aber nur für das Verschlüsseln und ist daher weg gedimmt, wenn Entschlüsseln eingestellt ist. Wenn hier z.B. 3 eingestellt ist, wird im Vigenère-Quadrat die Spalte mit dem dritten Klartextzeichen und die Zeile mit dem dafür relevanten Schlüsselzeichen eingefärbt. Am Schnittpunkt der beiden Markierungen kann man dann das Kryptzeichen ablesen. Das klappt aber nur fehlerfrei, wenn zu verschlüsselnder Klartext und Schlüssel keine anderen Zeichen als Buchstaben enthalten (auch keine Leerzeichen) - sonst kommt eine falsche Anzeige zustande. Dieses Spielzeug ist nur zur Illustration des Umgangs mit dem Vigenère-Quadrat gedacht. Fürs normale Ver- und Entschlüsseln braucht man das natürlich nicht. Ist 0 eingestellt, ist die Funktion ausgeschaltet. Das war's für diesmal. Nächstes Mal besprechen wir dann, wie man einen Vigenère brechen kann.
	So, machen wir weiter! Wie immer dran denken: nichtproportionale Schrift zur Anzeige verwenden (z.B. Courier). Wir waren beim Vigenère, also dem Klassiker der polyalphabetischen Substitution, den wir heute nach allen Regeln der Kunst brechen werden. Wir hatten letztes Mal besprochen, dass bei einem Vigenère umso mehr Tauschalphabete eingesetzt werden (und das Verfahren damit umso sicherer wird), je mehr unterschiedliche Buchstaben das Schlüsselwort enthält, womit es natürlich auch länger wird. Dem steht aber entgegen, dass das Schlüsselwort möglichst gut zu merken sein soll und auch unauffällig zu übergeben sein muss. Das wiederum ist mit möglichst kurzen Wörtern am besten möglich. Der Kompromiss liegt wie immer in der Mitte. Üblich sind Schlüsselwortlängen von acht bis fünfzehn Buchstaben. Das hat sich als am praktikabelsten erwiesen. Kürzere Schlüsselwörter sind zu unsicher, längere schlecht zu merken und zu handhaben. Auf alle Fälle ist das Schlüsselwort beim einfachen Vigenère immer wesentlich kürzer als die Nachricht selbst. Das führt dazu, dass wir wie gesehen das Schlüsselwort immer wieder aneinanderhängen müssen. Wir haben also eine periodische Codierung der Klarzeichen vor uns. Die Codierung, also die Auswahl der Tauschalphabete, folgt einem sich ständig wiederholenden Muster. Und genau hier liegt die wichtigste Schwachstelle des Verfahrens, an der die Kryptoanalyse angreift. Das Vigenère-Verfahren hat lange Zeit gut funktioniert und galt als nicht zu brechen, bis 1863 der preußische Infanteriemajor Friedrich Wilhelm Kasiski der Illusion ein Ende bereitete. Anfang des 20. Jahrhunderts legten dann die Herren Friedman und Kullback mit raffinierten statistischen Analyseverfahren noch eins oben drauf. Ein klassischer Vigenère ist heute also alles andere als sicher. Wenden wir uns erst mal Herrn Kasiski zu - dem Ersten, der dem Vigenère-Verfahren die Luft rausließ. Bereits paar Jahre vorher hatte zwar Charles Babbage diese Spur aufgenommen, aber weder publiziert noch bis zu Ende gedacht. Um Kasiskis Idee nachvollziehen zu können, müssen wir erst paar Vorüberlegungen anstellen. Bleiben wir der Einfachheit halber mal bei unserem Schlüsselwort "GARTEN", also bei einer Schlüssellänge von sechs Zeichen. Ab dem siebten Zeichen wiederholen sich dann die verwendeten Tauschalphabete hübsch in ihrer Reihenfolge. Das siebte Klarzeichen wird wie das erste verschlüsselt (mit "G"), das achte genau wie das zweite (mit "A") und so fort. Beim 13. Zeichen wiederholt sich das Drama, bei 19. ebenfalls. Aha, eine Regelmäßigkeit - das ist genau das, was wir brauchen. Das muss sich doch irgendwie nutzen lassen. In diese Kerbe setzen wir beherzt unseren nächsten Hieb. 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 k G A R T E N G A R T E N G A R T E N G A R T p h e u t e i s t e i n s c h o e n e r t a g c N E L M I V Y T V B R F I H F X R R X T R Z ^ ^ ^ ^ Fassen wir mal die jeweils gleich codierten Zeichen zusammen. Dazu denken wir uns den Text zeilenweise in eine Tabelle mit so vielen Spalten geschrieben, wie das Schlüsselwort Buchstaben hat - hier also in eine Tabelle mit sechs Spalten. In dieser Tabelle sind dann alle Zeichen jeder Spalte mit demselben Tauschalphabet verschlüsselt. Jede Spalte hat zwar ein anderes Tauschalphabet, aber innerhalb der Spalte haben alle Buchstaben das gleiche. 1 2 3 4 5 6 G A R T E N ........... N E L M I V Y T V B R F I H F X R R X T R Z In diesem Fall wurde also "NYIX" mit dem G-Alphabet codiert, "ETHT" mit dem A-Alphabet, "LVFR" mit dem R-Alphabet etc. Somit sind die Zeichen jeder dieser Spalten für sich betrachtet nichts anderes als eine monoalphabetische Verschlüsselung - ja mehr noch, es handelt sich bei ihnen jeweils um einen schlichten Caesar. In unserem Beispiel haben wir es also mit sechs verschiedenen Caesar-Verschlüsselungen zu tun. Die können wir mit unserem bereits bekannten statistischen Besteck fix und fachgerecht filetieren. Super, unsere Wunderwaffe hat ihre Kraft zurück. Wir müssen eben statt nur einem in diesem Fall sechs Caesar-Codes brechen. Natürlich ergeben die Zeichen einer Spalte keinen zusammenhängenden Text. Aber das spielt für uns keine Rolle - es geht uns im Moment ja lediglich darum, den Verschiebefaktor der Zeichen dieser Spalte (also letztlich den Schlüsselbuchstaben) herauszufinden. Und das funktioniert auch ohne zusammenhängenden Text. Die Zeichen einer Spalte behandeln wir in diesem Fall nicht als Text, sondern quasi als statistische Stichprobe. Eine Kleinigkeit sei aber nicht verschwiegen: An kurzen Vigenère-Texten kann man sich nach wie vor trefflich die Zähne ausbeißen. So auch bei unserem Beispieltext mit lediglich 22 Zeichen. Nach der Zerlegung in die Caesar-Gruppen bleiben uns vier Vierergruppen und zwei Dreiergruppen. Jede Gruppe für sich ist viel zu klein, als dass wir sie statistisch angreifen könnten. Kein Wunder, die Schlüssellänge sechs beträgt immerhin knapp ein Viertel der Textlänge. Das kann nichts werden. Aber bei einem durchaus realistischen Text von sagen wir mal 120 Zeichen Länge beträgt die Schlüssellänge von sechs dann grade noch ein Zwanzigstel der Textlänge, jede Spalte hat also 20 Zeichen - und damit lässt sich durchaus was anfangen. Wir können dann jeweils den häufigsten Buchstaben jeder Spalte ermitteln und darauf tippen, dass er dem "e" entspricht. Damit können wir die Verschiebung, also das verwendete Tauschalphabet errechnen und damit auch den Schlüsselbuchstaben. Selbst wenn einer oder zwei der so ermittelten Buchstaben falsch sind, weil das häufigste Zeichen einer Spalte eben doch nicht "e" entsprach, haben wir eine Chance, das Schlüsselwort anhand der anderen, richtig ermittelten Schlüsselbuchstaben zu erraten. Oder wir gehen davon aus, dass das häufigste Zeichen statt "e" vielleicht "n" (zweithäufigstes Zeichen der Normalverteilung) entspricht und versuchen es damit. Mit etwas Gefrickel kommt man jedenfalls meist früher oder später ans Ziel. Vielleicht gibt ja auch der mit dem noch nicht perfekten Schlüsselwort entzifferte Text schon irgendwelche Fetzen von Klartext und damit Vermutungen her, wie es richtig heißen muss. Haben wir z.B. statt "GARTEN" als Schlüsselwort "GARTER" ermittelt, wird also jedes sechste Klarzeichen falsch sein (weil wir es mit "R" statt mit "N" entschlüsselt haben), alle anderen stimmen aber: k G A R T E R G A R T E R G A R T E R G A R T c N E L M I V Y T V B R F I H F X R R X T R Z p h e u t e e s t e i n o c h o e n a r t a g * * * Wie in diesem Beispiel zu sehen, ist es nicht schwer, den Klartext zu erraten sowie den falschen Schlüsselbuchstaben zu identifizieren und richtigzustellen. Wir sehen, dass jedes sechste Zeichen im Klartext falsch ist. Der Rest passt. Damit ist klar: Der sechste Buchstabe unseres Schlüsselworts ist falsch, alle anderen sind ok. Als sechstes Klarzeichen erhalten wir "e", es müsste aber "i" lauten. Wir sind also vier Zeichen zu weit vorne im Alphabet gelandet. Der Schlüsselbuchstabe an dieser Stelle lautet "R". Wir müssen vier Stellen im Alphabet zurück, also zum "N". Mithin lautet das korrekte Schlüsselwort "GARTEN" statt "GARTER". Bingo. Ehrlicherweise muss man dazusagen, dass das natürlich Theorie ist. In der Praxis läuft es nicht immer so glatt. Ein Problem ist - wie wir gesehen haben - das Verhältnis zwischen Textlänge und Schlüssellänge. Ist der Text 15- oder 20-mal länger als der Schlüssel, stehen die Chancen gut. Je kürzer der Text bzw. je länger der Schlüssel, desto schlechtere Karten haben wir. Das nächste Problem ist die Textart. Je weniger Zeichen wir zur statistischen Auswertung haben, desto anfälliger wird unsere Methode für Abweichungen des Textes von der Norm. Haben wir z.B. pro Spalte (also pro Caesar) nur 15 Zeichen und der Text ist sehr untypisch - besteht also z.B. nur aus Zahlwörtern - dann wird der jeweils häufigste Buchstabe eben nicht immer dem "e" entsprechen. Gut, so weit zu den Vorüberlegungen. Wir sehen ganz deutlich, dass die Sache mit der Kenntnis der korrekten Schlüssellänge steht und fällt. Nehmen wir eine falsche Schlüssellänge an, dann sind natürlich nicht mehr alle in einer Spalte stehenden Zeichen mit dem gleichen Tauschalphabet codiert und unser Trick funktioniert nicht mehr. Das Problem ist also zunächst, erst mal die LÄNGE des Schlüssels zu finden. Der Schlüssel selbst interessiert uns zunächst noch gar nicht. Die Überlegung von Kasiski war nun, dass nicht nur der Schlüssel sich wiederholt, sondern ja auch der Klartext Wiederholungen aufweist. Viele Wörter kommen sehr häufig vor, z.B. Artikel, Präpositionen oder bestimmte Wortendungen ("-tion", "-ung", "-heit") oder Buchstabengruppen ("ver", "sch", "str"). Manche Wiederholungen ergeben sich auch zufällig - sogar über Wortgrenzen hinweg. Nehmen wir uns mal ein Beispiel vor: Der Klartext sei "Nord drei vier eins E-Koordinate ..." und er soll mit dem Schlüsselwort "GARTEN" verschlüsselt werden. Der Krypttext lautet also "TOIWH EKIMB IEKIE LIXUO IWMAG TV". Jetzt betrachten wir die Sache mal auf der Ebene der Einzelzeichen: k G A R T E N G A R T E N G A R T E N G A R T E N G A R p n o r d d r e i v i e r e i n s e k o o r d i n a t e c T O I W H E K I M B I E K I E L I X U O I W M A G T V ^ ^ ^ * * * * * * ^ ^ ^ Hier ist die Klarzeichenfolge "ord" zweimal auf die Schlüsselzeichenfolge "ART" getroffen, was dann natürlich zur gleichen Kryptzeichenfolge "OIW" geführt hat (^). Genauso traf zweimal "rei" auf "NGA" mit dem Ergebnis von "EKI" (*). Umgekehrt muss natürlich nicht jede Wiederholung im Krypttext auf ein solches Zusammentreffen zurückzuführen sein. So gibt es z.B. im Krypttext zweimal "IE", was aber keine echte Parallelstelle ist, sondern reiner Zufall. Einmal entstanden aus "er" + "EN" und einmal aus "in" + "AR". Solche Zufallstreffer sind bei Bigrammen (also Zweiergruppen) relativ häufig, bei Trigrammen eher selten und bei noch längeren Gruppen extrem selten. Üblicherweise sucht man daher nach wiederholten Trigrammen im Krypttext. Da hat man relativ wenige "falsche" Zufallstreffer und relativ viele "echte Treffer". Je länger die wiederholt vorkommende Zeichengruppe ist, desto sicherer kann man sein, keinen Zufallstreffer vor sich zu haben, aber desto seltener sind sie natürlich auch. Die echten Treffer beruhen immer auf einem bestimmten Teil des Schlüsselworts. Das Trigramm "OIW" beispielsweise auf dem Schlüsselteil "ART". Der Abstand zwischen den einzelnen Vorkommen von "ART" beträgt aber immer ein Vielfaches der Schlüssellänge, den zwischen den beiden "ART" steht eben ein- oder zwei- oder dreimal oder wie oft auch immer der Rest des Schlüsselworts. Denn Schlüsselwortsequenzen wiederholen sich immer nach sechs Zeichen, der Länge unseres Schlüsselworts. Zählt es nach, falls ihr es nicht glaubt. Der Abstand zwischen den Anfängen von zwei "GAR" oder "ART" oder "RTE" oder "TEN" oder "ENG" oder "NGA" beträgt immer genau sechs Zeichen. Eigentlich auch logisch. Daher suchen wir beim Kasiski-Test nach Wiederholungen im Krypttext (man nennt diese Wiederholungen "Parallelstellen") und zählt den Abstand zwischen ihnen aus. Bei uns also: OIW: Abstand 18 EKI: Abstand 6 Mehr als diese beiden Trigramme haben wir nicht, weil der Text ja so kurz ist. Das Prinzip lässt sich dennoch verdeutlichen. Man zerlegt nun die Abstände in ihre Primfaktoren: OIW: 18 = 2 x 3 x 3 EKI: 6 = 2 x 3 Ok, in diesem Fall ist das natürlich recht übersichtlich. Man nimmt nun die Primfaktoren, die in allen oder zumindest in den meisten Abständen vorkommen. Das sind hier 2 und 3. Diese beiden Faktoren multipliziert man einfach, das ist unsere Schlüssellänge. Und tatsächlich 2 x 3 = 6. Bingo. Bei längeren Texten ist das meist etwas deutlicher als bei unserem Minitext. Bei den heutigen Übungscaches ist ein Beispiel eines Kasiski-Tests bei einem längeren Text dabei. In der Praxis hat man natürlich immer auch mal Zufallstreffer dabei, die nichts mit der Schlüssellänge zu tun haben. Daher kommen die richtigen Primfaktoren nicht bei allen gefundenen Trigrammen vor. Es ist etwas Gefühlssache, aber man nimmt in der Regel die Faktoren, die am häufigsten in den Fundstellen vorkommen bzw. die den meisten (im Idealfall allen) gemeinsam sind. Manchmal sind auch zwei oder drei mögliche Schlüssellängen plausibel. Dann muss man eben für jede mögliche Länge das Zerlegen in Spalten und das Caesar-Programm durchziehen. Es gibt auch recht raffinierte statistische Tests, die auf einem etwas anderen Prinzip beruhen und die man zur Verfeinerung und Bestätigung einsetzt, aber wir lassen es hier mal beim Kasiski bewenden. Es ging ja nur darum zu zeigen, dass auch scheinbar relativ sichere Verschlüsselungsverfahren überraschende Schwächen aufweisen können. Daher hab ich zum Kasiski-Test und seinem Umfeld auch kein Tool extrahiert. Um damit sinnvoll arbeiten zu können, müssten wir einiges tiefer einsteigen. Verwendet für Vigenère am besten das CrypTool: "Analyse/ Symmetrische Verschlüsselung (klassisch)/ Ciphertext-Only/ Vigenère" (die Analyse nach Schrödel kann man meist vergessen). Das CrypTool arbeitet beim Vigenère mit einer schwellenwertgewichteten Autokorrelation. Das funktioniert bei einfacheren Vigenères mit nicht zu kurzem Text recht ordentlich. Bei kürzeren Texten oder trickreichen Schlüsseln wird es allerdings unzuverlässig bis hoffnungslos. Probiert es einfach mal mit diesen einfachen Vigenères: # Station X (www.coord.info/GC5FF4): Einfacher Vigenère mit sehr langem Text, also kein Problem. Besonders nett, weil die Dose bei einer "kryptologischen Wallfahrtsstätte" liegt. Nach meinem Geschmack und historisch korrekter hätte hier eigentlich ein mit der Enigma verschlüsseltes Rätsel hingehört, aber das hätten dann wohl nur echte Krypto-Freaks knacken können. So ist es eben ein Vigenère geworden. Das CrypTool bekommt das Schlüsselwort nicht perfekt raus, aber gut genug, um es vollends erraten oder anhand des Klartextes rekonstruieren zu können (Schlüsselwort ist der Name eines berühmten Kryptologen, der hier in Bletchley Park tätig war). # Station Xtra (www.coord.info/GCJNON). Noch einer bei Bletchley Park. Ein weiterer einfacher Vigenère. An diesem verschluckt sich zwar das CrypTool, aber ich häng euch mal den Kasiski-Test des Krypttextes an (mit Zettel und Bleistift ist das schon ein etwas mühseliges Unterfangen). "GUV" und "VVI" sind Zufallstreffer. Sucht aus den restlichen Treffern denjenigen Primfaktor raus, der in allen Fundstellen vorkommt - der entspricht der Schlüssellänge. Wenn ihr dem CrypTool die korrekte Schlüssellänge verratet, sollte der Rest dann kein Problem mehr sein. Und schon ist ein D4,5 im Handumdrehen gelöst - für uns ein schlapper D2 ;-) # kryptos (www.coord.info/GC33F71): Nettes kleines Rätsel auf Vigenère-Basis mit paar kleinen Tricks, die aber keine wesentlichen Probleme bereiten. Diesen mit fünf D-Sternen zu dekorieren ist zumindest aus unserer inzwischen kryptologisch versierten Sicht doch reichlich übertrieben. Drei hätten dicke gereicht ;-) # Napoleons langer Arm (www.coord.info/GC1MPAG): An diesem aus der sächsischen Serie könnt ihr euch auch mal versuchen, wobei der Owner noch einen Trick eingebaut hat, den er aber wie ich finde nur schlecht nachvollziehbar beschrieben hat (zumindest mir hat das nicht spontan eingeleuchtet). # DELTA LIMA ZERO GOLF YANKEE MIKE (www.coord.info/GC1MK6Y): Noch einer aus Sachsen, den der Owner mit nur D2 einstuft. Natürlich hab ich den auch geknackt, aber doch mit etwas Mühe. Vermutlich hab ich nicht kapiert, wie er sich den Lösungsweg vorstellt und hab evtl. paar unnötige Umwege beschritten.
	Nachtrag zu Lektion 6 aufgrund einiger Nachfragen Vom CrypTool gibt es eine Online- und eine Offline-Version. Empfehlenswert ist - wie in KrySem03 angemerkt - das Programm runterzuladen und zu installieren. Ist einfach bequemer und auch von der Datensicherheit her besser, als immer alles online zu machen. Also das Programm von http://www.cryptool.org/ct1download/SetupCrypTool_1_4_30_de.exe runterziehen und installieren. Wenn man das Programm dann laufen lässt, kann man entweder einen Krypttext reinladen oder - einfacher - den Text auf der Startseite einfach löschen und stattdessen den Krypttext da reinkopieren. Es ist übrigens empfehlenswert, den Text vor dem Reinkopieren etwas vorzubereiten (z.B. in einer Textverarbeitung). Der ganze Text sollte ein einziger Absatz sein. Also alle Buchstaben zusammenziehen ohne Absätze dazwischen. Außerdem ist es meist hilfreich, alle Satz- und Leerzeichen zu entfernen, sodas ein reiner Buchstabenstrang übrigbleibt. Den dann ins CrypTool reinkopieren. Dann zu "Analyse/ Symmetrische Verschlüsselung (klassisch)/ Ciphertext-only/ Vigenère". CrypTool schlägt nun eine Schlüssellänge vor. Die kann man entweder akzeptieren ("Weiter") oder korrigieren. Als nächstes schlägt CrypTool ein Schlüsselwort vor. Wiederum entweder akzeptieren ("Weiter") oder korrigieren. Dann wird der Kryptext mit diesem Schlüsselwort entschlüsselt. Und jetzt kann man erkennen, ob das so hinkommt. Wenn perfekter Klartext entsteht ist alles gut. Wenn der Klartext Fehler aufweist, dann stimmt wohl was mit dem Schlüsselwort nicht. Dann sollte man versuchen rauszufinden, welche Schlüsselbuchstaben falsch sind und wie sie wohl richtig lauten müssten (s. KrySem06). Wenn überhaupt nichts Brauchbares erscheint, war entweder das Schlüsselwort völlig daneben oder bereits die Schlüssellänge falsch. Randbemerkung: CrypTool gibt unüblicherweise Klartext in Großbuchstaben aus, davon darf man sich nicht verwirren lassen. Bei dem genannten Beispielcache "Station X" ermittelt CrypTool die Schlüssellänge korrekt mit 10. Als Schlüsselwort schlägt es "NLANTJRING" vor, was wenig vertrauenserweckend ist. Wobei z.B. der Schluss ("...RING") ja nicht ganz schlecht aussieht. Die Schlüssellänge könnte also gestimmt haben. Also einfach mal entschlüsseln lassen. Im Klartext erkennt man, wo die Probleme liegen: GHECANHEISAOWHIODENOHTSIDPOUROSFICEHINDOJSTOP... Der Anfang wird wohl heißen müssen: THE CACHE IS ... Also stimmt das erste Klarzeichen nicht ("G" statt "T") und auch das sechste ist falsch ("N" statt "C"). In der Folge sind natürlich dann auch der 11., der 16. der 21. der 26. etc. Klarbuchstabe falsch, weil die ja jeweils auf den 1. bzw. 6. Schlüsselbuchstaben treffen (falsche Buchstaben mit * markiert, an nichtproportionale Schrift denken): 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 N L A N T J R I N G N L A N T J R I N G N L A N T J R I N G G H E C A N H E I S A O W H I O D E N O H T S I D P O U R O * * * * * * Nun kann man rumprobieren und einfach mal an den falschen Schlüsselbuchstaben rumspielen. Oder man kann rechnen. Die Rechnung geht wie folgt: Erst mal muss man beachten, dass beim Vigenère das Klarzeichen im Alphabet nach vorne rückt, wenn man mit dem Schlüsselbuchstaben im Alphabet nach hinten rückt. Klarzeichen und Schlüsselzeichen bewegen sich also entgegengesetzt. Beispiel: Entschlüsseln wir das Kryptzeichen "F" mit dem Schlüsselzeichen "D", erhalten wir "c". Rücken wir mit dem Schlüsselzeichen im Alphabet um ein Zeichen nach hinten, also zu "E", landen wir beim Entschlüsseln von "F" bei "b". Schlüsselzeichen und Klarzeichen bewegen sich also entgegengesetzt. Wollen wir mit dem Klarzeichen nach vorne, muss das Schlüsselzeichen nach hinten rücken und umgekehrt. Das erste Klarzeichen in unserer Probeentschlüsselung ist "g", müsste aber "t" sein. Wir sind 13 Zeichen im Alphabet zu weit vorne, müssen damit also im Alphabet um 13 Stellen nach hinten rücken. Das heißt, wir müssen mit dem Schlüsselbuchstaben in die andere Richtung, sprich im Alphabet nach vorne. Der erste Schlüsselbuchstabe ist "N". Verlagern wir den mal 13 Buchstaben weiter nach vorne. Damit landen wir beim "A". Das Gleiche beim sechsten Klarzeichen. Wir haben ein "n", brauchen aber ein "c". Wir sind mit dem Klarzeichen elf Stellen zu weit hinten im Alphabet, müssen also weiter nach vorne (und damit mit dem Schlüsselbuchstaben nach hinten). Der sechste Schlüsselbuchstabe ist "J". Zählen wir elf Stellen nach hinten im Alphabet, landen wir bei "U". Unser Schlüsselwort muss also "ALANTURING" lauten. Also das CrypTool nochmal mit dem Krypttext starten. Schlüssellänge 10 bestätigen. Dann das falsch ermittelte Schlüsselwort korrigieren und entschlüsseln lassen. Schon haben wir den Klartext. Das Rumfummeln am Schlüssel kann man auch in unserem Vigenère-Tool machen. Da geht es noch etwas besser, weil man bei Veränderungen des Schlüsselworts gleich das Ergebnis sieht und nicht jedesmal vor vorne beginnen muss. Allerdings verhaspelt sich das CrypTool recht oft bei der Bestimmung der Schlüssellänge. Daher hab ich jetzt doch noch ein Kasiski-Tool gebastelt. Bei unserem Beispiel "Station X" ist die bei den meisten Fundstellen vertretene Primfaktorenkombination 2 x 5. Die ergibt die Schlüssellänge 10.
	****************** 7 ****************** Noch ein kurzer Nachtrag zum letzten Mal. Habt Ihr die angegebenen Beispiele ausprobiert? Ist es Euch gelungen, der "kryptos" zu knacken? Falls nicht, dann liegt heute der Kasiski-Test dafür bei. Damit sollte es dann keine Hürden mehr geben ("WSD", "JGR" und "CWG" sind Zufallstreffer, aber das erkennt Ihr ja inzwischen selbst). Nachdem wir jetzt die mono- und die polyalphabetische Substitution in ihren Grundlagen durchgesprochen haben, kommen wir dieses Mal noch zu vier etwas spezielleren Substitutionsformen - drei polyalphabetischen und einer monoalphabetischen. Diese sind zwar beim Cachen nur selten anzutreffen, aber man sollte dennoch zumindest mal davon gehört haben. Das gehört einfach zum kleinen Einmaleins der Kryptologie. Stellen wir erst mal paar Überlegungen zur Sicherheit der Verschlüsselungsmethoden an, die wir bisher besprochen haben. Beim Caesar gibt es ja nur 25 Schlüssel. Da ist der schnellste Weg zum Klartext ein Brute-force-Angriff, also einfach das Durchprobieren aller erdenklichen Möglichkeiten - das ist sogar noch schneller als die statistische Methode. Von Sicherheit kann hierbei natürlich keine Rede sein. Bei der allgemeinen monoalphabetischen Substitution beträgt der Schlüsselraum 26! (Fakultät 26, also 2 x 3 x 4 x 5 x 6 ... x 25 x 26), das ist eine gewaltige Zahl, nämlich 400 Quadrillionen - eine 4 mit 26 Nullen. Ein Brute-force-Angriff wäre in diesem Fall selbst mit einem ganzen Rechenzentrum völlig aussichtslos. Doch hier gibt es ja eine nette Abkürzung: die statistische Methode. Beim Vigenère hängt die Größe des Schlüsselraums von der Schlüssellänge ab und beträgt 26^d (26 hoch Schlüssellänge). Bei einer Schlüssellänge von sechs sind das also immerhin rund 309 Millionen Möglichkeiten. Wenn man nun alle Möglichkeiten mit einer Schlüssellänge von sagen wir mal vier bis sieben durchprobieren will, sind das gut 83 Milliarden Möglichkeiten. Moderne Großrechner schaffen gut eine Million Versuche pro Sekunde inklusive der Auswertung, ob sinnvoller Text dabei rauskam. In knapp drei Stunden müsste man also ein Ergebnis haben. Will man aber z.B. alle Möglichkeiten mit einer Schlüssellänge von vier bis fünfzehn durchnudeln, kommt man auf rund 1,7 Trilliarden mögliche Schlüssel. Bei einer Million Versuchen pro Sekunde wären also gut 55 Millionen Jahre notwendig, um alles durchzuprobieren. Klarer Fall: brute-force-mäßig keine Chance. Doch auch der Vigenère ist wie gesehen statistisch angreifbar, sofern die Textlänge nicht zu kurz ist. Was also kann man tun, um die Sicherheit zu erhöhen? Natürlich kann man wilde Systeme ersinnen, aber das Verfahren muss ja neben der Sicherheit auch einige weitere Bedingungen erfüllen. Es muss relativ einfach, schnell und unauffällig zu handhaben sein (wohlgemerkt möglichst auch ohne Computer). Es muss mit einem Schlüssel arbeiten, den man sicher und problemlos übermitteln kann und der möglichst auch gut zu merken sein sollte. Das Verfahren sollte auch unter widrigen Umständen gut funktionieren, z.B. auf hoher See, an der Front oder bei Expeditionen. Ohne elektronische Unterstützung ist das keine leichte Aufgabe und die Kryptographen haben sich damit zu allen Zeiten redlich abgemüht.
	One-Time-Pad und Vigenère-Autokey Dieses Problem erkannte auch bereits Vigenère selbst. Er hatte schon in "Traicté des Chiffres" (1586) ein verbessertes Verfahren beschrieben, dass sich aber aus unerfindlichen Gründen nie recht durchsetzen konnte. Die zugrundeliegende Überlegung ist ebenso einfach wie genial. Je länger das Schlüsselwort, desto sicherer das Verfahren. Ideal wäre es, für jedes Klarzeichen ein anderes Schlüsselzeichen zu verwenden, am besten nach einer rein zufälligen Abfolge. Es gibt dabei nur ein Problem: Wenn wir so vorgehen, dann wird der Schlüssel ebenso lang wie der Klartext. Damit haben wir ein ernsthaftes Problem, denn wir müssen dem Empfänger den Schlüssel ja auf einem absolut sicheren Kanal übermitteln. Wenn der Schlüssel aber so lang ist wie die Botschaft selbst und einen sicheren Kanal erfordert, dann können wir uns das Verschlüsseln auch sparen und gleich die Botschaft selbst übermitteln. Ist also für den regulären Gebrauch unpraktikabel, denn einen so sicheren Kanal gibt es im Regelfall einfach nicht. Trotzdem gibt es diese Methode im praktischen Einsatz. Sie heißt "One-Time-Pad" und ist tatsächlich nicht zu brechen - das lässt sich mathematisch beweisen. Voraussetzung ist aber eben, dass der Schlüssel wirklich so lang wie der Klartext ist, dass es sich bei ihm um eine rein zufällige Zeichenfolge handelt und dass jeder Schlüssel nur ein einziges Mal verwendet wird (daher auch der Name). Dann - und nur dann - ist das Ganze definitiv nicht zu knacken. Das One-Time-Pad ist sehr aufwendig, wurde und wird aber dennoch zum Nachrichtenaustausch auf höchster Ebene genutzt. Hochrangige diplomatische Kanäle, besonders heikle Agentennetze und auch der berühmte heiße Draht zwischen Washington und Moskau verwenden es. Das One-Time-Pad ist also ein wirklich absolut sicheres Verfahren, sofern es korrekt eingesetzt wird. Das Hauptproblem ist und bleibt aber die sichere Übergabe und Verwahrung des ausgesprochen unhandlichen Schlüssels. Merken kann man sich einen solchen Schlüssel natürlich nicht. Also braucht man verräterische Unterlagen. Und in der Tat sind schon zahlreiche Agenten dadurch aufgeflogen, dass man bei ihnen solche Schlüssellisten gefunden hat. Wie könnte man dieses Problem umgehen? Vigenères wirklich bestechende Idee ist eigentlich recht simpel, man muss nur drauf kommen: Das Problem ist ja der endlos lange und damit unmerkbare Schlüssel. Vigenère versuchte sich der Sache zu nähern, indem er zwar keine Zufallsfolge, aber doch ein sehr langes Schlüsselwort erdachte, das man sich natürlich nicht merken kann, aber auch gar nicht muss. Und das geht so: Man hat ein Schlüsselwort von sagen wir mal der Länge sechs - etwa unser GARTEN. Mit dem wird ganz normal nach Vigenère verschlüsselt. Bis zum sechsten Buchstaben. Für den siebten Buchstaben würde man beim klassischen Verfahren wieder mit dem ersten Schlüsselbuchstaben anfangen. Bei Vigenères Trick geht es aber einfach mit dem Klartext weiter. Der Klartext wird quasi mit sich selbst als Schlüsselwort verschlüsselt, nur dass Klartext und Schlüssel um die sechs Stellen des Schlüsselworts gegeneinander verschoben sind. Ganz schön pfiffig, was? Dieses Verfahren ist heute bekannt unter der Bezeichnung "Vigenère-Autokey" oder auch einfach "Autokey". Das Verfahren ist etwas umständlicher als der klassische Viegenère, aber wirklich enorm viel sicherer. Allerdings erreicht es bei Weitem nicht die Sicherheit des echten "One-Time-Pad", denn beim Schlüssel handelt es sich ja eben gerade nicht um eine Zufallsfolge, sondern um sinnvollen Text, der damit durch die in ihm enthaltene Information auch ein Muster aufgeprägt bekommt. Allerdings ist das Brechen eines Autokey auch mit Computerunterstützung wahrlich kein Spaziergang.

6. Dechiffrierprojekt Vigenère-Code  Informatikkurs 2006/07

	Auch hier verdanken wir die Masse der Zuarbeit eine Fortbildung für Informatiklehrer im Jahre 2005 in Dresden. Aber auch das JEFFERSON-Rad oder andere Verschiebetabellen sind gut geeignet, um Nachrichten nach Vigenère-Code zu chiffrieren. Ganz raffiniert lässt sich natürlich auch hier wieder das Krypto-Tool einsetzen.

7. Web-Links zum Thema Vigenère und weiteren Polyalphabetischen Chiffren

8. Aufgaben zum Thema Vigenère

	Der Vigenère- Ciffre ist eine polyalphabetischer Substiutionscode, das heißt, das ein und derselbe Buchstabe auf mehrere verschiedene Möglichkeiten hin verschlüsselt werden kann. Das macht diesen Chiffre auch heute noch und besonders bei kurzen Texten sehr schwer angreifbar. Aber für die ersten Aufgaben nutzen wir ja die Kenntnis der Schlüssel ;-)

9. Verwandte Themen

	Da monoalphebetische Chiffren die Mutter alles Verschlüsselungstechniken waren, sind sie zu faktisch jedem Bereich der Kryptologie verwandt. Und da via Computer die Krptologie auch etwas mit Binärmustern zu tun hat, gibt es auch ein reizvolles Verhältnis zur Logik.
	Schieberegister Zufallsmuster Bletchley-Park
	Vigenère-Verschlüsselung CÄSAR-Chiffre Kryptoanalyse - die Code-Knacker

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost am 5. Juli 2012 um 22.19 Uhr