Substitutionschiffren: 26! Schlüssel, geknackt durch Buchstabenzählen

Ein Abschnitt aus einer Sherlock-Holmes-Geschichte wurde mit einem geheimen Schlüssel verschlüsselt. Bei der Cäsar-Verschiebung probierst du die 25 Schlüssel nacheinander durch und beobachtest den jeweiligen Chi-Quadrat-Balken. Bei der allgemeinen Substitution ordnest du den häufigsten Geheimtextbuchstaben die häufigsten Buchstaben des Englischen zu und korrigierst die Paare anschließend anhand der entstehenden Wörter.

Rechenbeispiel — Substitutionschiffren: 26! Schlüssel, geknackt durch Buchstabenzählen

Mögliche Schlüssel	25
Buchstaben in der Nachricht	120
Ergebnis des Angriffs: kleinstes χ²	23,3
Zweitkleinstes χ²	445,8
Ist es der Schlüssel?	Ja

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Substitutionschiffren: 26! Schlüssel, geknackt durch Buchstabenzählen

Eine Substitutionschiffre ersetzt jeden Buchstaben der Nachricht durch einen anderen, und zwar jedes Mal durch denselben. Der Schlüssel ist eine Permutation des Alphabets; folglich gibt es 26! ≈ 4,03 × 10²⁶ mögliche Schlüssel. Die Cäsar-Chiffre ist der Spezialfall, bei dem alle Buchstaben um dieselbe Anzahl an Stellen im Alphabet verschoben werden, was 25 Schlüssel übrig lässt. Eine Häufigkeitsanalyse greift beide Verfahren an, indem sie zählt, wie oft jeder Geheimtextbuchstabe vorkommt, und dies mit den typischen Häufigkeiten von Buchstaben in gewöhnlichen Texten vergleicht.

Was die einzelnen Symbole bedeuten

χ²: Chi-Quadrat: die Summe von (O − E)² / E über alle 26 Buchstaben. Je kleiner der Wert, desto eher gleicht die Entschlüsselung dem Englischen
O: wie oft ein Buchstabe in der geprüften Entschlüsselung vorkommt
E: wie oft er in einem gleich langen Text mit den Buchstabenanteilen aus The Dancing Men vorkommen müsste

Setzt voraus: Verschlüsselt werden ausschließlich die 26 Buchstaben. Leerzeichen und Satzzeichen bleiben unverändert erhalten und verraten so die Wortlängen – genau wie die tanzenden Männchen mit ihren Fahnen. „Englisch“ steht für die Buchstabenhäufigkeiten aus einer Holmes-Geschichte mit 39.859 Buchstaben. Die Nachrichten der Seite stammen aus einer anderen Geschichte, sodass kein Text mit sich selbst verglichen wird. Die Testläufe ziehen zufällige Abschnitte aus The Solitary Cyclist und reproduzierbare Schlüssel, sodass stets dieselben Zahlenwerte erscheinen.

Fünfundzwanzig Schlüssel lassen sich rasch durchprobieren; welcher davon passte, erkennt man ab etwa 30 Buchstaben 🖖

Eine Cäsar-Verschiebung kennt 25 Schlüssel – wenige genug, um sie von Hand durchzugehen. Die eigentliche Arbeit liegt darin zu erkennen, welche Entschlüsselung tatsächlich englischer Text ist. Diese Aufgabe übernimmt hier Pearsons Chi-Quadrat-Test: Er summiert Buchstabe für Buchstabe auf, wie weit die gezählten Häufigkeiten von der Verteilung abweichen, die The Dancing Men für einen Text dieser Länge erwarten lässt. Bei 20.000 zufälligen Abschnitten aus einer anderen Holmes-Geschichte liefert der kleinste Wert bei 12 Buchstaben in 85,0 % der Fälle den richtigen Schlüssel, bei 31 Buchstaben bereits zu 99,1 %. Klick auf Cäsar, 11 Buchstaben für einen Fehlgriff: Verschiebung 7 erzielt einen besseren Wert als der echte Schlüssel und ergibt dan reoep swo – Unsinn, den jeder Mensch sofort verwirft, für den die reine Statistik aber blind ist.

Zählen findet das e, sonst fast nichts 🖖

Bei einer Nachricht mit 600 Buchstaben setzt die Zuordnung nach Rang das e in 96,5 % von 400 Zufallsversuchen an die richtige Stelle. Die darauf folgenden Buchstaben liegen jedoch zu dicht beieinander, als dass ihre Reihenfolge in einem kurzen Text stabil bliebe: In The Dancing Men liegen a, o, i, n, h und s alle zwischen 6,3 % und 8,0 %, sodass schon wenige zufällige Treffer die Rangfolge vertauschen. Ordne jeden Buchstaben stur nach Rang zu, und du triffst im Schnitt 6,3 der vorhandenen 23,5 Buchstaben – ein Drittel des Textes. Holmes selbst bemerkt bei der Entschlüsselung der tanzenden Männchen genau das: „Die Reihenfolge der englischen Buchstaben nach dem E ist keineswegs scharf ausgeprägt; ein Übergewicht, das sich im Durchschnitt einer Druckseite zeigt, kann sich in einem einzigen kurzen Satz schon umkehren.“ Er wartete auf mehr Text und las Wörter.

