Häufigkeitsanalyse
In längeren deutschen Texten ist das E der häufigste Buchstabe. Ein Verschlüsselungsverfahren, das jeden Buchstaben immer durch denselben Buchstaben ersetzt, verwischt diese Eigenheit der Sprache nicht und verrät damit seinen Schlüssel.
Definition
Die Häufigkeitsanalyse ist ein Verfahren der Kryptoanalyse. Sie zählt, wie oft jeder Buchstabe im Geheimtext vorkommt, und vergleicht das Ergebnis mit den bekannten Buchstabenhäufigkeiten der Sprache. Aus dem Vergleich ergibt sich, welcher Geheimtextbuchstabe für welchen Klartextbuchstaben steht.
Bei einem ausreichend langen Geheimtext bricht die Häufigkeitsanalyse jede monoalphabetische Substitution, also die Caesar-Verschlüsselung und die monoalphabetische Substitution mit einer Ersetzungstabelle. Dort steht für einen Klartextbuchstaben immer derselbe Geheimtextbuchstabe, die Häufigkeiten bleiben also erhalten und wandern nur zu anderen Buchstaben.
Buchstabenhäufigkeiten im Deutschen
Die Tabelle zeigt gerundete Durchschnittswerte für deutsche Texte, in denen Umlaute als AE, OE und UE und das ß als SS geschrieben sind. Ein einzelner Text weicht davon ab, je kürzer er ist, desto stärker.
| Buchstabe | Anteil | Buchstabe | Anteil | Buchstabe | Anteil |
|---|---|---|---|---|---|
| E | 17,4 % | U | 4,4 % | K | 1,2 % |
| N | 9,8 % | L | 3,4 % | Z | 1,1 % |
| I | 7,6 % | C | 3,1 % | P | 0,8 % |
| S | 7,3 % | G | 3,0 % | V | 0,7 % |
| R | 7,0 % | M | 2,5 % | J | 0,3 % |
| A | 6,5 % | O | 2,5 % | Y | 0,04 % |
| T | 6,2 % | B | 1,9 % | X | 0,03 % |
| D | 5,1 % | W | 1,9 % | Q | 0,02 % |
| H | 4,8 % | F | 1,7 % |
Merkhilfen:
- E ist mit Abstand der häufigste Buchstabe, danach folgt N.
- Die acht häufigsten Buchstaben E, N, I, S, R, A, T und D machen zusammen etwa zwei Drittel eines Textes aus.
- Häufige Buchstabenpaare sind EN, ER, CH, DE, EI und TE. Häufige Dreiergruppen sind EIN, ICH, DER, DIE, UND und SCH.
Vorgehen
- Die Buchstaben des Geheimtextes zählen und nach Häufigkeit ordnen.
- Den häufigsten Geheimtextbuchstaben dem E zuordnen, den zweithäufigsten dem N.
- Bei einer Caesar-Verschlüsselung ist damit der Schlüssel bekannt: Er ist der Abstand zwischen dem häufigsten Geheimtextbuchstaben und dem E.
- Bei einer Ersetzungstabelle weitere Buchstaben erschließen: über häufige Buchstabenpaare, über doppelte Buchstaben und über Wörter, die im Text vermutlich vorkommen.
- Den teilweise entschlüsselten Text lesen, Lücken aus dem Zusammenhang füllen und jede Vermutung am ganzen Text prüfen.
Die statistische Grundlage, absolute und relative Häufigkeit, erklärt der Artikel Häufigkeit.
Grenzen
- Kurze Texte: In einem Text aus wenigen Buchstaben ist das E nicht sicher der häufigste Buchstabe. Zuverlässig wird die Analyse erst ab etwa hundert Buchstaben.
- Ungewöhnliche Texte: Listen, Abkürzungen oder Texte in anderen Sprachen haben andere Häufigkeiten.
- Polyalphabetische Verfahren: Beim Vigenère-Verfahren wird derselbe Klartextbuchstabe je nach Schlüsselbuchstabe verschieden ersetzt. Die Häufigkeiten gleichen sich an, und die einfache Analyse scheitert. Sie gelingt erst wieder, wenn die Schlüssellänge bekannt ist (siehe Kasiski-Test).
- Transposition: Bei einer Transposition bleiben die Häufigkeiten der Klartextbuchstaben unverändert. Die Analyse zeigt dann nur, dass keine Substitution vorliegt.
Beispiele
Verschiebung aus dem häufigsten Buchstaben ermitteln
Der folgende Geheimtext wurde mit der Caesar-Verschlüsselung erzeugt, der Schlüssel ist unbekannt:
KWOXN ONOBG YMROD BOPPO XGSBE XCGSO NOBKW COOEX NVOCO XQOWO SXCKW OSXOX XOEOX DOHD
Die häufigsten Buchstaben:
| Buchstabe | O | X | B | C | N | S | W |
|---|---|---|---|---|---|---|---|
| Anzahl | 19 | 10 | 4 | 4 | 4 | 4 | 4 |
Der häufigste Buchstabe ist O. Vermutlich steht er für das E:
- [math]\displaystyle{ k = (14 - 4) \bmod 26 = 10 }[/math]
Die Entschlüsselung mit [math]\displaystyle{ k = 10 }[/math] bestätigt die Vermutung: AMEND EDERW OCHET REFFE NWIRU NSWIE DERAM SEEUN DLESE NGEME INSAM EINEN NEUEN TEXT
Monoalphabetischen Geheimtext schrittweise entschlüsseln
Der folgende Geheimtext wurde mit einer Ersetzungstabelle verschlüsselt:
LQTXQ QBZOZ BCCBP TLMDU LBGLP UBZVB UBPKE BPUKQ TBBTL BEKUB PBTTB PBLTY PUZBU BPELT ULBTX PPBYP OBZRB DOYPU UBZQX PUTMD BLPO
Schritt 1: Buchstaben zählen
| Buchstabe | B | P | U | T | L | Z |
|---|---|---|---|---|---|---|
| Anzahl | 23 | 14 | 11 | 10 | 9 | 6 |
Die beiden häufigsten Buchstaben stehen vermutlich für E und N: B für E, P für N. Alle übrigen Buchstaben bleiben zunächst offen (Punkt):
····· ·E··· E··EN ····· ·E··N ·E··E ·EN·· EN··· ·EE·· E···E NE··E NE··· N··E· EN··· ··E·· NNE·N ·E··E ···N· ·E··· N···· E·N·
Schritt 2: ein vermutetes Wort suchen
Im Text geht es um den Sommer. Das Wort SOMMER hat ein auffälliges Muster: An dritter und vierter Stelle steht derselbe Buchstabe, an fünfter Stelle ein E, und kein anderer Buchstabe des Wortes ist ein E oder ein N. Mit B für E und P für N passt im Geheimtext nur eine Stelle dazu. Sie beginnt an Position 3, gezählt ab 1: TXQQBZ. Daraus folgen T für S, X für O, Q für M, Z für R.
·MSOM MER·R E··EN S···· ·E··N ·ER·E ·EN·· EN··M SEES· E···E NESSE NE·S· N·RE· EN··S ··ESO NNE·N ·ER·E ···N· ·ERMO N·S·· E·N·
Schritt 3: Lücken aus dem Zusammenhang füllen
Jetzt lassen sich Wörter erraten, und jedes erratene Wort liefert weitere Buchstaben. Nach und nach ergeben sich die restlichen 12 Buchstaben des Textes (A, B, C, D, F, G, H, I, J, K, T, U). Der Klartext lautet:
IMSOM MERTR EFFEN SICHD IEKIN DERJE DENAB ENDAM SEESI EBADE NESSE NEISU NDRED ENBIS DIESO NNEUN TERGE HTUND DERMO NDSCH EINT