Kasiski Test

Kategorisierung:	Kryptoanalyse Klassisch / Substitution / polyalphabetisch
Siehe auch:	Kasiski-Test, Kappa-Test, Chi-Quadrat-Test
Herkunft / Verwendung:	Der Kasiski-Test (1863 veröffentlicht) ist in der Kryptografie ein Hilfsmittel zur Entzifferung von Chiffraten, die mittels der Vigenère Chiffre erzeugt wurden. Mit dem Test lässt sich die Länge des verwendeten Schlüssels bestimmen. Das Verfahren stützt sich darauf, dass sich ein im Verhältnis zur Chiffratlänge relativ kurzes Schlüsselwort ständig wiederholt wird. Das hat zur Folge, dass, wenn der Abstand zwischen zwei gleichen Wörtern im Klartext ein Vielfaches der Schlüsselwortlänge ist, diese sich auch (chiffriert) im Chiffrat wiederholen. Er wurde nach seinem Erfinder Friedrich Wilhelm Kasiski benannt. Zwar dechiffrierte noch vor Kasiski Charles Babbage eine Vigenere-Chiffre, doch hielt dieser sein Verfahren geheim, so dass beide Personen unabhängig voneinander Verfahren zum Knacken der Vigenere-Chiffre entwickelten. Den Test beschreibt Kasiski in seinem Buch Die Geheimschriften und die Dechiffrir-Kunst von 1863 ab Seite 34 mit folgenden Worten: §80. Jetzt sucht man zuerst zu ermitteln, aus wievielen Buchstaben der Schlüssel besteht. Zu diesem Zweck sucht man in der aufgeschriebenen Chiffre-Schrift alle Wiederholungen von zwei und mehreren Chiffern auf, zählt dann die Entfernung der gleichen Wiederholungen von einander schreibt diese mit der Zahl ihrer Entfernung von einander unter die Chiffre-Schrift und sucht diese Zahl in ihre Faktoren zu zerlegen. Z. B. man findet, dass zwischen den zwei sich wiederholenden Chiffern "gf" 28 Buchstaben liegen, so zählt man diese 2 Chiffern zu der Zahl 28 und erhält also die Zahl 30 als die Entfernung der Wiederholung gf von einander. Man schreibt also gf = 30 = 5 . 6. Hieraus kann man nach §76 schließen, dass der Schlüssel entweder 5 oder 6 Buchstaben enthält. Da die Anzahl der Buchstaben des Schlüssels hiernach noch unbestimmt ist, nach §77 die Wiederholung der Chiffern gf auch eine zufällige sein könnte, so schreibt man nach und nach alle Wiederholungen von mehreren Chiffern mit der Zahl ihrer Entfernung auf und zerlegt diese Zahlen in ihre Faktoren. Diejenigen Faktoren, welche am häufigsten gefunden werden, zeigen die Anzahl der Buchstaben des Schlüssels an.

Beschreibung des Verfahrens

Das Chiffrat wird nach sich wiederholenden Buchstabenfolgen (min. 2 oder besser 3 Buchstaben lang) durchsucht. Dann werden jeweils die Abstände zwischen den gleichen Buchstabenfolgen bestimmt und notiert (1. Buchstabe 1. Wiederholung bis 1. Buchstabe 2. Wiederholung minus 1). Danach werden die Abstände in ihre Primfaktoren zerlegt und das Augenmerk auf gleiche Teiler gelegt, die dann wahrscheinlich zur Schlüssellänge sind. Dabei ist zu beachten, dass sich z. B. eine Schlüssellänge von 8 durch die Faktorenhäufung von 2 (2*2*2=8) oder eine Schlüssellänge von 12 durch die Faktorenhäufung von 2 und 3 (2*2*3=12) ausdrückt.

