Caesar-Verschlüsselung [KSR Wiki]

Bei der Caesar-Verschlüsselung werden alle Buchstaben um eine Anzahl Stellen verrückt:

Aufgabe 1: Caesar-Verschlüsselung in Python

Schreibe eine Funktion caesar(klartext, n), die die Cäsar-Verschlüsselung umsetzt.

Gebe nur Grossbuchstaben aus.
Zeichen, die keine Buchstaben sind, sollen nicht verändert werden.
Wie kannst du das Chiffrat (den Ciphertext) entschlüsseln?

Ein paar Tipps

Du kannst über die Buchstaben eines Strings laufen wie über die Elemente einer Liste:

s = "Hallo KSR"
for buchstabe in s:
    print(buchstabe)

Einen String in Grossbuchstaben umwandeln:

print("Hallo KSR".upper())
>>> HALLO KSR

Alle Grossbuchstaben können in string.ascii_uppercase abgefragt werden. Mit str.find() können wir den Index (oder -1) finden:

import string
 
for buchstabe in "HALLO":
    print(string.ascii_uppercase.find(buchstabe))
 
>>>
7
0
11
11
14

Der Modulo-Operator % gibt uns den Rest der Ganzzahl-Division zurück. Das ist praktisch, um den Index wieder bei A starten zu lassen, wenn er grösser als Z wird:

import string
 
klartext = "Z"
index = string.ascii_uppercase.find(klartext)
index += 3
index = index % len(string.ascii_uppercase)
ciphertext = string.ascii_uppercase[index]
print(ciphertext)
 
>>> C

Lösung:

Aufgabe 2

a)

Die folgende Nachricht ist mit der Caesar-Verschlüsslung verschlüsselt, indem alle Buchstaben um $3$ Stellen verschoben wurden: LQIRUPDWLN!LVW!VXSHU

Als Alphabet wurden folgende Zeichen verwendet: ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 .,!?

Was bedeutet die Nachricht?

b)

Nutze deinen Code, um die folgende Nachricht zu knacken: XN06VI41ZN05U140KIQVRIV0018N6V8RI5PU7YRIVZIT47R0R0J

Tipp

Eine Weiterentwicklung der Caesar-Verschlüsselung erhält man, wenn man das Alphabet nicht nur um eine fest Anzahl stellen verschiebt, sondern das gesamte Alphabet durchmischt. Aus ABCDEFGHIJKLMNOPQRSTUVWXYZ wird dann zum Beispiel UELXBICNYAZJSQORTPKFMGVHWD oder VSEIYHJTBUPANRCOQDLXFWKMZG. Diese neu sortierte Version dient als Schlüssel und wird benötigt, um die Nachricht zu entziffern. Man muss also darauf achten, dass dieser nicht in feindliche Hände gelangt. Diese Art der Verschlüsselung nennt man eine monoalphabetische Verschlüsselung.

Aufgabe B1

Ist die Caesar-Verschlüsselung auch eine monoalphabetische Verschlüsselung?
Wie viele Möglichkeiten gibt es, eine Nachricht mit der Caesar-Verschlüsselung zu verschlüsseln? Es sollen nur die $26$-Standardbuchstaben des Alphabets verschlüsselt werden.
Wie viele Möglichkeiten gibt es für die monoalphabtische Verschlüsselung? (wieder mit $26$ Buchstaben).
Wie schätzt du die Sicherheit der monoalphabtischen Verschlüsselung ein? Welche Möglichkeiten gibt es, um eine damit verschlüsselte Nachricht zu entziffern?
Eine mit der Caesar-Methode verschlüsselte Nachricht kann man problemlos mit Brute-Force entschlüsseln (alle Möglichkeiten ausprobieren). Funktioniert dies bei der monoalphabetische Verschlüsselung auch? Gibt es bessere Möglichkeiten, eine solche zu entziffern?

Lösung

Aufgabe B2

Die Nachricht RYDDUYKFXUKEBKFBBKKBQXBPVBJF wurde mit dem Schlüssel UELXBICNYAZJSQORTPKFMGVHWD verschlüsselt. Schreibe ein Programm, mit welchem du die Nachricht im Klartext ermitteln kannst.

Tipps

Mehr Tipps

def decrypt(ciphertext, key):
    # oder string.ascii_uppercase
    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    cleartext = ""
    for letter in ciphertext:
        # TODO
        # 1: Jeden Buchstaben im Chiffrat einzeln entschlüsseln.
        # 1a: Index des Buchstabens im Schlüssel finden.
        index = ...
        # 1b: Klartext-Buchstaben am gleichen Index im Alphabet auslesen.
        clear_letter = ...
        # 2: entschlüsselten Buchstaben an den Klartext anfügen.
        cleartext = cleartext + clear_letter
    return cleartext
 
