Friedman-Test - Koinzidenzindex

Eine andere Möglichkeit, die Vigenère-Chiffre zu knacken, ist der Friedman-Test, mit dem sich relativ leicht überprüfen lässt, ob ein Chiffretext mit einem Schlüssel einer bestimmten Länge verschlüsselt wurde. Es ist daher eine gute Idee, den Friedman-Test mit dem Kasiski-Test zu kombinieren, der uns eine Reihe wahrscheinlicher Schlüssellängen liefert, und den Friedman-Test zu verwenden, um die wahrscheinlichste Schlüssellänge auszuwählen.

Koinzidenz-Index

Der Koinzidenzindex gibt an, wie wahrscheinlich es ist, dass zwei zufällig aus dem Text ausgewählte Buchstaben identisch sind. Bei dem Text "aaaaaa" beispielsweise besteht eine Wahrscheinlichkeit von 100 %, dass das ausgewählte Paar gleich ist. Bei dem Text "aaaabbc" ist die Wahrscheinlichkeit 1/3, und die größte Wahrscheinlichkeit ist, dass wir die beiden Buchstaben "a" wählen.

Wie kann man den Koinzidenzindex berechnen? Nehmen wir einen Eingabetext t und Werte n_a, n_b, …, n_z, die die Anzahl der Vorkommen eines bestimmten Buchstabens im Text t angeben. Für t = "aaaabbc" haben wir also die Werte von n_a = 4, n_b = 2, n_c = 1 und die anderen Werte sind Null.

Als nächstes zählen wir die Anzahl der identischen Buchstabenpaare. Wie viele verschiedene Paare des Buchstabens "a" gibt es? Wir können dieses Paar "aaaabbc" nehmen oder vielleicht dieses"aaaabbc" und ein paar andere. Wie viele gibt es insgesamt? Da die Reihenfolge keine Rolle spielt, wählen wir Kombinationen. Wir haben insgesamt n_a Möglichkeiten, den Buchstaben "a" zu wählen, und wir haben insgesamt n_a − 1 Möglichkeiten, ein weiteres "a" hinzuzufügen. Da die Reihenfolge keine Rolle spielt, fügen wir dem Wert zwei weitere hinzu. Somit ist die Anzahl aller verschiedenen Paare des Buchstabens "a" gleich:

$$ \frac{n_a\cdot(n_a-1)}{2} $$

Wir können diese Formel für alle Buchstaben anwenden, d.h. die Anzahl aller möglichen gleichen Buchstabenpaare ist gleich

$$ \frac{n_a\cdot(n_a-1)}{2} + \frac{n_b\cdot(n_b-1)}{2} + \dots + \frac{n_z\cdot(n_z-1)}{2}. $$

Für unseren Text würden wir erhalten:

$$ \frac{4\cdot3}{2}+\frac{2\cdot1}{2}+\frac{1\cdot0}{2}=7 $$

A sind die folgenden Paare gleicher Buchstaben:"aaaabbc", "aaaabbc", "aaaabbc", "aaaabbc", "aaaabbc", "aaaabbc", "aaaabbc", "aaaabbc".

Die obige Formel kann mit Hilfe der Summe aufgeschlüsselt werden (hier ist x bereits eine Variable, kein Buchstabe):

$$ \sum_{x=„a“}^{„z“} \frac{n_x\cdot(n_x-1)}{2} $$

Um die Wahrscheinlichkeit zu erhalten, dividiert man diesen Wert durch die Anzahl aller möglichen Buchstabenpaare (gleich oder verschieden), die im Text vorkommen. Wenn wir die Länge des Textes mit N bezeichnen, dann ist die Anzahl aller Paare

$$ \frac{N \cdot (N - 1)}{2} $$

Der Grund ist wieder derselbe: Wir haben insgesamt N Möglichkeiten, einen Buchstaben auszuwählen, und wir haben insgesamt N − 1 Möglichkeiten, einen weiteren Buchstaben hinzuzufügen, um ein Paar zu bilden. Da die Reihenfolge keine Rolle spielt, dividieren wir durch zwei. Die Gesamtwahrscheinlichkeit und der Koexistenzindex sind also gleich, nämlich IK:

$$ IK = \frac{\sum_{x=„a“}^{„z“} \frac{n_x\cdot(n_x-1)}{2}}{\frac{N \cdot (N - 1)}{2}} $$

Wir können die Zweier im Nenner abschneiden, so dass wir übrig bleiben:

$$ IK = \frac{\sum_{x=„a“}^{„z“} n_x\cdot(n_x-1)}{N \cdot (N - 1)} $$

Dies ist die endgültige Formel. Wenn wir die Werte aus unserem Text einsetzen:

$$ IK =\frac{\sum_{x=„a“}^{„z“} n_x\cdot(n_x-1)}{N \cdot (N - 1)}=\frac{4\cdot3+2\cdot1+1\cdot0}{7\cdot6}=\frac{14}{42}=\frac13 $$

Der Koinzidenzindex des Textes "aaaabbc" ist gleich einem Drittel. Das heißt, wir haben eine Wahrscheinlichkeit von einem Drittel, dass, wenn wir zufällig zwei Buchstaben im Text auswählen, diese Buchstaben gleich sind.

Koinzidenzindex eines Zufallstextes

