Kasiski-Test
Das Vigenère-Verfahren verwischt die Buchstabenhäufigkeiten, hat aber eine Schwachstelle: Das Schlüsselwort wiederholt sich. Der Kasiski-Test macht daraus einen Angriff.
Definition
Der Kasiski-Test ist ein Verfahren der Kryptoanalyse, das die Länge des Schlüsselwortes eines Vigenère-Geheimtextes bestimmt. Er sucht im Geheimtext nach Zeichenfolgen, die mehrfach vorkommen, und schließt aus ihren Abständen auf die Schlüssellänge [math]\displaystyle{ l }[/math]. Friedrich Wilhelm Kasiski hat das Verfahren 1863 veröffentlicht.
Die Idee dahinter: Steht dasselbe Klartextstück zweimal im Text und trifft es beide Male auf dieselbe Stelle des Schlüsselwortes, dann entsteht beide Male dasselbe Geheimtextstück. Das geschieht immer dann, wenn der Abstand der beiden Stellen ein Vielfaches der Schlüssellänge ist.
Vorgehen
- Im Geheimtext alle Zeichenfolgen aus mindestens drei Buchstaben suchen, die mehrfach vorkommen.
- Für jede Wiederholung den Abstand bestimmen: Position des zweiten Vorkommens minus Position des ersten. Kommt eine Folge öfter als zweimal vor, zählen die Abstände aufeinanderfolgender Vorkommen.
- Die Schlüssellänge aus den Abständen bestimmen.
- Den Geheimtext in Teiltexte zerlegen und jeden Teiltext mit der Häufigkeitsanalyse brechen.
Schlüssellänge bestimmen
Die Schlüssellänge [math]\displaystyle{ l }[/math] teilt jeden Abstand, der durch eine echte Wiederholung entstanden ist. Gesucht sind deshalb die gemeinsamen Teiler der Abstände. Der größte von ihnen ist der größte gemeinsame Teiler (ggT), berechnet über Teilerlisten oder mit dem euklidischen Algorithmus.
- Meist ist die Schlüssellänge der ggT der Abstände oder ein Teiler davon.
- Eine Wiederholung kann auch zufällig entstehen. Ihr Abstand passt dann nicht zu den anderen. Ein einzelner Ausreißer wird weggelassen, vor allem bei kurzen Folgen aus nur drei Buchstaben.
- Lange Wiederholungen sind fast nie zufällig und deshalb besonders zuverlässig.
Teiltexte bilden
Ist die Schlüssellänge [math]\displaystyle{ l }[/math] bekannt, wird der Geheimtext in [math]\displaystyle{ l }[/math] Teiltexte zerlegt: Der erste Teiltext enthält die Buchstaben an den Positionen [math]\displaystyle{ 1; 1 + l; 1 + 2l; \dots }[/math], der zweite die Buchstaben an den Positionen [math]\displaystyle{ 2; 2 + l; 2 + 2l; \dots }[/math] und so weiter. Das erste Zeichen des Geheimtextes hat dabei die Position 1 und gehört zum ersten Buchstaben des Schlüsselwortes.
Alle Buchstaben eines Teiltextes wurden mit demselben Schlüsselbuchstaben verschlüsselt. Jeder Teiltext ist deshalb eine Caesar-Verschlüsselung: Der häufigste Buchstabe steht vermutlich für das E, und aus dem Abstand zum E ergibt sich der Schlüsselbuchstabe.
Grenzen
- Der Geheimtext muss lang genug sein, damit Wiederholungen vorkommen und die Teiltexte eine brauchbare Statistik liefern.
- Je länger das Schlüsselwort ist, desto seltener treffen gleiche Klartextstücke auf dieselbe Stelle des Schlüssels.
- Gegen einen Schlüssel, der sich nicht wiederholt, ist der Test machtlos (siehe One-Time-Pad).
Eine zweite Methode, die Schlüssellänge zu schätzen, ist der Friedman-Test.
Beispiele
Schlüssellänge eines Geheimtextes bestimmen
Dieser Geheimtext wurde mit dem Vigenère-Verfahren verschlüsselt, das Schlüsselwort ist unbekannt:
BMRTR EXNDM ESXNY XBPGD PFWPZ DTXRZ LEYCE OXNLU EYWGT XSDXN HBROB ECHSP GDPGN ZANPK ERXNH XLVXN DBEUX DPGMZ KGPGS PAEYP ICGAN ADPGR ZLEYG EMXNO XMHXG
Folgen, die mehrfach vorkommen, mit ihren Positionen (das erste Zeichen des Geheimtextes hat die Position 1):
| Folge | Positionen | Abstände |
|---|---|---|
XND |
7, 79 | 72 |
PGDP |
18, 60 | 42 |
RZLEY |
29, 110 | 81 |
XNH |
49, 73 | 24 |
DPG |
62, 86, 107 | 24, 21 |
Die Teiler der Abstände:
| Abstand | Teiler |
|---|---|
| 21 | 1, 3, 7, 21 |
| 24 | 1, 2, 3, 4, 6, 8, 12, 24 |
| 42 | 1, 2, 3, 6, 7, 14, 21, 42 |
| 72 | 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72 |
| 81 | 1, 3, 9, 27, 81 |
Gemeinsame Teiler aller Abstände sind nur 1 und 3. Die Länge 1 wäre eine Caesar-Verschlüsselung. Die Schlüssellänge ist also vermutlich [math]\displaystyle{ l = 3 }[/math].
Teiltexte bilden und das Schlüsselwort ermitteln
Der Geheimtext aus dem ersten Beispiel wird in drei Teiltexte zerlegt:
| Teiltext | Positionen | Zeichen | häufigste Buchstaben |
|---|---|---|---|
| 1 | 1, 4, 7, … | BTXMX XGFZX LCXUW XXBBH GGAKX XXBXG KGAPG AGLGX XX |
X (14), G (8), B (4) |
| 2 | 2, 5, 8, … | MRNEN BDWDR EENEG SNRES DNNEN LNEDM GSEIA DREEN MG |
E (10), N (9), D (5) |
| 3 | 3, 6, 9, … | REDSY PPPTZ YOLYT DHOCP PZPRH VDUPZ PPYCN PZYMO H |
P (10), Y (5), Z (4) |
In jedem Teiltext wurde jeder Buchstabe um denselben Wert verschoben. Steht der häufigste Buchstabe für E mit dem Wert 4, ergibt sich der Schlüsselbuchstabe aus seinem Wert minus 4:
| Teiltext | häufigster Buchstabe | Rechnung | Schlüsselbuchstabe |
|---|---|---|---|
| 1 | X |
[math]\displaystyle{ (23 - 4) \bmod 26 = 19 }[/math] | T
|
| 2 | E |
[math]\displaystyle{ (4 - 4) \bmod 26 = 0 }[/math] | A
|
| 3 | P |
[math]\displaystyle{ (15 - 4) \bmod 26 = 11 }[/math] | L
|
Das Schlüsselwort lautet vermutlich TAL. Die Entschlüsselung mit dem Vigenère-Verfahren bestätigt es:
IMGAR TENST EHENN EBEND EMWEG DIERO SENJE DENAB ENDGI ESSEN WIRDI EROSE NDENN OHNER EGENW ELKEN SIEJE DENMO RGENS EHENW IRNAC HDENR OSENN EBEND EMWEG
Ergibt ein Versuch keinen lesbaren Text, prüft man in den betroffenen Teiltexten den zweithäufigsten Buchstaben. Je kürzer die Teiltexte sind, desto öfter ist das nötig.