Caesar-Verschlüsselung [KSR Wiki]

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
## Caesar-Verschlüsselung

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

{{ :gf_informatik:caesar.png?nolink&400 |}}
#### 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:

<code python>
s = "Hallo KSR"
for buchstabe in s:
    print(buchstabe)
</code>

Einen String in Grossbuchstaben umwandeln:

<code python>
print("Hallo KSR".upper())
>>> HALLO KSR
</code>

Alle Grossbuchstaben können in `string.ascii_uppercase` abgefragt werden. Mit [[https://docs.python.org/3/library/stdtypes.html?highlight=upper#str.find|str.find()]] können wir den Index (oder -1) finden:

<code python>
import string

for buchstabe in "HALLO":
    print(string.ascii_uppercase.find(buchstabe))

>>>
7
0
11
11
14
</code>

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:
<code python>
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
</code>

<nodisp 1>
++++Lösung:|
<code python caesar.py>

def caesar(klartext, n):
    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 .,!?'
    decrypted_text = ''
    # Jeden Buchstaben b im Klartext durchgehen. for-Schleife
    for b in klartext:
    # Mit jedem Buchstaben:
    #   - Position im Alphabet finden alphabet.find
        p = alphabet.find(b)
    #   - Position um n verschieben (Addition oder Subtraktion)
        p = p + n
    #   - Resultat eingrenzen auf 0...len(alphabet)
        p = p % len(alphabet)
        decrypted_text = decrypted_text + alphabet[p]
    return decrypted_text

key = 17
encrypted = caesar("my little secret", key)
print(encrypted)
print(caesar(encrypted, -key))
</code>
++++
</nodisp>

#### 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|
Probiere alle möglichen Verschiebungen aus. Am einfachsten geht dies mit einer ...!
++++


## Monoalphabetische Verschlüsslung

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**.


### Aufgaben B

#### Aufgabe B1

   1. Ist die Caesar-Verschlüsselung auch eine monoalphabetische Verschlüsselung?
   1. 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.
   1. Wie viele Möglichkeiten gibt es für die monoalphabtische Verschlüsselung? (wieder mit $26$ Buchstaben).
   1. Wie schätzt du die Sicherheit der monoalphabtischen Verschlüsselung ein? Welche Möglichkeiten gibt es, um eine damit verschlüsselte Nachricht zu entziffern?
   1. 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?

<nodisp 1>
++++Lösung|
Für den ersten Buchstaben A können wir unter 26 Möglichkeiten auswählen, um ihn umzuplatzieren. Für B bleiben noch 25, für C 24 Möglichkeiten, etc.

Es gibt also $26\cdot25\cdot...\cdot2\cdot1 = 26! \approx 4\cdot10^{26}$ Möglichkeiten, die Buchstaben umzusortieren.
++++
</nodisp>
#### 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|

   1. Gehe Buchstaben um Buchstaben durch die Nachricht.
   1. Ermittle die Position von diesem Buchstaben im durchmischten Alphabet (Schlüssel).
   1. Der Klartext-Buchstabe findet sich an dieser Position im normalen Alphabet.

++++

<nodisp 1>
++++Mehr Tipps|
<code python>
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))
</code>
++++
</nodisp>

<nodisp 1>
++++Lösung|
<code python>
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))
</code>
++++
</nodisp>

## Häufigkeitsanalyse

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:|
  * Klartext-Sprache muss bekannt sein oder vermutet werden.
  * Chiffrat muss genügend lang sein.
++++

### Aufgaben C
#### Aufgabe C1: Monoalphabetische Substitution knacken mit Häufigkeitsanalyse.

