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 PORTA-Chiffre unmittelbar erfolgreich, wenn das Primäralphabet bekannt ist (»Drehscheibe verloren«), insbesondere trivial gegen die BELASO-Chiffre.

Ansatz von KASISKI

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 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« bekannt.

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

E-Mail an Pommerening@imsd.uni-mainz.de.