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.
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.Entschlüsselung
Wenn dein Freund die Nachricht erhält, wenn er 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.
HUD ist, und der Verschiebungswert S=6, was war die ursprüngliche Botschaft? (Wichtig: Verwende Großbuchstaben))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.) |
