KryptologieDie Autokoinzidenzindizes eines Textes |
|
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
a | = | a0 a1 a2 | ... | aq-1aq aq+1 | ... | ar-1 |
a(q) | = | ar-qar-q+1ar-q+2 | ... | ar-1 a0 a1 | ... | ar-q-1 |
a(-q) | = | aq aq+1 aq+2 | ... | a2q-1a2qa2q+1 | ... | aq-1 |
Klar ist k(a,a(q)) = k(a,a(-q)).
Definition. Für einen Text a Î S* und eine natürliche Zahl q Î N heißt
kq(a) := k(a,a(q))der q-te Autokoinzidenzindex von a.
Achtung: In der Literatur ist diese Bezeichnung nicht üblich. Eine übliche Bezeichnung gibt es für diese Größe nicht.
Der q-te Autokoinzidenzindex definiert eine Abbildung
kq : S* ® Q.
Die konstante Abbildung k0 ist natürlich uninteressant.
Klar ist kq(a) = kr-q(a) für a Î Sr und 0 < q < r.
Betrachten wir nun einen periodisch polyalphabetisch verschlüsselten Text. Bei der Bestimmung von kq(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 kq(f(a)) » 1/n erwarten.
Ist allerdings l|q, so haben wir die Situation
s0a0 s1a1 | ... | s0aq s1aq+1 | ... |
s0a0 s1a1 | ... |
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 kq(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:
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].