Schlüssellänge von polyalphabetischen Substitutions-Chiffren bestimmen
Nachdem man die Art der Chiffre bestimmt hat und sicher ist, dass es sich um eine polyalphabetischen Substitutions-Chiffre handelt, gilt es als nächstes, die Länge des verwendeten Schlüssels zu bestimmen.Nur wenn wir die Schlüssellänge in Erfahrung bringen, wissen wir, wieviele unterschiedliche Einzelalphabete für die polyalphabetische Substitution verwendet worden sind. Nur dann können wir die richtigen Buchstaben in Gruppen zusammenfassen und statistischen Analysen unterwerfen.
Für die Vigenere Chiffre etwa wird jeder Klartext-Buchstabe um die Anzahl Positionen verschoben, die der verknüpfte Schlüsselbuchstabe vorgibt, um den Geheimtextbuchstaben zu erhalten.
Beispiel: Klartext = Beispielklartext, Schlüsselwort: Apfelstrudel
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
b e i s p i e l k l a r t e x t
A P F E L S T R U D E L A P F E Offset alphab.
+0 15 +5 +4 11 18 19 17 20 +4 +4 11 +0 15 +5 +4 Offset numeri.
B T N W A A X C E O E C T T C X
Ist der Vorrat an Schlüsselbuchstaben aufgebraucht, wird mit dem Schlüssel wieder von vorne begonnen. Im Beispiel wird der 1. und der 13. Buchstabe durch den selben Offset (nämlich +0) verschoben. Derselbe Offset +0 würde auch beim 25., 37., 49. usw. Zeichen auftreten, eben weil der Schlüssel immer wiederholt wird. Der Abstand zwischen den Schlüsselwiederholungen wird auch Periode genannt und entspricht der Schlüssellänge.Wenn wir jetzt die Schlüssellänge kennen würden, dann wüssten wir auch, welche Klartextbuchstaben gleich verschlüsselt worden sind, und wir könnten sie in Gruppen (Einzelalphabete) zusammenfassen, in der alle Buchstaben dieselbe Verschiebung aufweisen würden und auf die man dann eine Häufigkeitsanalyse fahren könnte.
Wie aber findet man die Schlüssellänge heraus? Dafür gibt es mehrere Verfahren. Die einfachste ist wohl der Kappa-Test, der auf dem Koinzidenzindex basiert. Dieser nimmt probeweise eine Schlüssellänge an und fasst die Chiffrat-Buchstaben entsprechend der Periode zusammen und rechnet dafür jeweils den Koinzidenzindex aus.
Beispiel für einen mit Vigenere verschlüsselten Text:
JUKVMXTXQWJEBSEVSXHRWAEDMXTBDJORLBLXEXKEQMNRWDEXHRKRFDVTUGFIRIGZYCGXGIXUGCLYLSZYPEBMIWSVGPSTMDRROEDRGIXDVOSGTRJULZQWEGFICUVGXENWZYPGXKENEGGEDTXVSVLMDIBWXHPORLNIBFKNVONPZVXOVGRSCASRKCAGEESZDLONLNRNEKMIBSMEIEEKZRWAVGIXUGCWSCADMXBBRWMHXMAKEKLIXDTRGRAKQXOEKCIXSVGROEPDKENWVMOEKRSNEGDVNBHCIXANEVKENLXOFTMHORXHRONDKISNXMKYLWDRONLBLVUXRWOLGTRQLTTFDEXQAYDXQWMHETICSXKAKEKDQEELRXOANBLNALRGRLHRWNASTWOIGFVEBBMHORXQHOUGCJKNWDMXEBRIBNXROKELSGREGVIXNWDVCCAKYOSLDPXUKOECSMCEMHMDIBELRMXDZDASSLJSCTUZVOSTBLONBMHOMDZICTVGIXEKRYMHMDELEKDWGAKJISNLBLVUXRWOLENGRDTDRNLBBLONMCIMKMDIBEBMWKBXQWYKEDMXDTRWWAGDWUANLWOHXMOYNGSIORIQSLIXQXOUGCHORLBLVUXRWOLIZWCTXFPEEVJPSCACENRXGXOEKDMXMTKLORNLYXDGTRWUXRWONPHVGAKSIXBBRIBVHKPONWREEFZDWMHENWCEGTRNDXMHOCDDPKUYFIWAVGXRAMCEXNPDVNEGVMBEKEERRXMAKSYTIBWNMHORUZVOSTBLONBMHOMDZICTVGIXLTFIX
Ergebnis des Kappa-Tests:
1: 4,53%
2: 4,533%
3: 4,451%
4: 4,48%
5: 8,196%
6: 4,408%
7: 4,348%
8: 4,543%
9: 4,58%
10: 8,266%
11: 4,503%
12: 4,402%
13: 4,408%
14: 4,389%
15: 7,999%
16: 4,734%
17: 4,377%
18: 4,394%
19: 4,662%
20: 8,117%
21: 3,993%
22: 4,264%
23: 4,506%
24: 4,428%
25: 7,771%
Wir wissen, dass der Klartext in deutsch verfasst ist und wir wissen, dass der Koinzidenzindex für Deutsch bei etwa 7,6% ist. Also markieren wir die entsprechenden Einträge der Ausgabe. Wir erhalten die Auffälligkeiten bei einer Periode von 5, 10, 15, 20 und 25. Die Schlüssellänge ist also 5, denn 10, 15, 20 und 25 sind Vielfache von 5 und logischerweise wiederholt sich ein fünfstelliger Schlüssel auch an diesen Stellen.Es gibt noch andere Tests, um die Schlüssellänge zu bestimmen, z. B. den Friedman Test, der die Ergebnisse des Kappatestes gegeneinander in Beziehung setzt und so eine annähernde Schlüssellänge ausrechnet.
Wahrscheinliche Schlüssellänge ca. 5,508
Aussagekräftiger ist aber der Kappa-Test. Anhand dessen Einzelwerte kann man sich ein besseres Bild machen und findet sich bei der Sprache und durch die Vielfachen bestätigt, die richtige Länge gefunden zu haben.Ein ähnlich wie der Kappa-Test funktionierender, ebenfalls statistischer Test ist der Chi-Quadrat-Test, der Chi-Quadrat bezogen auf die Einzelalphabete berechnet und miteinander vergleichbar macht. Das Einzelalphabet mit der wahrscheinlichsten Schlüssellänge weist normalerweise den höchsten Chi-Quadrat-Wert auf.
Ein weiterer Test zur Schlüssellängenbestimmung ist der Kasiski-Test. Dieser sucht nach Wiederholungen im Chiffrat und misst den Abstand zwischen deren Auftreten. Er spekuliert also darauf, dass gleiche Klartextbuchstaben mit gleichen Schlüsselbuchstaben verschlüsselt worden sind. Es wird erst bei längeren Texten aussagekräftig und schlägt besonders gut an, wenn zweimal das selbe, längere Wort mit dem Schlüssel auf selbe Weise verschlüsselt worden ist, weil bei diesem Wort zufälligerweise der Schlüssel an zwei Stellen im Chiffrat neu startete.
Bst.-Folge Abstand = Primfaktoren
----------------------------------
LBLVUXRWOL: 205 = 5 41
LBLVUXRWOL: 90 = 2 3 3 5
NLBLVUXRWO: 205 = 5 41
UZVOSTBLON: 290 = 2 5 29
...
Das Heraussuchen des richtigen Primfaktors (oder auch einem Produkt aus mehreren) ist allerdings nicht immer ganz eindeutig und benötigt etwas Erfahrung. Insofern ist der Kappa-Test leichter und sicherer zu handhaben.