15C: Caesar-Chiffre

Die Aufgaben 15A, 15B, und 15C können in beliebiger Reihenfolge bearbeitet werden.

Kryptographie ist die Kunst und Wissenschaft des Verbergens von Information, auf solch eine Art und Weise, dass nur bestimmte Leute es sehen können. In dieser Lektion werden wir eine der einfachsten kryptographischen Methoden einführen, die Caesar-Verschlüsselung (auch bekannt als eine sogenannte Verschiebechiffre), und du wirst lernen, wie man ein Programm schreibt, das diese Verschlüsselung bricht. Du wirst jeden Aspekt deiner Lösung selbst entwerfen (im Gegensatz zu Lektion 15A, die wir in Unterkapitel unterbrochen hatten)

Die Caesar-Verschlüsselung funktioniert, indem man jeden Buchstaben des Alphabets durch einen anderen Buchstaben ersetzt. Genauer gesagt bedeutet das, dass, wenn du einen Text kodieren möchtest, du jedesmal einen Verschiebungswert S wählen musst, der eine Zahl zwischen 0 und 25 ist. Dann ersetzt du jeden Buchstaben im Text mit dem Buchstaben, der S Stellen später im Alphabet steht, wobei du natürlich wieder am Anfang beginnen musst, nachdem du Z am Ende des Alphabets erreicht hast.

Beispiel

Nehmen wir an, wir wollen die geheime Botschaft

JOIN ME AT EIGHT BY THE ZOO

kodieren, und wir verwenden den Verschiebungswert S=2.
Die Verschlüsselungsregel besagt, dass jeder Buchstabe ersetzt wird durch den Buchstaben, der zwei Stellen später im Alphabet kommt. Zum Beispiel, da das Alphabet folgendermaßen aussieht: ABCDEFGHIJKL..., wird der erste Buchstabe J durch den Buchstaben L ersetzt. Des Weiteren ersetzen wir O durch Q, I durch K, etc. Um den Buchstaben Y zu verschlüsseln, müssen wir zurück zum Anfang: nach Y kommt Z, dann A, also ersetzen wir Y durch A. Dem selben Prinzip folgend wird Z durch B ersetzt. Also ist die verschlüsselte Version unserer Geheimbotschaft:

LQKP OG CV GKIJV DA VJG BQQ

Wenn Spione diese Nachricht sehen würden, wäre es ihnen nicht auf Anhieb klar, was deine Botschaft wäre.

Kurzübung: SPY CODER
Was ist das Resultat davon, wenn wir SPY CODER mit dem Verschiebungswert S=5 verschlüsseln? (Wichtig: Verwende Großbuchstaben) Du kannst ein Programm in der Konsole schreiben, um dies zu berechnen, wenn du möchtest, es könnte später hilfreich sein.
Richtig!

Entschlüsselung

Wenn dein Freund den geheimen Verschiebungswert S kennt, kann er die Nachricht mit Leichtigkeit entschlüsseln: er ersetzt einfach jeden Buchstaben durch denjenigen, der S Stellen früher im Alphabet kommt. Zum Beispiel würde dieser Freund L betrachten, zwei Stellen im Alphabet rückwärts gehen und J finden, von dem er jetzt wüßte, dass es der erste Buchstabe deiner Geheimbotschaft ist. Es ist natürlich wieder so, dass das Alphabet als zyklisch betrachtet wird, so dass Z vor A kommt, wie bereits im obigen Beispiel dargestellt.

Kurzübung: Spy Decoder
Wenn die verschlüsselte Botschaft HUD ist, und der Verschiebungswert S=6, was war die ursprüngliche Botschaft? (Wichtig: Verwende Großbuchstaben))
Richtig!

Für die andere Seite arbeiten

Du wurdest von einem Spion angeheuert, um eine Botschaft entschlüsseln zu helfen, die mit einer Verschiebechiffre verschlüsselt wurde. Ärgerlicherweise weiß der Spion nicht, was der Wert von S ist. Du wirst also Statistik benutzen müssen, um ein Programm zu schreiben, das eine gute Chance darauf hat, automatisch den richtigen Wert für S herauszubekommen.

Wir werden uns der Buchstabenhäufigkeit bedienen. Im Englischen, wie auch im Deutschen, sind manche Buchstaben sehr häufig (wie E) und andere sehr selten (wie J). Hier ist eine Tabelle mit Häufigkeitswerten, die auf dem Zählen von vorkommenden Buchstaben in einer großen Menge von Texten beruht:

