KryptologieKryptoanalyse einer Spaltentransposition |
|
DDSSR GNIEI GNSAE CSEII EASLM ITAGR NUUIU AUUHI PROEQ ILLOI ATIAP IALSU VFEAN ETELE IRNSB TESEO OREEE IHRDE CHANZ EJGKC LFTCE RTMHH DMNDR ODMOE DTAIN DNARI LNGYL EAUCT RRENB TEESI NHLRW EHSUT TZUOU EIAEM VFEKG HGTEN WICFN GTHNE EGEUH DUVIU DETDE IOETL ENEEE ZTCEF SNNBT AULRH SNNKC LCOAK ENNS
Die Häufung des Buchstabens E fällt auf. Der Geheimtext könnte durch Transposition entstanden sein.
Die Häufigkeiten der einzelnen Buchstaben sind:
E 39 R 14 H 11 M 5 W 2 X 0 N 22 U 14 C 9 K 4 J 1 I 20 S 13 G 9 B 3 P 1 T 17 L 12 O 9 V 3 Q 1 A 15 D 11 F 5 Z 3 Y 1 gesamt: 244Das stimmt sehr gut mit der Vorstellung überein, dass es sich um eine Transposition eines deutschen Textes handelt. Der Koinzidenzindex von 0.0661 ist für unsere Hypothese zwar etwas klein geraten, bringt uns aufgrund der recht kurzen Textlänge aber nicht von ihr ab. Die Autokoinzidenzindizes schwanken sehr stark, lassen aber keine Regelmäßigkeit erkennen; ebenso ergibt die Parallelstellensuche nach Kasiski Wiederholungen von Dreiergruppen in den Abständen 110, 70, 130, 135, 114, 79, 23, 10, die keine Periode erkennen lassen. Daher engen wir unsere Hypothese auf eine Spaltentransposition ein. Da es keine schnelle Methode gibt, um die Spaltenbreite zu erkennen, müssen wir die Breiten 2, 3, 4, ... durchprobieren. Stellen wir uns vor, wir sind dabei ohne vorherigen Erfolg bis zur Breite 8 vorgedrungen.
Da 244:8 = 30 Rest 4, hätten von den 8 Kolonnen je 4 die Länge 30 und 31, die aber wegen der Permutation der Spalten zunächst nicht zu unterscheiden sind. Daher werden im folgenden die Kolonnen so weit verlängert, dass ihr echter Inhalt auf jeden Fall erfasst wird; die echte Kolonne könnte gegenüber der (echten) Nachbarkolonne um bis zu drei Stellen verschoben sein. Da sich Zeilen im Text-Editor leichter handhaben lassen als Spalten, werden die Kolonnen im folgenden als Zeilen geschrieben; der mögliche echte Beginn der Kolonne liegt jeweils irgendwo in Spalte 1 bis 5 dieser Tabelle.
12345 1 DDSSRGNIEIGNSAECSEIIEASLMITAGRN 2 NUUIUAUUHIPROEQILLOIATIAPIALSUVF 3 VFEANETELEIRNSBTESEOOREEEIHRDECHA 4 CHANZEJGKCLFTCERTMHHDMNDRODMOEDTAI 5 DTAINDNARILNGYLEAUCTRRENBTEESINHLR 6 HLRWEHSUTTZUOUEIAEMVFEKGHGTENWICF 7 CFNGTHNEEGEUHDUVIUDETDEIOETLENEE 8 EEZTCEFSNNBTAULRHSNNKCLCOAKENNS
Eine gute Methode, um weiterzukommen, wäre jetzt, die Kolonnen paarweise aneinanderzulegen, jeweils mit allen möglichen Verschiebungen, und die auftretenden Bigramme mit ihrer erwarteten Häufigkeit gewichtet aufzuaddieren; Paare mit hohem Wert ergeben dann eine wahrscheinliche Nachbarschaft. Eine gute, für Handarbeit geeignete Methode ist aber auch, mögliche »CH«-Kombinationen herzustellen, falls die Klartextsprache Deutsch ist.
Kolonne 1 enthält ein »C«. Die möglichen Nachbarbuchstaben sind:
1 ... C ... 2 ... IL ... 3 ... TES ... 4 ... RTMH ... 5 ... EAUCT ... 6 ... IAEM ... 7 ... VIU ... 8 ... RH ...Darunter sind nur zwei »H« (und kein »K«); das ergibt die beiden möglichen Nachbarkolonnen:
1 DDSSRGNIEIGNSAECSEIIEASLMITAGRN 4 CHANZEJGKCLFTCERTMHHDMNDRODMOEDTAI 1 DDSSRGNIEIGNSAECSEIIEASLMITAGRN 8 EEZTCEFSNNBTAULRHSNNKCLCOAKENNSDie Beurteilung der Bigramm-Häufigkeiten, sei es visuell oder durch Auszählung, spricht für die zweite Möglichkeit, mit der wir dann auch (zunächst) weiterarbeiten. Da die Kolonne 8 drei »C« enthält, ist sie für die Fortsetzung besonders geeignet. Hier sind die möglichen Nachbarbuchstaben für das erste »C«:
2 ... UA ... 3 ... NET ... 4 ... ZEJG ... 5 ... NDNA ... 6 ... EHS ... 7 ... TH ... 8 ... C ...Als Nachbarn bieten sich hier nur die Kolonnen 6 und 7 an:
8 EEZTCEFSNNBTAULRHSNNKCLCOAKENNS 6 HLRWEHSUTTZUOUEIAEMVFEKGHGTENWICF 8 EEZTCEFSNNBTAULRHSNNKCLCOAKENNS 7 CFNGTHNEEGEUHDUVIUDETDEIOETLENEEDie erste Variante ergibt für die beiden anderen »C« in Kolonne 8 die Bigramme »CK« und »CH« - gut! -, die zweite Variante die Bigramme »CE« und »CO« - weniger gut!. Wir arbeiten also mit der ersten weiter und haben bisher die Anordnung
1 DDSSRGNIEIGNSAECSEIIEASLMITAGRN 8 EEZTCEFSNNBTAULRHSNNKCLCOAKENNS 6 HLRWEHSUTTZUOUEIAEMVFEKGHGTENWICFDamit ist auch schon klar, dass Kolonne 1 aus 31 Zeichen besteht. Das »E« am Anfang von Kolonne 8 gehört also in Wirklichkeit an das Ende von Kolonne 7, und Kolonne 8 besteht aus 30 Zeichen. Diese beiden sind also in Wahrheit die Kolonnen 4 und 5.
Für die wahre Anordnung der Kolonnen haben wir jetzt bereits das Teilschema
1 2 3 4 5 6 7 8 * * * 1 8 6 * *erkannt. Außerdem ist dann klar, dass Kolonne 6 aus 30 Zeichen besteht. Die beiden entdeckten »SCH« geben uns sehr viel Zuversicht, dass wir auf dem richtigen Weg sind; auch die übrigen Trigramme sehen gut bis brauchbar aus. Das obige Schema, das die möglichen Verschiebungen der Kolonnen berücksichtigt, schrumpft zu
1 DDSSRGNIEIGNSAECSEIIEASLMITAGRN (31) 2 UUIUAUUHIPROEQILLOIATIAPIALSUVF 3 FEANETELEIRNSBTESEOOREEEIHRDECHA 4 HANZEJGKCLFTCERTMHHDMNDRODMOEDTA 5 AINDNARILNGYLEAUCTRRENBTEESINHL 6 RWEHSUTTZUOUEIAEMVFEKGHGTENWIC (30) 7 FNGTHNEEGEUHDUVIUDETDEIOETLENEE (31) 8 EZTCEFSNNBTAULRHSNNKCLCOAKENNS (30)Insbesondere muss Kolonne 7 genau 31 Zeichen haben.
Suchen wir nun weiter nach »CH«: Kolonne 6 hat ein »C«, und zwar am Ende. Die möglichen Nachbarn könnten nach dem Schema:
2 ... VF 3 ... CHA 4 ... DTA 5 ... HL 6 ... C 7 ... EEnoch die Kolonnen 3 und 5 sein mit der Anordnung
1 DDSSRGNIEIGNSAECSEIIEASLMITAGRN 8 EZTCEFSNNBTAULRHSNNKCLCOAKENNS 6 RWEHSUTTZUOUEIAEMVFEKGHGTENWIC 3 FEANETELEIRNSBTESEOOREEEIHRDECHA 1 DDSSRGNIEIGNSAECSEIIEASLMITAGRN 8 EZTCEFSNNBTAULRHSNNKCLCOAKENNS 6 RWEHSUTTZUOUEIAEMVFEKGHGTENWIC 5 AINDNARILNGYLEAUCTRRENBTEESINHLDie erste der beiden sieht wesentlich besser aus, insbesondere fallen die beiden Fragmentpaare »INFO« ... »IKER« und »MATH« ... »IKER« auf - sollte da von Informatikern und Mathematikern die Rede sein?
Nehmen wir also das Kolonnenschema
1 2 3 4 5 6 7 8 * * * 1 8 6 3 *als weitere Arbeitsgrundlage an. Da wir nun auch wissen, dass Kolonne 3 nur 30 Zeichen hat, muss Kolonne 2 notwendig 31 Zeichen haben, und das Schema sieht nun so aus:
1 DDSSRGNIEIGNSAECSEIIEASLMITAGRN (31) 2 UUIUAUUHIPROEQILLOIATIAPIALSUVF (31) 3 EANETELEIRNSBTESEOOREEEIHRDECH (30) 4 ANZEJGKCLFTCERTMHHDMNDRODMOEDTA 5 AINDNARILNGYLEAUCTRRENBTEESINHL 6 RWEHSUTTZUOUEIAEMVFEKGHGTENWIC (30) 7 FNGTHNEEGEUHDUVIUDETDEIOETLENEE (31) 8 EZTCEFSNNBTAULRHSNNKCLCOAKENNS (30)Die Nachbarin von Kolonne 3, also die in Wirklichkeit letzte Kolonne, muss aus 30 Zeichen bestehen. Dafür kommen nur noch 4 und 5 in Frage. Zu dem »C« als vorletztem Zeichen von Kolonne 3 passt nur das »H« in Kolonne 5, und wir erhalten als bisherige Teillösung:
1 DDSSRGNIEIGNSAECSEIIEASLMITAGRN 8 EZTCEFSNNBTAULRHSNNKCLCOAKENNS 6 RWEHSUTTZUOUEIAEMVFEKGHGTENWIC 3 EANETELEIRNSBTESEOOREEEIHRDECH 5 INDNARILNGYLEAUCTRRENBTEESINHLund als Kolonnen
1 DDSSRGNIEIGNSAECSEIIEASLMITAGRN (31) 2 UUIUAUUHIPROEQILLOIATIAPIALSUVF (31) 3 EANETELEIRNSBTESEOOREEEIHRDECH (30) 4 ANZEJGKCLFTCERTMHHDMNDRODMOEDTA (31) 5 INDNARILNGYLEAUCTRRENBTEESINHL (30) 6 RWEHSUTTZUOUEIAEMVFEKGHGTENWIC (30) 7 FNGTHNEEGEUHDUVIUDETDEIOETLENEE (31) 8 EZTCEFSNNBTAULRHSNNKCLCOAKENNS (30)
Das »C« in Kolonne 5 passt zu einem »H« in Kolonne 4 (um eine Stelle verschoben wegen des Zeilenwechsels), das erste »C« in Kolonne 4 zu einem »H« in Kolonne 2. Damit haben wir die Kolonnen-Anordnung
1 2 3 4 5 6 7 8 4 2 7 1 8 6 3 5die Lösung
4 ANZEJGKCLFTCERTMHHDMNDRODMOEDTA 2 UUIUAUUHIPROEQILLOIATIAPIALSUVF 7 FNGTHNEEGEUHDUVIUDETDEIOETLENEE 1 DDSSRGNIEIGNSAECSEIIEASLMITAGRN 8 EZTCEFSNNBTAULRHSNNKCLCOAKENNS 6 RWEHSUTTZUOUEIAEMVFEKGHGTENWIC 3 EANETELEIRNSBTESEOOREEEIHRDECH 5 INDNARILNGYLEAUCTRRENBTEESINHLund den Klartext
»Auf der einundzwanzigsten deutschen Jahrestagung fuer kuenstliche Intelligenz in Freiburg trug Tony Cohn aus Leeds ueber qualitative raeumliche Schlussmethoden vor. Die Informatiker entdecken die algebraische Topologie. Die Mathematiker sollten diese Anwendung nicht verschlafen.«