Kasiski-Test

Finde die Schlüssellänge einer Chiffre mit wiederholtem Schlüssel aus den Abständen zwischen wiederholten Folgen.

Ausprobieren:

Geheimtext

Einstellungen

Folgenlänge

Faktoren bis

Drei Buchstaben ist die klassische Wahl. Zwei findet weit mehr Wiederholungen, die meisten davon Zufall, und vier oder mehr liefert nur die stärksten Belege, wofür ein längerer Text nötig ist.

Füge Geheimtext ein, um ihn zu untersuchen. Die Proben sind echter Vigenère-Geheimtext mit Schlüsseln aus fünf und sieben Buchstaben.

Mit dem Koinzidenzindex gegenprüfen

Die Chiffre mit dem Vigenère-Löser knacken

Mit bekanntem Schlüssel ver- oder entschlüsseln

So verwenden Sie Kasiski-Test

1
Geheimtext einfügen
Lege den verschlüsselten Text in das Feld. Ein paar hundert Buchstaben reichen meist, damit Wiederholungen auftauchen; unter etwa hundert gibt es oft nichts zu finden.
2
Folgenlänge wählen
Beginne bei drei Buchstaben. Wiederholt sich nichts, geh auf zwei herunter und behandle das Ergebnis als schwachen Beleg. Ist der Text lang und die Auswertung verrauscht, geh auf vier hinauf.
3
Den Rückhalt je Faktor lesen
Jede Kandidatenlänge wird gegen das gewertet, was der Zufall allein ihr gäbe, und vorgeschlagen wird das stärkste Mitglied jeder Familie von Teilern und Vielfachen. Die rohe Zahl der Abstände und die Zahl der verschiedenen Folgen dahinter stehen ebenfalls da: Ein Faktor, den mehrere verschiedene Folgen stützen, ist verlässlicher als eine geschwätzige Folge, die sich oft wiederholt, und dieses Urteil bleibt bei dir statt in der Punktzahl.

4
Die Länge an einen Löser geben
Gib die vorgeschlagene Länge an den Vigenère-Löser weiter oder prüfe sie gegen die Spaltentabelle des Koinzidenzindex-Rechners. Zwei Verfahren, die übereinstimmen, wiegen weit schwerer als eines allein.

Der Kasiski-Test, erklärt

Die Beobachtung, auf der das Verfahren ruht

Eine Vigenère-Chiffre verschiebt jeden Buchstaben um einen anderen Betrag und läuft dabei zyklisch durch ein Schlüsselwort. Das schlägt das Buchstabenzählen, denn derselbe Klartextbuchstabe wird je nach Position zu unterschiedlichen Geheimtextbuchstaben. Aber der Schlüssel wiederholt sich, und Wiederholung sickert durch.

Angenommen, das Wort THE steht zweimal im Klartext und trifft zufällig beide Male auf dieselben drei Schlüsselbuchstaben. Beide werden zu denselben drei Geheimtextbuchstaben. Der Abstand zwischen ihnen, in Buchstaben gezählt, ist dann eine ganze Zahl von Schlüsseldurchläufen, also ein Vielfaches der Schlüssellänge.

Ein einzelner solcher Zufall beweist wenig. Dutzende davon, faktorisiert und aufaddiert, zeigen geradewegs auf die Länge.

Was dieses Werkzeug misst

Jede Folge der gewählten Länge, die mehr als einmal vorkommt, wird mitsamt ihren Positionen gesammelt. Für jede werden alle paarweisen Abstände berechnet, nicht nur die Lücken zwischen Nachbarn, denn drei Vorkommen tragen drei Belege, und wer nur aufeinanderfolgende Lücken nimmt, wirft einen weg.

Danach bekommt jede Kandidatenlänge zwei Zahlen: wie viele Abstände sie teilt und aus wie vielen verschiedenen wiederholten Folgen mindestens einer davon stammt. Die Rangfolge nutzt die erste, um den Zufall bereinigt. Die zweite steht daneben und bleibt bewusst außerhalb der Wertung, denn sie ist ein Urteil und keine Arithmetik: Eine geschwätzige Folge, die sich achtmal wiederholt, bläht die Abstandszahl auf, ohne unabhängige Belege hinzuzufügen, während drei verschiedene Folgen, die sich auf einen Faktor einigen, drei getrennte Zufälle sind, die in dieselbe Richtung zeigen. Ruht die vorgeschlagene Länge auf einer einzigen Folge, ist genau das die Zahl, die dich zweifeln lassen sollte.

Die Teilerfalle

Hier stolpern die meisten, und es ist eher Rechnen als Kryptografie. Teilt 12 einen Abstand, dann teilen ihn auch 2, 3, 4 und 6. Jeder Teiler der echten Schlüssellänge erbt deren gesamte Punktzahl, eine nach Rückhalt sortierte Tabelle stellt also die kleinsten Faktoren nach oben, ganz gleich, wie der Schlüssel wirklich aussah.

