Kasiski-Test

Der Kasiski-Test ist in der Kryptografie 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 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.

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 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.

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ß.

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

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.

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.