| Kasiski-Test |
|
|
Letztmalig dran rumgefummelt: 18.02.19 19:39:12 |
 |
Jahrtausende lang war die Cäsr'sche Verschlüsselung ein hinreichend starker Chiffre - einfacher Schlüssel, leicht austauschbar und nicht komplexes Verfahren zur Chiffrierung und Dechiffrierung. und doch lag seine Schwäche buchstäblich auf der Hand. Selbst wenn Füllzeichen verwendet wurden, war eine statistische Häufigkeitsanalyse der Schlüssel zum Knacken des Codes. Diese Häufigkeit zu verwischen kam als Anliegen erstmalig im Italien der Renaissance auf - Intrigen und Missgunst, Verdachtsmomente und die große europäische Politik beförderten die Notwendigkeit nach tiefgründigerer Chiffrierung ohne wiederkehrende Häufigkeit der nach bekannter Verteilung vorkommenden Buchstaben des Alphabets. | ||||||
 |
|
||||||
|
1. Friedrich Kasisiki 2. Kasiski-Kreuz auf das Schlüsselwort "GELB" 3. Entschlüsseln eines Cyphertextes mit dem (Babbage) Kasiski-Test 4. Ein weiteres Praktisches Beispiel 5. Friedmann-Test und Koinzidenz-Index 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 |
||||||
|
Obwohl diese wirkungsvolle Methode zur Analyse polyalphabetischer Algorithmen zuerst von Kasiski veröffentlicht wurde, muss man erwähnen, dass der englische Mathematiker Charles Babbage (1792 - 1871), der unter anderem berühmt ist für seine Konzeption eines Vorgängers des modernen Computers, umfangreiche, allerdings unveröffentlichte Untersuchungen über Kryptographie durchgeführt hat. Insbesondere hatte er den Kasiski-Test bereits 1854 entwickelt, also neun Jahre vor Kasiski. Für eine detaillierte Darstellung siehe unten. |
| 1. Friedrich Kasiski und Charles Babage |
|
|
 |