Bei einem langen Zufallstext mit gleichmäßiger Verteilung der Buchstaben kommen alle Buchstaben des Textes ungefähr gleich häufig vor. Bei einem unendlich langen Text mit gleichmäßiger Verteilung der Buchstaben haben wir immer eine Wahrscheinlichkeit von 1/26, einen bestimmten Buchstaben zufällig zu wählen (wir zählen das englische Alphabet mit 26 Buchstaben). Wie hoch ist der Zufallsindex eines solchen Textes?

In einem solchen Text würden wir für jeden Buchstaben die Wahrscheinlichkeit $\frac{1}{26}\cdot\frac{1}{26}$ erhalten, dass wir das gleiche Buchstabenpaar wählen. Da wir insgesamt 26 verschiedene Buchstaben haben, ist die Gesamtwahrscheinlichkeit, dass wir zufällig zwei identische Buchstaben auswählen

$$ \sum_{i=1}^{26} \frac{1}{26}\cdot\frac{1}{26} = \sum_{i=1}^{26} \frac{1}{676} = \frac{26}{676} = \frac{1}{26}. $$

Sprachlicher Zufallsindex

Da ein Text, der in einer gemeinsamen Sprache wie Tschechisch geschrieben ist, kein Zufallstext ist, hat er einen anderen Koinzidenzindex als ein Zufallstext. Wie berechnet man den Koinzidenzindex einer Sprache? Kurz gesagt, wir sammeln irgendwo haufenweise tschechische Texte und berechnen den Koinzidenzindex dieser Texte.

Je mehr Texte wir sammeln, desto bessere Ergebnisse erhalten wir. Natürlich gibt es so etwas wie einen "offiziellen Koinzidenzindex der tschechischen Sprache" nicht, denn ein solcher Index ändert sich de facto mit jedem neu geschriebenen/gesprochenen Wort in der tschechischen Sprache.

Um dies zu veranschaulichen, habe ich versucht, diese Analyse anhand von fünftausend tschechischen Büchern durchzuführen, die ich auf saveto gekauft habe. Das Ergebnis war, dass der Koinzidenzindex der 5000 tschechischen Bücher ungefähr 0,0588 beträgt. Wir können also sagen, dass der Koinzidenzindex der tschechischen Sprache ungefähr bei 0,0588 liegt. Eine andere Quelle gibt einen sehr ähnlichen Wert an, nämlich 0,06027. Die gleiche Quelle gibt auch Indizes für andere Sprachen an:

Wie man die Vigenère-Chiffre mit Hilfe des Friedman-Tests knackt

Wir verwenden den Koinzidenzindex, um zu prüfen, ob eine bestimmte Länge die Länge des ursprünglichen Chiffrierschlüssels der Vigenère-Chiffre ist. Genaues Verfahren:

1. Wir schätzen, dass der Schlüssel zwischen 2 und 15 liegen könnte (warum 15? Das spielt keine Rolle.) Bezeichnen wir : K_o = {2,…,15}.

2. Mit Hilfe der Cassis-Methode finden wir eine weitere Menge wahrscheinlicher Schlüssel und bezeichnen sie mit K_k.

3. Wir vereinen die beiden Mengen K = K_o ∪ K_k. Damit haben wir alle wahrscheinlichen Längen der Vigenère-Chiffre. Mit anderen Worten: Wir probieren alle Längen zwischen 2 und 15 plus die Längen, die der Kasiski-Test liefert.

4. Für jede Schlüssellänge, d.h. für jede k∈ K: teilen wir den Chiffriertext in k Blöcke auf, wobei der erste Block immer den ersten Buchstaben des Chiffriertextes enthält, (1 + k)-diesen Buchstaben, (1 + 2k)-diesen Buchstaben, usw. Der zweite Block enthält immer den 2. Buchstaben des Chiffretextes, (2 + k)-dieser Buchstabe, (2 + 2k)-jener Buchstabe, usw. Wir markieren die Blöcke mit B_i.

5. Für jeden Block B_i berechnen wir den Kookkurrenzindex IK_i.

6. Wir berechnen den durchschnittlichen Cooccurrence-Index aller Blöcke:

   $$\mbox{IK} = \frac{\sum_{i=1}^k \mbox{IK}_i}{k}$$

7. Wir finden die Länge des Schlüssels, der den niedrigsten Koinzidenzindex hat. Dies ist wahrscheinlich die Länge des ursprünglichen Schlüssels.

8. Wir brechen die Vigenère-Chiffre mit dem klassischen Algorithmus zum Brechen der Vigenère-Chiffre mit Kenntnis der Schlüssellänge.

Online-Tool zum Brechen der Vigenère-Chiffre

Das folgende Tool simuliert das obige Verfahren.

Chiffretext:

wtzpokioidtgxulwnzswmsgpoflgvlbusducjlsoscvgjluacwmpdcwlymineuqjocucnfzoscvgjluacwmplpzwzlvxsnswkgakwluuskmloyirygzerfuccevcwtzpokioidtgxyipsemfiwmlsezqcvclkccfenpgwymrbtbqwpvrykwteuqlkvagbzhvovirynmnoxxqfckjexqtxphcwjanoysqevioxlxcxpdmyfscwyirkymxkcqmkxakrxuqvpruovzccymtykbguwbcudcrcyqpkdxqblsoscvgjluacwmpmpscwlhuouitjlptoumpkdxtkgvqeemrvzbwkoixkxbcwdgtfecergqnsdmkzpalsyladlsxocvgcewlsnqwufkjiyamowqpujaryghfonpgwzlglcinnzxgvtame