Kryptographie
Die Wissenschaft der Kryptographie befasst sich mit der Kunst, einen Text so zu verändern (zu verschlüsseln), dass ihn jeder, der möchte, sehen kann, aber nur der bestimmte Empfänger auch verstehen (also entschlüsseln) kann.
Im folgenden Diagramm siehst du den schematischen Ablauf einer typischen kryptographischen Anwendung. Ein Text, der geheim gehalten werden soll (Klartext genannt, weil es sich um einen lesbaren, z.B. deutschen Text handelt), soll an jemand anderes verschickt werden, ohne dass ein Fremder den Text lesen kann.
Dazu wird der Klartext mittels eines Schlüssels verschlüsselt und das dadurch entstandene Chiffrat (oder Geheimtext) an den Empfänger geschickt. Die so entstandene Verbindung wird als 'sicher' bezeichnet, was bedeutet dass niemand unbefugtes die Nachricht lesen kann. Mittels desselben Schlüssels kann der Empfänger das Chiffrat wieder in Klartext umwandeln (entschlüsseln).
Wichtige Begriffe
- Klartext: Der lesbare, ursprüngliche Text
- Chiffrat oder Geheimtext: Der verschlüsselte Text
- Schlüssel: Die Information, die zum Ver- und Entschlüsseln nötig ist
- Verschlüsseln: Klartext → Geheimtext
- Entschlüsseln: Geheimtext → Klartext
Zu diesem Zweck gibt es viele verschiedene Methoden. Wir betrachten zuerst symmetrische Verschlüsselungen. »Symmetrisch« bedeutet in diesem Zusammenhang, dass der Empfänger denselben Schlüssel verwendet wie der Sender.
Rotationschiffre (Caesar-Chiffre)
Nach der Überlieferung des römischen Schriftstellers Sueton verwendete Julius Cäsar ein Verschlüsselungsverfahren, um seinen Feldherrn im Krieg Nachrichten zu schicken. Er verschob dazu alle Buchstaben im Alphabet um drei Zeichen.
- Aus A wurde D
- Aus B wurde E
- Aus C wurde F
- ...
Am Ende des Alphabets fing er wieder vorne an: - Aus X wurde A - Aus Y wurde B - Aus Z wurde C
Beispiel: Caesar-Verschlüsselung
Wenn wir das Wort HALLO mit Caesars Methode (Verschiebung um 3) verschlüsseln:
Klartext: H A L L O
↓ ↓ ↓ ↓ ↓
Geheimtext: K D O O R
Aufgaben: Von Hand verschlüsseln
Aufgabe 1: Erste Entschlüsselung
Eine Nachricht von Julius Cäsar an seine Truppen könnte gelautet haben:
DQJULII
Entschlüssle diese Nachricht von Hand. Bedenke, dass Caesar sein Alphabet um 3 Stellen verschoben hat.
Lösung
D → A (3 zurück)
Q → N
J → G
U → R
L → I
I → F
I → F
Lösung: ANGRIFF
Aufgabe 2: Allgemeine Caesar-Chiffre
Die Caesar-Chiffre kann man verallgemeinern, indem man nicht nur um 3, sondern um eine beliebige Anzahl Stellen verschiebt.
a) Wie viele verschiedene Schlüssel gibt es bei einer allgemeinen Caesar-Chiffre?
Hinweise:
- Das Alphabet hat 26 Buchstaben
- Ist eine Verschiebung um 27 sinnvoll? Oder gibt es eine kleinere Zahl, die dasselbe bewirkt?
- Gibt es eine Verschiebung, die keine sinnvolle Verschlüsselung darstellt?
b) Hältst du das System für sicher? Wenn du weisst, dass ein Text mit der Caesar-Chiffre verschlüsselt ist, wie würdest du vorgehen um einen Geheimtext zu entschlüsseln, auch wenn du den Schlüssel nicht kennst?
Lösung
a) Es gibt 25 verschiedene Schlüssel (Verschiebung um 1 bis 25).
- Verschiebung um 0 ist keine Verschlüsselung
- Verschiebung um 26 ist gleich wie 0 (einmal rum)
- Verschiebung um 27 ist gleich wie 1
b) Das System ist nicht sicher! Man kann einfach alle 25 Möglichkeiten durchprobieren (Brute-Force-Angriff). Das dauert nur wenige Minuten von Hand.
Aufgabe 3: Geheimtext knacken
Du hast folgenden Geheimtext abgefangen. Du vermutest stark, dass er mit der Caesar-Chiffre verschlüsselt wurde:
GRRK CKMK LAKNXKT TGIN XUS
Versuche den Klartext zu bestimmen, indem du verschiedene Verschiebungen ausprobierst. Welcher Schlüssel wurde verwendet?
Tipp: Beginne mit kleinen Verschiebungen (1, 2, 3...) und prüfe, ob ein sinnvoller deutscher Text entsteht.
Programmierung: Caesar-Chiffre
Nun wollen wir die Caesar-Chiffre in Python programmieren. Unser Ziel sind zwei Funktionen:
verschluesseln(klartext, schluessel)entschluesseln(geheimtext, schluessel)
ASCII-Tabelle
Um Buchstaben zu verschieben, nutzen wir die ASCII-Codierung. In dieser Tabelle ist jedem Zeichen eine Zahl zugeordnet:
- A hat den Code 65
- B hat den Code 66
- C hat den Code 67
- ...
- Z hat den Code 90
Du findest hier die vollständige ASCII-Tabelle als Referenz. In Python können wir mit zwei Funktionen auf diese Tabelle zugreifen:
ord(zeichen)→ gibt die Zahl für ein Zeichen zurückchr(zahl)→ gibt das Zeichen für eine Zahl zurück
Beispiel: ord() und chr()
Aufgaben: Verschlüsselungsfunktion
Einzelne Zeichen verschieben
Aufgabe 4: Einzelnes Zeichen verschieben
Schreibe ein Programm, welches ein einzelnes Zeichen um eine Stelle im Alphabet verschiebt.
Vorgehen:
- Hole die ASCII-Nummer vom Zeichen mit
ord() - Addiere 1 zur Nummer
- Wandle die neue Nummer zurück in ein Zeichen mit
chr() - Gib das verschobene Zeichen aus
Teste dein Programm mit dem Buchstaben 'A' → sollte 'B' ergeben.
# Tests (Groß-/Kleinschreibung wird nicht beachtet)(Ctrl+I)
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
(Esc)
Aufgabe 5: Variable Verschiebung
Erweitere dein Programm so, dass du ein Zeichen um eine variable Anzahl Stellen verschieben kannst.
Definiere dazu eine Variable schluessel und verwende sie für die Verschiebung.
Teste:
- 'A' mit Schlüssel 3 → 'D'
- 'H' mit Schlüssel 3 → 'K'
# Tests (Groß-/Kleinschreibung wird nicht beachtet)(Ctrl+I)
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
(Esc)
Aufgabe 6: Alphabet-Ende behandeln
Problem: Was passiert, wenn wir 'Z' um 3 Stellen verschieben?
ord('Z') = 90
90 + 3 = 93
chr(93) = ']' ← Das ist kein Buchstabe!
Wir müssen am Alphabet-Ende wieder bei 'A' anfangen.
Lösung: Wir überprüfen, ob wir über das 'Z' hinausgehen und ziehen die Länge vom Alphabet ab:
neue_nummer = ascii_nummer + schluessel
# Falls wir über 'Z' (90) hinaus gehen:
if neue_nummer > ord('Z'):
neue_nummer = neue_nummer - 26 # 26 Buchstaben zurück
Noch besser mit Modulo:
# Position im Alphabet (0-25)
position = ascii_nummer - ord('A')
# Verschieben mit Wrap-around
neue_position = (position + schluessel) % 26
# Zurück zu ASCII
neue_nummer = neue_position + ord('A')
Implementiere die Lösung und teste:
- 'X' mit Schlüssel 3 → 'A'
- 'Z' mit Schlüssel 3 → 'C'
# Tests (Groß-/Kleinschreibung wird nicht beachtet)(Ctrl+I)
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
(Esc)
Verschlüsselungsfunktion
Aufgabe 7: Verschlüsselungsfunktion
Jetzt haben wir alle Bausteine! Schreibe eine Funktion verschluesseln, die einen kompletten Text verschlüsselt.
Signatur:
def verschluesseln(klartext, schluessel):
# ...
return geheimtext
Vorgehen:
- Erstelle einen leeren String
geheimtext = "" - Durchlaufe jeden Buchstaben im
klartext(mitfor) - Verschiebe jeden Buchstaben wie in Aufgabe 6
- Füge den verschobenen Buchstaben zu
geheimtexthinzu - Gib
geheimtextzurück
Teste:
print(verschluesseln("HALLO", 3)) # → "KDOOR"
print(verschluesseln("ANGRIFF", 3)) # → "DQJULII"
# Tests (Groß-/Kleinschreibung wird nicht beachtet)(Ctrl+I)
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
(Esc)
Entschlüsselungsfunktion
Aufgabe 8: Entschlüsselungsfunktion
Schreibe nun eine Funktion entschluesseln, die einen Geheimtext zurück in Klartext verwandelt.
Hinweis: Entschlüsseln ist wie Verschlüsseln, nur rückwärts. Statt den Schlüssel zu addieren, musst du ihn...?
Teste:
print(entschluesseln("DQJULII", 3)) # → "ANGRIFF"
print(entschluesseln("KDOOR", 3)) # → "HALLO"
# Wichtiger Test:
text = "GEHEIM"
verschluesselt = verschluesseln(text, 5)
wieder_klar = entschluesseln(verschluesselt, 5)
print(text == wieder_klar) # → True
# Tests (Groß-/Kleinschreibung wird nicht beachtet)(Ctrl+I)
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
(Esc)
Substitutionschiffre
Angriff auf die Substitutionschiffre
Wir versetzen uns nun in die Schuhe eines Angreifers, welcher plant einen Geheimtext zu entschlüsseln, aber ohne Kenntnisse vom Schlüssel! Ist dies überhaupt möglich?
Dazu könnte der Angreifer doch einfach alle möglichen Schlüssel ausprobieren...
Entschlüsselungszeit
Können wir überhaupt schnell genug die Schlüssel durchprobieren, damit wir in akzeptabler Zeit ein Geheimtext ohne bekannten Schlüssel entschlüsseln können?
Dazu messen wir die Zeit, die der Rechner benötigt, um einen Schlüssel auszuprobieren. In der Bibliothek von Python finden wir dazu eine passende Funktion:
import time
time.perf_counter()
Mit dieser Funktion können wir nun messen, wie lange unsere Entschlüsselungsfunktion braucht pro Schlüssel.
Aufgabe 9: Substitutionsverschlüsselung Dauer
Wie können wir mit der Zeitfunktion nun eine Zeitdauer messen? Messe, wie viel Zeit die Entschlüsselungsfunktion benötigt für den Geheimtext IRHHO.
# Tests (Groß-/Kleinschreibung wird nicht beachtet)(Ctrl+I)
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
(Esc)
Brute-Force-Angriff auf die Substitutionschiffre
Unser Ziel ist es nun den folgenden Geheimtext zu entschlüsseln, ohne Kenntnis des Schlüssels! In diesem Text treten nur die Buchstaben EIKLNORST plus Leerzeichen auf. Wir nehmen nun an, dass die Leerzeichen nicht verschlüsselt worden sind.
ELOI RITLS KNOITK ELSKLI LOEKLL
Wir wollen versuchen diesen Geheimtext mit der Methode der "roher Gewalt" zu brechen. Dazu müssen wir alle Möglichkeiten durchprobieren.
Aufgabe: Substitutionsverschlüsselung Angriff
Schreibe ein Programm um alle möglichen Schlüssel zu probieren.
# Tests (Groß-/Kleinschreibung wird nicht beachtet)(Ctrl+I)
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
(Esc)
Häufigkeitsanalyse
Wir wissen bereits, dass im allgemeinenen ein Brute-Force-Angriff auf die reguläre Substitutionsverschlüsselung nicht in nützlicher Zeit durchführbar ist. Wir können sie aber einfach angreifen, in dem wir zusätzliche (unversteckte) Informationen aus dem Geheimtext in den Angriff miteinbeziehen: die Buchstabenhäufigkeit. Dazu führt man eine Häufigkeitsanalyse durch. Um dies einfacher zu Programmieren, wollen wir zuerst eine weitere Datenstruktur kennenlernen: das "Wörterbuch" (dictionary) bzw. das assoziative Array.
assoziatives Array/Wörterbuch
Eine praktische neue Datenstruktur ist das assoziative Array. Darin können Elemente gespeichert werden, ähnlich wie bei einem normalen Array. Im normalen Array, wird über eine Ordnung auf ein Element zugegriffen, also über den Index, welcher z.B. auf das erste, zweite, dritte, i-te Element zugreift. Der Index ist dabei eine natürliche Zahl ≥ 0. Bei einem assoziativen Array wird nicht über einen Index auf ein Feld zugegriffen, sondern über einen Schlüssel, z.B. einen Buchstaben oder eine Zeichenkette. In Python können wir ein leeres assoziatives Array mit den geschweiften Klammern definieren.
wörterbuch = {}
wörterbuch["meinSchlüssel"] = 15
meinSchlüssel und Wert 15.
| Schlüssel | Wert |
|---|---|
| meinSchlüssel | 15 |
Ein weiteres Element kann in gleicher Weise hinzugefügt werden.
wörterbuch["andererSchlüssel"] = 99
| Schlüssel | Wert |
|---|---|
| meinSchlüssel | 15 |
| andererSchlüssel | 99 |
Um auf ein Element zuzugreifen, können wir den Schlüssel analog zum Index bei einem normalen Array verwenden:
print(wörterbuch["meinSchlüssel"])
Um über ein assoziatives Array zu iterieren, d.h. mit einer Schleife auf alle Elemente zugreifen, können wir die for .. in ..-Schleife verwenden.
for schlüssel in wörterbuch:
wert = wörterbuch[schlüssel]
print(f"Schlüssel ist: {schlüssel} und Wert ist: {wert}")
Beispiel: assoziatives Array/ Wörterbuch
# Tests (Groß-/Kleinschreibung wird nicht beachtet)(Ctrl+I)
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
(Esc)
Wörterbücher
Aufgabe: Wörterbücher
Erstelle ein neues und leeres assoziatives Array. Füge drei Elemente hinzu, mit den Schlüssel laenge, breite, kosten und frei gewählten Werten. Gib den Wert für den Schlüssel breite aus Gib alle Werte aus in dem du die for .. in ..-Schleife verwendest
# Tests (Groß-/Kleinschreibung wird nicht beachtet)(Ctrl+I)
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
(Esc)
Häufigkeitsanalyse
Aufgabe: Häufigkeitsanalyse
Mithilfe von assoziativen Arrays kannst du nun eine Häufigkeitsanalyse durchführen. Analysiere den nachfolgenden Geheimtext.
Wenn man überprüfen möchte, ob ein bestimmter Eintrag in einem assoziativen Array schon vorhanden ist, können wir das in Schlüsselwort verwenden:
a = { }
a["land"] = "Schweiz"
if "land" in a:
print("Wert zu Schlüssel land ist vorhanden")
if "ort" in a:
print("Wert zu Schlüssel ort ist vorhanden")
else:
print("Wert zu Schlüssel ort ist nicht vorhanden")
# Tests (Groß-/Kleinschreibung wird nicht beachtet)(Ctrl+I)
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
(Esc)
Aufgabe: Häufigkeitsanalyse Visualisieren
Kopiere dein Programm zur Häufigkeitsanalyse und stelle nun die Ergebnisse als Balkendiagramm dar.
Die Funktion für das Balkendiagramm plt.bar verlangt zwei Parameter: der erste für die x-Achse und der zweite für die y-Achse. Wir brauchen dazu vom assoziativen Array einmal alle Schlüssel als Array und einmal alle Werte als Array, das geht folgendermassen:
schlüssel = hf.keys()
werte = hf.values()
print(f"Alle SchlüsseL: {schlüssel}")
print(f"Alle Werte: {werte}")
Zusatz: Ignoriere die Sonderzeichen (Leerzeichen, Komma, etc.)
Deine Abbildung
# Tests (Groß-/Kleinschreibung wird nicht beachtet)(Ctrl+I)
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
(Esc)
# Tests(Groß-/Kleinschreibung wird nicht beachtet)(Ctrl+I)
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
(Esc)