Häufigkeitsanalyse erklärt

Jahrhundertelang bestand die beste Art, eine Nachricht zu verbergen, darin, jeden Buchstaben des Alphabets gegen einen anderen auszutauschen. Die Zahl der möglichen Schlüssel ist astronomisch, also schien die Verschlüsselung unknackbar. Doch ein Gelehrter in Bagdad hatte schon im 9. Jahrhundert ihre Schwäche gefunden: Eine Sprache verwendet manche Buchstaben weit häufiger als andere, und kein noch so gründliches Vertauschen verbirgt das. Die Häufigkeitsanalyse machte das Codeknacken vom Ratespiel zur Methode, und sie ist bis heute das Erste, was man an einer neuen Verschlüsselung ausprobiert.

Ein Balkendiagramm der Geheimbuchstaben vom häufigsten zum seltensten, abgeglichen mit den Häufigkeiten des Englischen, über einem Geheimtext, in dem die ersten Buchstaben gelöst sind
Ein Balkendiagramm der Geheimbuchstaben vom häufigsten zum seltensten, abgeglichen mit den Häufigkeiten des Englischen, über einem Geheimtext, in dem die ersten Buchstaben gelöst sind

Die Substitutionschiffre

Eine einfache Substitutionschiffre ersetzt jeden Buchstaben des Alphabets nach einer festen Tabelle durch einen anderen: etwa A durch Q, B durch W und so weiter, wobei jeder Buchstabe einmal verwendet wird. Die Tabelle ist der Schlüssel. Anders als die Caesar-Verschlüsselung, die das Alphabet nur verschiebt und 25 Schlüssel hat, kann die Substitutionschiffre jede beliebige Reihenfolge der Buchstaben verwenden: 26! Schlüssel, etwa 4 × 10²⁶. Selbst ein Computer, der eine Milliarde Schlüssel pro Sekunde testet, bräuchte mehr als zehn Milliarden Jahre, um alle auszuprobieren.

Al-Kindis Entdeckung

Um das Jahr 850 schrieb der arabische Philosoph Abu Yusuf al-Kindi eine Abhandlung über das Entziffern geheimer Botschaften, die älteste bekannte Beschreibung der Häufigkeitsanalyse. Sein Rat: einen langen Text in derselben Sprache nehmen, zählen, wie oft jeder Buchstabe vorkommt, dann die Buchstaben der geheimen Botschaft zählen und beide einander zuordnen, den häufigsten dem häufigsten, den nächsten dem nächsten. Gelehrte, die den Koran studierten, hatten seit Generationen Buchstaben und Wörter gezählt, und vielleicht entstand die Idee auf diese Weise.

Buchstaben, Paare und Wörter

Im Englischen sind etwa 12,7 % der Buchstaben ein E, 9 % ein T und 8 % ein A, während Z seltener als einmal in tausend Buchstaben vorkommt. Einzelne Zahlen weisen nur die Richtung, besonders in kurzen Texten, also nutzen Codeknacker jedes Muster, das sie finden können. Ein Wort aus einem Buchstaben ist A oder I. Die häufigsten Paare sind TH, HE, IN und ER, die häufigsten Doppelbuchstaben LL, EE, SS und OO. Auf Q folgt fast immer U. Ein häufiges Wort aus drei Buchstaben ist wahrscheinlich THE, und sobald T, H und E bekannt sind, ergeben sich Wörter wie THAT und THERE wie von selbst. Jede Sprache hat ihren eigenen Fingerabdruck: Im Deutschen und Niederländischen dominiert E noch stärker, während im Portugiesischen A vorn liegt.

Die tödliche Verschlüsselung einer Königin

1586 tauschte die in England gefangene Maria Stuart verschlüsselte Briefe mit Anthony Babington aus, der plante, sie zu befreien und Königin Elisabeth I. zu töten. Die Briefe wurden in Bierfässern hinausgeschmuggelt, gingen aber durch die Hände von Elisabeths Geheimdienstchef Francis Walsingham, dessen Codeknacker Thomas Phelippes die Verschlüsselung, eine Substitution mit einigen zusätzlichen Symbolen für häufige Wörter, durch Häufigkeitsanalyse brach. Die entschlüsselten Briefe bewiesen Marias Beteiligung an der Verschwörung, und sie wurde im Februar 1587 hingerichtet.

Die Häufigkeiten verbergen

