Zum Inhalt springen

Koinzidenzindex

Aus FLBK-Wiki
Version vom 15. November 2026, 07:47 Uhr von Flbkwikiadmin (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „Ob ein Geheimtext mit einem einzigen Alphabet oder mit mehreren verschlüsselt wurde, lässt sich an einer einzigen Kennzahl ablesen: dem Koinzidenzindex. ==Definition== Der '''Koinzidenzindex''' <math>IC</math> (englisch: index of coincidence) eines Textes ist die Wahrscheinlichkeit, dass zwei zufällig aus dem Text herausgegriffene Buchstaben gleich sind. Er misst, wie ungleichmäßig die Buchstaben verteilt sind: * Kommen wenige Buchstaben sehr oft vo…“)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Ob ein Geheimtext mit einem einzigen Alphabet oder mit mehreren verschlüsselt wurde, lässt sich an einer einzigen Kennzahl ablesen: dem Koinzidenzindex.

Definition

Der Koinzidenzindex [math]\displaystyle{ IC }[/math] (englisch: index of coincidence) eines Textes ist die Wahrscheinlichkeit, dass zwei zufällig aus dem Text herausgegriffene Buchstaben gleich sind. Er misst, wie ungleichmäßig die Buchstaben verteilt sind:

  • Kommen wenige Buchstaben sehr oft vor, ist der Koinzidenzindex hoch.
  • Kommen alle Buchstaben gleich oft vor, ist er niedrig.

Berechnung

Der Text hat [math]\displaystyle{ n }[/math] Buchstaben. Der Buchstabe A kommt [math]\displaystyle{ n_1 }[/math]-mal vor, B kommt [math]\displaystyle{ n_2 }[/math]-mal vor und so weiter bis Z mit [math]\displaystyle{ n_{26} }[/math]. Dann gilt:

[math]\displaystyle{ IC = \frac{n_1 \cdot (n_1 - 1) + n_2 \cdot (n_2 - 1) + \dots + n_{26} \cdot (n_{26} - 1)}{n \cdot (n - 1)} }[/math]

Im Zähler steht für jeden Buchstaben die Anzahl der Möglichkeiten, nacheinander zwei Stellen mit diesem Buchstaben zu treffen. Im Nenner steht die Anzahl der Möglichkeiten, nacheinander zwei beliebige Stellen zu treffen.

Deutung

Text Koinzidenzindex
deutscher Klartext etwa 0,076
Text aus zufälligen, gleich häufigen Buchstaben [math]\displaystyle{ \frac{1}{26} \approx 0{,}038 }[/math]
  • Bei einer monoalphabetischen Substitution werden die Buchstaben nur umbenannt. Die Häufigkeiten bleiben erhalten, der Koinzidenzindex des Geheimtextes liegt deshalb wie beim Klartext bei etwa 0,076. Dasselbe gilt für eine Transposition.
  • Bei einer polyalphabetischen Substitution wie dem Vigenère-Verfahren gleichen sich die Häufigkeiten an. Der Koinzidenzindex sinkt, und zwar umso weiter in Richtung 0,038, je länger das Schlüsselwort ist.

Die Werte gelten für lange, gewöhnliche Texte. Kurze Texte weichen deutlich ab.

Friedman-Test

Der Friedman-Test schätzt aus dem Koinzidenzindex die Länge [math]\displaystyle{ l }[/math] des Schlüsselwortes eines Vigenère-Geheimtextes. William Friedman hat ihn in den 1920er-Jahren entwickelt. Für deutsche Texte lautet die Schätzformel:

[math]\displaystyle{ l \approx \frac{0{,}0377 \cdot n}{(n - 1) \cdot IC - 0{,}0385 \cdot n + 0{,}0762} }[/math]

Dabei ist 0,0762 der Koinzidenzindex deutscher Texte, 0,0385 der Koinzidenzindex zufälliger Texte und 0,0377 die Differenz der beiden Werte.

Der Friedman-Test liefert nur eine Größenordnung, keine exakte Länge. Dafür gibt es zwei Gründe:

  • Der Wert 0,0762 gilt nur im Durchschnitt langer Texte. Ein einzelner Text weicht davon ab, vor allem ein kurzer.
  • Die Formel setzt voraus, dass die Buchstaben des Schlüsselwortes verschieden sind. Kommt ein Buchstabe im Schlüsselwort mehrfach vor, ist der Koinzidenzindex höher, und der Schätzwert fällt zu klein aus.

Der Friedman-Test ergänzt den Kasiski-Test: Der Kasiski-Test liefert mögliche Längen als gemeinsame Teiler von Abständen, der Friedman-Test zeigt, welche davon infrage kommt.

Beispiele

Koinzidenzindex eines kurzen Textes berechnen

Der Text ANANAS hat [math]\displaystyle{ n = 6 }[/math] Buchstaben.

Buchstabe Anzahl [math]\displaystyle{ n_i }[/math] [math]\displaystyle{ n_i \cdot (n_i - 1) }[/math]
A 3 [math]\displaystyle{ 3 \cdot 2 = 6 }[/math]
N 2 [math]\displaystyle{ 2 \cdot 1 = 2 }[/math]
S 1 [math]\displaystyle{ 1 \cdot 0 = 0 }[/math]
Summe 6 [math]\displaystyle{ 8 }[/math]
[math]\displaystyle{ IC = \frac{8}{6 \cdot 5} = \frac{8}{30} \approx 0{,}267 }[/math]

Der Wert ist sehr hoch, weil der kurze Text nur aus drei verschiedenen Buchstaben besteht.

Klartext und Geheimtext vergleichen

Text Länge [math]\displaystyle{ n }[/math] Koinzidenzindex
Klartext des Beispiels aus dem Artikel Kasiski-Test 125 0,1239
derselbe Text, mit dem Vigenère-Verfahren verschlüsselt 125 0,0542

Der Klartext hat hier einen besonders hohen Koinzidenzindex, weil in dem kurzen Text E und N noch häufiger sind als im Durchschnitt. Durch die Verschlüsselung mit einem Schlüsselwort aus drei Buchstaben sinkt der Wert deutlich: Es liegt eine polyalphabetische Substitution vor.

Schlüssellänge mit dem Friedman-Test schätzen

Für den Geheimtext aus dem Artikel Kasiski-Test gilt [math]\displaystyle{ n = 125 }[/math] und [math]\displaystyle{ IC \approx 0{,}0542 }[/math].

[math]\displaystyle{ l \approx \frac{0{,}0377 \cdot 125}{124 \cdot 0{,}0542 - 0{,}0385 \cdot 125 + 0{,}0762} \approx \frac{4{,}71}{1{,}98} \approx 2{,}4 }[/math]

Der Friedman-Test schätzt die Schlüssellänge auf etwa 2,4. Tatsächlich hat das Schlüsselwort 3 Buchstaben. Bei einem so kurzen Text ist die Schätzung grob. Sie zeigt aber, dass der Schlüssel kurz ist, und passt damit zum Ergebnis des Kasiski-Tests.