ciphertext = "RYDDUYKFXUKEBKFBBKKBQXBPVBJF"
key = "UELXBICNYAZJSQORTPKFMGVHWD"
print(decrypt(ciphertext, key))

Lösung

def decrypt(ciphertext, key):
    # oder string.ascii_uppercase
    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    cleartext = ""
    for letter in ciphertext:
        # 1: Jeden Buchstaben im Chiffrat einzeln entschlüsseln.
        # 1a: Index des Buchstabens im Schlüssel finden.
        index = key.find(letter)
        # 1b: Klartext-Buchstaben am gleichen Index im Alphabet auslesen.
        clear_letter = alphabet[index]
        # 2: entschlüsselten Buchstaben an den Klartext anfügen.
        cleartext = cleartext + clear_letter
    return cleartext
 
ciphertext = "RYDDUYKFXUKEBKFBBKKBQXBPVBJF"
key = "UELXBICNYAZJSQORTPKFMGVHWD"
print(decrypt(ciphertext, key))

Nicht alle Buchstaben kommen gleich oft vor in einer Sprache. Dies können wir nutzen, indem wir das Buchstabe-Histogramm des Chiffrats mit dem der vermuteten Klartext-Sprache vergleichen.

Was sind die Probleme und Voraussetzungen?

Lösung:

Aufgabe C1: Monoalphabetische Substitution knacken mit Häufigkeitsanalyse.

Versuche, das Chiffrat eines englischen Klartexts zu knacken.

Aufgabe C2

Ist die verschlüsselte Nachricht lange genug, kann man eine Häufigkeitsanalyse durchführen. In der deutschen Sprache kommt der Buchstabe „E“ mit gut $15\%$ eindeutig am häufigsten vor. Kommt also in der verschlüsselten Nachricht der Buchstabe „Q“ am häufigsten vor, können wir davon ausgehen, dass es sich bei diesem eigentlich um ein „E“ handelt. Mit dieser Methode kann man zumindest einmal die häufigsten paar Buchstaben richtig bestimmen. Bei den weniger häufigen Buchstaben wird die Reihenfolge dann wohl nicht mehr ganz stimmen. Mit ein paar cleveren Vermutungen, kann man dies aber relativ einfach korrigieren. Kommt zum Beispiel im verschlüsselten Text häufig das Wort „HIE“ vor, dürfte es sich beim „H“ um wohl um ein „D“ handeln. Ein „S“ wäre auch eine Möglichkeit, aber da „S“ der dritthäufigste Buchstabe ist, wurde dieser wohl bereits korrekt erkannt. Dabei hilft es zu wissen, welche Wörter besonders oft vorkommen: Liste der häufigsten Wörter der deutschen Sprache

Wähle eine der beiden Optionen:

Option 1: Häufigkeitsanalyse von einzelnem String (einfach)

Schreibe eine Funktion, die eine Linie Text einliest und eine Häufigkeitsanalyse durchführt. Das Alphabet soll nur aus den $26$ Standardbuchstaben Bestehen. Alle Buchstaben sollen in Kleinbuchstaben umgewandet werden. Umlaute wie Ä,ä,Ö,ö,Ü,ü sollen als ae,oe und ue, die Buchstaben é,è und à als e und a aufgefasst werden. Buchstaben in einem String kannst du wie folgt ersetzen: s = s.replace('é','e')

Wende deine Funktion auf den folgenden Ausschnitt von Goethe's Faust an und vergleiche deine Resultate mit den Musterlösungen:

Text Faust

