Kasiski-Verfahren

Einführung

Der Kasiski-Test ist in der Kryptoanalyse ein Hilfsmittel zur Entzifferung von Chiffraten, die mit dem Vigenère-Verfahren erzeugt wurden. 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.

Methode

n-Gramme bestimmen

Das Chiffrat wird nach sich wiederholenden Buchstabenfolgen (min. 2 oder besser 3 Buchstaben lang) durchsucht. Sie werden auch als n-Gramme bezeichnet. Je länger die gefunden n-Gramme sind, um so wahrscheinlicher ist es, dass der Abstand ein Vielfaches der Schlüssellänge ist. Dann werden jeweils die Abstände zwischen den gleichen Buchstabenfolgen bestimmt und notiert (1. Buchstabe 1. Wiederholung bis 1. Buchstabe 2. Wiederholung minus 1).

Es kann sein, dass rein Zufällig Wiederholungen von n-Grammen im Chiffrat gefunden werden. Dieser Wiederholungen sind aber unwahrscheinlicher als echte Doppelungen die durch die Verschlüsselung systematisch entstehen.

Dopplung Chiffrate (Quelle: http://www.inf-schule.de)

Schlüssellänge bestimmen

Kasiski hat die Annahme getroffen, dass bei einer Wiederholung eines n-Gramms eine Stelle im Chiffrat gefunden ist, in der höchtswahrscheinlich eine wiederkehrende und identische Zeichenfolge im Klartext durch den Schlüssel stets gleich cheffriert wurde. Daraus lässt sich folgern, dass der Schlüssel ein Teiler des Abstands der Wiederholung ist (Beispiel: Gesamtabstand 12 mit Teiler 4 siehe oben). Der Größte gemeinsame Teiler aller so ermittelten Abstände aller doppelten n-Gramme oder wiederum einem Teiler davon ist wahrscheinlich die Schlüssellänge. Für alle Buchstabenfolgen mit nur zwei Buchstaben kann man meist keinen ggT bestimmen, der größer als 1 ist, da fast immer ein Ausreißer dabei ist.

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 verschlüsselt wurde. Der Buchstabe an der Stelle Schlüssellänge + 1 wurde wieder mit dem 1. Buchstaben des Schlüssels chiffriert.

Bilden von Substitutionsgruppen

Die ursprünglich polyalphabetische Substitution zerfällt somit in mehrere einzelne monoalpabetische Substitutionsgruppen. Ist die Schlüssellänge z. B. 4, so gehören der 1., 5., 9., 13. etc. Buchstabe dem ersten Substitutionsgruppen an, dass wieder den Gesetzen der Häufigkeitsverteilung unterliegt. Der 2., 6., 10., 14. etc. würden entsprechend dem 2. Substitutionsgruppen angehören usw.

Schlüssel: . . . . Klartext: H A B E E I N E N K L E I N E N E S E L I M S T A L L G E S E H E N Geheimtext: D O J R A W V R J Y T R E B M A A G M Y E A A G W Z T T A G M U A B

Analyse Häufigkeitsverteilung

Jede Substitutionsgruppe muss jeweils einzeln per Häufigkeitsanalyse weiter analysiert und so die Verschiebung des Alphabets bestimmt werden.

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'):

JUKVMXTXQWJEBSEVSXHRWAEDMXTBDJORLBLXEXKEQMNRWDEXHRKRFDVTUGFIRIGZYCG XGIXUGCLYLSZYPEBMIWSVGPSTMDRROEDRGIXDVOSGTRJULZQWEGFICUVGXENWZYPGXK ENEGGEDTXVSVLMDIBWXHPORLNIBFKNVONPZVXOVGRSCASRKCAGEESZDLONLNRNEKMIB SMEIEEKZRWAVGIXUGCWSCADMXBBRWMHXMAKEKLIXDTRGRAKQXOEKCIXSVGROEPDKENW VMOEKRSNEGDVNBHCIXANEVKENLXOFTMHORXHRONDKISNXMKYLWDRONLBLVUXRWOLGTR QLTTFDEXQAYDXQWMHETICSXKAKEKDQEELRXOANBLNALRGRLHRWNASTWOIGFVEBBMHOR XQHOUGCJKNWDMXEBRIBNXROKELSGREGVIXNWDVCCAKYOSLDPXUKOECSMCEMHMDIBELR MXDZDASSLJSCTUZVOSTBLONBMHOMDZICTVGIXEKRYMHMDELEKDWGAKJISNLBLVUXRWO LENGRDTDRNLBBLONMCIMKMDIBEBMWKBXQWYKEDMXDTRWWAGDWUANLWOHXMOYNGSIORI QSLIXQXOUGCHORLBLVUXRWOLIZWCTXFPEEVJPSCACENRXGXOEKDMXMTKLORNLYXDGTR WUXRWONPHVGAKSIXBBRIBVHKPONWREEFZDWMHENWCEGTRNDXMHOCDDPKUYFIWAVGXRA MCEXNPDVNEGVMBEKEERRXMAKSYTIBWNMHORUZVOSTBLONBMHOMDZICTVGIXLTFIX

Die Wiederholung des Trigramm "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'):

PMAEGGAQAZVUACIJLLUWTWBWRVRBLRNYOSZWMCEHSVBOILNMGGHDVLNZMWOCAP ZJBOWWQMLNUPQVHPSDNCBUQVZYXDRBRXUTXSADORMCKLEWBJPMBIKFLZPLOKUQ BSGKMDMCUDJLCGOMCAAMGUTRXLDFLEBWAAMXYRAVNUFFIPGVOQUESZCVYVOTJB OWWQMLLVZMLNDWAARYLGNYWDEJKFXUGWKOYUQMGGIUBZYXWWEYXYYNUZQKLPYK YFNLNTWWAAAUQNDAWMWLUBLQAZKTWWMPWIAMLJQMOZYXBYCLBQFMMPXPZNUGBW RVCGNAUKADWWAAASGNZOUDWCLZSMDIPUWAEMWLDBJDBMNAQXSIJLNUEDMQLAQJ BYXVJAQVOXXZOTSICQXPZPYQRAWLCKLDMLQDVOILWLUWLEIWAVCLRMNZPSZNVU XUZMLNIUQTSXZENSJKJYIQLAPJJDJWNZCLZUWKCUORAQDVECIWHWBIAALZRUZU ETICLAOQLJUJBCAAAQJIAHWBEYKRQRUOSZUCCLZQUSKSZMICGKXRJDUFCLCVRF NLNUAWAYULDBVGBWRVBTZEVHJUKTISFZQQLJAGWVRXLDYYKRANZRXBZMKAHKLP JNLEBLHFSBARXNXDLYADRKFWHPALDJWNZCBUYJSDUJDUSGKZDUIKWBACGDUADW HLNVZBZQACKBDNVBLHGONAIUQTMLZQWBJTVNVBXJWNSWKXPMKTJTCOWJVJVLPL DMLJMAAMPYHTALJMSBNSXYIDUZUJKIPXZMLOADAWLCFRMNZPSZNVJTNQW

Hier ist die häufigste Wiederholung 4 mal "WAA" mit folgenden Faktoren:

WAA: 44 = 2 2 11

WAA: 56 = 2 2 2 7

WAA: 66 = 2 3 11

Da dies ein wenig dünn ist und die Schlüssellänge 4, 8 oder 11 sein könnte, müssen weitere Wiederholungen gesucht werden. Nachfolgend wurde besonderer Augenmerk auf längere Wiederholungen gelegt, die aussagekräftig sind, auch wenn sie sich nicht oft wiederholen, weil sie weniger wahrscheinlich zufällig sind:

RMNZPSZNV: 363 = 3 11 11

JBOWWQML: 121 = 11 11

RMNZPSZN: 363 = 3 11 11

MNZPSZNV: 363 = 3 11 11

JBOWWQM: 121 = 11 11

BOWWQML: 121 = 11 11

RMNZPSZ: 363 = 3 11 11

MNZPSZN: 363 = 3 11 11

NZPSZNV: 363 = 3 11 11

JBOWWQ: 121 = 11 11

BOWWQM: 121 = 11 11

OWWQML: 121 = 11 11

Nun kristallisiert sich heraus, dass die Schlüssellänge 11 ist, was auch der Wahrheit entspricht.