Hochschule Wismar
Transcrição
Hochschule Wismar
Hochschule Wismar Fachbereich Wirtschaft Projektarbeit Kryptographie 2004 Klassische Chiffren eingereicht von: Marcel Brätz geboren am 09. Mai 1977 in Brandenburg(Havel) Studiengang Wirtschaftsinformatik Matrikel Nr. : 102433 Betreuer: Prof. Dr. J. Cleve Wismar, den 15. Juni 2004 Inhaltsverzeichnis I Klassifikation der Klassischen Chiffren 3 1 Monoalphabetische Chiffren 1.1 Allgemeines . . . . . . . . . . . . . . . 1.2 Additive Chiffren . . . . . . . . . . . . 1.3 Multiplikative Chiffren . . . . . . . . . 1.4 Transpositionschiffren / Tauschchiffren 1.5 Substitutionschiffren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 4 5 6 7 2 Polyalphabetische Chiffren 2.1 Allgemeines . . . . . . . . 2.2 Homophone Chiffrierung . 2.3 Le Chiffre indechiffrable . 2.4 Play-Fair . . . . . . . . . 2.5 One-Time-Pad . . . . . . 2.6 Enigma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 9 9 10 13 13 15 II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kryptoanalyse 17 3 Kryptoanalyse 3.1 Kryptoanalyse monoalphabetischer Chiffren 3.2 Kryptoanalyse polyalphabetischer Chiffren . 3.2.1 Allgemeines . . . . . . . . . . . . . . 3.2.2 Das Wichtigste ist die Mustersuche... 3.2.3 ...und wieder monoalphabetisch! . . 3.2.4 Der Weisheit letzter Schluß... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 18 19 19 19 20 21 4 Mathematische Grundlagen 4.1 Häufigkeitstabellen . . . . . . . . . . . . 4.2 Verfahren zur Analyse . . . . . . . . . . 4.2.1 Häufigkeit . . . . . . . . . . . . . 4.2.2 Kasiski-Test . . . . . . . . . . . . 4.2.3 Koinzidenzindex / Friedman-Test 4.2.4 Entropie . . . . . . . . . . . . . . 4.2.5 Autokorrelation / Korrelation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 22 23 23 23 24 26 26 III . . . . . . . . . . . . . . Anhang 28 5 Kurze Geschichte der Kryptographie 29 6 Begriffe, Definitionen und Abkürzungen 32 7 Sourcecode 33 1 Einleitung/Vorwort Das Verschlüsseln von Nachrichten aller Art war schon immer eine Notwendigkeit, deshalb ist die Geschichte der klassischen Chiffren fast ebenso lang, wie die Geschichte der Schriftsprache. Erst mit der verstärktem Einsatz moderner Computer, also um 1950, endete die Zeit der klassischen Chiffren, da der Einsatz mächtiger Rechenmaschinen bis dahin ¨unknackbare¨ Verschlüsselungen plötzlich angreifbar machte. Die zum Einsatz kommenden Computer machten den notwendigen rechentechnischen Aufwand für statistische Berechnungen beherrschbar. Ich werde im Zuge dieser Ausarbeitung verschiedentlich darauf hinweisen, wo dies Anwendung fand und werde am Ende auch ein praktisches Beispiel geben, wieso die lange Zeit als unknackbar angesehene Vigenère-Chiffre plötzlich unsicher war. In dieser Ausarbeitung kann ich natürlich nicht alle Chiffren, die in den vielen Jahrhunderten erfunden und eingesetzt worden sind, näher beleuchten, zumal auch nicht alle Chiffren geknackt worden sind.[4, 7] Ich werde mich also an dieser Stelle auf grundsätzliche und klassische Chiffren beschränken. Viele an dieser Stelle ungenannt bleibende Chiffren, arbeiten grundsätzlich nach ähnlichen Algorithmen und sollen daher nicht näher behandelt werden. Nun stellt sich die Frage: Brauchen Privatpersonen überhaupt so etwas wie Kryptographie? Es gibt Dinge, die jedem wichtig sind, von denen man nicht will, daß jedermann diese liest. Also lautet die Antwort: Ja! Angefangen vom einfachen Tagebuch bis zu streng geheimen Wirtschaftsdaten, brauchen wir Kryptographie um für deren Sicherheit zu sorgen. Früher war Verschlüsselung größtenteils dem Militär und der Diplomatie vorbehalten. Als das Thema Kryptographie in der Öffentlichkeit populärer wurde, wurde sie in einigen Ländern sogar teilweise verboten. In den USA, dem Land mit den höchsten Ausgaben für derartige Technologien, beispielsweise werden Verschlüsselungstechnologien, mit der selben Sicherheitsstufe eingestuft, wie Waffentechnologieen. Die Wahl des jeweilig verwendeten Verfahren hängt vom notwendigen Schutz und von der Person / Organisation ab, vor der man Daten schützen will. Allerdings gibt es keinen Grund, schwächere Kryptoalgorithmen zu verwenden, wenn man nur einen einfachen Gegner hat. Im folgenden werde ich auf die grundlegenden Eigenschaften der einzelnen Verfahren eingehen, diese klassifizieren und anhand ausgewählter Vertreter erläutern und jeweils mit einem Beispiel dokumentieren. Ich füge außerdem Programmierbeispiele bei. Dabei kommt die Programmiersprache PHP zum Einsatz, um Algorithmen zu implementieren und deren Funktionsweise zu erläutern. Desweiteren habe ich eine Webseite[5] zusammengestellt, auf der es möglich ist, interaktiv, die hier behandelten Verschlüsselungstechnologien auszuprobieren. Nachdem das Implementieren der einzelnen Chiffren beleuchtet wird, stellt sich die Frage nach der Dekodierung der Chiffren, wenn der Schlüssel unbekannt ist. Das sogenannte ¨Brechen¨ von Verschlüsselungen, die Kryptoanalyse, stellt die einzelnen Verschlüsselungen auf eine harte Probe. Ich werde in einem gesonderten Kapitel darauf eingehen und einige der Techniken, die dabei zur Anwendung kommen, beleuchten. Ich erhebe keinen Anspruch auf Vollständigkeit. Ich möchte lediglich Ansätze aufzeigen. 2 Teil I Klassifikation der Klassischen Chiffren 3 Kapitel 1 Monoalphabetische Chiffren 1.1 Allgemeines In diesem Kapitel geht es um sehr einfache kryptographische Verfahren. Diese Verfahren sind nicht sicher, bilden aber ein wichtiges Fundament der modernen Kryptographie. Viele der Techniken, die schon bei den klassischen Chiffren zum Einsatz kamen, finden weiter Verwendung in modernen Verfahren. Man unterscheidet bei den bei den klassischen Chiffren: • monoalphabetische Chiffren und • polyalphabetische Chiffren Unter monoalphabetischen Chiffrierungen versteht man Verfahren, bei denen jeder Buchstabe des Alphabets zu dem selben Geheimtext-Buchstaben verschlüsselt wird. Man kann z.B. jedem Buchstaben ein bestimmtes Zeichen (oder einen anderen Buchstaben) zuordnen. Beispiele: Klartext: 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 Geheimtext: Q A Y W S X E D C R F V T G B Z H N U J M I K O L P Klartext: 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 Geheimtext: ! " § $ % & / ( ) = ? + * # - { 3 2 7 5 > | ] [ @ 5 Für diese Art der Chiffrierung gibt es tatsächlich 26 · 25 · 24 · ... 3 · 2 · 1 = 26! = ˜ 4 · 1026 Möglichkeiten! Warum diese Verfahren leider trotzdem (meistens) leicht zu knacken sind, wird im Kapitel Kryptoanalyse gezeigt. Wenn ein Buchstabe oder Zeichen durch einen anderen Buchstaben bzw. Zeichen ersetzt wird, nennt man das auch Substitution. Wie Transpositions-Algorithmen sind Substitutions-Algorithmen ein wichtiger Baustein für moderne Algorithmen. 1.2 Additive Chiffren Die einfachsten Verfahren sind Additive Chiffren, Verschiebechiffren. Diese Art der Chiffrierung soll schon Julius Caesar benutzt haben. Man verschlüsselt dabei einen beliebigen Text indem man das Klartextalphabet unter das Geheimtextalphabet schreibt, aber um k Stellen nach links oder 26 - k Stellen nach rechts verschoben. 1. Beispiel (Caesar-Chiffre): Klartext: 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 Geheimtext: 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 4 Hier wurde das Alphabet um 3 Stellen nach links verschoben. Man chiffriert nun eine Nachricht, indem man den Klartextbuchstaben durch den darunterstehenden Geheimtextbuchstaben ersetzt. Aus dem Wort klartext würde in unserem Fall NODUWHAW. Für k gibt es genau 26 Möglichkeiten. k wäre hier der Schlüssel. Man kann dieses äußerst simple Verfahren knacken, indem man einfach alle Möglichkeiten ausprobiert! Es gibt nur 26 verschiedene Schlüssel. 2. Beispiel (ROT13): Klartext: 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 Geheimtext: 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 ROT13 ist eine in Foren und Bulletin-Boards recht beliebte Chiffre. Sie hat den Reiz, dann man mit nochmaliger Verschlüsselung erneut den Klartext erhält. Solche Chiffrierungen werden also als additive Chiffrierungen bezeichnet, da wir eigentlich den Wert k zum Klartextbuchstaben addieren, um den Geheimtextbuchstaben zu erhalten. Dazu numerieren wir das Alphabet von 1 bis 25 durch, wobei wir z mit 0 belegen: a = 1 ... y = 25, z = 0 Um zu verschlüsseln, addieren wir k zu einem Buchstaben: a + 3 = D entspricht 1 + 3 = 4 Wenn die Summe größer als 26 ist, muss man diese Summe durch 26 teilen und den entstandenen Divisionsrest in einen Buchstaben zurückübersetzen. Dies nennt man auch Modulo-Operation, bzw. Modulo-Division. Beispiele: (y + 4) mod 26 = (25 + 4) mod 26 = 3 = C Zur Dechiffrierung subtrahiert man k vom Geheimtextbuchstaben. Dann addiert man 26 hinzu und führt eine Modulo-Operation durch: k = 3, Geheimtextbuchstabe: B (B - 3 + 26) mod 26 = (2 - 3 + 26) mod 26 = 25 = y k = 19, Geheimtextbuchstabe: X (X - 19 + 26) mod 26 = (24 - 19 + 26) mod 26 = 5 = e 1.3 Multiplikative Chiffren Bei dieser Chiffrierung verwendet man statt Addition Multiplikation modulo 26 (siehe vorheriges Kapitel). Wir multiplizieren jeden Klartextbuchstaben mit dem Schlüssel k. Ein Beispiel mit k = 2: Klartext: 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 Geheimtext: B D F H J L N P R T V X Z B D F H J L N P R T V X Z Auffallend ist hier, dass jeweils zwei unterschiedliche Buchstaben dasselbe Produkt ergeben! Daher können wir diese Substitution nicht als Chiffre verwenden. Damit die Chiffre bei der Dekodierung wieder eindeutige Resultate liefert darf es nicht zu Überlappungen bzw. Uneindeutigkeiten in der Chiffrierung kommen. Der Klartext muss also mit Hilfe des Schlüssels eindeutig aus dem Geheimtext rekonstruierbar sein! Also gilt: es kommen nur Alphabete in Frage, deren Elemente nur einmal vorkommen. Es kommen also nur Zahlen in Frage die mit 26 keine gemeinsamen Teiler haben. Das sind 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 und 25 5 12 Stück. Höhere Zahlen kommen nicht in Frage, weil die Modulo-Division wieder kleinere Zahlen liefert, welche den selben kriterien unterworfen werden. Nehmen wir nun mal einen Kandidaten aus dier zulässigen Liste: k = 3: Klartext: 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 Geheimtext: C F I L O R U X A D G J M P S V Y B E H K N Q T W Z Diese Chiffrierung funktioniert! Leider ist die Schlüsselzahl noch geringer als bei der Verschiebechiffre. 1.4 Transpositionschiffren / Tauschchiffren Bei einem Transpositions-Algorithmus bleiben die Buchstaben was sie sind, aber nicht wo sie sind. Ein Beispiel für solch einen Algorithmus ist die Skytale von Sparta, die vor ungefähr 500 v. Chr. benutzt worden sein soll. Der Sender wickelte ein schmales Band aus Pergament spiralförmig um die Skytale (ein Zylinder mit einem bestimmten Radius, der auch gleichzeitig der Schlüssel ist) und schrieb dann der Länge nach seine Nachricht auf das Band. Diese Nachricht wurde dann abgewickelt und an den Empfänger geschickt. Hatte dieser eine Skytale mit demselben Radius, konnte er die Nachricht lesen.[6] Ein Beispiel: H A L L O L E U T E W I E G E H T E S E U C H Wir verschlüsseln nun diesen Text mit einer Skytale des Umfangs U = 5, indem wir den Text in 5 Spalten aufteilen: H L W H U A E I T C L U E E H L T G S O E E E Das Ergebnis ergibt sich, indem man jede Spalte dieses Textes von oben nach unten liest und alles hintereinander aufschreibt: H L W H U A E I T C L U E E H L T G S O E E E Diese Art der Transposition wird auch Spaltentransposition genannt. Es gibt auch komplizierte Transpositionschiffrierungen, die jedoch fast ausnahmslos von Computern geknackt werden können. Die deutsche ADFGVX-Chiffrierung[6], die im ersten Weltkrieg verwendet wurde, stellt solch eine Chiffrierung dar. Für damalige Verhältnisse war dieser Algorithmus sehr komplex; er wurde jedoch von dem französischen Kryptoanalytiker Georges Painvin innerhalb weniger Wochen geknackt. Nach der Einführung durch das deutsche Militär im März 1918 war sie bereits Anfag Juni des selben Jahres nicht mehr sicher. Diese Chiffre war eine der berühmteren Transpositionschiffren, weil sie trotz ihrer Stärke sehr schnell geknackt wurde. Zur Funktionsweise soll folgendes Beispiel dienen[6]: Man ordnete die Buchstaben A-Z und die Ziffern 0-9 in einer 6x6 Matrix an wie folgt an. A D F G V X A 8 l 7 j x 9 D p t k u s e F 3 4 b 6 v y 6 G d o c w i 0 V 1 a 5 g r f X n h z m 2 q Dies ist der erste Schlüssel. Die Anordnung der Zeichen ist einem Codebuch entnommen und nicht willkührlich. Damit wurde die Nachricht als erstes verschlüsselt. In der Folge ergab sich eine Reihe von Bigrammen aus den Buchstaben A, D, F, G, V und X. Die Wahl der Buchstaben folgete aus der Unterschiedlichkeit der Darstellung im Morse-Code[5], um Übermittlungsfehler zu vermeiden. Mitteilung: a n g r i f f u m 1 0 u h r Geheimtext: DV AX GV VV VG XV XV GD GX AV XG GD DX VV In der 2. Stufe der Verschlüsselung werden alle Buchstaben des Geheimtextes unter einem Schlüsselwort angeordnet, welches dann alphabetisch sortiert wird. Dies vertauscht die darunter angeordneten Buchstaben und fragmentiert die Bigramme. Im folgenden wird da Schlüsselwort MARK verwendet: M D G V X G X D A V V G V X G X R A V X G A G V K X V V D V D V A V V G V X G X K X V V D V D V M D G V X G X D R A V X G A G V Nach dem Tauschen ergibt sich: Im Ergebnis steht nun folgender Text: VX DA VV GV GV VX VD XG XV GA GD XG XV DV Die Sicherheit dieses Algorithmus ist recht hoch. Dennoch würde ein mit ensprechenden Regeln programmierter Computer nur wenige Sekunden brauchen, um diesen Algorithmus zu brechen. Transposition ist eine wichtige Technik der Kryptographie und wird auch bei modernen Verfahren eingesetzt. 1.5 Substitutionschiffren Neben den bisher genannten monoalphabetischen Chiffren möchte ich auch die Substitutionschiffren einreihen, auch wenn diese Zuordnung nicht immer ganz richtig ist. Grundsätzlich sind sie aber Vertreter der sogenannten starken monoalphabetischen Chiffren, weil ganze Worte oder Silben auf einmal chiffriert werden. Anhand folgender zwei Vertreter wird die grundlegende Funktionsweise kenntlich gemacht. Genannt seien die Beale-Chiffre und die ¨Große Chiffre¨ vom französichen Sonnenkönig Ludwig dem XIV. Beide sind zu Lebzeiten der Urheber nicht geknackt worden. Beide verwenden ein rechtumfangreiches Alphabet. Die Beale-Chiffre greift beispielsweise auf ein Dokument als Schlüssel zurück. In diesem Dokument werden die Worte durchnummeriert und dann werden im zu verschlüsselnden Text Worte durch entsprechende Zahlen ersetzt. Im Ergebnis steht eine langen Liste von Zahlen, die nur noch mit Hilfe des Original Schlüsseldokuments entschlüsselt werden kann. Beal hatte Mitte des 19. Jahrhunderts 3 Dokumente, die in dieser Weise verschlüsselt waren hinterlassen, die auf einen Silberschatz im Wert von ca. 20 Mio. Dollar weisen sollten. Bis heute ist nur das 2. der 3 Dokumente entschlüsselt worden. Trotz der Tatsache, dass sich bereits Tausende Hobbykryptographen und auch die NSA damit beschäftigt haben bleibt unbekannt, was die anderen Dokumente für einen Inhalt haben. Beale hatte für das 2. Dokument eine besondere 7 Fassung der Unabhängigkeitserklärung von 1776 verwendet. Für die anderen beiden Texte hat er aber andere Schlüsselwörter genommen. Die Große Chiffre geht auf Antoine und Bonaventure Rossignol zurück. 1626 hatte der Vater Antoine einen Brief in die Hände bekommen und damit erfahren, dass das Hugenottenheer in Réalmont kurz vor der Aufgabe stand. Der Brief wurde unverschlüsselt zurück geschickt und die Verteidiger gaben auf. Nun im Dienste des Königs Ludwigs XIII und später unter seinem Nachfolger entwarfen sie die ¨Große Chiffre¨. Ende des 19. Jahrhunderts erst wurde sie durch französische Kryptoanalytiker geknackt. Auf diese Weise wurde unter anderem die lange umstrittene Identität des Mannes mit der eisernen Maskeaufgedeckt. 8 Kapitel 2 Polyalphabetische Chiffren 2.1 Allgemeines Bei den sogenannten polyalphabetischen Chiffrierungen wird derselbe Klartextbuchstabe nicht stets mit demselben Geheimtextbuchstaben verschlüsselt. Bei dieser Technik kommen mehrere monoalphabetische Chiffrierungen zum Einsatz (poly [gr.] = viele). 2.2 Homophone Chiffrierung Die homophone Chiffrierung dient dazu, die Häufigkeiten von Buchstaben zu verschleiern. Dabei ordnet man einem Buchstaben nicht ein, sondern mehrere Zeichen zu. Man ordnet allen 26 Buchstaben z. B. die Zahlen von 0 bis 99 zu; je höher die Häufigkeit des Buchstabens, desto größer die zugeordnete Zeichenmenge. Dem Buchstaben e würde man in unserem Beispiel 17 Zahlen zuordnen. Beim Chiffrieren ordnet man einem Klartextbuchstaben zufällig ein dazugehöriges Geheimtextzeichen zu. Der Empfänger kann dann mit einer Tabelle, die der Absender ihm hoffentlich übergeben hat, dechiffrieren. Leider ist dieses Verfahren nicht sicher, da bestimmte Buchstabengruppen nicht verborgen werden Der entscheidende Nachteil bei monoalphabetischen Chiffren ist, wie wir eben gesehen haben, die leidige Tatsache, dass Buchstabenhäufigkeiten nicht verborgen werden. So wird die Kryptoanalyse kinderleicht. Indem man einem Klartextbuchstaben nicht nur ein, sondern mehrere Geheimtextzeicnen zu ordnet, kann man die Häufigkeiten so verschleihern! Die Anzahl der Geheimtextzeichen sollte dabei der allgemeinen Häufigkeit des Klartextbuchstabens entsprechen. Das bedeutet, dass z.B. das e (Häufigkeit: ca. 17%) 17 Geheimtextzeichen von 100 Paaren 00 bis 99 zugewiesen bekäme. Ein Beispiel hierfür gestaltet sich wie folgt[2]: a: b: c: d: e: f: g: h: i: j: k: l: m: n: o: p: q: 10 20 28 04 09 00 08 07 14 57 23 16 27 30 02 31 25 21 34 06 19 18 41 12 24 39 52 59 71 03 11 35 05 84 49 43 62 63 67 68 72 77 79 82 80 70 81 87 33 38 40 42 53 54 55 60 66 75 85 86 92 93 99 97 47 89 46 50 65 76 88 94 9 r: s: t: u: v: w: x: y: z: 17 15 13 29 37 22 44 48 64 36 26 32 01 51 69 74 78 83 45 56 61 73 96 90 91 95 98 58 Um eine Nachricht zu chiffrieren, ordnet man jedem Klartextbuchstaben ein zufällig gewähltes Zeichen aus der Menge der möglichen Geheimtextzeichen für diesen Buchstaben zu. Da nun jeder Buchstabe mit etwa der gleichen Häufigkeit auftritt, wird die Kryptoanalyse mit ¨herkömmlichen¨ Methoden nun viel schwieriger. Allerdings ist auch bei dieser Chiffre eine Kryptoanalyse möglich: Zwar werden die Häufigkeiten einzelner Buchstaben verschleiert, Buchstabengruppen wie st, sch, ck bleiben jedoch erhalten. Ein Kryptoanalytiker kann den Geheimtext z. B. daraufhin analysieren, welche Geheimtextzeichen ganz bestimmte Nachfolger oder Vorgänger haben; z. B. das c mit Nachfolgern wie h und k, oder das e mit Nachfolger oder Vorgänger i (ei, ie). Diese Methoden sind natürlich noch keine richtige Kryptoanalyse, aber zeigen die Ansätze, wie ein Kryptoanalytiker an einen solchen Text herangehen kann. 2.3 Le Chiffre indechiffrable Der französische Diplomat Blaise de Vigenère (1523-1596) veröffentlichte um 1586 neben anderem eine polyalphabetische Chiffre, welche von der Idee her auf den florentiner Mathematiker Leon Battista Alberti (1404-1472) zurückgeht. Jener hatte 1466 eine Abhandlung zum verwenden mehrerer Geheimalphabete anstatt nur eines einzigen. Dies sollte die Stärke der Verschlüsselung dramatisch erhöhen. Klartextalphabet: 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 1. Geheimtextalphabet: W F O X G P Y H Q Z I R A J S B K T C L U D M V E N 2. Geheimtextalphabet: O X G P Y H Q Z I R A J S B K T C L U D M V E N W F Eine Nachricht sollte dabei abwechselnd buchstabenweise mit beiden Geheimtextalphabeten verschlüsselt werden. Hier ein Beispiel: Nachricht: Kodierung mit dem 1. Geheimtextalphabet: Kodierung mit dem 2. Geheimtextalphabet: DIESERTEXTISTGEHEIM XQGCGTLGVLQCLYGHGQA PIYUYLDYNDIUDQYZYIS Im Ergebnis steht nun dieser Text: XIGUGLLYVDQULQGZGIA Der Text ist nun mit mehreren Alphabeten verschlüsselt und ist nicht mehr mit einfachen Häufgkeitsanalysen, die bei monoalphabetischen Chiffren so erfolgreich waren, zu brechen. Dieser Ansatz und auch weitere Werke, die de Vigenère während seines diplomatischen Dienstes las, inspirierten ihn dazu wesentlich stärkere Chiffren zu entwickeln. Die Schwarzen Kammern in Europa (Dechiffrierdienste) konnten die diplomatische Post auf grund der benutzten schwachen monoalphabetischen Chiffren praktisch mitlesen, was eine starke Motivation war. In seinem Werk Traictè de Chiffres (1586) gibt er den Stand der Chiffierkunst wieder und veröffentlichte ausserdem die nach ihm benannte Vigenère-Chiffre. Die Idee ist die selbe, wie bei Alberti, mit dem Unterschied, dass mehr als 2 Alphabete zum Einsatz kommen sollten. Das folgende Schema soll demonstrieren, wie die Chiffre funktioniert. Klartext: Schlüsselwort: Geheimtext: p o l y a l p h a b e t i s c h K R Y P T O K R Y P T O K R Y P Z F J N T Z Z Y Y Q X H S J A W 10 Klartext | 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 ------------------------------------------------------------------Geheimtext 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 Tabelle 2.1: Vigeneré-Quadrat Das Schlüsselwort wird so oft aneinander gehängt, bis man genau so viele Buchstaben zusammen hat, dass man jeden Buchstaben des Klartextes mit einem korrespondierem den Buchstaben aus dem Schlüsselwort verschlüsselt. Hierzu dient das von Vigenère vorgestellte Vigenere-Quadrat: Hierbei befindet sich der Geheimtextbuchstabe in der Spalte in der sich der zu verschlüsselnde Buchstabe seht und der Zeile, die dem Schlüsselbuchstaben der diesem Buchstaben zugeordnet wird. Also Aus Klartextbuchstabe P und Schlüsselbuchstabe K wird der Geheimtextbuchstabe Z. Dies läßt sich auch mathematisch ausdrücken, indem wir die Buchstaben als Zahlen darstellen (a=0..z=25): (p+K) mod 26 = (15+10) mod 26 = 25 = Z Entschlüsselung ist analog dazu: (26+Z-K) mod 26 = (26 + 25 - 10) mod 26 = 15 = p Die Kerneigenschaft der Vigenère-Ciffre ist also die zyklische Verwendung mehrerer Alphabete. Auf diese Weise wurden sehr effektiv wesentliche Eigenschaften des verschlüsselten Textes verschleiert. Durch die ständig andere Verschlüsselung gleicher Buchstaben war es nicht länger möglich mit einer einfachen Häufigkeitsanalyse den Text zu entschlüsseln. Eine Schwäche hat die Vigenère-Chiffre. Die Verwendung mehrerer Alphabete zur Verschlüsselung sorgt zwar dafür dass die typischen Häufigkeitsverteilungen von Buchstaben verwischt werden. Dennoch fällt bereits bei kurzen Texten auf, dass ein Buchstabe gleich verschlüsselt wird, wenn er an einer Stelle steht, die ein Vielfaches der Schlüssellänge von einem anderen Vorkommen des selben Buchstaben ist. Im Beispiel oben wird das Wort ¨polyalphabetisch¨ mit dem Schlüsselwort KRYPTO verschlüsselt. Nun wird das p 2 mal gleich verschlüsselt 11 Abbildung 2.1: Schema der Vigenère-Chiffre [5] weil es an 1. und an 6. Stelle steht, beide sind 5 Stelle auseinander, was der Schlüsselwortlängeentspricht. Diese Schwäche war auch Blaise de Vigenère bewußt. Daher entwickelte er nur wenig später die AutokeyStromchiffre[10]. Abbildung 2.2: Schema der Autokey-Chiffre [5] Diese funktioniert genau, wie die bereits beschriebene Vigenère-Chiffre. Im Gegensatz zur Vigenère-Chiffre wird aber nach der ersten Verwendung des Schlüsselwortes die Klartextnachricht als weiterer Schlüssel verwendet. Klartextnachricht: DIESENACHRICHTISTGEHEIM Schlüssel: HUCHDIESENACHRICHTISTGE Geheimtextnachricht: KCGZHVEULEIEOKQUAZMZXOQ Diese Art der Verschlüsselung hat 2 Vorteile. Sie ist nicht mehr durch den Kasiski-Test oder gar den Verteilungstest von Willam Friedman (dazu mehr im Kapitel Kryptoanalyse) angreifbar. Außerdem ist es möglich auch aus einer teilweise zerstörten Nachricht noch Informationen zu gewinnen, indem man die Information aus Schlüssel und Klartext verwendete um die Nachricht zu vervollständigen. Damit Blaise de Vigenère die erste selbst synchronisierende, selbstkorrigierende Stromchiffre erfunden. Sie hatte also auch eine gewisse Fehlertoleranz zu bieten. Diese Eigenschaften und die Tatasache, dass sie mit damaligen Mittel vollständig unknackbar war, machte die Autokey-Chiffre zur ¨le chiffre indechiffrable¨. Beide Chiffren, die Vigenère-Chiffre und die Autokey-Chiffre, sollten bis ins 19. Jahrhundert keine große Rolle spielen. Nur so ist es zu erklären, dass der Beiname der Autokey-Chiffre auf die wesentlich schwächere Vigenère-Chiffre überging, dass quasi eine Verwechslung stattfand. Ausserdem findet man in der Literatur nur ganz unzureichende Referenzen. (Dies ist die Meinung des Autors) 12 Erst 200 Jahre später gelang es 2 Männern unabhängig voneinander die Vigenère-Verschlüsselung zu brechen. Dies waren die Herren Kasiski und Friedman. Eigendlich gehört der Tribut Charles Babbage, einem genialen Erfinder, aber seine Erfolge wurde erst bekannt, als man Ende des 19. Jahrhundert seinen umfangreichen Nachlass sichtete. Es heisst er habe im Gegensatz zu Friedman und Kasiski nicht nur die Vigenère-Chiffre geknackt, sondern auch die Autokey-Chiffre[10], da ich leider keinen genaueren Quellen zum Thema gefunden habe sei auf die Quelle [5] verwiesen. Der Kryptographiespielplatz beinhaltet eine sehr aufwendige Implementierung mehrerer Klassischer Chiffren, unter anderen auch der Autokey-Chiffre, sowie einer Reihe von Mechanismen zum Brechen der Vigenère-Chiffre und der Autokey-Chiffre. Dort sind genauere Informationen über die Funktionsweise zu finden. 2.4 Play-Fair Das Playfair-Verschlüsselungsverfahren arbeitet nach einem Algorithmus von Charles Wheatstone (1854). Es sei als Vertreter vieler kleinerer recht anspruchsvoller Chiffren aus dem 19. Jahrhundert genannt. Man benötigt zunächst ein Schlüsselwort. Das Schlüsselwort ist hier PEGASOS und wird an den Anfang der Matrix geschrieben. Da in der Matrix keine zwei gleichen Buchstaben auftauchen dürfen, werden doppelte Zeichen im Schlüsselwort durch das nächste freie Zeichen im Alphabet ersetzt. Die übrigen Zellen der Matrix werden dann mit den restlichen Zeichen des Alphabets aufgefüllt. Schon vorhandene Buchstaben werden dabei weggelassen. Im Fall der 5x5-Matrix wird im Alphabet das J weggelassen. P O H N V E B I Q W G C K R X A D L T Y S F M U Z Die Nachricht, die verschlüsselt werden soll, wird dann in Gruppen von je zwei Buchstaben (Bigramme) aufgeschrieben. Wir benutzen: AL LE SI ST HE RA US FL IE HE SO FO RT Zum Verschlüsseln nimmt man nun das erste Buchstabenpaar AL. Diese beiden Buchstaben bilden in der Tabelle die Endpunkte der Diagonalen eines Rechtecks (A-L von unten nach oben). Die Endpunkte der anderen Diagonalen (auch von unten nach oben gelesen) sind die Punkte P und M. Also wird das Buchstabenpaar AL durch das Paar PM ersetzt. Aus LE wird XR. Probleme gibt es bei dem Paar ST, da beide Buchstaben in der gleichen Zeile stehen. In diesem Fall nimmt man jeweils den Buchstaben rechts davon - TW. Steht links davon kein Buchstabe mehr, dann geht man einfach wieder an das Ende der Zeile. Stehen die Buchstaben eines Paares in der Tabelle übereinander wie beim Paar FL, so nimmt man jeweils die nächsten Buchstaben darunter - LY. Die verschlüsselte Botschaft lautet dann: PM XR TH TW KB UP BA LY KC KB TP KP CP Um die Sicherheit zu erhöhen, kann man vor dem Verschlüsseln Zeichenverdopplungen durch Einfügen von zum Beispiel X auflösen, da diese eine leichte Angriffsmöglichkeit bieten. Durch die Verwendung von Zeichenpaaren ist das Brechen des Algorithmus im Vergleich zu Verfahren, die nur einzelne Zeichen verwenden, schwieriger. So ist zum Beispiel eine Häufigkeitsanalyse weniger aussagekräftig und das Erstellen von Codebüchern aufwändiger. Eine Erkenntnis die auch bei der ADFGVX-Chiffre aus Kapitel 1 umgesetzt wurde. Moderne Verfahren benutzen deshalb nicht nur zwei Zeichen, so arbeitet etwa IDEA auf 64 Bit (also 8 Zeichen) Blöcken. 2.5 One-Time-Pad Im 1. Weltkrieg wurde die Schwäche vieler Verschlüsselungen dramatisch sichtbar, da viele Schlachtenausgänge durch die Durchbrechung vermeintlich sicherer Verschlüsselungen durchbrochen wurde. So zum Beispiel die 13 Zimmermann-Chiffre als auch die bereits erwähnte ADFGVX-Chiffre. Dies weckte Bedarf nach neueren stärkeren Verfahren zur Verschlüsselung. Eines dieser Verfahren ist das OneTime-Pad. Dieses ist das einzige bekannte Verfahren, das nicht nur praktisch, sondern auch theoretisch unknackbar ist. Leider ist dieses One-Time-Pad, welches 1917 von Major Joseph Mauborgne und Gilbert Vernam von AT&T erfunden wurde, in der Praxis schwierig umzusetzen. Folgende Bedingungen müssen nämlich erfüllt sein: Der Schlüssel • muss genauso lang sein wie der Klartext • muss streng zufällig gewählt sein • darf nur ein einziges Mal verwendet werden Verschlüsselt wird mit dem One-Time-Pad genauso, wie mit der Vigenère-Chiffre oder der Autokey-Chiffre, also indem wir die Buchstaben als Zahlen darstellen (a = 0 ... z = 25): (o + T) mod 26 = (14 + 19) mod 26 = 7 = H Entschlüsselung: (26 + H - T) mod 26 = (26 + 7 - 19) mod 26 = 14 = o Wenn man nun sehr lange Texte verschlüsseln muss, steht man vor dem Problem, einen sehr langen sehr zufälligen Schlüssel erzeugen. Die Entschlüsselung dieses Textes setzt voraus, dass der Schlüssel dem Empfänger bereits übermittelt wurde. Dies ist ein enormes logistisches Problem. Das ist auch der Grund, weshalb es nur sehr selten eingesetzt wird. Es gibt noch ein weiteres Problem. Der Schlüssel muss einem echten Zufallsprozess entstammen. Ein echter Zufallsprozess ist z.B. Würfeln oder eine Münze werfen oder Ausschläge eines Geigerzählers beim Messen von radioaktivem Zerfall. Computer-Zufallsgeneratoren erzeugen leider keine echten Zufallszahlen, sie berechnen nur die Zahlen mit Hilfe eines bestimmten Startwertes. Um also einen ¨guten¨ Schlüssel zu erhalten, müssen man sehr, sehr oft würfeln ... Als Schlüssel darf natürlich kein ¨richtiger¨ Text benutzt werden, da dieser wieder bestimmte statistische Eigenschaften hat. Die letzte Bedingung scheint auf den ersten Blick kein Problem darzustellen. Aber dem ist dennoch so. Selbst wenn der Schlüsselblock mehrere Gigabytes umfasst, kann ein Kryptoanalytiker den Klartext rekonstruieren, sofern er über mehrere Chiffretexte verfügt, deren Schlüssel sich überschneiden. Dazu verschiebt er die Chiffretexte paarweise gegeneinander und zählt die Anzahl der Übereinstimmungen (Siehe Autokorrelation S.26). Mitunter kann das soweit gehen dass ganze Textpassagen mit dem selben Verfahren wie für die VigenèreChiffre geknackt werden kann. Warum ist dieses für heutige Verhältnisse einfache Verfahren so sicher[6]? Der Grund ist ein bestimmter Chiffretext kann mit derselben Wahrscheinlichkeit zu jedem der möglichen Klartexte gleicher Länge gehören. Da jede Schlüsselsequenz gleich wahrscheinlich ist (der Schlüssel muss absolut zufällig sein!), besitzt ein Analytiker keinerlei Informationen, mit denen der den Chiffretext einer Kryptoanalyse unterziehen könnte. Beispiel: Klartext: o n e t i m e p a d Schlüssel: T B F R G F A R F M Geheimtext: I P K L P S F H G Q Der Schlüssel könnte ebensogut POYYAEAAZX lauten, was entschlüsselt salmoneggs ergibt oder BXFGMTMXM, was dechiffriert greenfluid bedeutet[6]. Im zweiten Weltkrieg wurde das One-Time-Pad von der englischen Entschlüsselungstruppe von Bletchley Park 14 benutzt, um dem Premierminister die Nachrichten zu übermitteln, die von den Deutschen mit der Enigma verschlüsselt worden waren und die Engländer geknackt hatten. Bis vor wenigen Jahren sollen die Gespräche über den ¨heißen Draht¨ zwischen dem Weißen Haus und dem Kreml mit Hilfe eines One-Time-Pads verschlüsselt worden sein. 2.6 Enigma Unter den Spezialmaschinen, die zur Erleichterung der routinemäßigen Chiffrierung und Dechiffrierung erfunden und über Jahre und Jahrzehnte weiterentwickelt wurden, ist die Enigma[12] wahrscheinlich weltweit die bekannteste. Mit ihr wurde während des Zweiten Weltkriegs der größte Teil der Funksprüche der deutschen Wehrmacht und Marine vor dem Absenden verschlüsselt und nach dem Empfang wieder entschlüsselt. Man nimmt an, daß während des Zweiten Weltkriegs 100 000 bis 200 000 Enigma Maschinen gebaut wurden. Die Geschichte der Computertechnik wird von der Zeit der Enigma bis heute von der Chiffrierung und den Bemühungen um die Brechung unbekannter Codes mitbestimmt. Wenn in der heutigen Situation des stürmischen Zusammenwachsens von Computern und digitalisierter Telekommunikation die Chiffrierung eine größere Rolle spielt als jemals zuvor in der Geschichte, läßt die Historie der Enigma ein wenig ahnen, was alles durch die systematische Veränderung von Buchstaben in der Weltgeschichte bewegt werden kann. Ein anderer Aspekt betrifft sicherlich unser wachsendes Wissen über die historischen Zusammenhänge während des Zweiten Weltkriegs, wodurch die Einschätzungen der Rolle von Chiffrierung und Code-Brechen fundierter und differenzierter wurden. So ist die Heldenrolle der Enigma eher eine negative, was ihre technische Überlegenheit und ihre Bedeutung für den deutschen Endsieg betrifft. Sie wurde, um im Bild zu bleiben, zum Podest, auf dem die Helden des Code-Knackens heute stehen. Die mit der Enigma chiffrierten Funksprüche wurden während des Kriegs in der Britischen Chiffrierstelle in Bletchley Park trotz immer neuer technischer Raffinessen dechiffriert, so daß die Alliierten diesen Teil des militärischen Funkverkehrs mit einigen Ausnahmen mithören konnten. Hierbei kam der Colossus (Abb 2.3) zum Einsatz, für damalige Begriffe ein Großrechner. Abbildung 2.3: Collossus Die Erfindung des in der Enigma verwendeten Arbeitsprinzips geht auf die Jahre des Ersten Weltkriegs zurück, als der amerikanische Bauunternehmer Edward Hugh Hebern (1869 - 1952) 1917 eine rotierende Vorrichtung zur polyalphabetischen Substitution mit unabhängigen Alphabeten erfand. Er bot seine Chiffriermaschinen vergeblich dem amerikanischen Militär an. 1918 meldete der Ingenieur Arthur Scherbius (1878 - 1929) das Rotorprinzip zum Patent an. Er stellte in seiner Chiffriermaschinen AG in Berlin die mit dem griechischen Wort für Rätsel als Enigma bezeichnete Maschine her und führte sie 1923 in Bern und 1924 beim Weltpostkongreß in Stockholm 15 der Öffentlichkeit vor. Die Enigma war damals nicht geheim. 1927 kaufte Scherbius die Patente des Niederländers Hugo Alexander Koch, der 1919 das Rotorprinzip selbst neu erfunden hatte. Die technische Weiterentwickelung der Enigma leitete nach Scherbius Tod 1929 Willi Korn. Auch in Schweden war das Rotorprinzip 1919 unabhängig erfunden worden. In allen Ländern war das Interesse staatlicher Stellen an diesen Maschinen zunächst gering. In Deutschland übernahm die Reichswehr die Enigma, und als mit Hitler 1933 die massive Aufrüstung eingeleitet wurde, gehörte die Enigma zum Programm. Während des Zweiten Weltkriegs war die Enigma zwar die meistverwendete, jedoch nicht die einzige Verschlüsselungsmaschine der deutschen Stellen. Die strategischen Nachrichten wurden mit wenigen noch komplexeren Geräten chiffriert. Seit 1933 wurde die Enigma beim Heer, bei der Marine und beim diplomatischen Dienst weiterentwickelt. Schon Scherbius hatte das Rotorsystem 1928 durch ein Steckbrett ergänzt, mit dem die Verschlüsselung noch komplizierter wurde. Das Funktionsprinzip beruht auf einfachen Stromkreisen, von denen jeder eine Buchstabentaste des schreibmaschinenüblichen Tastenfelds mit einem elektrischen Lämpchen verbindet, das auf dem Anzeigenfeld einen Buchstaben aufleuchten läßt. Mit jedem Tastendruck leuchtet ein neuer Buchstabe auf. Jeder einzelne Stromweg führt durch jede der drei Walzen über jeweils einen vorderen und einen hinteren Kontakt bis zur sogenannten Umkehrwalze und von dort wieder zurück durch sämtliche Walzen und zusätzlich durch die Stecker des Steckfeldes. Die Verschlüsselung findet durch ein recht kompliziertes System statt: • in jeder Walze sind nicht die sich gegenüberliegenden Ein- und Ausgangskontakte miteinander galvanisch verbunden, sondern sie sind nach einem bestimmten System gegeneinander verschränkt • die Steckanordnung auf dem Steckbrett wird variiert • bei jedem Tastendruck werden die Walzen nach einem bestimmten System um eine Stelle weitergedreht • aus einem Satz von fünf werden jeweils drei ausgewählt und in jeweils neu festgelegter Reihenfolge eingesetzt • auch die Anfangseinstellung der Walzen wird immer neu festgelegt • an jeder einzelnen Walze wird ein Einstellring eingestellt Beim Betrieb während des Kriegs wurden die verschiedenen Einstellungen alle acht Stunden gewechselt. 16 Teil II Kryptoanalyse 17 Kapitel 3 Kryptoanalyse 3.1 Kryptoanalyse monoalphabetischer Chiffren Die Kryptoanalyse ist die Wissenschaft, die sich mit dem Brechen der Verschiedenen Chiffren beschäftigt. Kryptographen und Kryptoanalytiker sind Gegenspieler. Während sich die Kryptoanalytiker mühen die Chiffren der Kryptographen zu brechen, mühen sich Kryptographen Chiffren zu entwickeln, die eine geeignete Sicherheit bieten. Jahrhundertelang verwendeten die Menschen in aller Welt ausschließlich monoalphabetische Chiffren, welche mittels einer einfachen Häufigkeitsanalyse zu knacken sind. Hier ein Beispiel: EHLGHUFHDVDUFKLIIUHKDWFHDVDUIXHUMHGHQWHAWGDVDOIDEHWXPGUHLEXFKVWDEHQY HUVFKREHQDXIGLHVHZHLVHZDUHQVHLQHEHIHKOHYRUXQEHUXIHQHQDXJHQJHVFKXHWCW Die Häufigkeitsanalyse dieses Textes liefert folgendes Ergebnis: Das geübte Auge sieht ohne jede weitere Ana- Abbildung 3.1: Häufigkeitsanalyse und Diagramme lyse, dass es sich bei diesem Text um einen monoalphabetisch verschlüsselten Text handelt. Diesen Clou liefert einerseit der Koinzidenzindex (KI-Index:= 0.8338..) der nahe bei 1 liegt und anderer seits die Ähnlichkeit der beiden Diagramme. Der Unterschied liegt im wesentlichen in einer Verschiebung beispielsweise der schwarz hervorgehobenen Säulen. Bei einer einfachen Chiffre, wie der Ceasarchiffre, kann man sich bei deutschen Texten dabei ganz einfach an dem ¨e¨ orientieren. Dies ist der häufigste Buchstabe sowohl im Deutschen als auch im Englischen (siehe Häufigkeitstabellen 4.1 auf Seite 22), um so die Alphabetverschiebung zu ermitteln. Die Analyse ergibt nun also ein Alphabetverschiebung um 3 Buchstaben und folgenden Klartext: BEI DER CAESAR CHIFFRE HAT CAESAR FUER JEDEN TEXT DAS ALPHABET UM 18 DREI BUCHSTABEN VERSCHOBEN AUF DIESE WEISE WAREN SEINE BEFEHLE VOR UNBERUFENEN AUGEN GESCHUETZT Dies ist natürlich nur ein einfaches Beispiel. Generell kann man daraus aber folgende Erkenntnis ableiten: Es gibt Buchstaben, die ihrer Häufigkeit wegen auffallen. So etwa die Buchstaben e und s. Und genau da liegt das Problem: Leider kommen nicht alle Buchstaben mit gleicher Häufigkeit vor. Das e kommt mit einer Häufigkeit von durchschnittlich 17,4 Prozent, das s mit 7,3, r mit 7, a mit 6,5 usw. vor (siehe Tabelle unten). Das klägliche Schlusslicht dieser Reihe ist übrigens das q, das nur mit 0,02 Prozent vertreten ist. Um einen verschlüsselten Text zu knacken, untersucht man zunächst die Häufigkeiten von jedem Geheimtextzeichen und probiert dann verschiedene Buchstaben aus, die aufgrund ihrer Häufigkeit passen könnten. Die Tatsache, dass sich die Häufigkeiten je nach Art des Textes (wissenschaftlich, politisch, privat ...) unterscheiden, stellt in der Regel kein großes Hindernis dar, da der Angreifer, der den Text abgefangen/gefunden hat, oft schon erraten kann, um was für eine Art es sich handelt. Führen die Einzelbuchstabenanalysen nicht zum Ziel sucht man nach Bigrammen (4.2 auf Seite 22) Kurze Texte sind schwieriger zu knacken, aber Computer können viele Möglichkeiten in kurzer Zeit durchprobieren (jeder normale Home-PC vielleicht 1 Million pro Sekunde) und daher auch Buchstaben ausprobieren, die normalerweise weniger häufig vorkommen. (siehe Häufigkeitstabellen 4.1 auf Seite 22) Bei Substitutionschiffren wie der ¨Großen Chriffre¨(siehe Seite 7) muss man anders herandgehen, da es sich beim Geheimtext um eine Ersetzung ganzer Silben und Wörter handelt. Aber auch hier kann man mit dem gleichen Ansatz Treffer landen. So führt auch hier eine Häufigkeitsanalyse zum Ziel. Die häufigsten der 578 Zahlen repräsentieren auch hier die in der französichen Sprache am häufigsten vorkommenden Silben. Hat man einen solchen Ansatz erstmal gefunden ist der Rest ein Kinderspiel. 3.2 3.2.1 Kryptoanalyse polyalphabetischer Chiffren Allgemeines Im 18. und vorallem im 19. Jahrhundert waren die Schwarzen Kammern in Europa sehr aktiv beider massenweise Entschlüsselung diplomatischer Post. Am effektivsten arbeitete die Wiener schwarze Kammer. Sie arbeitete wie die Post. Morgens um 7 Uhr kam die diplomatische Post der ausländischen Botschaften zur Analyse herein umd dann vollständig kopiert zu werden und dann an die entsprechenden Empfänger weitergeleitet zu werden. Mittags war die ganze Post abgearbeitet. Eine enorme Leistung wenn man bedenkt, dass hunderte, wenn nicht sogar tausende Briefe kopiert wurden. Danach wurden die Texte praktisch am Laufband entschlüsselt. Das ist eine beeindruckende Leistung. Doch wie geht man dabei vor? 3.2.2 Das Wichtigste ist die Mustersuche... Bei der Enschlüsselung monoalphabetischer Verschlüsselungen wurde erklärt, dass es häufig genügt einen Text auf Häufigkeitsverteilungen von Buchstaben und Buchstabenkombinationen zu untersuchen, um zu einem zufriedenstellenden Ergebnis zu kommen. Das geht bei polyalphabetischen Chiffren nicht. Der Grund dafür ist, dass es der der Sinn von polyalphabetischen Chiffren ist, Buchstabenhäufigkeiten zu verwischt. Das stellte Kryptoanalytiker lange Zeit vor große Probleme. Abhilfe schafften Analyseverfahren, wie der Kasiski-Test und Schätzverfahren, wie der Friedman-Test. Beide dienen dazu, bei der Vigenère-Chiffre die Schlüsselwortlänge zu ermitteln. Der Kasiski-Test ist sehr aufwendig und den Friedman-Test, der sich auf aufwendige statistische Berechnungen und Annahmen stützt, liefert recht ungenaue Ergebnisse. Trotzdem ist die Kombination sehr effektiv, um die Vigenère-Chiffre zu kompromitieren. Aus der Nachrichtentechnik stammt eine weitere Technik, welche man weit effektiver und auch vielseitiger einsetzen kann als die oben erwähnten. Es heißt Autokorrelation[1](siehe Seite 26). Hierbei wird der verschlüsselte 19 buchstabenweise an sich selbst vorbeigeführt. Bei jedem Schritt wird die Anzahl gleicher Buchstaben notiert, die untereinanderstehen. Das Ergebnis kann man als Säulendiagramm darstellen: Abbildung 3.2: Autokorrelation vigenère-verschlüsselter Text Abbildung 3.3: Autokorrelation autokey-verschlüsselter Text Auffällig ist das unterschiedliche Ergebnis der Autokorelation . Während das Ergebnis der Vigenèrechiffre eine typische Kammstruktur aufweist, liefert die Autokey-Chiffre lediglich einen einzigen Ausschlag. Dieser ist im übrigen die einzige Schwäche, die diese Chiffre aufzuweisen scheint. Da die Gleichverteilung der mit Autokey verschlüsselter Texte sehr hoch ist. Dies ist messbar mit Hilfe eine Entropieanalyse (siehe Seite 26). Je näher der Wert bei 4.7 liegt desto stärker die Chiffre. Bei Autokey-verschlüsselten Texten liegt dieser Wert meist über 4.5. Der Graph den die Autokorrelation bei einer Vigenèrechiffre liefert über den mittleren Abstand der ¨Kammzähne¨ die Schlüssellänge. Bei der Autokeychiffre liegt der eine starke Ausschlag genau an der Stelle, welche die genaue Schlüssellänge beschreibt. An diesen beiden Beispielen sieht man bereits, wie unterschiedlich die einzelnen Chiffren auf die Analyseverfahren reagieren. Das Ergebnis ist wie ein Fingerabdruck und erlaubt eine schnelle Identifikation der Chiffre. 3.2.3 ...und wieder monoalphabetisch! Bei der Vigenère-Chiffre geht man nach erfolgreicher Schlüsselwortlängenermittlung so vor, dass man den Text buchstabenweise nacheinander ind soviele Haufen teilt, wie die ermittelte Schlüsselwortlänge es vorgibt. Jeder dieser Haufen ist mit dem selben Buchstaben verschlüsselt worden. Wir wenden jetzt also ganzz elementare Techniken an, um die Alphabetverschiebung zu ermitteln. Danach werden die ermittelten Verschiebungen Buchstaben zugeordnet und man erhält das Schlüsselwort. (A..Z) := (0..25) Die Autokeychiffre erfordert ein anderes Vorgehen. Auch hier wird die Chiffre in so viele Einzelströme zerlegt, wie es die ermittelte Schlüsselwortlänge vorgibt. Jeder dieser Ströme ist mit einem anderen Buchstaben verschlüsselt. Im Gegensatz zur Vigenèrechiffre hilft uns eine Häufigkeitanalyse nicht weiter. Hier müssen wir probieren... Die Ströme werden mit jedem Buchstaben des Alphabets dekodiert und dann wird eine Häufigkeitsanalyse durchgeführt. Die Buchstabenverteilung wird mit der normalen Buchstabenverteilung des Alphabetes korreliert. Zur Kontrolle wird gleichzeitig mittels Friedman-Test darauf getestet, ob der Text monoalphabetisch ist. Von den 26 Ergebnissen, wählen wir die beiden mit dem niedrigsten Wert für den Friedman-Test und Treffer ist derjenige, welcher bei der erwähnten Korrelation die genaueste Übereinstimmung erziehlt. Nach dem Ermitteln der einzelnen Schlüsselwortbuchstaben ergibt sich das Schlüsselwort. Ist die Chiffre beschädigt 20 kann man das Verfahren trotzdem verwenden. Es ergibt sich ein anderes Schlüsselwort aber der Text bleibt ermittelbar (siehe 2.2)[5]. 3.2.4 Der Weisheit letzter Schluß... ... ist dies sicher nicht. Diese beiden Beispiele sind sicherlich nicht die einzigen Ansätze die es gibt um diese beiden Chiffren zu knacken. Aber die Komplexität des Lösungsverfahrens ist lediglich N 2 . Damit ist es wesentlich effizienter als das von Kasiski, welcher sich nicht unterhalb von N 3 implementieren läßt. Wenn jemand sich selbst an den beschriebenen Chiffren versuchen will, sei der ¨Kryptographiespielplatz¨[5] wärmstens empfohlen. Auserdem sei auf den beiliegenden Quellcode verwiesen, mit denen es möglich ist, wesentliche Elemente nachzubauen ... und nachzu vollziehen (siehe Seite 33). Eines wird beim Experimentieren mit den verschiedenen Chiffren klar. Die Kombination verschiedener polyalphabetischer Chiffren führt zu einer stärkeren Chiffre. So ist die Kombination Autokey→Vigenère→Autokey→Vigenère so stark, auch wenn man das selbe Schlüsselwort für jeden Verschlüsselungsschritt nimmt, dass es zu einer derartigen Gleichverteilung der Buchstaben führt, dass der resultierende Geheimtext mit den vorgestellten Verfahren nicht mehr zu brechen ist, und es wird um so schwerer je länger die Texte sind. 21 Kapitel 4 Mathematische Grundlagen 4.1 Häufigkeitstabellen Buchstabe Häufigkeit[%] Buchstabe Häufigkeit[%] Buchstabe Häufigkeit[%] A 6.51 J 0.27 S 7.27 B 1.89 K 1.21 T 6.15 C 3.06 L 3.44 U 4.35 D 5.08 M 2.53 V 0.67 E 17.40 N 9.78 W 1.89 F 1.66 O 2.51 X 0.03 G 3.01 P 0.79 Y 0.04 H 4.76 Q 0.02 Z 1.13 I 7.55 R 7.00 Tabelle 4.1: Häufigkeitstabelle für Buchstaben in deutschen Texten[2] Buchstabe Häufigkeit[%] EN 3.88 ER 3.75 CH 2.75 TE 2.26 DE 2.00 ND 1.99 EI 1.88 IE 1.79 IN 1.67 ES 1.52 Tabelle 4.2: Häufigkeitstabelle für Bigramme in deutschen Texten[2] Sprache Deutsch Englisch Esperanto Flämisch Französisch Interlingua Italiänisch Latein Portugisisch Spanisch Schwedisch Reihenfolge E N I R S A E T A O N I A I E O N S E N I A R D E A N R S I E A I L N O E A I O L N I E U T A M E A O S I D E A O S R N A E N R T S der D T R S L T T O T U S T R T S N R T I D I O Buchstaben nach U G H O L B M C H L D C U P F M R J U K M P D G G L S H V R M U O L D C M P V B R U D C M P V G S C D M P U V G R O D L V C P Q N C P U M L V F L C T U M P G W M G K L D V F B Häufigkeit W F K V Z P W Y B G V K C V B F Z H W J B Z C P F G H Q J Z B F H X Q J Z F B H Q B F G X H J G Q H J X Z B Q V H F Z C H P U Y J J Q Q F X W Q X W X Y Y X J X Y Z K K W Y Z B K W Y X Q W Z Tabelle 4.3: Buchstaben-Rangfolge verschiedenener Sprachen[8] 22 Y Z Y Q 4.2 Verfahren zur Analyse Die hier vorgestellten Verfahren sind nur eine kleine Auswahl an Techniken, die bei der Enschlüsselung von klassischen Chiffren zum Einsatz kommen können. Dennoch reichen sie bereits aus elaborate Chiffren, wie die Vigenère-Ciffre oder gar die Autokey-Stromchiffre, zu brechen[5]. 4.2.1 Häufigkeit Die Häufigkeitsanalyse stellt das elementarste Werkzeug zur Analyse dar. Mit ihr kann man ermitteln, welcher die Verteilung von Buchstaben, Wörtern oder Symbolen in Texten ist. Dokumentierte Verwendung dieser Techniken gehen bis ins 9. Jahrhundert zurück. 4.2.2 Kasiski-Test Der Kasiski-Test wurde 1863 von dem preußischen Infanteriemajor Friedrich Wilhelm Kasiski veröffentlicht. Er beruht auf folgender Überlegung: Wenn zwei gleiche Buchstabenfolgen verschlüsselt werden, entstehen daraus im Normalfall verschiedene Geheimtexte, da über ihnen verschiedene Buchstaben des Schlüssels stehen und sie somit mit verschiedenen Geheimtextalphabeten verschlüsselt werden. Hier ein Beispiel: Klartext: DERKLARTEXTWIRDZUMGEHEIMTEXT Schlüssel: PLUTOPLUTOPLUTOPLUTOPLUTOPLU Geheimtext: SPLDZPCNXLIHCKROFGZSWPCFHTIN Wenn der Abstand dieser Buchstabenfolgen aber ein Vielfaches der Schlüssellänge ist, dann werden beide Buchstabenfolgen mit den gleichen Geheimtextalphabeten verschlüsselt und es entsteht zweimal der gleiche Geheimtext. Hier ein Beispiel: Klartext: DERKLARTEXTWERDEGEHEIMTEXT Schlüssel: PLUTOPLUTOPLUTOPLUTOPLUTOP Geheimtext: SPLDZPCNXLIHYKRTRYASXXNXLI Um auf die Schlüsselwortlänge zu kommen, muss der Text allerdings länger sein, als der dieses Beispiels, denn es ist schon ein großer Zufall, wenn ein so kurzer Klartext überhaupt zwei gleiche Buchstabenfolgen enthält. Die Wahrscheinlichkeit dafür, dass ihr Abstand auch noch ein Vielfaches der Schlüsselwortlänge ist, ist sehr gering. Bei langen Texten funktioniert das Verfahren allerdings sehr gut: Man sucht also gleiche Buchstabenfolgen im Geheimtext und bestimmt ihren Abstand. Buchstabenfolgen, die kürzer als drei Zeichen sind, sollten dabei ignoriert werden, da sie oft zufällig entstehen. So tritt im ersten Beispiel die Zeichenfolge PC im Geheimtext zweimal auf, sie ist aber einmal aus dem Klartext AR und beim zweiten Mal aus EI entstanden. Natürlich können auch längere gleiche Zeichenfolgen im Geheimtext zufällig entstehen, dies geschieht aber deutlich seltener. Die gesuchte Schlüssellänge ist also ein Teiler der Abstände der gleichen Zeichenfolgen, die aus mindestens drei Buchstaben bestehen. Vorsichtiger ausgedrückt ist sie ein Teiler der meisten dieser Zeichenfolgen. Wenn man die Primfaktorzerlegung aller Abstände vergleicht, lassen sich gleiche Teiler schnell finden und außerdem fallen auch die zufällig entstandenen Abstände auf, da sie meist keine gemeinsamen Teiler mit den übrigen Abständen haben. Nachdem man die gleichen Teiler bestimmt hat, ist die genaue Schlüssellänge allerdings noch nicht bekannt, es ist lediglich anzunehmen, dass der größte gemeinsame Teiler der Abstände ein Vielfaches der gesuchten Schlüssellänge ist. Die ermittelten Abstände könnten beispielsweise 30, 75 und 105 sein, woraus man allerdings nicht schließen 23 kann, dass die Schlüssellänge 15 ist, denn 3 und 5 wären ebenfalls möglich. Der Kasiski-Test liefert also nur ein Vielfaches der Schlüssellänge. 4.2.3 Koinzidenzindex / Friedman-Test Mit dem Friedman-Test[2], der 1925 von William Friedman entwickelt wurde, lässt sich hingegen die Größenordnung der Schlüssellänge berechnen. Als Grundlage für die Herleitung der entsprechenden Formel dienen folgende Überlegungen: ¡n1 ¢ n · (ni − 1) ¡n2 ¢ = i (4.1) n · (n − 1) 2 Es sei eine beliebige Buchstabenfolge der Länge n gegeben. Die Anzahl der einzelnen darin enthaltenen Buchstaben werden mit n1 (für das A) bis n26 (für das Z ) bezeichnet. Es soll jetzt die Wahrscheinlichkeit dafür berechnet werden, dass zwei zufällig herausgegriffene Buchstaben gleich sind. Dazu bestimmt man zuerst die Wahrscheinlichkeit dafür, dass zwei beliebige Buchstaben dieser Buchstabenfolge As sind. Sie beträgt: 26 X ni · (ni − 1) i=1 n · (n − 1) = P26 ni · (ni − 1) n · (n − 1) i=1 (4.2) Für B gilt dasselbe mit n2 statt n1 usw. Werden alle diese Einzelwahrscheinlichkeiten von A bis Z addiert, enthält man die gesuchte Wahrscheinlichkeit für ein Paar aus zwei gleichen Buchstaben: P26 ni · (ni − 1) I = i=1 (4.3) n · (n − 1) Dieser Wert wird mit I (oder k, dem griechischen κ Kappa) bezeichnet und stellt den sogenannten Koinzidenzindex dar: P26 ni · (ni − 1) I = i=1 (4.4) n · (n − 1) Als nächstes sollen die Wahrscheinlichkeiten für das Auftreten eines bestimmten Buchstaben bekannt sein. Die Wahrscheinlichkeit, dass ein zufällig gewählter Buchstabe ein A ist, sei p1 usw. Dann wäre die Wahrscheinlichkeit, zufällig zwei As zu finden etwa p21 . Sie wäre genau p21 , wenn es erlaubt wäre, einen Buchstaben zweimal zu wählen. Der Text soll so lang sein, dass der dadurch entstehenden Fehler nicht ins Gewicht fällt. Durch Summieren dieser Werte soll wieder die Wahrscheinlichkeit für ein Buchstabenpaar aus gleichen Buchstaben bestimmt werden. Der auf diese Weise errechnete Wert entspricht also etwa dem Koinzidenzindex: I≈ 26 X p2i (4.5) i=1 Für die deutsche Sprache lassen sich für die Wahrscheinlichkeiten p1 bis p26 die Häufigkeiten aus Tabelle 1 einsetzen. Man erhält in diesem Fall folgenden Wert: I≈ 26 X p2i = 0.0762 (4.6) i=1 Für eine Buchstabenfolge, in der jeder Buchstabe mit der gleichen Wahrscheinlichkeit auftritt, gilt pi = Dann erhält man einen deutlich kleineren Wert: I≈ 26 X 1 ( )2 = 0.0385 26 i=1 1 26 . (4.7) Als nächstes soll die Wahrscheinlichkeit berechnet werden, mit der zwei zufällig aus einem Vigenère-chiffrierten Geheimtext gewählte Buchstaben gleich sind. Diese Wahrscheinlichkeit hängt von der Länge des Schlüssels ab, die im folgenden Text mit L bezeichnet wird. Wenn der Geheimtext zeilenweise in eine Tabelle mit L Spalten geschrieben wird, dann wurden alle Buchstaben einer Spalte mit dem selben Geheimtextalphabet verschlüsselt. Da alle Buchstaben einer Spalte mit der gleichen monoalphabetischen Chiffrierung verschlüsselt wurden, ist die 24 Häufigkeitsverteilung unter ihnen erhalten geblieben. Die Wahrscheinlichkeit, hier zwei gleiche Buchstaben zu n finden ist also etwa 0,0762. Da es L Spalten mit jeweils L Buchstaben gibt (Rundungsfehler können bei großen Texten vernachlässigt werden), lässt sich die Anzahl der Buchstabenpaare aus gleichen Spalten folgendermaßen errechnen: 1 n−L n · (n − L) 1 n n )= (4.8) L · · · ( − 1) = n · · ( 2 L L 2 L 2·L n n Zur Erläuterung: Es gibt L Möglichkeiten, den ersten Buchstaben in einer Spalte zu wählen und L − 1 Möglich1 keiten für den zweiten Buchstaben. Da die Reihenfolge keine Rolle spielt, wird mit 2 multipliziert. Dies wäre die Anzahl der Buchstabenpaare pro Spalte, also wird noch mit L multipliziert und man erhält die gesamte Anzahl der Buchstabenpaare aus gleichen Spalten. Da unter ihnen jedes mit einer Wahrscheinlichkeit von etwa 0,0762 aus gleichen Buchstaben besteht, findet man in gleichen Spalten voraussichtlich n · (n − L) = 0.0762 2·L (4.9) Paare aus gleichen Buchstaben. Wenn das Buchstabenpaar allerdings Buchstaben aus verschiedenen Spalten erhält, wurden sie auch mit verschiedenen Chiffrierungen verschlüsselt (Voraussetzung ist, dass der Schlüssel nur aus verschiedenen Buchstaben besteht). Die Häufigkeitsverteilung der Geheimtextbuchstaben ist dann also echt zufällig. Daraus ergibt sich, dass die Wahrscheinlichkeit für zwei gleiche Buchstaben in verschiedenen Spalten etwa 0,0385 beträgt. Die Anzahl der Buchstabenpaare mit Buchstaben aus verschiedenen Spalten ist die Anzahl aller Paare minus die oben errechnete Anzahl von Paaren mit Buchstaben aus gleichen Spalten: µ ¶ n n · (n − L) n · (n − 1) n · (n − L) n · (n − 1) · L − n · (n − L) n2 · L − n2 n2 · (L − 1) − = − = = = 2 2·L 2 2·L 2·L 2·L 2·L (4.10) Da jedes dieser Paare mit einer Wahrscheinlichkeit von 0,0385 aus gleichen Buchstaben besteht, gibt es in verschiedenen Spalten etwa n2 · (L − 1) = 0.0385 (4.11) 2·L Paare aus gleichen Buchstaben. Addiert man die oben errechnete Anzahl, so erhält man die Anzahl aller Buchstabenpaare des Textes, die aus gleichen Buchstaben bestehen: n · (n − L) n2 · (L − 1) · 0.0762 + · 0.0385 2·L 2·L (4.12) Teilt man diesen Term durch die Anzahl aller Buchstabenpaare des Textes, erhält man die Wahrscheinlichkeit, zufällig ein Paar aus gleichen Buchstaben zu finden: n·(n−L) 2·L 2 · 0.0762 + n ¡n¢ ·(L−1) 2·L · 0.0385 (4.13) 2 Durch Umformung erhält man folgenden Term, der also eine Annäherung des Koinzidenzindexes darstellt (Die einzelnen Zwischenschritte können im Anhang nachgelesen werden): I≈ 0.0377 · n 0.0385 · n − 0.0762 + L · (n − 1) n−1 (4.14) Da man den Koinzidenzindex durch Zählen der einzelnen Buchstaben leicht ermitteln kann, muss die Gleichung nur noch nach L aufgelöst werden und man erhält eine Formel für die Länge des Schlüssels: L≈ 0.0377 · n (n − 1) · I − 0.0385 · n + 0.0762 (4.15) Die Werte, die diese Formel liefert, sind zwar nicht sehr genau, aber zusammen mit den Ergebnissen des KasiskiTests lässt sich die Schlüssellänge in den meisten Fällen eindeutig bestimmen. 25 4.2.4 Entropie Mit Hilfe des Informationsgehaltes[1] der einzelnen Nachrichten kann nun die mittlere Information berechnet werden, die eine Quelle mit einer gegebenen Verteilung liefert. Für die Durchschnittsbildung werden die einzelnen Nachrichten mit der Wahrscheinlichkeit ihres Auftretens gewichtet. Entropie(p[1], p[2], ..., p[r]) := −[p[1] ∗ log(p[1]) + p[2] ∗ log(p[2]) + ... + p[r] ∗ log(p[r])] Die Entropie einer Quelle bezeichnet somit die sie charakterisierende Verteilung. Sie misst die Information, die man durch Beobachten der Quelle im Mittel gewinnen kann, oder umgekehrt die Unbestimmtheit, die über die erzeugten Nachrichten herrscht, wenn man die Quelle nicht beobachten kann. Anschauliche Beschreibung der Entropie Die Entropie gibt die Unsicherheit als Anzahl der notwendigen Ja / Nein-Fragen zur Klärung einer Nachricht oder eines Zeichens an. Hat ein Zeichen eine sehr hohe Auftrittswahrscheinlichkeit, so hat es einen geringen Informationsgehalt. Dies entspricht etwa einem Gesprächspartner, der regelmäßig mit ja antwortet. Diese Antwort lässt auch keine Rückschlüsse auf Verständnis oder Aufmerksamkeit zu. Antworten, die sehr selten auftreten, haben einen hohen Informationsgehalt. Extremwerte der Entropie Für Dokumente, die ausschließlich Großbuchstaben enthalten, ist die Entropie mindestens 0 bit/char (bei einem Dokument, das nur aus einem Zeichen besteht) und höchstens log(26) bit/char = 4,700440 bit/char (bei einem Dokument, in dem alle 26 Zeichen gleich oft vorkommen). Für Dokumente, die jedes Zeichen des Zeichensatzes (0 bis 255) enthalten können, ist die Entropie mindestens 0 bit/char (bei einem Dokument, das nur aus einem Zeichen besteht) und höchstens log(256) bit/char = 8 bit/char (bei einem Dokument, in dem alle 256 Zeichen gleich oft vorkommen). 4.2.5 Autokorrelation / Korrelation Autokorrelation[1] Die Autokorrelation eines Dokuments ist eine Kennzahl für die Ähnlichkeit von Teilen des Dokuments. Mit Hilfe der Autokorrelation kann unter Umständen die Schlüssellänge eines verschlüsselten Dokuments ermittelt werden. (z.B. bei Vigenère und Autokey) Die Autokorrelationsfunktion C(t) misst die Ähnlichkeit einer Folge (s[i]) = s[1]s[2]... und der um t Stellen verschobenen Folge (s[i + t]) = s[t]s[t + 1]... . Man betrachtet einen Folgenabschnitt der Länge n und definiert: A(t) := Anzahl der übereinstimmenden Glieder der Folgen (s[i]) und (s[i + t]) im betrachteten Abschnitt. D(t) := Anzahl der nicht übereinstimmenden Glieder der Folgen (s[i]) und (s[i + t]) im betrachteten Abschnitt. Die Autokorrelationsfunktion C(t) = A(t)−D(t) n . Im Falle von endlichen Folgen wird die Folge s (azyklisch) um t Positionen verschoben, das heißt die Folge (s[i + t]) hat nur n-t Folgenglieder (wenn n die Länge der Folge (s[i]) ist). Zur Berechnung der Autokorrelation betrachtet man nun die Folgen s[1]s[2]...s[n − t + 1] und s[t]s[t + 1]...s[n] und berechnet deren Korrelation. Die Autokorrelationsfunktion wird unter anderem bei der Ermittlung der Periodenlänge zur automatischen Analyse des Vigenère-Verschlüsselungsverfahrens und Verschlüsselung durch byteweise Addition und exklusives Oder benutzt. Siehe dazu das Kapitel Szenarien. 26 Korrelation[1] Die folgenden Aussagen über Korrelation gelten hier für eine unabhängige gleichverteilte Binärfolge: • Binärfolge heißt, dass die einzelnen Ereignisse der Zufallsfolge den Wert 1 oder 0 annehmen. • Unabhängig heißt, dass die Wahrscheinlichkeit für das Eintreffen des (n+1)-ten Ereignisses unabhängig von allen Werten der n vorherigen Ereignisse ist. • Gleichverteilt bedeutet für die Ereignisse der Zufallsfolge, dass die Wahrscheinlichkeit einer 0 gleich der Wahrscheinlichkeit einer 1 ist. Die Ähnlichkeit zweier Folgen wird üblicherweise durch ihre Korrelation gemessen. Die Korrelation C zweier Folgenabschnitte der Länge n berechnet sich als die Zahl A der übereinstimmenden und der Zahl D der nicht übereinstimmenden Folgenglieder nach der Formel: C := A−D n Der Erwartungswert für die Korrelation zweier unabhängiger Zufallsfolgen ist demnach also Null. Zwei Folgen, die häufiger übereinstimmen, haben dagegen einen positiven Korrelationswert. Im Grenzfall völliger Übereinstimmung ist A = n, D = 0 und daher C = 1. Umgekehrt erhält man bei weniger als n2 Übereinstimmungen eine negative Korrelation. Der Betrag der Korrelation zweier Folgen ist daher ein Maß für deren Abhängigkeit. 27 Teil III Anhang 28 Kapitel 5 Kurze Geschichte der Kryptographie Menschliche Schrift gibt es seit rund 6000 Jahren; seit über 3000 Jahren wird diese verschlüsselt. ca. ca. ca. ca. ca. ca. 1900 v.Chr. 1000 v.Chr. 600 v.Chr. 500 v.Chr. 200 v.Chr. 100 - 44 v.Chr. ca. 500 n.Chr. 855 n. Chr. 1412 1397 1466 1518 - 1400 Non-standard Zeichen Mesopotamien In Palästina werden Texte mit der Atbash verschlüsselt. Die Griechen verschlüsseln Nachrichten mit Hilfe der Skytale. Der Grieche Polybios beschreibt erstmals sein Polybios-System. Julius Cäsar schreibt vertrauliche Botschaften in dem nach ihm benannten Caesar-Code. Dies ist der bekannteste aller monoalphabetischen Algorithmen. In Europa beginnt die ¨Dunkle Zeit der Kryptographie¨, d.h. sie wurde der schwarzen Magie zugeordnet. In dieser Zeit ging viel Wissen über die Kryptographie verloren, im Gegensatz dazu blühte die Kryptographie im persischen Raum auf. Im arabischen Raum erscheint das erste Buch über Kryptologie. Abu Abd al-Raham al-Khahil ibn Ahmad ibn Amr ibn Tammam al Farahidi al-Zadi al Yahamadi beschreibt stolz in seinem Buch unter anderem die geglückte Entschlüsselung eines für den byzantinischen Kaiser bestimmten griechischen Codes. Eine 14-bändige arabische Enzyklopädie beschreibt auch kryptographische Methoden. Dabei wird neben der Substitution und der Transposition erstmals die Methode der mehrmaligen Substitution an einem Klartextzeichen erwähnt. Auf Wunsch Clemens des VII. erfindet Gabrieli di Lavinde die erste Nomenklatur (Nomenklatur-Code). Dieser Nomenklatur-Code wurde wegen seiner Einfachheit in den nächsten 450 Jahren vor allem in diplomatischen Kreisen verwendet. Leon Battista Alberti (1404 - 1472), einer der führenden Kräfte der italienischen Renaissance, veröffentlicht sein Buch ¨Modus scribendi in ziferas¨, in dem erstmals die von ihm erfundenen Chiffrierscheiben erwähnt werden. Albertis zahlreiche kryptologischen Leistungen beruhen auf der Tatsache, dass er Sekretär jener Behörde war, die sich an der römischen Kurie (päpstlicher Hof) mit Geheimschriften befasste. Er wird als ¨Vater der Kryptographie¨ bezeichnet. Im deutschsprachigen Raum erscheint das erste gedruckte Buch über Kryptologie. Der Verfasser ist Johannes Trithemius. 29 1586 1628 1700 1795 1854 1854 1857 1860 1883 1891 1917 1919 1921 1922 1923 1929 1941 1949 1973 1975 1976 1977 1978 Das Buch ¨Tractié de Chiffre¨ des französischen Diplomaten Blaise de Vigenère erscheint. Seine Verschlüsselungsmethode, die später nach ihm als Vigenère-Code benannt wurde, wird so der Öffentlichkeit zugänglich gemacht. Dieser Code ist der bekannteste unter allen polyalphabetischen Algorithmen. Antione Rissignol wird der erste vollzeitlich angestellte Kryptoanalytiker, nachdem seine Entschlüsselung einer feindlichen chiffrierten Botschaft die Belagerung Realmonts durch die Hugenotten beendete. Seitdem sind Kryptoanalytiker ein fester Bestandteil des militärischen Apparats. Der russische Zar benutzt eine große Code-Tabelle von 2000-3000 Silben und Worten zur Chiffrierung seiner Botschaften. Thomas Jefferson entwickelt den ersten Chiffrierzylinder namens ¨wheel cipher¨. Er benutzte sie aber nie, so dass sie in Vergessenheit geriet bzw. nie der Öffentlichkeit zugänglich wurde. Deshalb wurde der Chiffrierzylinder parallel zu Jeffersons an unterschiedlichen Orten nochmals erfunden. Der Engländer Charles Babbage erfindet einen Chiffrierzylinder, ähnlich der ¨wheel cipher¨. Der englische Physiker Charles Wheatstone erfindet eine Chiffre, die mit einer 5*5 Matrix arbeitet. Sein Freund Lord Lyon Playfair Baron von St. Andrews machte diese Chiffre in den höheren militärischen und diplomatischen Kreisen des viktorianischen Englands bekannt. Die Chiffre bekam so den Namen Playfair-Code. Beauforts Cipher Friedrich Kasiski und William F. Friedman entwickeln statistische Methoden zur Kryptoanalyse, die auch den bis dahin als unknackbar geltenden Vigenère-Code entschlüsseln. ¨La Cryptographie militaire¨ von Auguste Kerckhoff von Nieuwendhoff erscheint. Es gilt als Meilenstein in der Kryptographie der Telegraphenzeit. Beinhaltet die ¨Prinzipien von Kerckhoff¨ für die Kryptologie. Der französische Major Etienne Bazeries erfindet einen Chiffrierzylinder: sein Bazeries-Zylinder war der ¨wheel cipher¨ im Prinzip ähnlich. Der Amerikaner Gilbert S. Vernam entdeckt und entwickelt das ¨One Time-Pad¨. Magelin Maschinen Der Kalifornier Edward Hebern baut die erste Chiffriermaschine nach dem Rotor-Prinzip. Thomas Jeffersons ¨wheel cipher¨ wird in den USA entdeckt, von der US-Marine weiterentwickelt und fand so bis in den 2. Weltkrieg Anwendung. Vorstellung der vom deutschen Ingenieur Arthur Scherbius entwickelten Rotormaschine ¨Enigma¨ auf dem internationalen Postkongress. Mit der Gründung der ¨Chiffriermaschinen AG¨ vermarktet A. Scherbius seine Enigma in alle Welt. Hill-Chiffre Dekodierung der japanischen Angriffsmeldung für den 2. Weltkrieg (viele Historiker meinen, dass die Kryptologie im 2. Weltkrieg ein Jahr Krieg erspart hat). Shannon La Padula Diffie und Hellman zeigen, dass Public Key-Verfahren theoretisch möglich sind, obwohl sie das Gegenteil beweisen wollten. Diffie-Hellman Schlüsselaustausch Der ab 1975 von IBM entwickelte DES (Data Encryption Standard) wird zum Standardverfahren auserkoren. Das nach seinen Entwicklern Ronald Rivest, Adi Shamir und Leonard Adleman benannte RSA-Verfahren wird veröffentlicht. Es ist das erste praktisch einsetzbare Public Key-Verfahren und es gilt als innovativster Beitrag der kryptologischen Forschung unseres Jahrhunderts. 30 1985 1986 1990 1991 1997 10/2000 Goldwasser, Micali und Racoff stellen sog. Zero Knowledge-Verfahren vor (Blind Signatures). Unabhängig voneinander schlagen Neal Koblitz und Victor Miller vor, Elliptische Kurven im Bereich der Public Key-Kryptographie einzusetzen. Xueija Lai und James Massey entwickeln das IDEA-Verfahren, das z.B. in der Kryptologiesoftware PGP (Pretty Good Privacy) von Phil Zimmermann eingesetzt wird. DSA, eingeführt durch das NIST. Known-Plaintext-Attacke auf DES erfolgreich von EFF durchgeführt. Als AES (Advanced Encryption Standart) wird von NIST nach einem langen öffentlichen Ausschreibungsverfahren der Algorithmus Rijndael zum Nachfolger von DES gewählt. 31 Kapitel 6 Begriffe, Definitionen und Abkürzungen mod Kryptographie Krypt(o)analyse Kryptoanalytiker Angriff, Attacke Kryptologie Chiffre Chiffrierung Dechiffrierung Geheimtext Klartext Modulo, Operator für Restdivision ist die Wissenschaft von der Verschlüsselung von Daten. Ein Kryptograph entwickelt kryptographische Verfahren zur Verschlüsselung von Daten. beschäftigt sich mit der Analyse von verschlüsselten Daten. Das Ziel eines Kryptoanalytiker ist es, eine verschlüsselte Nachricht zu knacken. Er versucht Schwachstellen in einem kryptographischen System zu finden und diese für das ¨Knacken¨ des Verfahrens auszunutzen. (Angreifer) ist jemand, der versucht, ein kryptographisches System anzugreifen, z.B. mit Hilfe von Kryptoanalyse. Ein sog. ¨Angriff ¨ auf ein kryptographisches System bezeichnet ein Verfahren, mit dem Schwachstellen in diesem System ausgenutzt werden mit dem Ziel, eine verschlüsselte Botschaft zu entschlüsseln, d.h. lesbar zu machen (¨knacken¨). Angriffe sind das Ergebnis einer erfolgreichen Kryptoanalyse. vereinigt Kryptographie und Kryptoanalyse. Ein Kryptologe ist also auf beiden Gebieten tätig. Er entwickelt selbst kryptographie Algorithmen und führt Tests an anderen Verfahren durch. ist ein Synonym für ein Verschlüsselungsverfahren. ist ein Synonym für Verschlüsselung; damit kann aber auch ein Verschlüsselungs-Verfahren gemeint sein, kann also auch synonym zu Chiffre verwendet werden. ist ein Synonym für Entschlüsselung. ist das Resultat der Verschlüsselung. (auch Chiffrat, Geheimtext) der unverschlüsselte Text. 32 Kapitel 7 Sourcecode Datei: fkt_coder.php <? ######################################################## ## ## Bibliothek für Kodier und Dekodieralgorithmen ## Version 1.3, Marcel Brätz, 30.04.2004 ## ######################################################## ## Autokey-Chiffre v1.0, baut auf Vigenère-Chiffre auf ######################################################## function kodAutokey($orgtxt, $key, $alfa){ $key2 = $key.$orgtxt; $codtxt= kodieren($orgtxt, $key2, $alfa); return $codtxt; } function dekAutokey($codtxt, $key, $alfa){ $offset=strlen($key); $orgtxt=dekodieren(substr($codtxt,0,$offset), $key, $alfa); for ($t=$offset;$t<(strlen($codtxt));$t++){ $orgtxt.=dekodieren(substr($codtxt,$t,1), substr($orgtxt,$t-$offset,1), $alfa); } return $orgtxt; } ######################################################## ## Vigenère-Chiffre v1.0 ######################################################## function kodieren($orgtxt,$key,$alfa){ // Buchstabenweise Verchiebekodierung // monoalphabetisch bei Schlüssellänge 1 // sonst polyalphabetisch $laengetxt=strlen($orgtxt); $laengekey=strlen($key); for($t=0;$t<$laengetxt;$t=$t+1){ $keytxt .= substr($key,($t%$laengekey),1); } for($t=0;$t<$laengetxt;$t=$t+1){ $wertbuch = indexVonBuchstabe($alfa,substr($orgtxt,$t,1)); $wertkey = indexVonBuchstabe($alfa,substr($keytxt,$t,1)); $codtxt = $codtxt.buchstabeVonIndex($alfa,($wertbuch+$wertkey)%26); } 33 return $codtxt; } function dekodieren($codtxt,$key,$alfa){ // siehe kodieren $laengetxt=strlen($codtxt); $laengekey=strlen($key); for($t=0;$t<$laengetxt;$t=$t+1){ $keytxt .= substr($key,($t%$laengekey),1); } for($t=0;$t<$laengetxt;$t=$t+1){ $wertbuch = indexVonBuchstabe($alfa,substr($codtxt,$t,1)); $wertkey = indexVonBuchstabe($alfa,substr($keytxt,$t,1)); if ($wertbuch<$wertkey){ $wertbuch=$wertbuch+26; } $orgtxt = $orgtxt.buchstabeVonIndex($alfa,($wertbuch-$wertkey)%26); } return $orgtxt; } ######################################################## ## Funktionen zur Erzeugung neuer Alphabete ######################################################## function createMulAlfa($alfa, $key){ // erzeugt ein Alphabet auf für eine Multiplikative Chiffre for($t=0;$t<26;$t++){ $alfa2[$t]=buchstabeVonIndex($alfa,(indexVonBuchstabe($alfa,$alfa[$t])*$key)%26); } return $alfa2; } function rotieren($alfa, $key){ // Rotiert ein Alphabet for($t=0;$t<26;$t++){ $alfa2[$t]=buchstabeVonIndex($alfa,(indexVonBuchstabe($alfa,$alfa[$t])+$key)%26); } return $alfa2; } function substituiere($text, $alfa1, $alfa2){ // Algorithmus zur Umsetzung eines Textes aus einem Alphabet in ein anderes // dies ist eine Ersetzung des Zeichen aus alfa1 durch das Zeichen an der selben // Stelle in alfa2 $laengetxt=strlen($text); for($t=0;$t<$laengetxt;$t=$t+1){ $buchstabe = buchstabeVonIndex($alfa2, indexVonBuchstabe($alfa1,substr($text,$t,1))); $codtext = $codtext.$buchstabe; } return $codtext; } ######################################################## ## Hilfsfunktionen ######################################################## function indexVonBuchstabe($alfa,$letter){ // liefert den Index des Buchstaben aus dem verwendeten Alphabet // A..Z --> 0..25 for ($t=0;$t<sizeof($alfa);$t=$t+1){ if($letter==$alfa[$t]) { 34 return $t; break; } } } function buchstabeVonIndex($alfa,$index){ // liefert den Buchstaben aus dem verwendeten Alphabet // 0..25 --> A..Z return $alfa[$index]; } function getmstime(){ return (substr(microtime(),11,10)+substr(microtime(),0,10)); } function spacing($text, $zeichen){ if($zeichen<=1) {$zeichen=1;} for ($t=0;$t<strlen($text);$t++){ $text2.=substr($text,$t,1); if(($t+1)%$zeichen==0 && $t>0) {$text2.=" ";} } return $text2; } ?> Datei: fkt_decipher.php <? function prob($x,$y){ // rel Häufgkeit if($y==0) $y=-1; return ($x/$y); } function hauf($text){ // absolute Häufigkeiten der Buchstaben aus dem Alphabet global $alfa; $hauf=array(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0); for ($t=0;$t<strlen($text);$t++){ $zeichen = substr($text,$t,1); $index = indexVonBuchstabe($alfa,$zeichen); $hauf[$index] = ($hauf[$index]+1); } return $hauf; } function entropie($text){ // binärer Informationsgehalt $hauf = hauf($text); for ($t=0;$t<26;$t++){ $p=prob($hauf[$t],strlen($text)); if($p>0) { $z=$p*log($p)/log(2); }else{ $z=0; } $ent=($ent+$z); } $ent=(-$ent); return $ent; } function koinzidenzIndex($text){ 35 //wahrscheinlichste Keylänge aus Häufigkeiten der Buchstaben im Text $kappa=0; $n=strlen($text); $hauf = hauf($text); for ($t=0;$t<26;$t++){ $kappa = ( $kappa + ( $hauf[$t] * ( $hauf[$t] - 1 ) ) ); } if($n!=0) $kappa = ( $kappa / ( $n * ( $n - 1 ) ) ); $ki = ( .0377 * $n / ( ($n-1) * $kappa - .0385 * $n + .0762 ) ); return $ki; } function str_splitt($text){ for($t=0;$t<strlen($text);$t++){ $arr[$t]=substr($text, $t, 1); } return $arr; } function akt($text){ // Autokorellation liefert Mustertreffer global $ungefiltert; $arr1=str_splitt($text); $arr2=@array_fill(0,sizeof($arr1),0); for($t=0;$t<sizeof($arr1);$t++){ $summe=0; for($u=0;$u<sizeof($arr1);$u++){ if( $arr1[$u]==$arr1[($u+$t)%(sizeof($arr1))] ){ $summe++; } } $arr2[$t]=$summe; } $am=@array_sum($arr2)/sizeof($arr2); for($t=0;$t<sizeof($arr2);$t++){ if($arr2[$t]>3*$am && !$ungefiltert) $arr2[$t]=4*$am; } return $arr2; } function ak_akt($text, $siz){ $n=strlen($text)/$siz; for ($t=0;$t<$n;$t++){ $z=($t*$siz); $txt=substr($text, $z, $siz); $arr_tmp=akt($txt); if(is_array($arr2)){ for ($x=0;$x<sizeof($arr_tmp);$x++){ $arr2[$x]=$arr2[$x]+$arr_tmp[$x]; } }else{ $arr2=$arr_tmp; } } return $arr2; } function filterakt($arr2){ // gute Werte filtern 36 global $schw1; global $schw2; $am=@array_sum($arr2)/sizeof($arr2); for($t=0;$t<sizeof($arr2);$t++){ switch((($arr2[$t]-$am*$schw1))>=$schw2){ case 1: $wert=100;break; default: $wert=0;break; } $arr[]=$wert; } return $arr; } function showakt($arr2,$height,$part,$width,$space,$ab){ // Trefferspektrum anzeigen global $schw1; global $schw2; echo "<center><table border=0 cellspacing=0 cellpadding=0>"; echo "<tr><td valign=bottom>"; $am=@array_sum($arr2)/sizeof($arr2); for($t=0;$t<sizeof($arr2)/$part;$t++){ // nur die Hälfte des spektrums nötig... // weil Spiegelsymmetrisch $part=2; if($t>=$ab){ if(($arr2[$t]-$schw2)>($am*$schw1)){ echo "<img src=image/bar2.gif width=$width height="; echo round($arr2[$t]/max(array_slice($arr2,1,sizeof($arr2)-2))*$height,0).">"; }else{ echo "<img src=image/bar.gif width=$width height="; echo round($arr2[$t]/max(array_slice($arr2,1,sizeof($arr2)-2))*$height,0).">"; } if($space>0) echo "<img src=image/bar.gif width=$space height=0>"; } } echo "</td></tr>"; echo "<tr><td valign=bottom>"; echo "</td></tr>"; echo "</table></center>"; } function gzt($n){ // Alle ganzzahligen Teiler $t=1; $i=0; while($t<=$n){ if(($n%$t)==0){ $liste[] = $t; $i++; } $t++; } return $liste; } function keylen($arr){ // Keylänge ermitteln (häufigster Abstand des Spektrums, Modus) $pos=0; for($t=0;$t<sizeof($arr)/2;$t++){ if($arr[$t]>0) { 37 $tmp[$t-$pos]++; $pos=$t; } } $arr2=@array_fill(0,sizeof($tmp),0); return (@array_search(@max($tmp),$tmp)); } function trennen($text, $num){ // Codetext in monoalphabetische Buchstabenmengen aufteilen $txt=str_splitt($text); for($t=0;$t<sizeof($txt);$t++){ $strngs[$t%$num]=$strngs[$t%$num].$txt[$t]; } return $strngs; } function findrot($text){ // Alphabetverschiebung finden global $AP; global $alfa; $VX=varianz($AP[de]); $SX=sqrt(varianz($AP[de])); $sp=hauf($text); $sps=array_sum($sp); for ($t=0;$t<sizeof($sp);$t++){ $sp[$t]=round($sp[$t]/$sps*100,2); } for ($t=0;$t<sizeof($sp);$t++){ for ($u=0;$u<sizeof($sp);$u++){ $sp2[$u]=$sp[($t+$u)%sizeof($sp)]; } $VY=varianz($sp2); $SY=sqrt(varianz($sp2)); $cov=covarianz($AP[de], $sp2); $r[$t]=abs($cov/sqrt($VX*$VY)); } $b=array_search(max($r),$r); return $b; } function findpw($text, $pwl){ // Schlüsselwort ermitteln global $alfa; $texte = trennen($text, $pwl); for($t=0;$t<sizeof($texte);$t++){ $rot[$t]=findrot($texte[$t]); $pass=$pass.buchstabeVonIndex($alfa, $rot[$t]); } return $pass; } function findpw_ak($text, $pwl){ // Schlüsselwort ermitteln für Autokey global $alfa; global $AP; $texte = trennen($text, $pwl); for($t=0;$t<sizeof($texte);$t++){ unset($arr); 38 for ($u=0;$u<sizeof($alfa);$u++){ $arr[]=koinzidenzIndex(dekAutokey($texte[$t],$alfa[$u],$alfa)); } echo "<br>"; $y[$t][0]=array_search(min($arr),$arr); echo $alfa[$y[$t][0]].$y[$t][0]." "; $arr2=array_merge(array_slice($arr, 0, $y[$t][0]-1), array_slice($arr, $y[$t][0]+1, sizeof($arr))); $y[$t][1]=array_search(min($arr2),$arr2); if($y[$t][1]>=$y[$t][0]) $y[$t][1]++;$y[$t][1]++; echo $alfa[$y[$t][1]].$y[$t][1]; $rot1=abs(13-findrot(dekAutokey($texte[$t],$alfa[$y[$t][0]],$alfa))); $rot2=abs(13-findrot(dekAutokey($texte[$t],$alfa[$y[$t][1]],$alfa))); echo " ".$rot1." ".$rot2; if($rot1==13){ $letter=$alfa[$y[$t][0]]; } if($rot2==13) { $letter=$alfa[$y[$t][1]]; } $pass=$pass.$letter; } return $pass; } function varianz($arr){ $x=mittelwert($arr); for ($t=0;$t<sizeof($arr);$t++){ $n=$arr[$t]; $m=(($n-$x))*(($n-$x)); $summe=$summe + $m; } return ($summe/sizeof($arr)); } function covarianz($arr, $arr2){ if (sizeof($arr)!=sizeof($arr)){ return "error"; }else{ $x=mittelwert($arr); $y=mittelwert($arr2); for ($t=0;$t<sizeof($arr);$t++){ $summe=$summe+($arr[$t]-$x)*($arr2[$t]-$y); } return $summe/sizeof($arr); } } function mittelwert($arr){ for ($t=0;$t<sizeof($arr);$t++){ $summe=$summe+$arr[$t]; } return $summe/sizeof($arr); } ?> 39 Literaturverzeichnis [1] Skript zu CrypTool 1.3.04 (Stand Aug. 2003) Technische Universität Darmstadt, Universität Siegen, Deutsche Bank http://www.cryptool.de/ [2] Facharbeit zum Thema Kryptographie von Daniel Faber (Stand Dez. 2002) http://daniel-faber.org/schule/facharbeit/ [3] Angewandte Kryptographie von W. Ertel (2001 Fachbuchverlag Leipzig) http://www.fh-weingarten.de/˜ertel/kryptobuch.html [4] Famous Unsolved Codes and Ciphers http://www.elonka.com/UnsolvedCodes.html [5] Kryptographiespielplatz http://www.mbraetz.de/ (Stand Mai 2004) [6] Geheime Botschaften von Simon Singh http://www.simonsingh.net/ [7] CryptoLounge - Offlineversion (Stand Feb. 2002) http://cryptolounge.cjb.net/ [8] http://www.und.nodak.edu/org/crypto/crypto/ [9] http://www.wikipedia.de/ [10] http://encyclopedia.thefreedictionary.com/Autokey%20cipher [11] http://codebreaker.dids.com/index.htm [12] http://www.deutsches-museum.de/ausstell/meister/enigma.htm 40 Abbildungsverzeichnis 2.1 2.2 2.3 Schema der Vigenère-Chiffre [5] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Schema der Autokey-Chiffre [5] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Collossus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1 3.2 3.3 Häufigkeitsanalyse und Diagramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Autokorrelation vigenère-verschlüsselter Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Autokorrelation autokey-verschlüsselter Text . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 41 Tabellenverzeichnis 2.1 Vigeneré-Quadrat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.1 4.2 4.3 Häufigkeitstabelle für Buchstaben in deutschen Texten[2] . . . . . . . . . . . . . . . . . . . . . . 22 Häufigkeitstabelle für Bigramme in deutschen Texten[2] . . . . . . . . . . . . . . . . . . . . . . . 22 Buchstaben-Rangfolge verschiedenener Sprachen[8] . . . . . . . . . . . . . . . . . . . . . . . . . . 22 42 Index Additive Chiffren, 4 ADFGVX-Cipher, 6 Alberti, Leon Battista, 10 Angriff, 32 Autokey-Chiffre, 10, 12, 14 ROT13, 5 Beale-Chiffre, 7 Bigramme, 13 Tauschchiffren, 6 Schwarze Kammern, 10 Skytale, 6 Substitutive Chiffre, 7 Vigenère, Blaise de, 10 Vigenère-Chiffre, 10, 11, 14, 20 Vigenère-Quadrat, 11 Caesar-Chiffre, 4 Chiffre, 32 Chiffretext, 32 Chiffrierung, 32 Wheatstone, Charles, 13 Zimmermann-Chiffre, 14 Dechiffrierung, 32 Enigma, 15 Firedman-Test, 24 Friedman-Test, 19 Große Chiffre, 7 Häufigkeitsanalyse, 23 homophone Chiffren, 9 Kasiski-Test, 19, 23 Klartext, 32 Kryptoanalyse, 18, 32 Kryptoanalytiker, 32 Kryptographie, 32 Kryptographiespielplatz, 13 Kryptologie, 32 Le Chiffre indechiffrable, 10 Mann mit der eisernen Maske, 8 Modulo, 5, 32 monoalphabetische Chiffren, 4 Morse-Code, 7 Multiplikative Chiffre, 5 Mustersuche, 19 One-Time-Pad, 13 Play-Fair-Chiffre, 13 polyalphabetische Chiffren, 9 Rossignol, Antoine und Boneventure, 8 43