Kryptologie Die Autokoinzidenzindizes eines Textes

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

Definition

Für die Kryptoanalyse periodischer polyalphabetischer Chiffren ist die folgende Konstruktion besonders interessant:

Sei a_(q) bzw. a_(-q) der um q Stellen zyklisch nach rechts bzw. links verschobene Text, also

Klar ist κ(a,a_(q)) = κ(a,a_(-q)).

Definition. Für einen Text a ∈ Σ^* und eine natürliche Zahl q ∈ N heißt

κ_q(a) := κ(a,a_(q))

Achtung: In der Literatur ist diese Bezeichnung nicht üblich. Eine übliche Bezeichnung gibt es für diese Größe nicht.

Beispiele.

Eigenschaften

Der q-te Autokoinzidenzindex definiert eine Abbildung

κ_q : Σ^* → Q.

Die konstante Abbildung κ₀ ist natürlich uninteressant.

Klar ist κ_q(a) = κ_r-q(a) für a ∈ Σ^r und 0 < q < r.

Anwendung

Betrachten wir nun einen periodisch polyalphabetisch verschlüsselten Text. Bei der Bestimmung von κ_q(a) wird im allgemeinen die Verschiebung q kein Vielfaches der Periode l sein. Bei der Zählung der Koinzidenzen treffen also Buchstaben zusammen, die im wesentlichen unabhängig voneinander monoalphabetisch verschlüsselt sind. Wir werden also nach I.3.1 ein Ergebnis κ_q(f(a)) ≈ 1/n erwarten.

Ist allerdings l|q, so haben wir die Situation

wo also die untereinander stehenden Zeichen mit der gleichen monoalphabetischen Substitution verschlüsselt sind und somit genau dann übereinstimmen, wenn sie im Klartext übereinstimmten. Wir erwarten jetzt also, dass κ_q(f(a)) in der Nähe der für die Sprache typischen Zeichenkoinzidenz liegt.

Genauer ist also für eine polyalphabetische Verschlüsselung f der Periode l folgendes zu erwarten:

1. Ist l kein Teiler von q und r-q, so ist κ_q(f(a)) ≈ 1/n.
2. Ist aber l Teiler von q und q klein gegenüber r, so ist κ_q(f(a)) ≈ κ_q(a) ungefähr die typische Zeichenkoinzidenz.

Das ist die zweite Anwendung der Koinzidenzbestimmung: Erkennung der Periode einer polyalphabetischen Substitution an den Autokoinzidenzindizes. Im Vergleich zur Parallelstellenanalyse berücksichtigt ein Autokoinzidenzindex auch Wiederholungen der Länge 1 im Abstand q; d. h., die Information, die die Periode im Geheimtext hinterlässt, wird wesentlich besser ausgenützt als bei der Parallestellensuche nach KASISKI. (»Statt nur einem oberflächlichen Foto wird ein Röntgenbild angefertigt.«) Man kann hoffen, dass sich die Periode einer polyalphabetischen Chiffre deutlich verrät.

Um eine Vorstellung von der Bedeutung dieser noch vagen Aussagen zu erhalten, rechnen wir als nächstes ein Beispiel durch; das dazu benützte Perl-Programm steht hier [online-Aufruf].