Wie berechnet man die Schlüssellänge der Vigenère-Chiffre?
Kapitoly: Die Vigenère-Chiffre, Wie man die Vigenère-Chiffre mit Kenntnis der Schlüssellänge knackt, Schätzung der Schlüssellänge der Vigenère-Chiffre, Wie berechnet man die Schlüssellänge der Vigenère-Chiffre?, Friedman-Test - Koinzidenzindex
Kasiski-Test
Es gibt in der Tat ein Verfahren, mit dem man die Länge des verwendeten Schlüssels zumindest annähernd abschätzen oder die Anzahl der möglichen Schlüssel auf eine einigermaßen kleine Menge reduzieren kann. Diese Schwachstelle wurde unabhängig voneinander von zwei Personen entdeckt, nämlich von Charles Babbage und Friedrich Kasiski. Babbage war der erste, aber Kasiski war der erste, der sie veröffentlichte, weshalb die Methode nach ihm benannt ist - die Kasiski-Methode oder der Kasiski-Test.
Der Hauptvorteil der Vigenère-Chiffre besteht darin, dass, wenn zwei gleiche Wörter in einem offenen Text vorkommen, diese mit unterschiedlichen Schlüsseln verschlüsselt werden. Normalerweise. Manchmal aber auch nicht, und genau das macht sich dieser Algorithmus zunutze.
Stellen wir uns vor, wir wollen den Text "Heute gehe ich ins Kino oder ins Theater" verschlüsseln. Ich werde entweder mit dem Auto oder mit dem Taxi fahren." Wir verwenden den Schlüssel "cipher". Der resultierende Chiffretext ist "vvjj pmril dg snea fmgf dg lnmavtf gobmil tsu gld scyvm fmgf sstneom". Leerzeichen werden absichtlich im Chiffretext belassen.
Interessant ist, dass das Wort "oder" zweimal im Klartext vorkommt. Im Idealfall würden beide Vorkommen im Chiffretext zu einem anderen Chiffretext verschlüsselt werden. Der Zufall wollte es aber, dass beide Vorkommen des Wortes "oder" zu dem Wort "fmgf" verschlüsselt wurden. Wie ist das passiert? Schauen wir uns an, wie der Schlüssel angewendet wurde:
| Ich gehe heute Abend ins Kino oder ins Theater. Ich werde entweder mit dem Auto oder mit dem Taxi fahren. |
| sifr asifr as ifra sifr as ifrasif rasifr asi fra sifra sifr asifras |
Wir sehen, dass bei der Schlüsselwiederholung das erste "oder" mit dem "sifr"-Teil des Schlüssels verschlüsselt wurde und das zweite "oder" mit genau demselben Teil des Schlüssels. Zufall ist dumm, er kommt vor.
Das Verfahren zur Ermittlung der Schlüssellänge
Aber wir können diesen Fehler nutzen, um die Länge des Schlüssels zu schätzen. Nehmen wir nun an, wir haben nur den Chiffretext "vvjj pmril dg snea fmgf dg lnmavtf gobmil tsu gld scyvm fmgf sstneom" als Eingabe. Wir stellen fest, dass die beiden Wörter "fmgf" identisch sind. Wir vermuten, dass es sich ursprünglich um die gleichen Wörter handelte, die versehentlich mit dem gleichen Chiffrierwort verschlüsselt wurden.
Wir berechnen nun den Abstand zwischen diesen Wörtern. Wir zählen die Anzahl der Buchstaben vom Anfang des ersten Wortes "fmgf" bis zum Anfang des zweiten Wortes "fmgf", d.h. diesen Abstand: "vvjj pmril dg snea fmgf dg lnmavtf gobmil tsu gld scyvm fmgf sstneom" (Leerzeichen nicht mitgerechnet). Insgesamt gibt es 30 Buchstaben. Wenn wir richtig lagen und die beiden Wörter "fmgf" tatsächlich dasselbe Wort sind, dann ist der Schlüssel so lang wie einer der beiden Faktoren von 30. Und warum? Einer der Faktoren ist zum Beispiel die Zahl 6. Wenn der Schlüssel die Länge 6 hätte, sagen wir den Schlüssel "abcdef", dann würde die Verschlüsselung des Klartextes wie folgt aussehen:
| Ich gehe heute Abend ins Kino oder ins Theater. Ich werde entweder mit dem Auto oder mit dem Taxi dorthin fahren. |
| abcd efabc de fabc defa bc defabcd efabcd efa bcd efabc defa bcdefab |
Wir können sehen, dass die Wörter wieder mit demselben Teil des Schlüssels verschlüsselt werden würden. Wenn die Wörter ein Vielfaches der Schlüssellänge voneinander entfernt sind, verschlüsseln sie denselben Teil des Schlüssels.
An diesem Punkt wissen wir also, dass der Schlüssel wahrscheinlich eine der Längen 2, 3, 5, 6, 10, 15, 30 hat. Das ist immer noch eine ganze Menge an Möglichkeiten - wir können das Verfahren weiter anwenden und versuchen, ein anderes Paar gleich verschlüsselter Wörter zu finden. Wenn wir feststellen, dass ihr Abstand 15 beträgt, wären wir bei 3 und 5 angelangt, und von da an wäre es ein Kinderspiel.
Online-Tool zum Knacken der Vigenère-Chiffre
Das Tool demonstriert den vorherigen Algorithmus. Es versucht, identische Textblöcke im Chiffriertext zu finden. Wenn es solche Blöcke findet, berechnet es daraus die wahrscheinlichen Schlüssellängen und versucht, den Schlüssel für alle Längen zu finden. Dann wählt es den besten Schlüssel aus. Wenn kein passender Block gefunden wird, bricht der Algorithmus ab.
Natürlich könnte das Tool noch verbessert werden, indem man versucht, alle Schlüssel bis zu einer bestimmten Grenze abzukürzen, falls dies nicht gelingt. Der Algorithmus probiert nur Schlüssel aus, deren Länge kleiner oder gleich st ist.
Dieser Algorithmus kann oft einen langen Schlüssel in relativ kurzer Zeit verarbeiten, wenn der Text lang genug ist. Sie können versuchen, diesen Text in das Tool einzufügen und ihn zu brechen. Das Tool wird einen Schlüssel der Länge 58 finden.