faust = 'Habe nun, ach! Philosophie, Juristerei und Medizin, Und leider auch Theologie Durchaus studiert, mit heissem Bemühn. Da steh ich nun, ich armer Tor! Und bin so klug als wie zuvor; Heisse Magister, heisse Doktor gar Und ziehe schon an die zehen Jahr Herauf, herab und quer und krumm Meine Schüler an der Nase herum Und sehe, dass wir nichts wissen können! Das will mir schier das Herz verbrennen. Zwar bin ich gescheiter als all die Laffen, Doktoren, Magister, Schreiber und Pfaffen; Mich plagen keine Skrupel noch Zweifel, Fürchte mich weder vor Hölle noch Teufel Dafür ist mir auch alle Freud entrissen, Bilde mir nicht ein, was Rechts zu wissen, Bilde mir nicht ein, ich könnte was lehren, Die Menschen zu bessern und zu bekehren. Auch hab ich weder Gut noch Geld, Noch Ehr und Herrlichkeit der Welt; Es möchte kein Hund so länger leben! Drum hab ich mich der Magie ergeben, Ob mir durch Geistes Kraft und Mund Nicht manch Geheimnis würde kund; Dass ich nicht mehr mit saurem Schweiss Zu sagen brauche, was ich nicht weiss; Dass ich erkenne, was die Welt Im Innersten zusammenhält, Schau alle Wirkenskraft und Samen, Und tu nicht mehr in Worten kramen. O sähst du, voller Mondenschein, Zum letztenmal auf meine Pein, Den ich so manche Mitternacht An diesem Pult herangewacht. Dann über Büchern und Papier, Trübselger Freund, erschienst du mir! Ach! könnt ich doch auf Bergeshöhn In deinem lieben Lichte gehn, Um Bergeshöhle mit Geistern schweben, Auf Wiesen in deinem Dämmer weben, Von allem Wissensqualm entladen, In deinem Tau gesund mich baden!Weh! steck ich in dem Kerker noch? Verfluchtes dumpfes Mauerloch, Wo selbst das liebe Himmelslicht Trüb durch gemalte Scheiben bricht! Beschränkt mit diesem Bücherhauf, den Würme nagen, Staub bedeckt, Den bis ans hohe Gewölb hinauf Ein angeraucht Papier umsteckt; Mit Gläsern, Büchsen rings umstellt, Mit Instrumenten vollgepfropft, Urväter Hausrat drein gestopft Das ist deine Welt! das heisst eine Welt!Und fragst du noch, warum dein Herz Sich bang in deinem Busen klemmt? Warum ein unerklärter Schmerz Dir alle Lebensregung hemmt? Statt der lebendigen Natur, Da Gott die Menschen schuf hinein, Umgibt in Rauch und Moder nur Dich Tiergeripp und Totenbein.Flieh! auf! hinaus ins weite Land! Und dies geheimnisvolle Buch, Von Nostradamus eigner Hand, Ist dir es nicht Geleit genug? Erkennest dann der Sterne Lauf, Und wenn Natur dich Unterweist, Dann geht die Seelenkraft dir auf, Wie spricht ein Geist zum andren Geist. Umsonst, dass trocknes Sinnen hier Die heilgen Zeichen dir erklärt. Ihr schwebt, ihr Geister, neben mir; Antwortet mir, wenn ihr mich hört! (Er schlägt das Buch auf und erblickt das Zeichen des Makrokosmus.)Ha! welche Wonne fliesst in diesem Blick Auf einmal mir durch alle meine Sinnen! Ich fühle junges, heilges Lebensglück Neuglühend mir durch Nerv und Adern rinnen. War es ein Gott, der diese Zeichen schrieb, Die mir das innre Toben stillen, Das arme Herz mit Freude füllen, Und mit geheimnisvollem Trieb Die Kräfte der Natur rings um mich her enthüllen? Bin ich ein Gott? Mir wird so licht! Ich schau in diesen reinen Zügen Die wirkende Natur vor meiner Seele liegen. Jetzt erst erkenn ich, was der Weise spricht. "Die Geisterwelt ist nicht verschlossen; Dein Sinn ist zu, dein Herz ist tot! Auf, bade, Schüler, unverdrossen Die irdsche Brust im Morgenrot!" (er beschaut das Zeichen.) Wie alles sich zum Ganzen webt, Eins in dem andern wirkt und lebt! Wie Himmelskräfte auf und nieder steigen Und sich die goldnen Eimer reichen! Mit segenduftenden Schwingen Vom Himmel durch die Erde dringen, Harmonisch all das All durchklingen! Welch Schauspiel! Aber ach! ein Schauspiel nur! Wo fass ich dich, unendliche Natur? Euch Brüste, wo? Ihr Quellen alles Lebens, An denen Himmel und Erde hängt, Dahin die welke Brust sich drängt Ihr quellt, ihr tränkt, und schmacht ich so vergebens? (er schlägt unwillig das Buch um und erblickt das Zeichen des Erdgeistes.) Wie anders wirkt dies Zeichen auf mich ein! Du, Geist der Erde, bist mir näher; Schon fühl ich meine Kräfte höher, Schon glüh ich wie von neuem Wein. Ich fühle Mut, mich in die Welt zu wagen, Der Erde Weh, der Erde Glück zu tragen, Mit Stürmen mich herumzuschlagen Und in des Schiffbruchs Knirschen nicht zu zagen. Es wölkt sich über mir Der Mond verbirgt sein Licht Die Lampe schwindet! Es dampft! Es zucken rote Strahlen Mir um das HauptEs weht Ein Schauer vom Gewölb herab Und fasst mich an! Ich fühls, du schwebst um mich, erflehter Geist Enthülle dich! Ha! wies in meinem Herzen reisst! Zu neuen Gefühlen All meine Sinnen sich erwühlen! Ich fühle ganz mein Herz dir hingegeben! Du musst! du musst! und kostet es mein Leben! (Er fasst das Buch und spricht das Zeichen des Geistes geheimnisvoll aus. Es zuckt eine rötliche Flamme, der Geist erscheint in der Flamme.)'

