Kryptologie Transpositions-Chiffren - Ansätze zur Kryptoanalyse

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

Anagrammieren

... ist die Standard-Methode der Kryptoanalyse von Transpositionen. Sie bedeutet, die richtige Reihenfolge der Buchstaben wieder herzustellen. Dazu ist in jedem Fall Kontextinformation nötig, da Anagramme in aller Regel nicht eindeutig zu lösen sind, wie jeder »Besuchskartenrätsel«-Löser weiß. Es gibt sogar WWW-Adressen, wo man sich zu einer gegebenen Zeichenkette Anagramme erzeugen lassen kann.

Die Zeichenkette »Klaus Pommerening« ergab 75707 (!) Anagramme, darunter so geistreiche wie

  GERMANEN IM PULK SO     MAN KEGLE SPION RUM 
  ANMERKEN: SO LUMPIG!    ALGENKNOSPE IM RUM  
  SIGNALE KOMMEN PUR      KLINGE AUS POMMERN  
  MAGNESIUM-KNORPEL       SAUGNOME KLIMPERN   
  SPIONAGEN UM KREML      KLAGE NUR, MEIN MOPS
  KLAMMERUNG IN POSE      KOPIERSAMMLUNGEN    

und so sinnlose, aber als korrektes Deutsch erscheinende wie

  ANGEL MERK UNI MOPS     GASEN EMPOR UM LINK
  PLAGE MEIN KORN MUS     GRAUPE MOSLEM KINN 
  OMEGA KLIMPERN UNS      AKNE GLOMM SEIN PUR
  SANGEN KEIM POL RUM     SAMMLER PEKING UNO 

Ansatzpunkte

... zum erfolgreichen Anagrammieren sind:

• ein wahrscheinliches Wort,
• charakteristische Bi- und Trigramme (QU, CH, SCH, im englischen auch TH, THE),
• Bigrammhäufigkeiten - werden beim Probieren versuchsweise Geheimtext-Kolonnen aneinandergelegt, so verrät sich eine korrekte Position durch die hohe Gesamtwahrscheinlichkeit der vorkommenden Bigramme.

Je »breiter« die Transposition, desto schwieriger wird das Anagrammieren.

Allgemeine, nichtperiodische, Transpositionschiffren sind daher ziemlich schwer zu brechen. Das ändert sich sofort, wenn zwei Geheimtexte exakt gleicher Länge vorliegen, die mit dem gleichen Schlüssel erzeugt wurden. Man schreibt sie untereinander und versucht es mit multiplem Anagrammieren unter Beachtung der Bigramm-Wahrscheinlichkeiten.

Siehe dazu auch die Analyse des Kryptogramms aus Mathias Sandorf.

Ein ausführliches Tutorial zur Kryptoanalyse von Doppel-Transpositions-Chiffren, einer Standard-Methode noch im ersten Weltkrieg, enthält das Buch

• Wayne G. Barker: Cryptanalysis of the Double Transposition Cipher. Aegean Park Press, Laguna Hills 1995.

Beispiel für die Anwendung der Bigrammhäufigkeiten

Bei der soeben durchgeführten Analyse einer Spaltentransposition haben wir die ersten zwei Entscheidungs- und damit potenziellen Verzweigungspunkte nach dem Aussehen der entstehenden Bigramme beurteilt. Wendet man systematisch die Bigrammhäufigkeiten nach der Tabelle an, indem man die dort aufgeführten relativen Häufigkeiten einfach zu einem Score zusammenaddiert, so sieht das wie folgt aus.

Am ersten Entscheidungspunkt war die Alternative:

1     DDSSRGNIEIGNSAECSEIIEASLMITAGRN
4     NZEJGKCLFTCERTMHHDMNDRODMOEDTAI

1     DDSSRGNIEIGNSAECSEIIEASLMITAGR 
8     EZTCEFSNNBTAULRHSNNKCLCOAKENNS

   DN  1.2  NC  0.5  SR  1.2  IM  3.5  MM  8.8  NI  6.6
   DZ  0.6  IL  3.2  AT  7.1  IN 21.8  IO  2.6
   SE 14.5  EF  1.5  EM  3.2  ED  2.9  TE 30.7
   SJ  0.3  IT 10.1  CH 91.0  AR  7.9  AD  1.7
   RG  3.6  GC  0.0  SH  1.3  SO  4.1  GT  5.8
   GK  1.0  NE 12.4  ED  2.9  LD  4.0  RA 10.6

   DE 46.9  NS  7.5  SU  2.2  IN 21.8  MA 15.4
   DZ  0.6  IN 21.8  AL  9.2  IK  1.6  IK  1.6
   ST 17.0  EN 22.9  ER 23.4  EC  1.4  TE 30.7
   SC 13.0  IB  0.9  CH 91.0  AL  9.2  AN 15.8
   RE 14.9  GT  5.8  SS 11.1  SC 13.0  GN  1.6
   GF  0.6  NA  6.9  EN 22.9  LO  4.0  RS  7.2

Übungsaufgabe: Berechne analog die Scores für den zweiten Entscheidungspunkt:

8  EEZTCEFSNNBTAULRHSNNKCLCOAKENNS
6  LRWEHSUTTZUOUEIAEMVFEKGHGTENWIC 

8  EEZTCEFSNNBTAULRHSNNKCLCOAKENNS
7  FNGTHNEEGEUHDUVIUDETDEIOETLENEE

Diese Methode, einen Score zu bilden, ist nur schwach theoretisch fundiert. Man kann sich auch andere ausdenken, auch wesentlich gröbere [Übungsaufgabe].

Lineare Analyse

... nutzt die Beobachtung, dass die Transposition eine lineare Abbildung über dem endlichen Ring Z/nZ ist - sofern das Alphabet damit identifiziert wird - und wird im folgenden bei den linearen Chiffren behandelt.

Simulated Annealing

... ist eine Optimierungsmethode, die offenbar auch zum Lösen von Transpositions-Chiffren erfolgreich eingesetzt werden kann. Hier einige externe Links:

• Simulated Annealing.
• Crank (Cryptanalysis Toolkit).