Kasiski-Test
aus Wikipedia, der freien Enzyklopädie
Der Kasiski-Test ist ein Hilfsmittel zur Entschlüsselung Vigenère-kodierter Texte. Mit ihm lässt sich die Länge des verwendeten Schlüsselwortes bestimmen.
Inhaltsverzeichnis |
[Bearbeiten] Geschichte
Im Jahr 1854 gelang es dem Engländer Charles Babbage (1791-1871), einen Vigenère-kodierten Text zu entschlüsseln. Allerdings hielt er seine Methode geheim. 1863 veröffentlichte der preußische Infanteriemajor Friedrich Wilhelm Kasiski (1805-1881) im Buch „Die Geheimschriften und die Dechiffrierkunst“ dieses Verfahren, das er unabhängig von Babbage fand. Ihm zu Ehren wird das Verfahren als Kasiski-Test bezeichnet.
[Bearbeiten] Allgemeine Vorgehensweise
Gegeben sei das Kryptogramm, ein Vigenère-verschlüsselter Text. Zuerst durchsucht man den Geheimtext nach Buchstabenfolgen der Länge 3 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 sich 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 Buchstabenfolgen 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 Friedmantest herangezogen werden.
[Bearbeiten] 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, einem Vielfachen 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ß.
[Bearbeiten] 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 = 3x5. 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 (14 Buchstaben)). 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 x 7 x 7
70 = 2 x 5 x 7
14 = 2 x 7
[Bearbeiten] 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.
Es braucht nicht viele Erklärungen, warum die Länge 2 ausgeschlossen wird, so dass als mögliche Schlüsselwortlängen nur 7 und 14 verbleiben.
[Bearbeiten] Literatur
- A. Beutelspacher: Kryptologie. 2-te erweiterte Auflage, Vieweg 1991,ISBN 3-528-18990-8
