Friedman-Test
Der Friedman-Test bietet eine weitere Möglichkeit, die Schlüssellänge in einer Vigenère-Chiffre zu bestimmen. Dazu dient der durch Friedman definierte Koinzidenzindex I. Er wird zur Bewertung der Häufigkeitsverteilung in Schlüsseltexten verwendet. Der Koinzidenzindex I gibt die Wahrscheinlichkeit an, dass zwei unabhängig voneinander gewählte Zeichen übereinstimmen. Er nimmt bei polyalphabetischer Substitution in Abhängigkeit von der Schlüssellänge ab und erreicht bei einer zufälligen Anordnung von Buchstaben einen Wert von ca. 0,038. Für Texte die in europäischen Sprachen verfasst sind erreicht er einen Wert von ungefähr 0,07. Dieser Umstand wird zur Ermittlung der Schlüssellänge benutzt (Quelle: Kryptographie und IT-Sicherheit: Grundlagen und Anwendungen, 2011; Stephan Spitz, Michael Pramateftakis, Joachim Swoboda; Seite 10ff).
Es seien
A ein Alphabet mit A={a0, ....., an−1}
pi die Wahrscheinlichkeit für das Auftreten des Zeichens ai
Der Koinzidenzindex erreicht seinen minimalen Wert, wenn alle Zeichen gleichwahrscheinlich sind. D.h. pi=1/n und daraus folgt Ir=1/n . Für das lateinische Alphabet (nur Großbuchstaben) gilt: Ir=1/26= 0,038 . Für eine Nachricht in deutscher Sprache wird Id= 0,0762 und für eine Nachricht in englischer Sprache wird Ie= 0,065. Diesen Wert haben auch Schlüsseltexte, die durch monoalphabetische Substitution entstanden sind, da Buchstaben nur vertauscht werden.
Die Idee des Tests ist nun die folgende: Man berechnet zunächst den Koinzidenzindex. Wenn dieser (bei deutschen Texten) ungefähr 0,0762 beträgt, handelt es sich mitgroßer Wahrscheinlichkeit um eine monoalphabetische Verschlüsselung. Wenn der Index deutlich kleiner ist, dann ist der Text polyalphabetisch chiffriert. Der Wert wird kleiner,da sich die Buchstabenverteilung bei einer polyalphabetischen Verschlüsselung immer mehr einem zufälligen Alphabet (mit Index 0,03846) annähert. Auch bei einem Wert von zum Beispiel 0,042 könnte man von einer polyalphabetische Verschlüsselung ausgehen, da die Verteilung der Buchstaben schon „zufälliger“ ist als in allgemeinen deutschen Texten. Da der Wert nah an Ir= 1/26 = 0,038 ist, handelt es sich höchst wahrscheinlich um eine polyalphabetische Verschlüsselung.
Der Ausgangspunkt der Betrachtung ist, dass man die Schlüssellänge k als gegeben annimmt und den verschlüsselten Text der Länge n in k Zeilen aufteilt, so dass in jeder Zeile alle Geheimtextbuchstaben mit dem selben Buchstaben des Schlüsselwortes verschlüsselt werden. Diese Zeilen sind somit monoalphabetisch verschlüsselt. Im Beispiel links wäre die Schlüssellänge k=5. Der Text hat die Länge n=100. Jeder monoalphabetische Block hat die Länge n/k=20.
Man kann die Anzahl aller Zeichenpaare in einem monoalphabetischen Block berechnen. Da die Reihenfoge der Zeichen keine Rolle spielt, wird die Anzahl der Paare durch zwei geteilt (Quelle: Kryptografie in Theorie und Praxis
Mathematische Grundlagen für Internetsicherheit, Mobilfunk und elektronisches Geld: Beutelspacher, Albrecht, Neumann, Heike B., Schwarzpaul, Thomas; 2010, S.16 ff):
Für den 1. monoalphabetischen Block wären das 950 mögliche Zeichenpaare die man bilden kann. Die Anzahl
aller Zeichenpaare in den verbleibenden monoalphabetischen Blöcken berechnet man wie folgt:
Auch hier spielt die Reihenfolge keine Rolle, so dass die Anzahl der Paare durch zwei geteilt wird. Für die verbleibenden 4 monoalphabetischen Blöcke aus unserem Beispiel bedeutet dies, dass es 4.000 mögliche Zeichenpaare gibt.
Nun können wir die Zahl der Paare aus gleichen Buchstaben im gesamten Text angeben, indem wir die Anzahl aller Zeichenpaare aus dem 1. monoalphabetischen Block mit der Wahrscheinlichkeit für gleiche Zeichen für deutsche Texte - also Id - multiplizieren und dieses Produkt addieren mit der Anzahl aller Paare für die verbleibenden 4 monoalphabetischen Blöcke multipliziert mit der Wahrscheinlichkeit für gleiche Zeichen in polyalphabetischen Texten Ir:
Dividiert man nun durch die Zahl der Paare insgesamt n*(n-1)/2 erhält man die Wahrscheinlichkeit für Paare aus gleichen Buchstaben für den gesamten Text, was dem Koinzidenzindex I für den Text entspricht. Dieser lässt sich leicht bestimmen und daher kann man die Funktionen nach k umstellen:
Für I = 0,044 ergibt sich: ((0,076-0,038)*n)/(99)*0,0446 - 0,038*100 + 0,076 = 6,01 = k. Die berechnete Schlüssellänge k liegt damit nahe am tatsächlichen Schlüssel von 5 aus dem Beispiel.