Friedman Test

Kategorisierung:

Klassisch / Substitution / polyalphabetisch

Herkunft / Verwendung:

Grundlage des nach William Friedman benannten und 1925 von ihm veröffentlichten Testes ist der von ihm ersonnene Koinzidenzindex, der angibt, wie hoch die Wahrscheinlichkeit ist, dass zwei zufällig aus einem Text gegriffene Buchstaben übereinstimmen.

Der Test wird zur Schlüssellängebestimmung von Chiffraten aus polyalphabetischen Substitutions Chiffren benutzt. Chiffre also, die den 1. Klartextbuchstaben mit dem 1. Schlüsselbuchstaben, den 2. Klartextbuchstaben mit dem 2. Schlüsselbuchstaben usw. - und bei beispielweise eine Schlüssellänge von 5 - den 6. Klartextbuchstaben wieder mit dem 1. Schlüsselbuchstaben chiffriert, weil ein kurzer Schlüssel wiederholt wird. Wäre der Schlüssel genausolang wie der Klartext, würde es sich um eine sichere Chiffre handeln (siehe One-Time-Pad).

Beschreibung des Verfahrens

Mit ein paar Überlegungen zur Wahrscheinlichkeitsrechnung kann man den Aufwand, der mit dem Kappa-Test betrieben wird, zusammenfassen und verringern.

Es sei ein Vigenere-Chiffrat Chiff mit der Länge n und der einer Anzahl Blöcke k gegeben:


Chiff=jukvmxtxqwjebsevsxhrwaedmxtbdjorlblxexkeqmnrwdexhr
      krfdvtugfirigzycgxgixugclylszypebmiwsvgpstmdrroedr

n=100
k=5 (unbekannt)

jukvm xtxqw jebse vsxhr waedm xtbdj orlbl xexke qmnrw dexhr 
krfdv tugfi rigzy cgxgi xugcl ylszy pebmi wsvgp stmdr roedr

jxjvwxoxqdktrcxypwsr \                  <- chiff. m. 1. Bst. d. Schlüssels
utesatremeruigulesto  \                 <-           2. Bst.
kxbxeblxnxfggxgsbvme   > 5 Blöcke k     <-           3. Bst.
vqshddbkrhdfzgczmgdd  /                 <-           4. Bst.
mwermjlewrviyilyiprr /                  <-           5. Bst.
|________ _________|
         v
 je 20 (n/k) Zeichen

Nun fragt man sich:

A. Wie hoch ist die Wahrscheinlichkeit, dass zwei gleiche Buchstaben im selben Block auftauchen?
B. Wie hoch ist die Wahrscheinlichkeit, dass zwei gleiche Buchstaben in verschiedenen Blöcken auftauchen?

A.: Da jeder Block n/k Buchstaben enthält, ist die Anzahl der Buchstabenpaare in einem Block: (n/k * (n/k-1)) * k / 2
B.: Die Anzahl gleicher Buchstabenpaare aus verschiedenen Blöcken ist n * (n - n/k) / 2

Für A ergibt sich, weil wir wissen, dass Buchstaben im selben Block die Ursprungssortierung haben, die Anwendung des Koinzidenzindex der deutschen (oder einer anderen) Spache I_d.
Für B ergibt sich eine zufällige Sortierung und die Anwendung des Koinzidenzindex für zufällige Texte I_z (Kehrwert der Anzahl unterschiedlicher Buchstaben, Z. B. 1/26).

Für die Gesamtanzahl gleicher Paare aus A und B gilt dann:

((n/k * (n/k-1)) * k / 2) * I_d + (n * (n - n/k) / 2) * I_z

Der Koinzidenzindex dafür, also die Frage wie wahrscheinlich zwei zufällig herausgegriffene zeichen übereinstimmen, wäre demnach:

I_c = (((n/k * (n/k-1)) * k / 2) * I_d + (n * (n - n/k) / 2) * I_z) / ( n*(n-1) / 2).

Der Koinzidenzindex I_c des Chiffrats und die Länge des vorliegenden Textes sind aber bekannt bzw. lassen sich berechnen. Einzige Unbekannte ist die Blockgröße k, die der Schlüssellänge entspricht.

Durch Umstellung der Gleichung nach der Blockgröße k erhält man eine Formel, mit der man die Schlüsselänge annähernd berechnen kann:

k = (I_d - I_z) * n / ( I_c * (n - 1) - I_z * n + I_d )

Code / Chiffre online dekodieren / entschlüsseln bzw. kodieren / verschlüsseln (DeCoder / Encoder / Solver-Tool)

Vorher etwas mit dem Vigenere Chiffre verschlüsseln.

Quellen, Literaturverweise und weiterführende Links

Beutelspacher, Neumann und Schwarzpaul: Kryptografie in Theorie und Praxis, Vieweg Verlag 2005, S. 17
Ertel, Wolfgang: Angewandte Kryptographie, Hanser Verlag 2012, S. 43
Beutelspacher, Albrecht: Kryptologie - Eine Einführung..., Springer Spektrum Verlag 2015, S. 40