Versuche, das [[https://studio.code.org/s/frequency_analysis/lessons/1/levels/1|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: [[https://de.wikipedia.org/wiki/Liste_der_häufigsten_Wörter_der_deutschen_Sprache|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|
<code python>
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.)'
</code>
++++

++++Tipps|
Für jeden Buchstaben musst du irgendwo dessen Anzahl speichern. Eine Möglichkeit ist, eine Liste mit Zahlen zu verwenden. Die erste Zahl steht für die Anzahl "A", die zweite für die Anzahl "B" usw. 

Den Index für jeden Buchstaben könnte man zum Beispiel mit `string.ascii_lowercase.find(letter)` berechnen - `find()` gibt eine negative Zahl zurück, falls `letter` nicht gefunden wird (zum Beispiel Satzzeichen).
++++

++++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%
```
++++
<nodisp 1>
++++Python Lösung|
<code python>
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))
</code>
++++
</nodisp>


##### 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 [[https://www.gutenberg.org|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:

<code python>
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
</code>

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.

<nodisp 1>
++++Lösung mit Gutenberg|
<code python>
# 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))
</code>
++++
</nodisp>

#### 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:
<code python>
['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']
</code>

++++Verschlüsselter Text|
rx jlw rxn wjxnzvc qr zqtjnbvxivt ljrrvx 4 isxvl nbyzm wsxsjo, tslm jlw tsx lyxrsz mj nvql, nvhx nbyzm nytsx. lqvrslw isxv sjo wqv qwvv tvuyrrvl, nqv uyllbvl nqkh ql vqlv rvxuijxwqtv jlw tvhvqrlqngyzzv tvnkhqkhbv gvxnbxqkuvl, wvll rqb nyzkhvr jlnqll iyzzbvl nqv lqkhbn mj bjl hsevl. rx wjxnzvc isx wqxvubyx vqlvx oqxrs lsrvln txjllqltn, wqv eyhxrsnkhqlvl hvxnbvzzbv. vx isx txynn jlw ejzzqt jlw hsbbv osnb uvqlvl hszn, wsojx sevx vqlvl nvhx txynnvl nkhljxxesxb. rxn wjxnzvc isx wjll jlw ezylw jlw evnsnn wyddvzb ny gqvz hszn, iqv lybivlwqt tvivnvl isxv, isn szzvxwqltn nvhx ljbmzqkh isx, wvll ny uyllbv nqv wvl hszn jevx wvl tsxbvlmsjl xvkuvl jlw mj wvl lskhesxl hqljevxndshvl. wqv wjxnzvcn hsbbvl vqlvl uzvqlvl nyhl lsrvln wjwzvc jlw ql qhxvl sjtvl tse vn lqxtvlwiy vqlvl dxskhbqtvxvl fjltvl. wqv wjxnzvcn evnsnnvl szzvn, isn nqv iyzzbvl, wykh nqv hsbbvl sjkh vql tvhvqrlqn, jlw wsnn vn fvrslw sjowvkuvl uyllbv, isx qhxv txynnbv nyxtv. vqloskh jlvxbxstzqkh isxv vn, ivll wqv nskhv rqb wvl dybbvxn hvxsjnuyrrvl ijxwv. rxn dybbvx isx wqv nkhivnbvx gyl rxn wjxnzvc; wykh wqv evqwvl hsbbvl nqkh nkhyl nvqb vbzqkhvl fshxvl lqkhb rvhx tvnvhvl. rxn wjxnzvc evhsjdbvbv nytsx, wsnn nqv tsx uvqlv nkhivnbvx hsbbv, wvll wqvnv jlw wvxvl lqkhbnljbm gyl vqlvr rsll isxvl ny jlwjxnzvchsob, iqv rsl vn nqkh ljx wvluvl uyllbv. wqv wjxnzvcn nkhsjwvxbvl evqr tvwsluvl wsxsl, isn wqv lskhesxl nstvl ijxwvl, nyzzbvl wqv dybbvxn vqlvn bstvn ql qhxvx nbxsnnv sjouxvjmvl. wqv wjxnzvcn ijnnbvl, wsnn sjkh wqv dybbvxn vqlvl uzvqlvl nyhl hsbbvl, wykh wvl hsbbvl nqv lqv tvnvhvl. sjkh wqvnvx fjltv isx vql tjbvx txjlw, nqkh gyl wvl dybbvxn ovxlmjhszbvl; rqb vqlvr nyzkhvl uqlw nyzzbv qhx wjwzvc lqkhb ql evxjhxjlt uyrrvl.

++++