Kryptologie Periodenanalyse nach KASISKI

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Historische Ansätze zur Kryptoanalyse der periodischen polyalphabetischen Chiffre

PORTA und die ARGENTIs:

• Erraten des Schlüssels.
• Wahrscheinliches Wort.

Angriff mit bekanntem Klartext

... ist schwer bei unabhängigen Alphabeten.

... ist gegen die Drehscheiben-Chiffre unmittelbar erfolgreich, wenn das Primäralphabet bekannt ist (»Drehscheibe verloren«), insbesondere trivial gegen die BELASO-Chiffre.

Historisches Beispiel

Im ersten Weltkrieg nutzte die britische Marine unter anderem die GRONSFELD-Chiffre, also die BELASO-Chiffre mit einer Verschiebung um höchstens neun Zeichen, bei der der Schlüssel durch eine periodisch zu wiederholende Ziffernfolge beschrieben werden kann. Dem Mathematiker Ludwig Föppl, der beim deutschen Funker-Kommando diente, fiel auf, dass eine bestimmte Gruppe von 18 Buchstaben im britischen Funkverkehr ziemlich häufig vorkam. Er vermutete, dass dies eine Standard-Floskel sein müsse, und hatte schließlich mit »What is your position?« Erfolg - ohne dass er vorher gewusst hatte, welche Chiffre verwendet wird.

Übungsaufgabe. Welches ist der Schlüssel, wenn der von Pöppel beobachtete Geheimtext AIGYL UCPAW SQWJZ NRP war?

Quelle: Hilmar-Detlef Brückner: Germany's first Cryptanalysis on the western front: Decrypting british and french naval ciphers in World War I. Cryptologia 29 (2005), 1 - 22.

Angriff auf kurze »Vigenère«-Chiffrate:

Tobias Schrödel: Breaking short Vigenère ciphers. Cryptologia 32 (2008), 334 - 347.

Ansatz von KASISKI

[F. W. KASISIKI, preussischer Major, 1805 - 1881]

1. Schritt: Bestimmung der Periode l.
2. Schritt: Anordnen des Textes in Zeilen der Länge l. Die Spalten (»Kolonnen«, »Latten«) sind dann jeweils für sich monoalphabetisch verschlüsselt.

Bei der Kryptoanalyse der Spalten tritt allerdings die Schwierigkeit auf, dass sie keine zusammenhängenden Texte repräsentieren. Textmuster sind keine Hilfe; es ist nur die Häufigkeitsanalyse möglich.

Allerdings gibt es Vereinfachungen, wenn die Alphabete abhängig sind:

• Zurechtrücken der Häufigkeitsgebirge,
• Symmetrie der Position.

Besonders einfach ist das Brechen der BELASO-Chiffre, sobald die Periode bekannt ist: Hier ist jede Kolonne nur noch CAESAR-verschlüsselt, es muss also jeweils nur 1 Buchstabe identifiziert werden.

Ansätze zur Periodenbestimmung

1. Exhaustionsmethode: Es werden die Längen l = 1, 2, 3, ... durchprobiert. Das richtige l verrät sich dadurch, dass die Häufigkeiten in den Kolonnen die erwartete Verteilung haben.
2. Parallelstellensuche (Mustererkennung) nach KASISKI: siehe unten.
3. Koinzidenzindex (Statistik) nach FRIEDMAN, KULLBACK und SINKOV: siehe den nächsten Abschnitt.

Die Parallelstellensuche wurde von KASISKI 1863 veröffentlicht und beendete den Glauben an die Unbrechbarkeit der periodischen polyalphabetischen Substitution.

[In einem Einzelfall hatte sie schon PORTA angewendet, ihm war die Möglichkeit eines systematischen Vorgehens aber nicht in den Sinn gekommen. BABBAGE [Bild] (1791 - 1871) hatte das Verfahren etwa 10 Jahre vor KASISKI entdeckt, seine Entdeckung aber geheim gehalten, so dass er ohne Einfluss auf die Entwicklung der Kryptologie blieb.]

Im Gegensatz zur Exhaustionsmethode machen die beiden anderen Methoden sofort deutlich, wenn keine Periodizität vorliegt.

Die Parallelstellensuche

... beruht auf folgenden Beobachtungen:

1. Wenn ein Klartext mit l Alphabeten in zyklischer Reihenfolge chiffriert wird und eine Buchstabengruppe k-mal im Klartext vorkommt, so wird sie im Geheimtext ungefähr je k/l-mal mit jedem der Alphabete verschlüsselt beginnen.
2. Wenn diese Buchstabengruppe so auf gleiche Weise verschlüsselt wird, entsteht im Geheimtext ein wiederholtes Muster in einem Abstand, der ein Vielfaches von l ist.
3. Nicht jede Wiederholung im Geheimtext muss so entstanden sein; hierfür ist die Wahrscheinlichkeit aber deutlich geringer. Die Berechnung dieser Wahrscheinlichkeit ist in der Stochastik als »Geburtstagsphänomen« [PDF-Datei] bekannt, siehe auch.

K. Pommerening: Kasiski's Test: Couldn't the repetitions be by accident? Cryptologia 30 (2006), 346-352.

Hier ein Perl-Programm, das Parallelstellen sucht; Direktaufruf per Formular.

Übungsaufgabe. Suche die Parallelstellen in einem der zuvor erstellten polyaphabetischen Geheimtexte.