|
Friedrich Kasiski wurde im November 1805 in
Westpreußen geboren und trat im Alter von 17 Jahren in ein ostpreußisches
Infanterieregiment ein. Er machte eine Militärkarriere; als er sich 1852 aus
dem aktiven Dienst zurückzog, war er Major. Obwohl er sich beim Militär für
die Kryptologie interessiert hatte, schrieb er seine Ideen erst nach 1860
nieder. 1863 erschien sein "Bändchen Die Geheimschriften und die
Dechiffrierkunst". Der Inhalt galt weitgehend der Lösung polyalphabetischer
Chiffren mit periodischen Schlüsselwörtern, einem Problem, mit dem sich Kryptologen seit Jahrhunderten herumgeschlagen hatten. Obwohl die
Veröffentlichung kaum beachtet wurde, gilt sie bei Historikern als wichtiger
Beitrag für die Kryptologie. |
||||||
|
Ziel des Tests · Hilfe zur Entschlüsselung von Texten, die mit Vigenère-Chiffre verschlüsselt sind · dient zur Bestimmung der Schlüssellänge Historische Einordnung · 1854 Entschlüsselung eines Vigenère-Textes durch Charles Babbage (keine Veröffentlichung) · 1863 veröffentlicht Friedrich Wilhelm Kasiski (preußischer Infanteriemajor) das Verfahren Funktion · gegeben ist ein Vigenère-verschlüsselter Text · Untersuchung nach Buchstabenfolgen (von 3 Buchstaben oder länger), die mehrmals auftreten · Bestimmung des Abstands zwischen der Folge (vom ersten Buchstaben der ersten Folge bis einschließlich dem ersten Buchstaben der zweiten Folge) · eine Liste von natürlichen Zahlen entsteht → Primzahlzerlegung · am häufigsten auftauchende Primzahl ist vermutlich Schlüssellänge oder Vielfaches der Schlüssellänge · Nachteil: zufällige Wiederholungen können auftreten, die vom Computerprogramm nicht erkannt werden, mein Programm arbeitet nur mit 3-er-Blöcken Beispiel
→ Im Chiphertext erhalten wir zwei Buchstabenfolgen von je 4 Buchstaben. Diese Häufung kann zufällig auftreten (bei kurzen Buchstabenfolgen häufig der Fall) oder kann auf ein gleiches Wort schließen lassen (wahrscheinlicher). Folgenabstand: 15 Länge des Keywords: 5 → Da Fünf ein Vielfaches von 15 ist, wird der Text mit den gleichen Buchstaben verschlüsselt, was zur Entstehung des gleichen Chiphertextes führt. Dieses Prinzip macht sich der Kasiski-Test zunutze und kann so eine ungefähre Schlüssellänge bestimmen. |
| 2. Kasiski-Kreuz auf das Schlüsselwort "GELB" |
|
|
|
|
|
Hier wird nicht mehr jedes Zeichen einzeln durch ein gleiches ersetzt, sondern eine Schlüssel- oder Codewortfolge wird zur Chiffrierung sowie natürlich auch zu deren Dechiffrierung herangezogen. Damit ist die Ersetzung nicht mehr mono-, sondern eben polyalphabetisch. |
|
Die meisten Kryptoanalytiker
hatten inzwischen die Hoffnung aufgegeben, die Vigenere-Verschlüsselung zu
brechen, doch ein Briefwechsel mit einem Zahnarzt aus Bristol regte Babbage
dazu an, es selbst zu versuchen. John Hall Brock Thwaites, in Sachen
Kryptographie mit Vorwissen nicht all zu sehr belastet, behauptete 1854,
eine neue Verschlüsselungsmethode entdeckt zu haben, die allerdings der
Vigenere-Verschlüsselung entsprach. Er schrieb an das Journal of the Society
of Arts mit der Absicht, seine Idee patentieren zu lassen, offenbar ohne zu
wissen, daß er mehrere Jahrhunderte zu spät kam. Babbage teilte der
Gesellschaft mit, die Verschlüsselung sei »sehr alt und findet sich in den
meisten Büchern«. Thwaites war empört und forderte Babbage heraus, seine
Verschlüsselung zu knacken. Ob dies möglich war, hatte zwar nichts mit der
Frage zu tun, ob sie neu war, doch Babbages Neugier war jetzt angestachelt,
und er machte sich auf die Suche nach einem Schwachpunkt in der
Vigenere-Verschlüsselung. Eine schwierige Verschlüsselung zu knacken ist vergleichbar mit dem Aufstieg an einer glatten Felswand. Der Kryptoanalytiker sucht nach jeder Unebenheit, nach jedem Spalt, die den kleinsten Halt bieten könnten. Bei einer monoalphabetischen Verschlüsselung stützt er sich auf die Häufigkeit der Buchstaben, denn die häufigsten Lettern wie e, n und i werden ins Auge fallen, wie sie auch verkleidet sein mögen. Bei der polyalphabetischen Vigenere-Verschlüsselung sind die Häufigkeiten stark ausgeglichen, da ja anhand des Schlüsselworts zwischen den Alphabeten hin und her gewechselt wird. Auf den ersten Blick scheint die Felswand daher vollkommen glatt. Wie wir schon wissen, besteht die große Stärke der VigenereVerschlüsselung darin, dass der gleiche Buchstabe auf verschiedene Weise chiffriert wird. Wenn das Schlüsselwort zum Beispiel GELB ist, kann jeder Buchstabe im Klartext auf vier verschiedene Weisen verschlüsselt werden, denn das Schlüsselwort enthält vier Buchstaben. Jeder Buchstabe des Schlüsselworts verweist auf ein anderes Geheimtextalphabet der Vigenere-Tafel, wie Tabelle unten zeigt. Ich habe die Spalte e hervorgehoben, um zu verdeutlichen, dass dieser Buchstabe unterschiedlich verschlüsselt wird, je nachdem, welcher Buchstabe des Schlüsselworts das Geheimtextalphabet festlegt: |
|
Vigenère-Kreuz für "E" - hier angewandt auf das Schlüsselwort "GELB" E kann verschlüsselt werden auf: F, I, K oder P |
|
Auf die gleiche Weise werden ganze Wörter unterschiedlich verschlüsselt - das Wort die könnte als JMP, EOI, OJK und HTF verschlüsselt werden, je nach seiner Stellung zum Schlüsselwort. Zwar erschwert dies die Entschlüsselung erheblich, doch ist sie nicht unmöglich. Der entscheidende Punkt ist folgender: Wenn es nur vier Möglichkeiten gibt, das Wort die zu verschlüsseln, und in der ursprüngliche Nachricht das Wort die mehrmals auftaucht, dann ist es höchst wahrscheinlich, dass einige der vier möglichen Verschlüsselungen im Geheimtext wiederholt auftauchen. Dies zeigt das folgende Beispiel, in dem der Text »die Lilie, die Rose und die Tulpe« anhand der Vigenere-Tafel mit dem Schlüsselwort GELB verschlüsselt wurden: |
|
|
|
Schlüsselwort GELBGELBGELBGELBGELBGELBGE Klartext dieliliedieroseunddietulpe Geheimtext
JMPMOPTFJMPSUWPVTHOJKXFMVI Das Wort die wird
beim ersten und beim zweiten Mal mit JMP, beim dritten Mal mit OJK
verschlüsselt. Der Grund für die Wiederholung von JMP ist, dass das zweite
die um acht Buchstaben gegenüber dem ersten die verschoben ist, und acht ist
ein Vielfaches der Länge des Schlüsselworts, das vier Buchstaben lang ist.
Anders gesagt, das erste die wurde nach seiner Stellung zum Schlüsselwort
chiffriert, und wenn wir zum zweiten die gelangen, ist das Schlüsselwort
genau zweimal umgelaufen, es ergibt sich exakt dieselbe Stellung des die,
und die Verschlüsselung wird wiederholt. Babbage erkannte, dass ihm diese Art der Wiederholung genau den Ansatzpunkt lieferte, den er brauchte, um die Vigenere-Verschlüsselung zu knacken. Es gelang ihm mit einigen recht einfachen Schritten, die jeder Kryptoanalytiker nachvollziehen konnte, die vermeintlich unentzifferbare Chiffre zu brechen. Ein Beispiel mag zeigen, wie dieses pfiffige Verfahren funktioniert. |
|
eine Vigenere-Tafel, bei der das Schlüsselwort GELB verwendet wird. Für den Buchstaben e ergeben sich vier Verschlüsselungsvarianten, F, I, K und P. |
| 3. Entschlüsseln eines Cyphertextes mit dem (Babbage) Kasiski-Test |
|
|
|
|
|
Das Vignère-Quadrat ist bis heute eine grundsätzlichen Tabellen der Chiffre-Technik und meint damit sowohl den Vorgang des Chiffrierens, als auch den Prozess des Dechiffrierens. Grundsätzlich bezieht es sich auf die Zahl 26 - ebenfalls eine Basisgröße der Chiffre-Technik. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Stellen wir uns vor, wir hätten die verschlüsselte Botschaft nach der Tabelle unten abgefangen. Wir wissen, dass es sich diesmal um einen englischen Text handelt, der mit dem Vigenere-Verfahren chiffriert wurde, doch wir haben keine Ahnung, um was es im Klartext geht, und auch das Schlüsselwort kennen wir nicht. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
der Geheimtext, verschlüsselt mit dem Vigenere-Verfahren |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
WUBEF IQLZU RMVOF EHMYM WTIXC GTMPI FKRZU PMVOI RQMMW OZMPU LMBNY VQQQM VMVJL EYMHF EFNZP SDLPP SDLPE VQMWC XYMDA VQEEF IQCAY TQOWC XYMWM SEMEF CFWYE YQETR LIQYC GMTWC WFBSM YFPLR XTQYE EXMRU LUKSG WFPTL RQAER LUVPM VYQYC XTWFQ LMTEL SFJPQ EHMOZ CIWCI WFPZS LMAEZ IQVLQ MZVPP XAWCS MZMOR VGVVQ SZETR LQZPB JAZVQ IYXEW WOICC GDWHQ MMVOW SGNTJ PFPPA YBIYJ UTWRL QKLLL MDPYV ACDCF QNZPI FPPKS DVPTI DGXMQ QVEBM QALKE ZMGCV KUZKI ZBZLI UAMMVZ |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Die erste Stufe der Kryptoanalyse von Babbage besteht darin, nach
Buchstabenfolgen zu suchen, die mehr als einmal im Geheimtext vorkommen.
Solche Wiederholungen können auf zwei Weisen zustande kommen. Am
wahrscheinlichsten ist, dass dieselben Buchstabenfolgen im Klartext mit
demselben Teil des Schlüssels chiffriert wurden. Zudem kommt es in seltenen
Fällen vor, dass zwei verschiedene Buchstabenfolgen im Klartext mit
verschiedenen Teilen des Schlüsselworts chiffriert wurden und zufällig
identische Folgen im Geheimtext ergeben haben. Wenn wir uns auf längere
Folgen beschränken, dann schließen wir diese zweite Möglichkeit weitgehend
aus, und im folgenden Beispiel berücksichtigen wir nur Wiederholungen, die
aus mindestens vier Buchstaben bestehen. In Tabelle 6 sind diese
Wiederholungen aufgelistet, zusammen mit den Abständen zwischen ihnen. Zum
Beispiel taucht die Folge E-F-I-Q in der ersten Zeile des Geheimtextes auf
und wiederholt sich 95 Buchstaben später. Das Schlüsselwort dient nicht nur dazu, den Klartext in Geheimtext zu verwandeln, auch der Empfänger braucht es, um den Geheimtext wieder in Klartext zu übersetzen. Wenn wir also das Schlüsselwort ausfindig machen könnten, wäre es ein leichtes, den Text zu entziffern. Bislang wissen wir noch nicht genug, um das Schlüsselwort herauszufinden, doch Tabelle 6 liefert einige gute Hinweise auf seine Länge. Auf der linken Seite der Tabelle sind die Wiederholungen und die jeweiligen Zwischenräume aufgelistet, auf der rechten Seite stehen die Teiler dieser Zwischenräume - die Zahlen, mit denen sich die Zahl der zwischen liegenden Buchstaben ohne Rest teilen lässt. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Wiederholungen und Abstände zwischen Wiederholungen im Geheimtext |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Zum Beispiel wiederholt sich die Folge W-C-X-Y M nach 20 Buchstaben und die
Zahlen 1, 2, 4, 5,10 und 20 sind Teiler, weil sich 20 ohne Rest durch sie
teilen lässt. Diese Teiler lassen auf sechs Möglichkeiten schließen:
Die erste Möglichkeit kann ausgeschlossen werden, weil ein Schlüsselwort,
das nur aus einem Buchstaben besteht, nichts anderes bewirkt als eine
monoalphabetische Verschlüsselung - für sie würde immer nur eine Zeile des
Vigenere-Quadrats verwendet, und das Geheimtextalphabet bliebe unverändert.
Unwahrscheinlich, dass ein Kryptograph dies tun würde. Alle anderen
Möglichkeiten werden mit einem Häkchen in der entsprechen den Spalte von
Tabelle oben angezeigt. Jedes Häkchen verweist auf eine mögliche
Schlüsselwortlänge. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
An diesem Punkt rufen wir uns in Erinnerung, dass jedes Geheimtextalphabet
im Vigenere-Quadrat ein Alphabet ist, das um einen Wert zwischen 1 und 26
Stellen verschoben ist. Daher sollte die obige Häufigkeitsverteilung
ähnliche Merkmale wie die für das Klaralphabet aufweisen, nur eben um einige
Stellen verschoben. Indem wir die B1-Verteilung mit dem
Klaralphabet vergleichen, sollte es möglich sein, die Verschiebung zu
erschließen. Abbildung unten zeigt die erwartete Häufigkeitsverteilung für
einen englischen Text mit 74 Buchstaben, dieselbe Menge wie in der
Textprobe, die in Abbildung oben ausgewertet ist. Die Normalverteilung weist Spitzen, Plateaus und Täler auf, und um sie mit der Verteilung des B1-Geheimtextes gleichzusetzen, suchen wir nach der auffälligsten Merkmalskombination. Zum Beispiel bilden die drei Spitzen R-S-T in der Normalverteilung und das breite Tal rechts davon, das sich von U bis nach Z erstreckt, ein sehr auffälliges Merkmalspaar. Die einzigen ähnlichen Merkmale in der B1-Verteilung sind die drei Spitzen bei V-W-X, gefolgt von dem Tal, das sich sechs Buchstaben weit von Y nach D erstreckt. Dies würde entweder darauf schließen lassen, dass alle Buchstaben, die mit B, verschlüsselt wurden, um vier Stellen verschoben sind, oder dass B1ein Geheimtextalphabet darstellt, das mit E, F, G, H ... beginnt. Dies wiederum bedeutet, dass der erste Buchstabe des Schlüsselworts, B1 wahrscheinlich E lautet. Diese Annahme können wir überprüfen, indem wir die B1-Verteilung um vier Buchstaben zurück verschieben und sie mit der Normalverteilung vergleichen. Abbildung 15 zeigt beide Verteilungen zum Vergleich. Die Übereinstimmung zwischen den Spitzenwerten ist tatsächlich sehr deutlich, und daher können wir mit einiger Sicherheit davon ausgehen, dass das Schlüsselwort mit E beginnt. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
die B1-verteilung um vier Stellen nach links verschoben, verglichen mit der Normalverteilung im Englischen |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Fassen wir das Bisherige zusammen. Die Suche nach Wiederholungen im
Geheimtext hat es uns ermöglicht, die Länge des Schlüsselworts, nämlich fünf
Buchstaben, herauszufinden. Dies wiederum ermöglichte uns, den Geheimtext in
fünf Teile aufzulösen, deren jeder gemäß einer monoalphabetischen
Substitution verschlüsselt wurde, die durch einen bestimmten Buchstaben des
Schlüsselworts festgelegt ist. Wir haben den Teil des Geheimtextes
analysiert, der nach dem ersten Schlüsselbuchstaben chiffriert wurde, und
wir konnten zeigen, dass dieser Buchstabe, B1 wahrscheinlich E lautet.
Diesen Schritt wiederholen wir nun, um den zweiten Buchstaben des
Schlüsselworts zu finden. Wir erstellen eine Häufigkeitstabelle für den
2-ten, 7-ten, 12-ten, 17-ten ... Buchstaben im Geheimtext. Wiederum
vergleichen wir das sich ergebende Häufigkeitsgebirge (siehe Abbildung
unten) mit der Normalverteilung, um die Verschiebung zu erschließen. Diese Verteilung ist schwerer zu analysieren. Für die drei benachbarten Spitzenwerte, die R-S-T entsprechen, gibt es auf den ersten Blick keine Kandidaten. Allerdings zeichnet sich deutlich ein Tal von G nach L ab, das wahrscheinlich dem Tal entspricht, das sich in der Normalverteilung von U nach Z erstreckt. Wenn dies der Fall wäre, würden wir die drei Spitzen R-S-T bei D, E und F erwarten, doch die Spitze beim Geheimbuchstaben E fehlt. Probehalber betrachten wir diesen fehlenden Spitzenwert als statistischen Ausrutscher und folgen unserem ersten Eindruck, dass die Senke von G bis L ein auffälliges Merkmal ist, das auf eine Verschiebung hindeutet: Alle Buchstaben, die nach B2 verschlüsselt wurden, wären danach um zwölf Stellen verschoben worden. Das hieße, B2 legt ein Geheimtextalphabet fest, das mit M, N, O, P beginnt. Der zweite Buchstabe des Schlüsselworts wäre also M. Wir können diese These wiederum überprüfen, indem wir die B2-Verteilung um 12 Buchstaben zurück verschieben und sie mit der Normalverteilung vergleichen. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Ab hier soll die Analyse nicht weiter verfolgt werden - es mag genügen zu sagen,
dass die Auswertung des 3-ten, 8-iten, 13-ten usw. Buchstabens ergibt, dass
der dritte Buchstabe des Schlüsselworts I lautet, die Auswertung des 4-ten,
9-ten, 14-ten usw. Buchstabens, dass der vierte Buchstabe L lautet, und die
Analyse des 5-ten, 10-ten, 15-ten usw. Buchstabens schließlich ergibt, dass
der fünfte Buchstabe Y lautet. Das Schlüsselwort ist EMILY Der erste
Buchstabe des Geheimtextes ist W, verschlüsselt nach dem ersten Buchstaben
des Schlüsselworts, nämlich E. Wenn wir die Verschlüsselung vom Ende her
aufdröseln, verfolgen wir zunächst die Zeile des Vigenere-Quadrats, die mit
E beginnt, bis wir zum W gelangen, dann gehen wir in der entsprechenden
Spalte nach oben. Am Anfang der Spalte finden wir den Buchstaben s, und er
muss der erste Buchstabe des Klartexts sein. Wir wiederholen diesen Vorgang
und sehen, dass der Klartext mit sittheedownandhavenoshamecheekbyjowl ...
beginnt. Fügen wir sinnvolle Wortzwischenräume und Satzzeichen ein, dann
bekommen wir: Sit thee down, and haue no shame, Let me screw thee up a peg: Thou shalt not be saved by works: Fill the cup, and fill the can: Lasst mich eine Flasche öffnen: Nicht erlösen werden Euch gute Taten: Füllt den Krug, füllt den Becher: Dies sind Strophen aus einem Gedicht von Alfred Tennyson mit dem Titel »The
Vision of Sin«. Wie es sich fügt, ist das Schlüsselwort der Name von
Tennysons Frau, Emily Sellwood. Ich habe einen Ausschnitt aus diesem Gedicht
als Beispiel für eine Kryptoanalyse gewählt, weil es Anlass zu einem
interessanten Briefwechsel zwischen Babbage und dem großen Dichter war.
Babbage, den eifrigen Statistiker und Fachmann für Sterblichkeitstabellen,
störten die Zeilen »Jeden Augenblick stirbt ein Mensch, jeden Augenblick
wird ein Mensch geboren«. So erbot er sich, Tennysons »ansonsten
wunderschönes« Gedicht zu korrigieren: |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 4. Ein weiteres Praktisches Beispiel |
|
|
|
|
|
Der Kasiski-Test beruht auf folgender Idee: Wenn im Klartext zwei Folgen aus gleichen Buchstaben auftreten (zum Beispiel zweimal das Wort ein), so werden im Allgemeinen die entsprechenden Folgen im Geheimtext verschieden ausfallen; denn schon der jeweils erste Buchstabe der beiden Folgen wird in der Regel verschieden verschlüsselt. Wenn aber die beiden Anfangsbuchstaben der Folgen mit Hilfe desselben Schlüsselwortbuchstabens verschlüsselt werden, so sind die beiden Geheimtextbuchstaben gleich. In diesem Fall werden auch die jeweils zweiten Buchstaben der Klartextfolgen mit demselben Schlüsselwortbuchstaben verschlüsselt; also ergeben sich auch im Geheimtext die gleichen Buchstaben. Das heißt also: Wenn die beiden Anfangsbuchstaben der Klartextfolgen mit demselben Schlüsselwortbuchstaben verschlüsselt werden, so bestehen die entsprechenden Geheimtextfolgen aus den gleichen Buchstaben. | |||||||||||||||
|
Kasiski-Test (Bestimmen der Schlüsselwortlänge): Man sucht gleiche Folgen im Geheimtext und bestimmt deren Abstand. Dieser ist (vermutlich) ein Vielfaches der Schlüsselwortlänge. | |||||||||||||||
|
Mit heutigen Methoden kann auch ein Vigenere-chiffrierter Text geknackt werden. Denn ein genügend langer Geheimtext weist viele statistisch erfassbare Regelmäßigkeiten auf, die es einem ermöglichen, das Schlüsselwort zu erschließen. Der erste veröffentlichte Angriff stammt von dem preußischen Infanteriemajor Friedrich Wilhelm Kasiski (1805 - 1881), der diesen 1863 publiziert hat. | |||||||||||||||
|
Angenommen, Mr. X (unser Angreifer) hat den
folgenden Text abgefangen, von dem er weiß oder vermutet, dass er
Vigenere-chiffriert ist: EYRYC FWLJH
FHSIU BHMJO UCSEG FMWVZ TYOIS UUIIS ECIZV SVXVF FBVVB ECLIS SUVSS JNRZQ INKVG Ein Geheimtext, der mit der Methode von Vigenere verschlüsselt wurde |
|||||||||||||||
|
|
|||||||||||||||
|
Wann tritt der Fall auf, dass zwei Buchstaben mit demselben
Schlüsselwortbuchstaben verschlüsselt werden? Nun genau dann, wenn das
Schlüsselwort zwischen sie genau einmal, genau zweimal, genau dreimal, ...
'passt'. Mit anderen Worten: Genau dann, wenn der Abstand der beiden
Klartextbuchstaben ein Vielfaches der Schlüsselwortlänge ist (siehe Muster
oben). Um den Abstand zwischen zwei Folgen zu bestimmen, geht man so vor: Man zählt die Anzahl der Buchstaben zwischen den jeweils ersten Buchstaben der Folgen, wobei man den ersten Buchstaben nicht mitzählt. Zum Beispiel haben die Folgen, die mit dem Buchstaben Nr. 11 bzw. mit dem Buchstaben Nr. 26 beginnen, den Abstand 15. Angenommen, Mr. X (unser Angreifer) hat den unten folgenden Text abgefangen, von dem er weiß oder vermutet, dass er Vigenere-chiffriert ist: Wir fassen zusammen: Wenn zwei Klartextfolgen aus gleichen Buchstaben einen Abstand haben, der ein Vielfaches der Schlüsselwortlänge ist, so entsprechen ihnen im Geheimtext Folgen aus gleichen Buchstaben. |
|||||||||||||||
|
Nun dreht Mr. X den Spieß um: Wenn er im Geheimtext zwei Folgen aus gleichen Buchstaben findet, so vermutet er, dass ihr Abstand 'wahrscheinlich' ein Vielfaches der Schlüsselwortlänge ist. Diese Wahrscheinlichkeit folgt dem "Gesetz je länger, je lieber": Gleiche Buchstaben sagen, wie wir wissen, gar nichts über die Schlüsselwortlänge aus, und auch Paare aus gleichen Buchstaben können sich 'zufällig' ergeben. Aber aus Folgen von drei oder mehr gleichen Buchstaben kann Mr. X schon ziemlich zuverlässig auf die Schlüsselwortlänge schließen. In unserem Beispiel erkennt er: | |||||||||||||||
|
EYRYC FWLJH FHSIU BHMJO UCSEG FMWVZ TYOIS UUIIS ECIZV SVXVF Ein Geheimtext, der mit der Methode von Vigenere verschlüsselt wurde |
|||||||||||||||
|
Tabelle Auswertung der Folgen aus gleichen Buchstaben |
|||||||||||||||
|
Der größte gemeinsame Faktor ist 5. Also
könnte ein (zu) optimistischer Kryptoanalytiker frohlocken und sagen, „Ich
weiß, dass die Schlüsselwortlänge 5 ist". In der Tat funktioniert der
Kasiski-Test in der Praxis sehr gut. Wenn der Kryptoanalytiker Mr. X allerdings vorsichtig ist, wird er nur sagen, "Dies ist ein starkes Indiz dafür, dass die Schlüsselwortlänge 5 ist". Warum tut Mr. X gut daran, vorsichtig zu sein? Es gibt dafür zwei Gründe.
Auch aus diesem Grund wird mit dem Friedmann-Test auf eine zweite Methode verwiesen - diese ergibt die Größenordnung der Schlüsselwortlänge. Eine Kombination beider Methoden lässt einen dann kaum mehr in die Irre gehen. |
|||||||||||||||
|
|
| 5. Friedmann-Test und Koinzidenzindex |
|
|
|
|
|
Eine Vigenère-Chiffre
knacken - dies schien bis in das Jahr
1852 mathematisch und technisch völlig unmöglich - der Vigenère-Chiffre
war scheinbar nicht angreifbar - und noch schöner: es wurde folgerichtig
auch gar nicht erst ernsthaft probiert ;-) Diese Grundeinstellung ist heutzutage fast schon pervers, selbstverständlich (sicherer als den Vigenère) und oft erfolgreich wird heut' jeder Chiffre dieser Art angegriffen und mit hoher Wahrscheinlichkeit geknackt. |
|
|
|
| 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. | ||||||||||||
|
|
 zur Hauptseite |
© Samuel-von-Pufendorf-Gymnasium Flöha | © Frank Rost November 2002 |
|
... dieser Text wurde nach den Regeln irgendeiner Rechtschreibreform verfasst - ich hab' irgendwann einmal beschlossen, an diesem Zirkus nicht mehr teilzunehemn ;-) „Dieses Land braucht eine Steuerreform, dieses Land braucht eine Rentenreform - wir schreiben Schiffahrt mit drei „f“!“ Diddi Hallervorden, dt. Komiker und Kabarettist |
Kasiski-Tester von Martin
Schmidt aus dem Jahr 2007 - lauffähiger Download als JAR-Datei
