Einfache Chiffren

• Grundbegriffe: Klartext $m$, Schlüssel $k$, Chiffretext $c$ – die drei Grundzutaten jeder Verschlüsselung.
• Schutzziele: Privacy, Authenticity, Integrity, Non-Repudiation, Perfect Forward Secrecy.
• Historische Chiffren: Caesar (26 Schlüssel), Affine (312), Substitution ($26!$), Vigenère (polyalphabetisch), OTP (perfekte Sicherheit).
• Angriffe: Buchstabenhäufigkeitsanalyse, Koinzidenzindex, Bigramme knacken monoalphabetische Chiffren mühelos.
• Klausurfokus: Rechnen mit modularen Verschiebungen, Schlüsselraum bestimmen, Chiffren dechiffrieren.

Grundbegriffe der Verschlüsselung

Ein Verschlüsselungsverfahren transformiert einen Klartext $m$ (message) mit Hilfe eines Schlüssels $k$ (key) in einen Chiffretext $c$ (cipher text):

$c = E_k(m) \qquad m = D_k(c)$

Codieren und Verschlüsseln sind nicht dasselbe: Codieren macht Daten maschinenlesbar (z.B. ASCII, Morse) – jeder kann decodieren. Verschlüsseln benötigt einen geheimen Schlüssel, ohne den keine Rekonstruktion möglich sein soll.

Schutzziele

Caesar-Chiffre

Jeder Buchstabe wird um $k$ Stellen im Alphabet verschoben. Mit $A=0, B=1, \ldots, Z=25$:

$c_i = (m_i + k) \bmod 26 \qquad m_i = (c_i - k) \bmod 26$

Schlüsselraum: nur 26 Möglichkeiten (davon $k=0$ trivial). Brute-Force: in Sekunden knackbar – einfach alle 26 Verschiebungen ausprobieren.

Affine Chiffre

Verallgemeinerung der Caesar-Chiffre: der Schlüssel besteht aus zwei Zahlen $k = (a, b)$:

$c_i = (a \cdot m_i + b) \bmod 26$

Damit die Chiffre umkehrbar ist, muss $a$ zu $26$ teilerfremd sein: $\gcd(a, 26) = 1$. Andernfalls wäre die Abbildung nicht bijektiv.

Schlüsselraum: $\varphi(26) = \varphi(2)\cdot\varphi(13) = 1 \cdot 12 = 12$ gültige $a$-Werte, mal $26$ $b$-Werte $=$ 312 Schlüssel.

Die 12 gültigen $a$-Werte sind: $\{1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25\}$.

Substitutionschiffre (monoalphabetisch)

Jeder Buchstabe wird durch einen beliebigen anderen ersetzt – der Schlüssel ist eine Permutation der 26 Buchstaben.

Schlüsselraum: $26! \approx 4{,}03 \cdot 10^{26}$ – Brute-Force unmöglich.

Aber: Buchstabenhäufigkeit bleibt erhalten! Im Deutschen ist $e \approx 17\%$ der häufigste Buchstabe, $n \approx 10\%$, $i \approx 8\%$. Man ordnet die häufigsten Chiffretext-Zeichen den häufigsten Klartext-Buchstaben zu → in wenigen Minuten geknackt.

Vigenère-Chiffre (polyalphabetisch)

Verwendet ein Schlüsselwort $k = k_0 k_1 \ldots k_{n-1}$, das zyklisch über den Klartext gelegt wird:

$c_i = (m_i + k_{i \bmod n}) \bmod 26$

Gleiche Klartext-Buchstaben werden auf verschiedene Chiffretext-Buchstaben abgebildet → einfache Häufigkeitsanalyse schlägt fehl.

Angriff: Kasiski-Test (Wiederholungen finden) + Friedman-Test (Koinzidenzindex) zur Bestimmung der Schlüssellänge. Danach n Caesar-Chiffren einzeln knacken.

One-Time-Pad (OTP)

Wie Vigenère, aber mit drei strikten Bedingungen:

1. Schlüssel ist echt zufällig.
2. Schlüssel ist mindestens so lang wie der Klartext.
3. Schlüssel wird nur ein einziges Mal verwendet.

