Auf einen Blick
- Kryptographie-Klausur = Rechnen + Verstehen. Beide Teile werden bewertet, aber die Rechenteile geben oft mehr Punkte pro Aufgabe.
- Rechenschwerpunkte: Affine Chiffren, RSA-Schlüsselgenerierung + Ver-/Entschlüsselung, Diffie-Hellman, ggT + erweiterter Euklid, modulare Inverse.
- Verstehens-Schwerpunkte: Symmetrisch vs. asymmetrisch, hybride Verfahren, Hash-Funktionen für Signaturen, MITM + PKI, Sicherheitsstatus von MD5/SHA-1/SHA-256.
- Übungsaufgaben aus dem Skript: Substitutionsanalyse, Schablonen-Kryptogramm, Koinzidenzindex, Komprimierung + Verschlüsselung, affine Chiffren, One-Time-Pad.
- Faustregel: Wer alle Übungen aus dem Skript rechnen kann, hat die Klausur zur Hälfte in der Tasche.
Kernkonzepte
Übungen aus dem Skript im Überblick
| Übung | Thema | Methode |
|---|---|---|
| 1 | Substitutionschiffre knacken | Häufigkeitsanalyse (E, N, I dominant im Deutschen) |
| 2 | Schablonen-Kryptogramm | 8×6-Raster, Brute-Force-Aufwand $2^{48}$ Muster |
| 3 | Koinzidenzindex | $IC = \sum \frac{n_i(n_i-1)}{N(N-1)}$, deutsch $\approx 0{,}076$ |
| 4 | Verschlüsselung + Komprimierung | Erst komprimieren, dann verschlüsseln (Reihenfolge!) |
| 5 | Affine Chiffre $k=(a,b)$ | $c = (am+b) \bmod 26$, $m = a^{-1}(c-b) \bmod 26$ |
| 6–8 | One-Time-Pad | XOR mit Zufallsschlüssel, perfekte Sicherheit |
Klausurrelevante Vorlesungs-Themen
- RSA-Rechnungen: $n=pq$, $\varphi(n)=(p-1)(q-1)$, $d=e^{-1} \bmod \varphi(n)$, $c=m^e \bmod n$, $m=c^d \bmod n$.
- Diffie-Hellman: Alice $A=g^a \bmod p$, Bob $B=g^b \bmod p$, gemeinsamer Schlüssel $K=B^a=A^b \bmod p$.
- Hashkollisionen: Geburtstagsangriff senkt Sicherheit von $2^n$ auf $2^{n/2}$.
- Signatur-Verifikation: Bei RSA-Signatur $s=H(m)^d \bmod n$, Verifikation $s^e \equiv H(m) \bmod n$.
- Modulare Arithmetik: Erweiterter Euklid für multiplikative Inverse ist Grundwerkzeug.
Formelsammlung für die Klausur
- Caesar: $c = (m+k) \bmod 26$, $m = (c-k) \bmod 26$
- Affin: $c = (am+b) \bmod 26$, Bedingung $\gcd(a,26)=1$
- Affin invers: $m = a^{-1}(c-b) \bmod 26$
- OTP: $c_i = m_i \oplus k_i$, mit $|k| \geq |m|$ und $k$ zufällig, einmalig
- RSA: $d \cdot e \equiv 1 \pmod{\varphi(n)}$
- DH-Schlüssel: $K = g^{ab} \bmod p$
- Geburtstag: Kollision bei $\approx \sqrt{2^n} = 2^{n/2}$ Versuchen
Merksätze
🧮 Rechenaufgaben mit Lösung
Klick auf eine Aufgabe, um den vollständigen Lösungsweg zu sehen.
Aufgabe 1 — Affine Chiffre entschlüsseln (Übung 5b)
n c n f z. Bestimme den Klartext.
Lösung
Schritt 1: Multiplikative Inverse von $a=9$ modulo 26 bestimmen.
Suche $a^{-1}$ mit $9 \cdot a^{-1} \equiv 1 \pmod{26}$.
Probieren: $9 \cdot 3 = 27 = 26+1 \equiv 1 \pmod{26}$. Also $a^{-1} = 3$.
Schritt 2: Entschlüsselungsformel aufstellen.
$m = a^{-1}(c-b) \bmod 26 = 3 \cdot (c - 13) \bmod 26$
Schritt 3: Buchstaben-zu-Zahl-Zuordnung ($a=0, b=1, \dots, z=25$).
| Chiffre | c (Zahl) | c − 13 | 3·(c−13) | mod 26 | Klartext |
|---|---|---|---|---|---|
| n | 13 | 0 | 0 | 0 | a |
| c | 2 | −11 ≡ 15 | 45 | 19 | t |
| n | 13 | 0 | 0 | 0 | a |
| f | 5 | −8 ≡ 18 | 54 | 2 | c |
| z | 25 | 12 | 36 | 10 | k |
Klartext: attack
Aufgabe 2 — Caesar-Chiffre mit unbekanntem Schlüssel
KHOOR (Caesar-verschlüsselt). Bestimme den Klartext ohne Kenntnis des Schlüssels.
Lösung
Vorgehen: Brute-Force über alle 25 möglichen Verschiebungen $k=1..25$.
Formel: $m_i = (c_i - k) \bmod 26$
| k | Ergebnis | Sinnvoll? |
|---|---|---|
| 1 | JGNNQ | nein |
| 2 | IFMMP | nein |
| 3 | HELLO | JA |
| 4 | GDKKN | nein |
Bei $k=3$ ergibt sich das englische Wort HELLO — das ist der Klartext.
Klartext: HELLO (mit k = 3)
Aufgabe 3 — RSA komplett durchrechnen
Schritt 1 — Modul n berechnen
$n = p \cdot q = 5 \cdot 11 = 55$
Schritt 2 — Eulersche Funktion φ(n)
$\varphi(n) = (p-1)(q-1) = 4 \cdot 10 = 40$
Schritt 3 — Prüfen ob e gültig ist
$\gcd(e, \varphi(n)) = \gcd(3, 40) = 1$ ✓
Schritt 4 — Privaten Schlüssel d berechnen
Suche $d$ mit $3d \equiv 1 \pmod{40}$.
Probieren (oder erweiterter Euklid): $3 \cdot 27 = 81 = 2 \cdot 40 + 1$, also $81 \equiv 1 \pmod{40}$.
$\Rightarrow d = 27$
Schritt 5 — Nachricht m = 4 verschlüsseln
$c = m^e \bmod n = 4^3 \bmod 55 = 64 \bmod 55 = 9$
Schritt 6 — Probe: Entschlüsseln
$m = c^d \bmod n = 9^{27} \bmod 55$
Schnelle Rechnung mit Square-and-Multiply: $9^2=81\equiv 26$, $9^4\equiv 26^2=676\equiv 16$, $9^8\equiv 16^2=256\equiv 36$, $9^{16}\equiv 36^2=1296\equiv 31$.
$27 = 16+8+2+1$: $9^{27} \equiv 31 \cdot 36 \cdot 26 \cdot 9 \bmod 55$
$31 \cdot 36 = 1116 \equiv 16$, $16 \cdot 26 = 416 \equiv 31$, $31 \cdot 9 = 279 \equiv 4$ ✓
Öffentlicher Schlüssel: (e=3, n=55) · Privater Schlüssel: d=27 · Chiffretext: c=9
Aufgabe 4 — Diffie-Hellman-Schlüsselaustausch
Schritt 1 — Alice sendet A
$A = g^a \bmod p = 3^4 \bmod 17 = 81 \bmod 17$
$81 = 4 \cdot 17 + 13 \Rightarrow A = 13$
Schritt 2 — Bob sendet B
$B = g^b \bmod p = 3^6 \bmod 17 = 729 \bmod 17$
$3^2 = 9$, $3^4 = 81 \equiv 13$, $3^6 = 3^4 \cdot 3^2 = 13 \cdot 9 = 117 \equiv 117 - 6\cdot 17 = 117-102 = 15$
$B = 15$
Schritt 3 — Alice berechnet K
$K = B^a \bmod p = 15^4 \bmod 17$
$15 \equiv -2 \pmod{17}$, also $15^4 \equiv (-2)^4 = 16 \bmod 17$
$K = 16$
Schritt 4 — Bob berechnet K (Probe)
$K = A^b \bmod p = 13^6 \bmod 17$
$13 \equiv -4$, $13^2 \equiv 16 \equiv -1$, $13^6 = (13^2)^3 \equiv (-1)^3 = -1 \equiv 16$ ✓
Gemeinsamer Schlüssel: K = 16
Aufgabe 5 — Geburtstagsangriff auf 32-Bit-Hash
Lösung
Regel: Bei einem Hash mit $n$ Bit findet der Geburtstagsangriff mit hoher Wahrscheinlichkeit eine Kollision nach $\approx 2^{n/2}$ Versuchen.
Hier: $n = 32$, also $2^{32/2} = 2^{16}$.
$2^{16} = 65\,536$
Zum Vergleich — Preimage-Angriff
Ein Preimage-Angriff (finde $x$ mit $H(x) = h$) benötigt $2^{32} \approx 4{,}3$ Mrd. Versuche — also $2^{16}$-mal so viele.
≈ 2^16 = 65.536 Nachrichten
Aufgabe 6 — Zweifache affine Chiffre (Übung 5d)
Schritt 1 — Erste Chiffre
$c_1 = (a_1 m + b_1) \bmod 26$
Schritt 2 — Zweite Chiffre auf c₁ angewendet
$c_2 = (a_2 c_1 + b_2) \bmod 26 = a_2 (a_1 m + b_1) + b_2 \bmod 26$
$c_2 = (a_1 a_2) \, m + (a_2 b_1 + b_2) \bmod 26$
Schritt 3 — Struktur erkennen
Setze $A = a_1 a_2 \bmod 26$ und $B = a_2 b_1 + b_2 \bmod 26$. Dann:
$c_2 = (A m + B) \bmod 26$
Das ist wieder eine affine Chiffre mit Schlüssel $(A, B)$.
Konsequenz für die Sicherheit
Die Verkettung erhöht die Schlüsselvielfalt nicht. Der Schlüsselraum einer einfachen affinen Chiffre umfasst $\varphi(26) \cdot 26 = 12 \cdot 26 = 312$ Schlüssel — die zweifache Anwendung bleibt in derselben Menge.
Keine Sicherheitserhöhung: doppelt affin ≡ einfach affin
Aufgabe 7 — OTP-Analyse ohne Schlüssel
xzttreef aus einem One-Time-Pad. Der Schlüssel ist unbekannt. Was kannst du über den Klartext folgern?
Analyse
Beim OTP gilt: $c_i = m_i \oplus k_i$ (bzw. bei Buchstaben: $c_i = (m_i + k_i) \bmod 26$).
Zu jedem beliebigen Klartext $m'$ derselben Länge existiert ein passender Schlüssel $k' = c \oplus m'$, der zu diesem Klartext führt.
Konkret
Bei 8 Zeichen sind theoretisch $26^8 \approx 2{,}09 \cdot 10^{11}$ verschiedene Klartexte möglich — jeder davon ist gleich wahrscheinlich, solange der Schlüssel unbekannt ist. Ohne zusätzliche Information ist es unmöglich zu unterscheiden, ob der Klartext ATTACKAT, URLAUB12 oder KLAUSURT ist.
Kernpunkt
Genau darin liegt die informationstheoretische Sicherheit des OTP nach Shannon: Der Chiffretext liefert null Information über den Klartext, weil jede Deutung gleich plausibel ist.
Ohne Schlüssel: KEINE Aussage über Klartext möglich → perfekte Sicherheit
Aufgabe 8 — Schablonen-Brute-Force (Übung 2)
Schritt 1 — Anzahl der Muster
Jede der 48 Zellen hat 2 Zustände, also $2^{48}$ Muster.
$2^{48} = 281\,474\,976\,710\,656 \approx 2{,}81 \cdot 10^{14}$
Schritt 2 — Realistischer Aufwand
Ein moderner Rechner schafft $\approx 10^9$ Prüfungen pro Sekunde:
$\frac{2{,}81 \cdot 10^{14}}{10^9} \approx 2{,}81 \cdot 10^5 \text{ s} \approx 78 \text{ Stunden}$
Aber
Klassische Schablonen (Fleissner-Rotoren) haben zusätzliche Restriktionen (z.B. genau 12 Löcher, keine Überlappung bei Rotation), die den Suchraum drastisch reduzieren.
Brute-Force-Aufwand: 2^48 ≈ 2,81 · 10^14 Muster
Übungsfragen
F1 Nenne 3 klassische Chiffren und ihre Schwächen.
- Caesar-Chiffre: Nur 25 mögliche Schlüssel — Brute-Force in Sekunden. Zusätzlich anfällig für Häufigkeitsanalyse.
- Vigenère-Chiffre: Polyalphabetisch, aber der Kasiski-Test findet die Schlüssellänge, dann zerfällt die Chiffre in mehrere Caesar-Chiffren.
- Monoalphabetische Substitution: Enormer Schlüsselraum ($26! \approx 4 \cdot 10^{26}$), aber trivial per Häufigkeitsanalyse zu brechen (E, N, I, R, S dominant im Deutschen).
F2 Wie unterscheiden sich symmetrische und asymmetrische Verfahren?
- Symmetrisch (AES, DES, ChaCha20): Sender und Empfänger nutzen denselben geheimen Schlüssel. Schnell, aber Schlüsselaustausch ist das Problem.
- Asymmetrisch (RSA, ECC, DH): Öffentlicher Schlüssel zum Verschlüsseln, privater Schlüssel zum Entschlüsseln. Langsam, löst aber das Schlüsselaustausch-Problem.
- Faustregel: Symmetrisch ist ~1000× schneller als asymmetrisch. Deshalb kombiniert man beide in hybriden Verfahren.
F3 Was ist ein hybrides Verfahren?
- Sender erzeugt einen zufälligen Sitzungsschlüssel $K$ (symmetrisch, z.B. AES-256).
- Sender verschlüsselt die Nachricht mit $K$ symmetrisch (schnell).
- Sender verschlüsselt $K$ selbst mit dem öffentlichen RSA-Schlüssel des Empfängers.
- Empfänger entschlüsselt $K$ mit seinem privaten Schlüssel und dann die Nachricht mit $K$.
F4 Erkläre kurz: Diffie-Hellman, RSA, ECDSA.
- Diffie-Hellman: Schlüsselaustausch über unsicheren Kanal. Beide Parteien einigen sich auf $p, g$, tauschen $g^a$ bzw. $g^b$ aus, berechnen $K = g^{ab}$. Sicherheit: diskretes Logarithmus-Problem.
- RSA: Asymmetrische Verschlüsselung + Signatur. Basiert auf der Schwierigkeit, große Zahlen $n=pq$ zu faktorisieren. $c = m^e \bmod n$, $m = c^d \bmod n$.
- ECDSA: Digitale Signatur auf elliptischen Kurven. Bietet gleiches Sicherheitsniveau wie RSA mit deutlich kürzeren Schlüsseln (256 Bit ECC ≈ 3072 Bit RSA).
F5 Warum werden bei digitalen Signaturen Hash-Funktionen eingesetzt?
- Geschwindigkeit: Asymmetrische Operationen (RSA-Signatur) sind langsam. Nur den Hash zu signieren spart Zeit.
- Größenkontrolle: Der Hash ist fest kurz (z.B. 256 Bit), egal wie lang die Nachricht ist. Passt in den RSA-Modul.
- Sicherheit: Ohne Hash wären algebraische Angriffe möglich (z.B. Homomorphie-Ausnutzung bei RSA: Signatur von $m_1 \cdot m_2$ = Signatur von $m_1 \cdot$ Signatur von $m_2$).
F6 Was ist ein Man-in-the-Middle-Angriff und wie schützt PKI davor?
PKI-Schutz:
- Zertifizierungsstelle (CA) signiert öffentliche Schlüssel: $\text{Zertifikat} = \text{Sign}_{CA}(\text{Name, } K_{pub})$.
- Empfänger prüft die CA-Signatur mit dem bekannten CA-Public-Key.
- Vertrauenskette: Root-CA → Zwischen-CA → Endzertifikat.
- Mallory kann keine gültigen Zertifikate ausstellen, weil er den CA-Privatschlüssel nicht kennt.
F7 Nenne 3 Hash-Verfahren und ihre Sicherheitsstatus.
| Verfahren | Ausgabe | Status |
|---|---|---|
| MD5 | 128 Bit | GEBROCHEN — Kollisionen in Sekunden erzeugbar (Wang 2004) |
| SHA-1 | 160 Bit | GEBROCHEN — SHAttered-Angriff 2017, praktische Kollisionen |
| SHA-256 | 256 Bit | SICHER — Stand 2026 keine praktischen Angriffe bekannt |
F8 Was macht das One-Time-Pad theoretisch sicher?
- Der Chiffretext $c$ ist statistisch unabhängig vom Klartext $m$.
- Zu jedem beliebigen Klartext $m'$ derselben Länge existiert ein Schlüssel, der $c$ erzeugt.
- Ohne Schlüssel: $P(m|c) = P(m)$ — der Chiffretext liefert null Information.
- Schlüssel mindestens so lang wie die Nachricht
- Schlüssel echt zufällig (nicht Pseudozufall!)
- Schlüssel nur ein einziges Mal verwendet
F9 Warum "erst komprimieren, dann verschlüsseln"?
- Klartexte enthalten Redundanz (natürliche Sprache, Dateiformate) → Kompression funktioniert.
- Nach guter Verschlüsselung sieht der Chiffretext wie Zufallsrauschen aus → keine Redundanz → keine Kompression mehr möglich.
- Zusätzlich: Kompression vor der Verschlüsselung entfernt statistische Muster, erschwert Kryptoanalyse.
F10 Was ist der Koinzidenzindex und wozu dient er?
Typische Werte:
- Deutscher Text: $IC \approx 0{,}076$
- Englischer Text: $IC \approx 0{,}065$
- Zufälliger Text (Uniformverteilung): $IC \approx 1/26 \approx 0{,}038$
F11 Warum reicht bei affiner Chiffre nicht jedes $a$?
Bedingung: $\gcd(a, 26) = 1$.
Da $26 = 2 \cdot 13$, sind alle geraden $a$ und $a=13$ ausgeschlossen. Zulässige Werte:
1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25 → $\varphi(26) = 12$ Werte.
F12 Was ist Challenge-Response-Authentisierung?
- Server sendet Client eine zufällige Challenge $c$.
- Client berechnet Antwort $r = f(c, K)$ mit gemeinsamem/privatem Schlüssel $K$ (z.B. HMAC, Signatur).
- Server verifiziert $r$.
- Kein Passwort im Klartext auf der Leitung.
- Replay-Schutz durch frische Challenge pro Session.