Quelltext der Seite 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 ===
[[Datei:Dopplung Chiffrate.png|mini]]
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.

=== 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 [[Euklidischer-algorithmus-ggt|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äufigkeitsanalyse|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 VMOEKRSNEGDVNBHCIXANEVKENLXOFT'''MHO'''RXHRONDKISNXMKYLWDRONLBLVUXRWOLGTR QLTTFDEXQAYDXQWMHETICSXKAKEKDQEELRXOANBLNALRGRLHRWNASTWOIGFVEBB'''MHO'''R XQHOUGCJKNWDMXEBRIBNXROKELSGREGVIXNWDVCCAKYOSLDPXUKOECSMCEMHMDIBELR MXDZDASSLJSCTUZVOSTBLONB'''MHO'''MDZICTVGIXEKRYMHMDELEKDWGAKJISNLBLVUXRWO LENGRDTDRNLBBLONMCIMKMDIBEBMWKBXQWYKEDMXDTRWWAGDWUANLWOHXMOYNGSIORI QSLIXQXOUGCHORLBLVUXRWOLIZWCTXFPEEVJPSCACENRXGXOEKDMXMTKLORNLYXDGTR WUXRWONPHVGAKSIXBBRIBVHKPONWREEFZDWMHENWCEGTRNDX'''MHO'''CDDPKUYFIWAVGXRA MCEXNPDVNEGVMBEKEERRXMAKSYTIBWN'''MHO'''RUZVOSTBLONB'''MHO'''MDZICTVGIXLTFIX 

Die Wiederholung des Trigramm "'''MHO'''" kommt gleich 6 mal im Text vor. Die Abstände und deren [[Primfaktorzerlegung|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 [[Primfaktorzerlegung|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 [[Primfaktorzerlegung|Primfaktoren]] 2 (2*2=4) bzw. 2 und 3 (2*3=6) gehäuft.

Chiffrat ([[Vigenere-verfahren|Vigenere Chiffr]]e mit dem Kennwort 'Kirschtorte'): 

PMAEGGAQAZVUACIJLLUWTWBWRVRBLRNYOSZWMCEHSVBOILNMGGHDVLNZMWOCAP ZJBOWWQMLNUPQVHPSDNCBUQVZYXDRBRXUTXSADORMCKLEWBJPMBIKFLZPLOKUQ BSGKMDMCUDJLCGOMCAAMGUTRXLDFLEB'''WAA'''MXYRAVNUFFIPGVOQUESZCVYVOTJB OWWQMLLVZMLND'''WAA'''RYLGNYWDEJKFXUGWKOYUQMGGIUBZYXWWEYXYYNUZQKLPYK YFNLNTW'''WAA'''AUQNDAWMWLUBLQAZKTWWMPWIAMLJQMOZYXBYCLBQFMMPXPZNUGBW RVCGNAUKADW'''WAA'''ASGNZOUDWCLZSMDIPUWAEMWLDBJDBMNAQXSIJLNUEDMQLAQJ 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.