Auch die Lösung ist Arithmetik. Belaste jeden Faktor mit dem Rückhalt, den der Zufall verschenkt: 2 teilt die Hälfte beliebiger Abstände umsonst, also muss ihre rohe Zahl halbiert werden, bevor sie neben einem Faktor stehen darf, der nur ein Sechstel teilt. So korrigiert schlägt die echte Schlüssellänge ihre eigenen Teiler, denn ein Teiler trägt nur seinen eigenen Anteil am Beleg. Korrigiere zusätzlich das Rauschen, das einem Faktor zusteht und mit ihm wächst, und die echte Länge schlägt auch ihre Vielfachen. Übrig bleibt eine einzige Regel ohne jeden gestellten Wert: In jeder Familie aus Teilern und Vielfachen bleibt das stärkste Mitglied. Die vollständige Auswertung steht weiter unten, damit du anders entscheiden kannst: Stützt sich die vorgeschlagene Länge auf nur eine Folge, während sechs Folgen einen anderen Faktor stützen, lohnt der einen Blick.

Wann es scheitert und was dann hilft

Der Kasiski-Test braucht Wiederholungen, und eine kurze Nachricht hat unter Umständen schlicht keine. Er verliert auch gegen Chiffren, die Wiederholung bewusst vermeiden, und er sagt gar nichts über ein Verfahren mit laufendem Schlüssel oder ein Einmalschlüsselsystem, bei dem der Schlüssel nie zyklisch wird.

Der Koinzidenzindex nähert sich derselben Frage von der Gegenseite: Er ignoriert Wiederholungen vollständig und misst die Buchstabenverteilung jeder möglichen Spaltenaufteilung. Weil beide Verfahren auf unterschiedlichen Eigenschaften des Textes beruhen, scheitern sie selten gemeinsam, und eine Länge, die beide stützen, ist meist die richtige.

Häufig gestellte Fragen

Was ist der Kasiski-Test?

Es ist ein 1863 von Friedrich Kasiski veröffentlichtes Verfahren, um die Schlüssellänge einer Chiffre mit wiederholtem Schlüssel zu finden. Trifft dieselbe Klartextfolge auf denselben Teil des Schlüssels, entsteht dieselbe Geheimtextfolge. Der Abstand zwischen zwei solchen Folgen ist daher ein Vielfaches der Schlüssellänge, und wer viele dieser Abstände faktorisiert, sieht die Länge hervortreten.

Warum schlägt es 6 vor, wenn 2 und 3 denselben Rückhalt haben?

Weil jeder Teiler der echten Länge genau dieselben Abstände teilt wie sie. Ist der Schlüssel 6 Buchstaben lang, erreichen 2 und 3 in der rohen Zählung mindestens so viel wie 6, und eine allein nach Rückhalt sortierte Liste würde bei fast jedem Text 2 empfehlen. Der Vorschlag behält den größten gut gestützten Faktor und streicht dessen Teiler, was ein Kryptoanalytiker nach Augenmaß ohnehin tut.

Wie viel Geheimtext ist nötig?

Das Verfahren lebt von Wiederholungen, und die werden seltener, je kürzer der Text ist. Ein paar hundert Buchstaben liefern meist mehrere Trigramm-Wiederholungen. Unter etwa hundert findest du oft nichts, und was du findest, ist ebenso wahrscheinlich Zufall wie Beleg.

Warum stimmen die Positionen nicht mit dem überein, was ich sehe?

Positionen und Abstände werden nur in Buchstaben gezählt. Leerzeichen, Ziffern, Satzzeichen und Zeilenumbrüche werden vor jeder Messung entfernt, denn die Chiffre hat sie ebenfalls nie gesehen. Ein Werkzeug, das sie mitzählt, liefert für denselben Text andere Zahlen.

Soll ich Folgen aus zwei Buchstaben verwenden?

Nur als letztes Mittel. In ein paar hundert Buchstaben wiederholen sich Paare ständig rein zufällig, und die Faktorenzählung wird zu Rauschen, das jede beliebige Länge bereitwillig stützt. Drei Buchstaben ist die klassische Wahl, weil eine zufällige Trigramm-Wiederholung selten genug ist, um etwas zu bedeuten.

Was, wenn Kasiski und der Koinzidenzindex sich widersprechen?

Vertraue dem mit mehr Belegen und bevorzuge eine Länge, die beide zulassen. Die Verfahren scheitern unterschiedlich: Kasiski tut sich schwer, wenn der Text kurz ist oder wenige Wiederholungen hat, der Koinzidenzindex, wenn der Schlüssel im Verhältnis zur Nachricht lang ist. Bei Widerspruch ist ein gemeinsames Vielfaches oder ein gemeinsamer Teiler der beiden Antworten oft die echte Länge.

Verlässt mein Geheimtext meinen Browser?

Nein. Die gesamte Untersuchung läuft auf der Seite. Nichts wird hochgeladen, protokolliert oder irgendwo gespeichert.