Koinzidenzindex

aus Wikipedia, der freien Enzyklopädie

Der Koinzidenzindex eines oder zweier Texte ist eine statistische Methode, mit der verschlüsselte oder unverständliche Texte auf sprachliche Eigenschaften untersucht werden können. Er wird in der Kryptoanalyse und bei der Entschlüsselung historischer Schriftdokumente eingesetzt. Die Methode wurde von William Friedman für kryptologische Zwecke entwickelt und im Jahr 1920 in seiner bahnbrechenden Arbeit The Index of Coincidence and its Applications in Cryptography publiziert.

[Bearbeiten] Definition

Unter dem Begriff Koinzidenzindex sind vier Funktionen zusammengefasst, die meist mit den griechischen Buchstaben und (Kappa, Chi, Psi und Phi) bezeichnet werden. Oft wird als der Koinzidenzindex bezeichnet, wobei vom historischen Standpunkt wohl eher das Anrecht auf diesen Namen hat.

Gegeben seien zwei gleich lange Texte über dem gleichen Alphabet. Dann ist das der beiden Texte

wobei das Kronecker-Delta bezeichnet (also δ(x_i,x'_i) = 1, falls x_i = x'_i und 0 sonst).

Damit ist eine Zahl zwischen 0 und 1, wobei 1 genau dann auftritt, wenn beide Texte gleich sind. Werden die Zeichen zufällig mit gleicher Wahrscheinlichkeit aus einem Alphabet mit n Zeichen gewählt, so ist der Erwartungswert für gleich 1 / n, da jeder Summand mit Wahrscheinlichkeit 1 / n gleich 1 / k ist (und sonst gleich 0).

Da man in der Kryptoanalyse oft aus kurzen Texten viel Information herauspressen möchte, ist die Funktion , die, wie die folgenden Funktionen, auf Friedmans Mitarbeiter Solomon Kullback (1935) zurückgeht, gelegentlich aussagekräftiger:

wobei angibt, wie oft das -te Zeichen des Alphabets im Text T bzw. T' auftritt. Die Funktion hängt also allein von den Buchstabenhäufigkeiten der beiden Texte ab. Nun ist

Während angewandt auf zwei Texte aus zufälligen gleichverteilten Zeichen wie den Erwartungswert 1 / n hat, ist das für nicht mehr der Fall, da δ(x_i,x_i) immer gleich 1 ist. Deshalb schließt man sinnvollerweise bei der Summation die Zeichen an der gleichen Position aus und definiert

Ebenso wie kann allein aus den Buchstabenhäufigkeiten der beiden Text berechnet werden, jedoch ist für einen Text aus Zufallszeichen der Erwartungswert für gleich 1 / n, während er für größer ist (nämlich (n + k − 1) / nk). Insbesondere für kurze Texte ist der Unterschied markant.

[Bearbeiten] Bedeutung des Koinzidenzindex

Geht man von Texten aus gleichverteilten Zufallszeichen über zu in einer Sprache verfassten Texten, so ändert sich der erwartete Wert erheblich. Eine Faustregel besagt, dass er etwa doppelt so groß ist.

Nimmt man beispielsweise die 26 Zeichen des deutschen Alphabets (Umlaute werden durch ae, oe, ue ersetzt und Lücken und Satzzeichen ignoriert), so liegt der erwartete Wert für und etwa bei 0,0762, während im Englischen der Erwartungswert bei 0,0661 liegt. Bei Gleichverteilung der Buchstaben ist der Erwartungswert 1/26 also etwa 0,0385. Der wesentlich höhere Wert für die deutsche Sprache gegenüber der englischen Sprache spiegelt vor allem die wesentlich größere Häufigkeit des dominanten Buchstabens E im Deutschen (etwa 17,5%) gegenüber dem Englischen (etwa 12,7%) wider. Denn der Erwartungswert E_S für die Sprache S lässt sich aus den Buchstabenhäufigkeiten nach der Formel

berechnen, wobei p_i die Wahrscheinlichkeit des i-ten Zeichens des Alphabets in Texten der entsprechenden Sprache angibt.

In verwandten Sprachen ähneln sich oft die Erwartungswerte E_S, so dass bei unbekannten Texten anhand des Koinzidenzindex Vermutungen auf den zugehörigen Sprachraum angestellt werden können.

[Bearbeiten] Bedeutung in der Kryptoanalyse

Die wesentliche Eigenschaft ist hier, dass sich bei einer einfachen monoalphabetischen Substitutionsverschlüsselung weder noch ändern, sofern die beteiligten Texte auf die gleiche Art verschlüsselt sind. Eine sprachliche Zuordnung hinreichend langer Texte wird somit allein auf statistischer Basis möglich.

Bei einer periodischen polyalphabetischen Substitutionsverschlüsselung ist der Koinzidenzindex noch wertvoller, denn die Schlüssellänge der Verschlüsselung kann mit folgender Formel abgeschätzt werden (Friedman-Test). Für die Sprache S lautet die Formel für die Schlüssellänge h

Diese Formel lässt sich theoretisch herleiten unter der Annahme, dass alle Schlüsselzeichen verschieden sind. Der Wert ist also vor allem bei mit kurzen Schlüsseln verschlüsselten kurzen Texten aufschlussreich, insbesondere in Kombination mit dem Kasiski-Test. Hat man mit längeren Schlüsselwörtern verschlüsselte längere Texte zur Verfügung, so ist das folgende Vorgehen präziser.

Entfernt man vom Text T einmal die ersten r Zeichen und einmal die letzten r Zeichen, so erhält man zwei Texte, deren bestimmt werden kann. Ist r ein Vielfaches der Schlüssellänge, so sollte sein, da die verglichenen Einzelzeichen mit dem gleichen Schlüssel verschlüsselt sind. Ist r jedoch kein Vielfaches der Schlüssellänge, so ist mit einem deutlich niedrigeren Wert für zu rechnen, da die verglichenen Zeichen nur selten gleich verschlüsselt sind. Wiederholte Sequenzen im Schlüsselwort, mit denen man den Kasiski-Test und den Friedman-Test überlisten kann, beeinflussen die Ergebnisse hier nur ansatzweise und sollten in der Regel erkannt werden.

Auch bei nicht periodischen polyalphabetischen Verschlüsselungen lassen sich diese Methoden gewinnbringend nutzen. Insbesondere erkennt man bei zwei mit dem gleichen One-Time-Pad verschlüsselten Texten durch Berechnung von sofort diese kryptographische Sünde und kann zum Beispiel durch die Methode des wahrscheinlichen Wortes angewandt auf einen der Texte versuchen, Klartextsequenzen im anderen Text zu erzeugen.

Der Koinzidenzindex eignet sich also für sogenannte Ciphertext-only Angriffe (wo über den Inhalt des verschlüsselten Textes nichts bekannt sein muss) auf Substitutionsverschlüsselungen, wodurch diese Verfahren (natürlich außer einem korrekt angewendeten One-Time Pad) als ausgesprochen unsicher angesehen werden müssen.