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.: 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 Id.
Für B ergibt sich eine zufällige Sortierung und die Anwendung des Koinzidenzindex für zufällige Texte Iz (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) * Id + (n * (n - n/k) / 2) * Iz

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

Ic = (((n/k * (n/k-1)) * k / 2) * Id + (n * (n - n/k) / 2) * Iz) / ( n*(n-1) / 2).

Der Koinzidenzindex Ic 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 = (Id - Iz) * n / ( Ic * (n - 1) - Iz * n + Id )

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