Kasiski-Test
Der Kasiski-Test ist in der Kryptoanalyse ein Hilfsmittel zur Entzifferung von Chiffraten, die mit dem Vigenère-Verfahren erzeugt wurden. Mit ihm lässt sich die Länge des verwendeten Schlüsselwortes bestimmen.
Geschichte
Im Jahr 1854 gelang es dem Briten Charles Babbage (1791–1871), einen Vigenère-verschlüsselten Text zu entziffern. Allerdings hielt er seine Methode geheim. 1863 veröffentlichte der preußische Infanteriemajor Friedrich Wilhelm Kasiski (1805–1881) im Buch „Die Geheimschriften und die Dechiffrir-Kunst“ dieses Verfahren, das er unabhängig von Babbage erfand. Ihm zu Ehren wird das Verfahren als Kasiski-Test bezeichnet.
Allgemeine Vorgehensweise
Gegeben sei das Kryptogramm, ein Vigenère-verschlüsselter Text. Zuerst durchsucht man den Geheimtext nach Buchstabenfolgen der Länge 2 oder länger, die mehrmals vorkommen. Anschließend bestimmt man den Abstand zwischen je 2 gleichen Folgen, das heißt, man zählt die Buchstaben vom ersten Buchstaben der ersten Folge (einschließlich) bis zum ersten Buchstaben der zweiten Folge (ausschließlich). So verfährt man mit allen gefundenen Folgen und schreibt die Abstände auf. Man erhält eine Liste von natürlichen Zahlen. Diese werden nun in Primfaktoren zerlegt. Gleiche Teiler lassen sich somit schnell finden. Zufällig entstandene Übereinstimmungen sind dann auch leicht erkennbar, weil sie aus der Reihe fallen. Allerdings wird die genaue Schlüssellänge nicht bekannt, denn der Kasiski-Test liefert nur Vielfache der Schlüssellänge. Zur genauen Betrachtung kann dann aber der Friedman-Test herangezogen werden, der zusätzlich einen Hinweis darauf gibt, ob es sich um eine mono- oder polyalphabetische Verschlüsselung handelt.
Idee des Kasiski-Tests
Weshalb liefert der Kasiski-Test recht zuverlässige Aussagen über die Schlüsselwortlänge? Betrachten wir dazu die folgenden Verschlüsselungen:
Der Klartext (1. Zeile) wird mit Schlüsselwort PLUTO (Länge 5) Vigenère-kodiert. Der Geheimtext steht in der 3. Zeile.
DER KLARTEXT WIRD ZUM GEHEIMTEXT PLU TOPLUTOP LUTO PLU TOPLUTOPLU SPL DZPCNXLI HCKR OFG ZSWPCFHTIN
Im Klartext kommt zweimal die Zeichenfolge TEXT vor. Trotzdem unterscheiden sich die entsprechenden Zeichenfolgen im Geheimtext. Der Grund hierfür ist, dass TEXT das erste Mal mit UTOP, das zweite Mal jedoch mit OPLU kodiert wird. Dies geschieht deshalb, weil der Abstand zwischen TEXT und TEXT 17 Buchstaben beträgt. Das Schlüsselwort hat aber 5 Buchstaben, und weil 5 kein Teiler von 17 ist, werden beide Textstellen nicht mit demselben Teil des Schlüsselwortes kodiert, sodass auch nicht dieselben Buchstabenfolgen im Geheimtext zu erwarten sind. Ändern wir nun das kleine Beispiel ein wenig um.
DER KLARTEXT WERDE GEHEIMTEXT PLU TOPLUTOP LUTOP LUTOPLUTOP SPL DZPCNXLI HYKRT RYASXXNXLI
Dieses Mal wird TEXT zweimal mit UTOP verschlüsselt; deshalb stimmen auch die Folgen im Kryptogramm überein. Bestimmt man auch hier den Abstand zwischen TEXT und TEXT, kommt man auf 15, ein Vielfaches von 5, der Schlüsselwortlänge. Zusammenfassend stellt man fest: Gleiche Buchstabenfolgen (Wörter, Silben, Wortstämme usw.) ergeben nur dann gleiche Buchstabenfolgen im Kryptogramm, wenn der Abstand zwischen ihnen ein Vielfaches der Schlüsselwortlänge ist. Oder anders gesagt: Tritt im Kryptogramm eine Buchstabenfolge zweimal auf und wurde mit ihr dasselbe Wort verschlüsselt, so ist der Abstand zwischen den beiden Folgen ein Vielfaches der Schlüsselwortlänge. Beim Kasiski-Test wird nach gleichen Buchstabenfolgen im Kryptogramm gesucht. Man setzt nun voraus, dass sie dasselbe Wort verschlüsseln. Stimmt das, so ist der Abstand ein Vielfaches der Schlüsselwortlänge. Wurde aber nicht dasselbe Wort verschlüsselt, ist der Abstand kein Vielfaches der Schlüsselwortlänge, und die beiden Stellen im Geheimtext sind nur zufällig gleich. Natürlich erkennt man nicht sofort, ob „zufällig“ dieselbe Zeichenfolge entstanden ist, oder ob wirklich dasselbe Wort verschlüsselt wurde. Deshalb werden am Ende auch gemeinsame Faktoren gesucht, um die „unpassenden“ Abstände zu finden. Selbstverständlich passiert es vor allem bei kurzen Folgen, dass sie zweimal vorkommen, obwohl nicht dasselbe Wort verschlüsselt wurde. Das ist auch der Grund, warum man in der Regel nicht nach gleichen Folgen der Länge 2 sucht. Die Wahrscheinlichkeit, dass die Buchstabenfolgen im Klartext nicht übereinstimmen, ist einfach zu groß.
Beispiele
Es sei der folgende Vigenère-verschlüsselte Geheimtext gegeben.
SPL DZPCNXLI HYKRT RYASXXNXLI
Die Folge NXLI kommt im Geheimtext zweimal vor. Der Abstand zwischen diesen beiden Textstellen beträgt 15 Zeichen. 15 kann in die Primfaktoren 3 und 5 zerlegt werden. Unter der Annahme, dass es sich nicht um zufälliges Auftreten handelt, wird man sagen können, dass dasselbe Wort (bzw. Silbe, Wortanfang o. ä.) verschlüsselt wurde. Man wird hier also annehmen, dass das Schlüsselwort die Länge 3, 5 oder 15 hat.
Selbstverständlich können bei längeren Geheimtexten genauere Aussagen über die Länge des Schlüsselwortes getroffen werden. Die Gründe hierfür sind im Wesentlichen: Es kommen mehrere Buchstabenfolgen doppelt vor. Eine Buchstabenfolge (besonders bei häufig vorkommenden Wörtern, z. B. Artikel, Pronomen, Konjunktionen) kommt sogar dreimal oder noch öfter im Kryptogramm vor.
Gegeben sei der folgende Vigenère-verschlüsselte Geheimtext (verschlüsselt wurde 1.Mose, Kapitel 1, Vers 1–4 mit dem Schlüsselwort ALTESTESTAMENT, das 14 Buchstaben lang ist). Mit dem Kasiski-Test soll die Länge des Schlüsselwortes bestimmt werden.
AXTRX TRYLC TYSZO EMLAF QWEUZ HRKDP NRVWM WXRPI JTRHN IKMYF WLQIE NNOXW OTVXB NEXRK AFYHW KXAXF QYAWD PKKWB WLZOF XRLSN AAWUX WTURH RFWLL WWKYF WGAXG LPCTG ZXWOX RPIYB CSMYF WIKPA DHYBC SMYFW KGMTE EUWAD LHSLP AVHFK HMWLK
Vorgehensweise: Suchen gleicher Textfolgen mindestens der Länge 3, diese markieren und Abstände bestimmen.
AXTRX TRYLC TYSZO EMLAF QWEUZ HRKDP NRVWM WXRPI JTRHN IKMYF WLQIE NNOXW OTVXB NEXRK AFYHW KXAXF QYAWD PKKWB WLZOF XRLSN AAWUX WTURH RFWLL WWKYF WGAXG LPCTG ZXWOX RPIYB CSMYF WIKPA DHYBC SMYFW KGMTE EUWAD LHSLP AVHFK HMWLK
XTR: Abstand 3 XRPI: Abstand 98 YFW: Abstand 70 YBCSMYFW: Abstand 14
Zerlegen der Abstände in Primfaktoren.
3 = 3 98 = 2 × 7 × 7 70 = 2 × 5 × 7 14 = 2 × 7
Auswertung
Wie man an der Primfaktorenzerlegung erkennen kann, sind alle Abstände (außer dem ersten) Vielfache von 14. Der Abstand 3 ist vermutlich ein zufälliges Zusammentreffen. Daraus ergeben sich die folgenden Vermutungen für die Schlüsselwortlänge: 2, 7 oder 14, und tatsächlich hat der Schlüssel ALTESTESTAMENT die Länge 14.
Literatur
- Albrecht Beutelspacher: Kryptologie. Eine Einführung in die Wissenschaft vom Verschlüsseln, Verbergen und Verheimlichen. Ohne alle Geheimniskrämerei, aber nicht ohne hinterlistigen Schalk, dargestellt zum Nutzen und Ergötzen des allgemeinen Publikums. 2. erheblich erweiterte und hoffentlich verbesserte Auflage. Vieweg, Braunschweig 1991, ISBN 3-528-18990-8.