JavaScripts › Verschlüsselungen
Häufigkeitsanalyse
Zählt die Buchstaben eines Textes, stellt sie der deutschen Normalverteilung gegenüber und errät damit die Caesar-Verschiebung.
Der arabische Gelehrte al-Kindi beschrieb im neunten Jahrhundert das Werkzeug, mit dem sich fast jede klassische Verschlüsselung knacken lässt: das Auszählen der Buchstaben. Der Gedanke dahinter ist einfach. In jeder Sprache kommen bestimmte Buchstaben viel häufiger vor als andere — im Deutschen ist das E mit rund 17 Prozent mit Abstand der häufigste, gefolgt von N, I, S und R. Wird nun jeder Buchstabe durch einen anderen ersetzt, ändern sich zwar die Namen, aber nicht die Häufigkeiten: Der häufigste Buchstabe im Geheimtext ist mit ziemlicher Sicherheit das E.
Dieses Script zählt für euch aus. Tragt einen Text ein — verschlüsselt oder nicht — und ihr bekommt die Verteilung als Balken, daneben zum Vergleich die deutsche Normalverteilung. Bei einem normalen deutschen Text sehen beide Reihen ähnlich aus; bei einem Caesar-verschlüsselten Text ist die Verteilung dieselbe, nur seitlich verschoben. Genau daraus errät das Script die Verschiebung und nennt sie unter der Auswertung.
Das Verfahren hat Grenzen, und die sind lehrreich. Es braucht Material: Bei zwanzig Buchstaben sind die Häufigkeiten reines Rauschen, ab etwa zweihundert wird es zuverlässig. Es versagt bei Umstellungsverfahren wie der Zaunpfahl-Verschlüsselung, weil dort die Buchstaben dieselben bleiben und nur ihre Reihenfolge wechselt — die Verteilung ist unverändert die des Klartextes. Und es versagt beim Vigenère-Quadrat, weil dort jeder Buchstabe anders verschoben wird und sich die Häufigkeiten dadurch einebnen. Genau das war jahrhundertelang der Ruhm dieses Verfahrens.
Die Verteilung eines gut verschlüsselten modernen Textes ist übrigens vollkommen flach: Jedes Byte kommt gleich häufig vor. Wenn ihr die SHA-256-Prüfsumme eines langen Textes hier einwerft, seht ihr, wie das aussieht.
Ausgezählt werden nur A–Z; Umlaute werden vorher zu ae, oe, ue und ss aufgelöst.
So funktioniert das Script
Das Script macht drei Dinge: auszählen, mit einer Referenzverteilung vergleichen und daraus die wahrscheinlichste Verschiebung bestimmen. Der letzte Teil ist der interessanteste, weil er ein statistisches Standardverfahren in fünf Zeilen zeigt.
const zahlen = new Array(26).fill(0);
for (let i = 0; i < text.length; i++) {
zahlen[text.charCodeAt(i) - 65]++;
}Das Auszählen ist ein Klassiker: ein Array mit 26 Fächern, alle auf null gesetzt. charCodeAt(i) - 65 rechnet den Buchstaben in seine Position um — A wird zu 0, Z zu 25 — und dient direkt als Fachnummer. Kein Suchen, kein Vergleichen: Der Buchstabe ist der Index. Dieses Muster heißt Zählarray und ist eine der schnellsten Arten, Häufigkeiten zu bestimmen.
const beobachtet = zahlen[(i + schritt) % 26] / gesamt * 100;
const erwartet = deutsch[i];
summe += (beobachtet - erwartet) * (beobachtet - erwartet) / erwartet;Das ist der Kern und heißt in der Statistik Chi-Quadrat-Test. Für jede angenommene Verschiebung wird gefragt: Wie weit liegt die gemessene Häufigkeit von der erwarteten entfernt? Die Differenz wird quadriert — dadurch zählen Abweichungen nach oben und unten gleich, und große fallen stärker ins Gewicht als kleine. Anschließend wird durch den Erwartungswert geteilt: Eine Abweichung von einem Prozentpunkt ist beim seltenen Q ein grober Fehler, beim häufigen E kaum der Rede wert.
for (let schritt = 0; schritt < 26; schritt++) {
const wert = abweichung(zahlen, gesamt, schritt);
if (wert < besterWert) { besterWert = wert; besterSchritt = schritt; }
}Nun werden schlicht alle 26 Verschiebungen durchprobiert und diejenige behalten, bei der die Abweichung am kleinsten ist. Das ist das übliche Muster für „finde das Beste": ein Merker für den bisher besten Wert, anfangs auf Infinity gesetzt, damit der erste Versuch ihn garantiert unterbietet. Anders als beim Durchprobieren mit den Augen entscheidet hier eine Zahl — und das funktioniert auch dann noch, wenn der Text zu kurz zum Lesen ist.
width: (anteil / 18 * 100) + "%"Die Balken sind keine Grafik, sondern schlicht farbige Flächen mit einer prozentualen Breite. Geteilt wird durch 18, weil der häufigste deutsche Buchstabe knapp darunter liegt — so füllt das E den Balken fast ganz aus und der Rest bleibt gut ablesbar. Die gepunktete Linie darüber sitzt an der erwarteten Häufigkeit; wo Balken und Linie zusammenfallen, passt die Verteilung.
Zum Anpassen: Für englische Texte ersetzt ihr das Array deutsch durch die englischen Häufigkeiten (dort ist E mit 12,7 Prozent ebenfalls Spitzenreiter, dann folgen T, A und O). Wollt ihr statt einzelner Buchstaben Paare auszählen — im Deutschen sind ER, EN und CH die häufigsten —, braucht ihr ein Zählarray mit 676 Fächern und rechnet den Index als erster * 26 + zweiter.
Script für die eigene Homepage
Kopiert euch den kompletten Code und fügt ihn an der Stelle eurer Seite ein, an der das Script erscheinen soll. Er läuft ohne weitere Dateien und ohne fremde Server.