Wikipedia · einfach zusammengefasst · Stand
Kasiski-Test
Der Kasiski-Test ist in der Kryptoanalyse ein Hilfsmittel zur Entzifferung von Chiffraten, die mit dem Vigenère-Verfahren erzeugt wurden.
Inhalt5 Abschnitte
Zweck und Grundprinzip
Der Kasiski-Test ist ein Verfahren der Kryptoanalyse, also der Untersuchung verschlüsselter Texte. Er dient dazu, bei einem mit dem Vigenère-Verfahren erzeugten Chiffrat die Länge des verwendeten Schlüsselwortes zu bestimmen. Die genaue Schlüssellänge liefert er zunächst nicht direkt: Die gefundenen Abstände sind nur Vielfache der Schlüssellänge.
Man sucht im Geheimtext wiederholt auftretende Buchstabenfolgen. Unter der Annahme, dass diese Folgen im Klartext dieselbe Zeichenfolge verschlüsselten, lässt ihr Abstand auf mögliche Teiler und damit auf die Länge des Schlüsselwortes schließen.
Vorgehensweise
Zuerst wird das Kryptogramm nach Buchstabenfolgen der Länge 2 oder mehr durchsucht, die mehrfach vorkommen. Für jedes Paar gleicher Folgen bestimmt man den Abstand: Gezählt werden die Buchstaben vom ersten Buchstaben der ersten Folge einschließlich bis zum ersten Buchstaben der zweiten Folge ausschließlich.
Alle gefundenen Abstände bilden eine Liste natürlicher Zahlen. Diese Zahlen werden in Primfaktoren zerlegt. Gemeinsame Teiler lassen sich dadurch leicht erkennen. Abstände ohne passende gemeinsame Faktoren können auf zufällig gleiche Geheimtextfolgen hinweisen.
In der Regel sucht man nicht nach gleichen Folgen der Länge 2. Bei so kurzen Folgen ist die Wahrscheinlichkeit besonders groß, dass sie zwar im Geheimtext gleich aussehen, aber unterschiedliche Klartextfolgen verschlüsseln. Zur genaueren Bestimmung kann anschließend der Friedman-Test eingesetzt werden. Er gibt außerdem einen Hinweis darauf, ob eine mono- oder polyalphabetische Verschlüsselung vorliegt.
Warum Abstände Hinweise geben
Beim Vigenère-Verfahren wird ein Klartext mit einem sich wiederholenden Schlüsselwort verschlüsselt. Gleiche Klartextfolgen ergeben deshalb nur dann gleiche Geheimtextfolgen, wenn sie mit demselben Abschnitt des Schlüsselwortes kodiert werden. Das ist der Fall, wenn ihr Abstand ein Vielfaches der Schlüsselwortlänge ist.
Im Beispiel mit dem Schlüsselwort PLUTO der Länge 5 kommt TEXT zweimal vor. Bei einem Abstand von 17 ist 5 kein Teiler von 17: Die beiden Vorkommen werden mit unterschiedlichen Schlüsselabschnitten, nämlich UTOP und OPLU, kodiert und erscheinen daher im Geheimtext verschieden. Wird der Abstand auf 15 geändert, wird TEXT beide Male mit UTOP verschlüsselt; die Geheimtextfolgen stimmen überein. Die Zahl 15 ist ein Vielfaches von 5.
Der Test setzt bei gleichen Geheimtextfolgen zunächst voraus, dass sie dieselbe Klartextfolge verschlüsseln. Ist diese Annahme falsch, handelt es sich um eine zufällige Übereinstimmung und ihr Abstand muss kein Vielfaches der Schlüssellänge sein. Mehrere Wiederholungen und ihre gemeinsamen Faktoren helfen, solche unpassenden Abstände zu erkennen.
Beispiele und Auswertung
Im Geheimtext „SPL DZPCNXLI HYKRT RYASXXNXLI“ erscheint NXLI zweimal. Der Abstand beträgt 15 Zeichen. Da 15 die Primfaktoren 3 und 5 hat, kommen unter der Annahme einer nicht zufälligen Wiederholung Schlüsselwortlängen von 3, 5 oder 15 infrage.
Bei längeren Geheimtexten sind genauere Aussagen möglich, weil mehrere Folgen doppelt vorkommen oder eine Folge sogar dreimal oder öfter erscheint. Im ausführlichen Beispiel wurde 1. Mose, Kapitel 1, Vers 1–4 mit dem 14 Buchstaben langen Schlüsselwort ALTESTESTAMENT verschlüsselt. Gefundene Folgen und Abstände sind: XTR mit Abstand 3, XRPI mit Abstand 98, YFW mit Abstand 70 sowie YBCSMYFW mit Abstand 14. Die Primfaktorzerlegungen lauten 3 = 3, 98 = 2 × 7 × 7, 70 = 2 × 5 × 7 und 14 = 2 × 7.
Alle Abstände außer 3 sind Vielfache von 14; der Abstand 3 wird daher vermutlich als zufälliges Zusammentreffen bewertet. Daraus ergeben sich zunächst die möglichen Schlüsselwortlängen 2, 7 oder 14. Tatsächlich hat ALTESTESTAMENT die Länge 14.
Geschichtlicher Hintergrund
1854 gelang Charles Babbage (1791–1871) die Entzifferung eines Vigenère-verschlüsselten Textes, doch hielt er seine Methode geheim. Friedrich Wilhelm Kasiski (1805–1881), preußischer Infanteriemajor, veröffentlichte 1863 in „Die Geheimschriften und die Dechiffrir-Kunst“ ein unabhängig von Babbage erfundenes Verfahren. Nach ihm heißt es Kasiski-Test.
