Friedman-Test (Kryptologie)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Kryptologie ist der Friedman-Test ein Verfahren zur Analyse eines Textes, der durch Polyalphabetische Substitution (z. B. Algorithmus von Vigenère) verschlüsselt wurde. Mit ihm kann die Länge des Schlüssels bestimmt werden. Er wurde von William Frederick Friedman entwickelt.

Anwendung[Bearbeiten]

Es sei ein Vigenère-Schlüsseltext der Länge m mit der Anzahl der Blöcke n gegeben. Wir berechnen nun den Koinzidenzindex \kappa eines solchen Textes. Es gibt zwei Typen von Buchstabenpaaren:

  • A beide stehen an gleicher Blockposition,
  • B sie stehen an verschiedenen Blockpositionen.

Die Wahrscheinlichkeit, dass zwei Buchstaben vom Typ A gleich sind, ist µ := 0,0762 (für längere deutsche Texte). Weiterhin ist die Wahrscheinlichkeit, dass zwei Buchstaben vom Typ B gleich sind, gleich \phi := 0,0385.

In jeder Blockposition gibt es m/n Buchstaben und damit {m/n \choose 2} Paare. Also ist die Anzahl der Paare vom Typ A gleich

n\cdot\frac{m/n\cdot(m/n-1)}{2}=\frac{m(m-n)}{2n}.

Die übrigen

{m \choose 2}-\frac{m(m-n)}{2n}=\frac{m^2(n-1)}{2n}

Paare sind vom Typ B. Damit erhält man für den Koinzidenzindex

\kappa=\frac{\frac{m(m-n)}{2n}\cdot\mu+\frac{m^2(n-1)}{2n}\cdot\phi}{m(m-1)/2}=\frac{(m-n)\cdot\mu+m(n-1)\cdot\phi}{n(m-1)}.

Löst man nun nach n auf so ergibt sich

n=\frac{m(\mu-\phi)}{\kappa(m-1)+\mu-m\cdot\phi}.

Die vermutete Schlüssellänge des Codewortes ist dann eine ganze Zahl, die in der Nähe dieser Schätzung liegt.

Andere Verfahren[Bearbeiten]

Der Kasiski-Test dient zum Herausfinden der Schlüssellänge anhand sich wiederholender Zeichengruppen.

Literatur[Bearbeiten]

  • Albrecht Beutelspacher: Kryptologie. Eine Einführung in die Wissenschaft vom Verschlüsseln, Verbergen und Verheimlichen. Ohne alle Geheimniskrämerei, aber nicht ohne hinterlistigen Schalk, dargestellt zum Nutzen und Ergötzen des allgemeinen Publikums. 2. erheblich erweiterte und hoffentlich verbesserte Auflage. Vieweg, Braunschweig 1991, ISBN 3-528-18990-8.