Die Erfinder von Verschlüsselungen wehrten sich. Homophone Verschlüsselungen gaben häufigen Buchstaben jeweils mehrere Symbole, sodass jedes Symbol etwa gleich oft vorkam. Blender, bedeutungslose Symbole, wurden im Text verstreut, um die Zählungen zu verwirren. Die eigentliche Antwort kam mit polyalphabetischen Verschlüsselungen wie der Vigenère-Verschlüsselung des 16. Jahrhunderts, die beim Verschlüsseln zwischen mehreren Alphabeten wechseln, sodass ein Klartextbuchstabe zu vielen verschiedenen Geheimbuchstaben wird. Sie hielt stand, bis Charles Babbage und Friedrich Kasiski im 19. Jahrhundert zeigten, wie man die Länge des Schlüssels findet und dann die Häufigkeitsanalyse auf jedes Alphabet einzeln anwendet.

Wie Computer Kryptogramme lösen

Auch ein Programm kann nicht jeden Schlüssel ausprobieren, aber es kann klettern. Es beginnt mit einer Vermutung, bewertet das Ergebnis danach, wie sehr es der Sprache ähnelt, meist danach, wie häufig seine Gruppen aus zwei bis vier Buchstaben sind, und vertauscht dann Buchstabenpaare im Schlüssel, wobei es jeden Tausch behält, der den Wert erhöht. Hilft kein Tausch mehr, rüttelt es den Schlüssel durch und beginnt erneut mit dem Aufstieg, wobei es das beste Ergebnis behält. Dieses Verfahren, Bergsteigeralgorithmus oder Hill Climbing genannt, löst eine Substitutionschiffre aus einigen hundert Buchstaben in Sekundenbruchteilen, und Varianten davon haben historische Verschlüsselungen geknackt, die Menschen jahrhundertelang widerstanden hatten.

Häufigkeitsanalyse heute

Moderne Verschlüsselungen wie AES sind so entworfen, dass der Geheimtext völlig zufällig aussieht: Jeder Bytewert kommt gleich oft vor, und dieselbe Nachricht wird jedes Mal anders verschlüsselt. Die Häufigkeitsanalyse findet bei ihnen keinen Ansatzpunkt. Die Idee lebt dennoch weiter: Sprachstatistiken helfen zu erkennen, ob eine Entschlüsselung richtig ist, die Verschlüsselungen von Rätseln und Escape Rooms zu knacken und alte verschlüsselte Briefe aus Archiven zu lesen. 2023 wurden jahrhundertelang verschollene Briefe Maria Stuarts mit Computerhilfe entschlüsselt.

Selbst ausprobieren

Öffnen Sie das Häufigkeitsanalyse-Tool für einen verschlüsselten Absatz auf Englisch, Deutsch, Französisch, Spanisch, Italienisch, Portugiesisch oder Niederländisch. Vergleichen Sie im Diagramm die Buchstabenzahlen mit der Sprache, nutzen Sie die Hinweise aus Paaren, Doppelbuchstaben und kurzen Wörtern und tragen Sie den Schlüssel Buchstabe für Buchstabe ein. Tipp und Prüfen helfen, wenn Sie nicht weiterkommen, und der Löser zeigt, wie der Bergsteigeralgorithmus die Arbeit beendet.

Häufig gestellte Fragen

Warum ist E im Englischen der häufigste Buchstabe?

Weil es in vielen der häufigsten englischen Wörter vorkommt, etwa THE, BE, HE, WE und ARE, und in gängigen Endungen wie -ED und -ES. Die meisten europäischen Sprachen teilen das: Auch im Französischen, Deutschen, Niederländischen und Spanischen liegt E vorn.

Kann die Häufigkeitsanalyse jede Verschlüsselung brechen?

Nein. Sie bricht Verschlüsselungen, bei denen jeder Klartextbuchstabe immer durch dasselbe Symbol ersetzt wird. Verschlüsselungen, die die Ersetzung unterwegs ändern, oder moderne Verschlüsselungen, die mit Bits statt mit Buchstaben arbeiten, erfordern andere Methoden oder lassen sich überhaupt nicht brechen.

Was ist ein Kryptogramm-Rätsel?

Ein Zitat oder Satz, mit einer einfachen Substitution verschlüsselt und abgedruckt, damit Leser es von Hand lösen. Kryptogramme erscheinen seit dem 19. Jahrhundert in Zeitungen und werden genau so gelöst, wie es das Tool zeigt: mit den kurzen Wörtern und den häufigsten Buchstaben beginnen.

Wie gelang die Entschlüsselung der verschollenen Briefe Maria Stuarts?

2023 identifizierten George Lasry, Norbert Biermann und Satoshi Tomokiyo 57 verschlüsselte Briefe in einer französischen Bibliothek als ihre. Die Verschlüsselung verwendete fast 200 Symbole, also kombinierten sie einen Bergsteigeralgorithmus am Computer, der die wahrscheinliche Bedeutung vieler Symbole vorschlug, mit sorgfältiger Handarbeit für den Rest.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Häufigkeitsanalyse-Tool öffnen