A B C D E F G H I
.0817 .0149 .0278 .0425 .1270 .0223 .0202 .0609 .0697
J K L M N O P Q R
.0015 .0077 .0402 .0241 .0675 .0751 .0193 .0009 .0599
S T U V W X Y Z
.0633 .0906 .0276 .0098 .0236 .0015 .0197 .0007

So tritt im Englischen L zum Beispiel in einer Häufigkeit von .0402=4.02% auf, was bedeutet, dass L in einem durchschnittlichen englischen Text 4.02% der Zeit auftaucht.

Bezeichne den Wert eines Buchstaben in der Tabelle oben als Güte. Dann, für unsere statistische Methode, definiere die Güte eines Satzes so, dass sie gleich der Summe der Güte jedes Buchstabens in ihm ist. Zum Beispiel ist die Güte der Kette GOOD

goodness("GOOD") = .0202 + .0751 + .0751 + .0425 = .2129

Nun ist es so, dass die Idee hinter einer Häufigkeitsanalyse die ist, dass Ketten mit höherer Güte auch mit höherer Wahrscheinlichkeit einen sinnvollen Text darstellen. Wenn ein Spion zum Beispiel die verschlüsselte Botschaft "JRRG" sieht, könnte das entweder den Originaltext "GOOD" darstellen, mit dem Verschiebewert S=3, oder "IQQF" mit dem Verschiebewert S=1. Aber die Güte von "IQQF" ist

goodness("IQQF") = .0697 + .0009 + .0009 + .0223 = .0938

und da .0938 < .2129, sollte dein Programm zu dem Schluss kommen, dass GOOD mit höherer Wahrscheinlichkeit die korrekte Botschaft ist als IQQF.

Die Beurteilung von Ketten durch ihre goodness ist nicht perfekt. Wenn zum Beispiel die Geheimbotschaft JAZZ wäre und der geheime Verschiebewert S=10 wäre, dann wäre der verschlüsselte Text TKJJ. Wenn du nun TKJJ in deine Lösung eingibst, wird sie natürlich S=10 versuchen, und JAZZ als Möglichkeit mit einer Güte von .0846 in betracht ziehen, aber das beste Resultat ist S=5, was OFEE ergibt, mit einer Güte von .3514. Dein Programm sollte das Nonsensewort OFEE als beste Lösung ausgeben. (Häufigkeitsanalysen wie diese funktionieren besser, wenn die Geheimbotschaft länger ist.)

Programmierübung: Auto-Decryption
Schreibe ein Programm, welches das folgende macht: zunächst sollte es eine Zeile input einlesen, die die verschlüsselte Nachricht ist, und die aus Großbuchstaben und Leerstellen besteht. Dein Programm muss versuchen, die Botschaft mit allen 26 möglichen Werten der Verschiebung S zu lesen; aus diesen 26 möglichen Originalbotschaften, drucke diejenige aus, die die höchste Güte hat.

Damit es leichter ist für dich, werden wir die Variable letterGoodness (also: BuchstabenGüte) für dich vordefinieren, eine Liste von einer Länge von 26, die den Werten in der Häufigkeitstabelle weiter oben entspricht.

letterGoodness = [.0817,.0149,.0278,.0425,.1270,.0223,.0202,...
Klick hier um einen allgemeinen Ratschlag zu erhalten.
Gib Testbefehle wie print(meinefunktion("Test-Argument")) unten ein.

Die obige Lösung nennt man eine brute force Lösung, also eine Lösung mit Brachialgewalt, da du einfach alle 26 Möglichkeiten durchprobiert hast. Du hättest das sogar von Hand machen können, wenn nötig. Moderne kryptographische Protokolle sind hingegen so konstruiert, dass brute force Lösungen versagen, selbst wenn du sehr schnelle Computer verwendest, um alle Möglichkeiten auszuprobieren.

Wenn du dieses automatische Decodierungssystem genauer machen wolltest, könntest du andere Statistiken beachten, wie zum Beispiel: „welche Buchstaben erscheinen wahrscheinlicher nebeneinander? Welche Buchstaben erscheinen wahrscheinlicher am Wortanfang?“ Dies ist auch hilfreich bei allgemeineren monoalphabetischen Substitution, wo Buchstaben andere Buchstaben ersetzen, aber nicht auf zyklische Art und Weise. Für solche Codes funktioniert Brachialgewalt nicht, da es 26*25*...*1 mögliche Substitutionen gibt, was etwa 4 * 1026 entspricht (vierhundert Quatrillionen).

Du hast diese Lektion beendet! Um diesen Erfolg zu feiern, sende ruhig deinen Freunden eine verschlüsselte Botschaft.