Wenn die genaue Schlüssellänge bekannt ist, ist damit klar geworden, dass jeder 1. Buchstabe des Klartextes mit dem 1. Buchstaben des Schlüssels, jeder 2. Buchstabe des Klartextes mit dem 2. Buchstaben des Schlüssels usw. und der (Schlüssellänge+1). Buchstabe wieder mit dem 1. Buchstaben des Schlüssels chiffriert worden ist. Die ursprünglich polyalphabetische Substitution zerfällt somit in mehrere einzelne monoalpabetische Substitutionsgruppen, die jeweils einzeln z. B. per Häufigkeitsanalyse weiter analysiert werden können. Ist die Schlüssellänge z. B. 6, so ist gehören der 1., 7., 13., 19. etc. Buchstabe dem ersten Substitutionsgruppen an, dass wieder den Gesetzen der Häufigkeitsverteilung unterliegt. Der 2., 8., 14., 20. etc. würden entsprechend dem 2. Substitutionsgruppen angehören usw.

Wurden alle Chiffrat-Buchstaben der Substitutionsgruppen durch wahrscheinliche (nach Häufigkeitsverteilung) Klartextbuchstaben ersetzt, stellt sich im Idealfall sofort ein komplett dechiffrierter Klartext dar. Wahrscheinlich muss aber noch kombiniert werden. Schon lesbare Wörter oder einzelne, falsche Buchstaben im Dechiffrat geben Anhaltspunkte dazu, wo noch etwas "gedreht" werden muss.

Das Vorkommen von genügend vielen Buchstabenwiederholungen stellt sich erst bei genügend langem Text ein. Genau wird die nachfolgende Häufigkeitsanalyse nur von Erfolg gekrönt sein, wenn der Text lang genug ist. Ein kurzes Schlüsselwort erleichert zudem die Kryptoanalyse.

Beispiele

Chiffrat (Vigenere Chiffre mit dem Kennwort 'Katze'): JUKVMXTXQWJEBSEVSXHRWAEDMXTBDJORLBLXEXKEQMNRWDEXHRKRFDVTUGFIRIGZYCGXGIXUGCLYLSZYPEBMIWSVGPSTMDRROEDRGIXDVOSGTRJULZQWEGFICUVGXENWZYPGXKENEGGEDTXVSVLMDIBWXHPORLNIBFKNVONPZVXOVGRSCASRKCAGEESZDLONLNRNEKMIBSMEIEEKZRWAVGIXUGCWSCADMXBBRWMHXMAKEKLIXDTRGRAKQXOEKCIXSVGROEPDKENWVMOEKRSNEGDVNBHCIXANEVKENLXOFTMHORXHRONDKISNXMKYLWDRONLBLVUXRWOLGTRQLTTFDEXQAYDXQWMHETICSXKAKEKDQEELRXOANBLNALRGRLHRWNASTWOIGFVEBBMHORXQHOUGCJKNWDMXEBRIBNXROKELSGREGVIXNWDVCCAKYOSLDPXUKOECSMCEMHMDIBELRMXDZDASSLJSCTUZVOSTBLONBMHOMDZICTVGIXEKRYMHMDELEKDWGAKJISNLBLVUXRWOLENGRDTDRNLBBLONMCIMKMDIBEBMWKBXQWYKEDMXDTRWWAGDWUANLWOHXMOYNGSIORIQSLIXQXOUGCHORLBLVUXRWOLIZWCTXFPEEVJPSCACENRXGXOEKDMXMTKLORNLYXDGTRWUXRWONPHVGAKSIXBBRIBVHKPONWREEFZDWMHENWCEGTRNDXMHOCDDPKUYFIWAVGXRAMCEXNPDVNEGVMBEKEERRXMAKSYTIBWNMHORUZVOSTBLONBMHOMDZICTVGIXLTFIX die Wiederholung "MHO" kommt gleich 6 mal im Text vor. Die Abstände und deren Primfaktoren sind: MHO: 100 = 2 2 5 5 MHO: 95 = 5 19 MHO: 225 = 3 3 5 5 MHO: 50 = 2 5 5 MHO: 15 = 3 5 Der häufigste Primfaktor ist die 5 (8x). Gefolgt von 3x3, 3x2 und 1x19.
In diesem Beispiel ist die Schlüssellänge also 5. Wäre die Schlüssellänge etwa 4 oder 6, wären die Primfaktoren 2 (2*2=4) bzw. 2 und 3 (2*3=6) gehäuft.