Tipps

Lösungen

a   5.16%
b   1.88%
c   3.97%
d   4.75%
e  15.37%
f   1.84%
g   2.78%
h   6.42%
i   8.13%
j   0.23%
k   1.07%
l   3.90%
m   3.14%
n   9.42%
o   2.83%
p   1.11%
q   0.04%
r   6.83%
s   6.51%
t   6.67%
u   4.00%
v   0.65%
w   1.85%
x   0.05%
y   0.45%
z   0.94%

Python Lösung

import string
 
def normalize(text):
    """Replaces umlauts with base characters, and lower-case variants."""
    text = text.lower()
    text = text.replace('ä', 'a')
    text = text.replace('ö', 'o')
    text = text.replace('ü', 'u')
    return text
 
def count_letters(text):
    """Computes relative frequency of lower-case ASCII letters in text."""
    # 1: Prepare empty data
    alphabet = string.ascii_lowercase
    counts = [0] * len(alphabet)  # Creates [0, 0, ..., 0]
    total = 0
 
    # 2: Count occurrences
    for letter in text:
        letter = normalize(letter)
        index = alphabet.find(letter)
        # find() returns negative numbers if not found
        # (punctuation etc.) -> ignore these.
        if index >= 0:
            counts[index] = counts[index] + 1
            total = total + 1
 
    # 3: Divide by total to get relative frequencies.
    for i in range(len(counts)):
        counts[i] = counts[i] / total
 
    return counts
 
def print_percentages(counts):
    """Pretty-print frequency data."""
    for i in range(len(counts)):
        letter = string.ascii_lowercase[i]
        percent = counts[i]
        # Print the letter with width 2
        # Print the frequency with width 6 and precision 2, in percent format.
        print(f"{letter:2}{percent:6.2%}")
 
print_percentages(count_letters(faust))

Option 2: Häufigkeitsanalyse von ganzem Buch (anspruchsvoll)

Wie in Option 1, nur soll anstelle eines einzelnen Strings ein ganzes Buch eingelesen und analysiert werden. Auf Project Gutenberg findest du über $60'000$ gratis Ebooks. Wähle ein Buch aus und klicke dann auf „Plain Text UTF-8“. Das Buch erscheint dann im einfachen Textformat direkt im Browser. Über den dazugehörigen Link, kannst du das Buch direkt in Python einlesen:

from urllib.request import urlopen
count = 0
data = urlopen(<Pfad zur Datei>)
text = data.read().decode('utf-8')  # reads all downloaded bytes, convert to text

Kontrolle: am häufigsten vorkommen sollte $E$ (gut $15\%$), gefolgt von $N$ (ca. $10\%$) und $S$. Die letzten Ränge machen typischerweise $Y$, $Q$ und $X$ unter sich aus.

Lösung mit Gutenberg

# Rest as above.
from urllib.request import urlopen
 
faust = urlopen('http://www.gutenberg.org/files/21000/21000-0.txt')
s= faust.read().decode('utf-8')
print_percentages(count_letters(s))

Aufgabe C3 (optional)

Versuche, mithilfe einer Häufigkeitsanalyse den Text (in deutscher Sprache, nur Kleinbuchstaben) unten möglichst fest zu entschlüsseln. Aus welchem Buch ist dieser?

Die Buchstaben in der folgenden Liste ist entsprechend ihrer typischen Häufigkeit in der deutschen Sprache geordnet:

['e', 'n', 's', 'r', 'i', 'a', 't', 'd', 'h', 'u', 'l', 'c', 'g', 'm', 'o', 'b', 'w', 'f', 'k', 'z', 'p', 'v', 'j', 'y', 'x', 'q']

Verschlüsselter Text