Dann ist das OTP nach Shannon informationstheoretisch sicher („perfect secrecy"): Zu jedem Chiffretext existiert für jeden möglichen Klartext genau ein passender Schlüssel – der Angreifer erhält keinerlei Information.

Kryptoanalyse-Werkzeuge

Buchstabenhäufigkeit (deutsch):

Koinzidenzindex $I$: Wahrscheinlichkeit, dass zwei zufällig gewählte Zeichen eines Textes gleich sind:

$I = \dfrac{\sum_{i=A}^{Z} n_i (n_i - 1)}{N (N-1)}$

Beim Vigenère: Chiffretext hat niedrigen $I \approx 0{,}038$. Nach richtiger Zerlegung in Spalten (Schlüssellänge) steigt $I$ jeder Spalte auf $\approx 0{,}076$ → Schlüssellänge gefunden.

Angriffsarten (Attacker Models)

Buchstaben-Tabelle (A=0 … Z=25)

Die brauchst du für jede Rechnung. Zeichne sie ganz oben auf deinen Schmierzettel, dann sparst du dir jedes Mal das Nachdenken.

Merkanker: A=0, M=12, N=13, Z=25. Alles andere zählst du in ±1-Schritten dazu.

1. Cäsar verschlüsseln

Formel: $c_i = (m_i + k) \bmod 26$ mit Schlüssel $k \in \{0,\dots,25\}$.

1. Klartext in Großbuchstaben schreiben, Leerzeichen und Satzzeichen streichen.
2. Jeden Buchstaben mit der Tabelle in eine Zahl übersetzen.
3. Auf jede Zahl den Schlüssel $k$ addieren.
4. Falls das Ergebnis $\geq 26$ ist, ziehe 26 ab (das ist die Modulo-Operation).
5. Zahl zurück in Buchstaben übersetzen — fertig.

Beispiel: Klartext HALLO, Schlüssel $k=3$.

Zahlen: H=7, A=0, L=11, L=11, O=14.

Addieren: $7{+}3{=}10$, $0{+}3{=}3$, $11{+}3{=}14$, $11{+}3{=}14$, $14{+}3{=}17$.

Keine Zahl $\geq 26$, also kein Modulo nötig. Rückübersetzen: 10=K, 3=D, 14=O, 14=O, 17=R.

Chiffrat: KDOOR.

2. Cäsar entschlüsseln

Formel: $m_i = (c_i - k) \bmod 26$. Wenn negativ, addiere 26.

1. Chiffrat in Zahlen übersetzen.
2. Von jeder Zahl den Schlüssel $k$ abziehen.
3. Falls Ergebnis negativ, addiere 26 (Modulo-Trick rückwärts).
4. Zahlen wieder in Buchstaben übersetzen.

Beispiel: Chiffrat KDOOR, Schlüssel $k=3$.

Zahlen: K=10, D=3, O=14, O=14, R=17.

Subtrahieren: $10{-}3{=}7$, $3{-}3{=}0$, $14{-}3{=}11$, $14{-}3{=}11$, $17{-}3{=}14$.

Keine negative Zahl, kein $+26$ nötig. Rückübersetzen: 7=H, 0=A, 11=L, 11=L, 14=O.

Klartext: HALLO.

3. Cäsar Brute-Force-Analyse

Der Schlüsselraum ist winzig: nur 26 mögliche Verschiebungen (davon eine trivial). Alle durchprobieren geht per Hand in wenigen Minuten.

1. Nimm die ersten 4–6 Buchstaben des Chiffrats — mehr brauchst du fast nie.
2. Schreibe eine Tabelle: linke Spalte $k=0,1,2,\dots,25$, rechts die Entschlüsselung mit diesem $k$.
3. Für jede Zeile: ziehe $k$ von jedem Chiffrat-Buchstaben ab (mod 26).
4. Scanne die rechte Spalte nach einem lesbaren deutschen Wort.
5. Sobald ein Wort auftaucht — Treffer. $k$ ablesen.

Beispiel: Chiffrat KDOOR. Zahlen: 10, 3, 14, 14, 17.

$k=1$: 9,2,13,13,16 = JCNNP — Müll.

$k=2$: 8,1,12,12,15 = IBMMP — Müll.

$k=3$: 7,0,11,11,14 = HALLO — Treffer. Schlüssel $k=3$.

4. Häufigkeitsanalyse für Cäsar

Im Deutschen ist E mit Abstand der häufigste Buchstabe (ca. 17 %), gefolgt von N, I, S, R, A, T. Weil Cäsar jeden Buchstaben gleich verschiebt, bleibt dieses Ranking im Chiffrat erhalten — nur eben verschoben.

1. Zähle im Chiffrat, wie oft jeder Buchstabe vorkommt (Strichliste).
2. Finde den häufigsten Chiffrat-Buchstaben $x$.
3. Vermute: $x$ entspricht dem Klartext-E.
4. Berechne $k = (x - \text{E}) \bmod 26 = (x - 4) \bmod 26$.
5. Entschlüssele das ganze Chiffrat mit diesem $k$ und prüfe, ob deutscher Text herauskommt.
6. Wenn nicht: probiere den zweithäufigsten Buchstaben als E, oder als N.

Beispiel: Chiffrat KHOHIRQLHUW GDV WHDP. Buchstabenzählung: H kommt 4× vor, gewinnt klar.

Vermutung: H (=7) im Chiffrat ist E (=4) im Klartext. Also $k = (7 - 4) \bmod 26 = 3$.

Probe: mit $k=3$ entschlüsseln → TELEFONIERT DAS TEAM. Passt. Schlüssel bestätigt: $k=3$.

5. Vigenère verschlüsseln

Formel: $c_i = (m_i + k_{i \bmod \ell}) \bmod 26$, wobei $\ell$ die Länge des Schlüsselworts ist. Jeder Klartext-Buchstabe wird mit dem passenden Buchstaben des zyklisch wiederholten Schlüsselworts verschoben.

1. Schlüsselwort direkt unter den Klartext schreiben, so oft wiederholen bis alle Klartext-Buchstaben ein Schlüssel-Zeichen darunter haben.
2. Beide Zeilen in Zahlen übersetzen.
3. Spaltenweise addieren.
4. Modulo 26 (also $-26$ falls Ergebnis $\geq 26$).
5. Zahlen zurück in Buchstaben — das ist das Chiffrat.

Beispiel: Klartext GEHEIM, Schlüsselwort KEY.

Ausrichtung: G E H E I M / K E Y K E Y.

Zahlen Klartext: 6, 4, 7, 4, 8, 12. Zahlen Schlüssel: 10, 4, 24, 10, 4, 24.

Summen: $6{+}10{=}16$, $4{+}4{=}8$, $7{+}24{=}31 \to 31{-}26{=}5$, $4{+}10{=}14$, $8{+}4{=}12$, $12{+}24{=}36 \to 36{-}26{=}10$.

Ergebnis: 16, 8, 5, 14, 12, 10 = QIFOMK.

6. Vigenère entschlüsseln

Formel: $m_i = (c_i - k_{i \bmod \ell}) \bmod 26$. Falls negativ, $+26$.

1. Schlüsselwort unter das Chiffrat schreiben, zyklisch wiederholen.
2. Beide Zeilen in Zahlen übersetzen.
3. Spaltenweise Chiffrat minus Schlüssel rechnen.
4. Bei negativem Ergebnis $+26$.
5. Zahlen in Buchstaben zurückübersetzen — Klartext ist da.

Beispiel: Chiffrat QIFOMK, Schlüsselwort KEY.

Ausrichtung: Q I F O M K / K E Y K E Y.

Zahlen Chiffrat: 16, 8, 5, 14, 12, 10. Zahlen Schlüssel: 10, 4, 24, 10, 4, 24.

Differenzen: $16{-}10{=}6$, $8{-}4{=}4$, $5{-}24{=}-19 \to -19{+}26{=}7$, $14{-}10{=}4$, $12{-}4{=}8$, $10{-}24{=}-14 \to -14{+}26{=}12$.

Ergebnis: 6, 4, 7, 4, 8, 12 = GEHEIM.