Selbst eine ganze Erzählung als Geheimtext lässt fünf Buchstaben falsch 🖖

Mehr Geheimtext stabilisiert die Häufigkeiten. Allerdings nähern sie sich den Werten genau der vorliegenden Erzählung an – und zwei Texte desselben Autors stimmen nie exakt überein. Klick auf Subst., ganze Erzählung: Alle 32.725 Buchstaben aus The Solitary Cyclist, abgeglichen mit The Dancing Men, platzieren 21 Buchstaben richtig und fünf falsch (h, i, n, f und y). Damit stimmen 76,1 % des Textes. Der Cyclist verwendet das h (6,69 %) einen Hauch öfter als das i (6,67 %) und das n (6,34 %); in den Dancing Men liegen i und n dagegen vor dem h. Holmes selbst gibt die Reihenfolge mit T, A, O, I, N, S, H, R, D, L an – doch ausgerechnet in der Geschichte, in der er das ausspricht, kommt H vor S.

Aufgabe vollständig gelöst

Wo das Zählen aufhört und das Lesen beginnt 4 Schritte
Klick auf Subst., 600 Buchstaben. Wie lange bräuchte ein Computer, der eine Milliarde Schlüssel pro Sekunde testet, um alle durchzuprobieren? Knacke dann die Nachricht: Was verraten dir die reinen Häufigkeiten und was die häufigsten Wörter?

Öffne diese Aufgabe im Tool
1. Es gibt 26! = 403.291.461.126.605.635.584.000.000 Schlüssel, rund 4,03 × 10²⁶. Bei 10⁹ Schlüsseln pro Sekunde entspricht das 4,03 × 10¹⁷ Sekunden. Ein Jahr hat 3,16 × 10⁷ Sekunden; das ergibt 1,28 × 10¹⁰ Jahre: 12,8 Milliarden Jahre.
  
  $26! = 403291461126605635584000000 \approx 4.03 \times 1 0^{26}, \frac{4.03 \times 1 0 ^{26}}{1 0 ^{9} \times 3.16 \times 1 0 ^{7}} = 1.28 \times 1 0^{10} years$
2. Der häufigste Geheimtextbuchstabe ist I mit 80 von 600 Vorkommen (13,3 %). In The Dancing Men liegt das e bei 12,44 %; I steht also für e. Die nächsten drei, O, N und X, kommen 49-, 47- und 45-mal vor. Diese Werte liegen viel zu nah beieinander, um sie verlässlich zu ordnen. Eine reine Rangfolge ordnet ihnen t, a und o zu – alle drei falsch. Die Ergebnistabelle zeigt das Resultat: Eine Zuordnung rein nach Rang trifft nur 3 der 23 Buchstaben, magere 14,2 % des Textes.
  
  $\frac{80}{600} = 13.3% \approx 12.44% : I \to e, 49, 47, 45 for O, N, X$
3. Nun zu den Wörtern. Die dreibuchstabigen Wörter OBJ und XDI kommen je fünfmal vor. XDI endet auf I, also e: Das legt the nahe, womit X für t steht und D für h. OBJ ist dann höchstwahrscheinlich and: O ist a, B ist n, J ist d. Das häufigste zweibuchstabige Wort, PK, taucht achtmal auf und passt zu of. XP kommt fünfmal vor und liest sich damit als to, was die bisherigen Treffer bestätigt.
  
  $XDI \to t h e, OBJ \to an d, PK \to o f, XP \to t o$
4. Trage diese acht Buchstaben in die Felder ein. e, t, h, a, n, d, o und f decken 321 der 600 Buchstaben ab, also 53,5 %. Die erste Zeile lautet nun f·o· the ·ea·· 1894 to 1901. Mehr lässt sich aus den Häufigkeiten nicht herausholen. Vor einer Jahreszahl ist f·o· so gut wie sicher from. Das liefert r und m – ab hier liest man einfach den Text.
  
  $\frac{321}{600} = 53.5% of the message from 8 letters$
Antwort

12,8 Milliarden Jahre, um jeden Schlüssel zu testen. Das reine Zählen liefert genau einen Buchstaben, das e; drei häufige Wörter steuern sieben weitere bei. Und diese acht Buchstaben entschlüsseln bereits 53,5 % der Nachricht.

$1.28 \times 1 0^{10} years; 8 letters \to 53.5%$

Lernpfad

Wie Chiffren gebrochen werden

Quellen (1)

Both passages the page counts, and Holmes's words quoted in the second and third insights: Arthur Conan Doyle, "The Adventure of the Dancing Men" and "The Adventure of the Solitary Cyclist," in The Return of Sherlock Holmes. Project Gutenberg eBook #108.

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.