Kryptologie Der Koinzidenzindex einer stochastischen Sprache

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

Definition

Für eine stochastische Sprache M ⊆ Σ^* mit Buchstabenhäufigkeiten p_s heißt

der Koinzidenzindex von M (nach FRIEDMAN).

Deutung: Für unabhängige Texte a, b ∈ M gleicher Länge ist

Beispiele. 1.) κ_Σ^* = 1/n. Im Spezialfall n = 26 ist κ_Σ^* ≈ 0.0385.

• für M = »Deutsch«: κ_M ≈ 0.0762,
• für M = »Englisch«: κ_M ≈ 0.0661.

Eigenschaften

Da ∑_s∈Σ p_s = 1, gilt 1/n ≤ κ_M ≤ 1, und zwar

1. κ_M = 1/n ⇔ alle p_s = 1/n,
2. κ_M = 1 ⇔ ein p_s = 1, alle übrigen = 0.

Das folgt aus

1. 1 = (∑_s∈Σ p_s×1)² ≤ ∑_s∈Σ p_s² × ∑_s∈Σ 1 = n × ∑_s∈Σ p_s²
   
   mit Gleichheit ⇔ (p_s)_s∈Σ = c×(1)_s∈Σ (als Vektor) ⇔ alle p_s gleich ⇔ alle p_s = 1/n.
   
   
2. ∑_s∈Σ p_s² ≤ ∑_s∈Σ p_s = 1, da 0 ≤ p_s ≤ 1, also p_s² ≤ p_s,
   
   mit Gleichheit ⇔ alle p_s² = p_s ⇔ alle p_s = 0 oder 1.

Anwendungen

1.) Bei polyalphabetischer Substitution ist die Wiederverwendung des gleichen Schlüssels mit hoher Wahrscheinlichkeit erkennbar (egal, ob periodisch oder nicht):

Für verschiedene polyalphabetische Substitutionen f, g ist zu erwarten, dass

Jetzt ist auch geklärt, dass bei gleicher Substitution

2.) Sei c ein Geheimtext aus einer polyalphabetischen Verschlüsselung eines Textes a ∈ M der Periode l. Welche Werte sind für κ_q(c) zu erwarten?

Daraus ergeben sich folgende erwartete Werte für den Autokoinzidenzindex:

1. Fall, l|r:

2. Fall, l kein Teiler von r:

Insbesondere gilt für q << r:

Damit ist auch das im Beispiel beobachtete Autokoinzidenzspektrum erklärt, und die typischen Autokoinzidenzspektren sehen so aus.