---

Chiffrat (Vigenere Chiffre mit dem Kennwort 'Kirschtorte'): Hier ist die häufigste Wiederholung 4 mal "VLX" mit folgenden Faktoren: VLX: 279 = 3 3 31 VLX: 172 = 2 2 43 VLX: 191 = 191 Da hier die Aussagekraft gering ist, da sehr unterschiedliche und hohe Primfaktoren aufgeführt sind und rechnerisch die Schlüssellänge 4, 9 oder mehr als 30 (unwahrscheinlich) in Frage kommen könnten, müssen weitere Wiederholungen gesucht werden.

Nachfolgend wurde besonderer Augenmerk auf längere Wiederholungen gelegt, die aussagekräftiger sind, auch wenn sie sich nicht oft wiederholen, weil sie aufgrund der Länge weniger wahrscheinlich zufällig sind. Beim Überfliegen des Ergebnisses zeigt sich, dass die 11 sehr oft vorkommt: DOVLXMPVF: 363 = 3 11 11 RNWQMYWP: 121 = 11 11 DOVLXMPV: 363 = 3 11 11 OVLXMPVF: 363 = 3 11 11 RNWQMYW: 121 = 11 11 NWQMYWP: 121 = 11 11 DOVLXMP: 363 = 3 11 11 OVLXMPV: 363 = 3 11 11 VLXMPVF: 363 = 3 11 11 RNWQMY: 121 = 11 11 NWQMYW: 121 = 11 11 WQMYWP: 121 = 11 11 DOVLXM: 363 = 3 11 11 OVLXMP: 363 = 3 11 11 VLXMPV: 363 = 3 11 11 LXMPVF: 363 = 3 11 11 LDMVJG: 187 = 11 17 RNWQM: 121 = 11 11 NWQMY: 121 = 11 11 WQMYW: 121 = 11 11 QMYWP: 121 = 11 11 ... 11 scheint als Schlüssellänge praktikabler als 31, 43 oder 191. Außerdem ist sie häufigster Primfaktor. Es kristalliert sich also heraus, dass die Schlüssellänge 11 ist, was auch der Wahrheit entspricht.

Code / Chiffre online dekodieren / entschlüsseln bzw. kodieren / verschlüsseln (DeCoder / Encoder / Solver-Tool)

Vorher etwas mit dem Vigenere Chiffre verschlüsseln.

Quellen, Literaturverweise und weiterführende Links

Kasiski, Friedrich Wilhelm: Die Geheimschriften und die Dechiffrir-Kunst, Mittler & Sohn Verlag Berlin 1863, S. 34
Singh, Simon: Geheime Botschaften, Hanser Verlag 2000, S. 91
Kippenhahn, Rudolf: Verschlüsselte Botschaften, Nikol Verlag 2006, S. 208
Franke, Herbert W.: Die geheime Nachricht, Umschau Verlag 1982, S. 69
Bauer, Friedrich L.: Entzifferte Geheimnisse, Springer Verlag 1995, S. 263
Beutelspacher, Neumann und Schwarzpaul: Kryptografie in Theorie und Praxis, Vieweg Verlag 2005, S. 16
Ertel, Wolfgang: Angewandte Kryptographie, Hanser Verlag 2012, S. 40
Beutelspacher, Albrecht: Kryptologie - Eine Einführung..., Springer Spektrum Verlag 2015, S. 36
Fumy, Walter und Rieß, Hans Peter: Kryptographie: Entwurf, Einsatz und Analyse..., Oldenbourg Verlag 1988, S. 56
Kahn, David: The Codebreakers - The Story of Secret Writing, Macmillan Verlag 1968, S. 207
Gaines, Helen Fouché: Cryptanalysis, Dover Verlag New York 1956, S. 127
Wobst, Reinhard: Abenteuer Kryptologie, Addison-Wesley-Verlag 2001, S. 92