[JoGu]

Kryptologie

Lauftext-Chiffrierung - Kryptoanalyse nach FRIEDMAN
a7Hzq .#5r<
kÜ\as TâÆK$
ûj(Ö2 ñw%h:
Úk{4R f~`z8
¤˜Æ+Ô „&¢Dø

W. F. Friedman: Methods for the Solution of Running-Key Ciphers.
Riverbank Publication No. 16 (1918).
In: The Riverbank Publications Vol 1, Aegean Park Press 1979.

Gegeben ist ein Kryptogramm, das mit einer Lauftext-Chiffre erstellt wurde. Der Ansatz von FRIEDMAN ist die Beobachtung, dass ein signifikanter Teil der Geheimtextbuchstaben durch Kombination zweier häufiger Klartextbuchstaben entsteht.

Gehen wir etwa von folgenden Häufigkeiten für die neun häufigsten Buchstaben der deutschen Sprache aus:

ENI RSA TDU
18.0 % 10.6 % 8.1 % 7.2 % 6.9 % 6.0 % 5.7 % 5.4 % 4.6 %
Diese machen also zusammen etwa 72.5 % eines deutschen Textes aus.

Nehmen wir an, das der Schlüssel hinreichend unabhängig vom Klartext ist, so können wir erwarten, dass etwa 53 % der Geheimtextbuchstaben aus einer Kombination zweier dieser häufigen Klartextbuchstaben entstanden sind. Das alleine ist noch nicht sehr beeindruckend. Im bisherigen Beispiel 

                                  |   | | |     |   |
  Klartext:   i c h k o m m e m o r g e n u m z e h n
  Schlüssel:  V O M E I S E B E F R E I T S I N D S T
              ---------------------------------------
  Geheimtext: D Q T O W E Q F Q T I K M G M U M H Z G
sind es sogar nur die 6 markierten von insgesamt 20; das Verfahren wird hier nicht gut funktionieren.

Betrachten wir noch ein anderes Beispiel: 

              | | | | |       | |         | |   |       |   | |  
  Klartext:   d e u t s c h l a n d b e s i e g t p a r a g u a y
  Schlüssel:  E I N E N A T U E R L I C H E S P R A C H E H A T T
              ---------------------------------------------------
  Geheimtext: H M H X F C A F E E O J G Z M W V L P C Y E N U T R
Hier sind es 13 von insgesamt 26 Buchstaben. Hiermit wird jetzt das Vorgehen erklärt.

Beginnen wir mit den ersten vier Buchstaben und sehen uns alle Möglichkeiten an, wie diese entstanden sein können: 

  Klartext:   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
  Schlüssel:  H G F E D C B A Z Y X W V U T S R Q P O N M L K J I
                    | |                 |             |          
  Geheimtext: H H H H H H H H H H H H H H H H H H H H H H H H H H

  Klartext:   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
  Schlüssel:  M L K J I H G F E D C B A Z Y X W V U T S R Q P O N
                      |       |                   | | |          
  Geheimtext: M M M M M M M M M M M M M M M M M M M M M M M M M M

  Klartext:   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
  Schlüssel:  H G F E D C B A Z Y X W V U T S R Q P O N M L K J I
                    | |                 |             |          
  Geheimtext: H H H H H H H H H H H H H H H H H H H H H H H H H H

  Klartext:   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
  Schlüssel:  X W V U T S R Q P O N M L K J I H G F E D C B A Z Y
                    | |                             | |          
  Geheimtext: X X X X X X X X X X X X X X X X X X X X X X X X X X
Die hochwahrscheinlichen Paare sind wieder markiert; verdichten wir die Tabelle zu 
  DENU EISTU DENU DETU
  EDUN IEUTS EDUN UTED
  H    M     H    X
Es gibt insgesamt 4·5·4·4 = 320 mögliche Kombinationen dieser Paare, wobei einige schon auf den ersten Blick ausgeschieden werden können - z. B. der Beginn DS in Klartext und Schlüssel.

Beim Start mit dem Paar DE ist als Fortsetzung EI oder US denkbar. Im ersten Fall geht es auf genau einem Weg sinnvoll weiter: 

  DEUT
  EINE
Im zweiten Fall könnte DE eine Fortsetzung sein, zu der sich aber kein passendes viertes Paar findet. Möglich wäre als drittes Paar auch NU denkbar und dann als viertes ET oder TE; also behalten wir zwei weitere Möglichkeiten 
  DEUT  DUNE  DUNT
  EINE  ESUT  ESUE
die freilich beide nicht sehr überzeugend wirken.

Beim Start mit ED finden wir eine genau symmetrische Situation vor und erhalten daher die gleichen drei Möglichkeiten, nur mit vertauschtem Klartext und Schlüssel.

Beim Start mit NU kann es mit IE oder US weitergehen. Im ersten Fall ist ED die einzige plausible Fortsetzung und dann TE: 

  DEUT  DUNE  DUNT  NIET
  EINE  ESUT  ESUE  UEDE
Im zweiten Fall könnte es mit DE (und dann noch mit ET) oder NU (und dann nicht mehr gut) weitergehen; also haben wir noch eine weitere Möglichkeit 
  DEUT  DUNE  DUNT  NIET  NUDE
  EINE  ESUT  ESUE  UEDE  USET
sowie alle dazu symmetrischen; insgesamt also 10 halbwegs plausible Möglichkeiten - immer vorausgesetzt, die ersten vier Buchstaben von Klartext und Schlüssel waren sämtlich unter den neun häufigsten.

Von den fünf aufgezählten Möglichkeiten sieht die erste am plausibelsten aus; auch die vierte scheint recht gut, wenn wir bedenken, dass der Schlüsseltext ja mitten in einem Wort (z. B. »müde«) anfangen könnte. Beginnen wir auf jeden Fall mit der ersten Möglichkeit, die die Fortsetzung SCH nahelegt. Das passt: 

  DEUTSCH
  EINENAT
- Natürlich würde man, wenn man hiermit nicht weiterkommt, auch z. B. »deutlich« oder »deuten« ausprobieren. -

Als nächsten Buchstaben in der ersten Zeile wird man E oder L probieren und sich für L entscheiden (Fortsetzung unten U, sonst B). Also ist das Startwort DEUTSCHLAND mit ziemlicher Sicherheit entschlüsselt. Von da aus hangelt man sich, wenn auch immer noch mühselig, weiter.

Autor: Klaus Pommerening, 16. Juni 2002; letzte Änderung: 2. Januar 2005.