hwr-notes/Kryptografie/klausur/gesamtzusammenfassung.md

# Kryptographie – Gesamtzusammenfassung zur Klausurvorbereitung

**HWR Berlin | Prof. Dr. Björn Grohmann | Stand: 31.03.2026**

---
## Inhaltsverzeichnis
1. [IT-Sicherheitsbegriffe (Schutzziele)](#1-it-sicherheitsbegriffe)
2. [Klassische Kryptographie](#2-klassische-kryptographie)
3. [Informationstheoretische Sicherheit](#3-informationstheoretische-sicherheit)
4. [Kryptographische Primitive](#4-kryptographische-primitive)
5. [Bit Commitment](#5-bit-commitment)
6. [Symmetrische Verschlüsselung](#6-symmetrische-verschlüsselung)
7. [AES – Advanced Encryption Standard](#7-aes)
8. [Betriebsmodi (Modes of Operation)](#8-betriebsmodi)
9. [Angriffsmodelle & IND-CPA-Sicherheit](#9-angriffsmodelle--ind-cpa)
10. [MAC, HMAC & AEAD](#10-mac-hmac--aead)
11. [Public-Key-Kryptographie – Grundlagen](#11-public-key-kryptographie)
12. [RSA-Kryptosystem](#12-rsa)
13. [ElGamal-Verschlüsselung](#13-elgamal)
14. [IND-CCA, IND-CCA2 & Padding](#14-ind-cca-ind-cca2--padding)
15. [Digitale Signaturen](#15-digitale-signaturen)
16. [Zertifikate & PKI](#16-zertifikate--pki)
17. [TLS (Transport Layer Security)](#17-tls)
18. [IPSec](#18-ipsec)
19. [Quantencomputer & Kryptographie](#19-quantencomputer)
20. [Post-Quantum Kryptographie (PQC)](#20-post-quantum-kryptographie)
21. [Homomorphe Verschlüsselung](#21-homomorphe-verschlüsselung)
22. [Multi-Party Computation (MPC)](#22-multi-party-computation-mpc)
23. [Zero Knowledge Proofs (ZKP)](#23-zero-knowledge-proofs)
24. [Differential Privacy](#24-differential-privacy)
25. [Trusted Execution Environments (TEE)](#25-trusted-execution-environments)
26. [Privacy-Schutzziele & Technologien](#26-privacy-schutzziele--technologien)
---
## 1. IT-Sicherheitsbegriffe
### Die 4 Sicherheitsziele (VIVA)
In der Kryptographie und IT-Sicherheit werden vier grundlegende Schutzziele unterschieden:

| Schutzziel | Englisch | Bedeutung |
|---|---|---|
| **Vertraulichkeit** | Confidentiality | Nur berechtigte Personen können auf Daten zugreifen. Schutz vor unbefugtem Mitlesen. |
| **Integrität** | Integrity | Daten wurden nicht unbemerkt verändert. Manipulationen werden erkannt. |
| **Verfügbarkeit** | Availability | Daten und Systeme sind für Berechtigte zugänglich, wenn sie benötigt werden. |
| **Authentizität** | Authenticity | Der Absender ist zweifelsfrei identifizierbar. Die Herkunft von Daten ist verifizierbar. |

**Zusätzlich:** **Verbindlichkeit (Non-Repudiation)** – ein Absender kann das Senden einer Nachricht nicht abstreiten. Oft als 5. Schutzziel oder als Teil der Authentizität betrachtet.

**Historisches Beispiel:** Beim Babington-Plot (1586) fehlten alle vier Schutzziele: Maria Stuarts Chiffre bot keine echte Vertraulichkeit (Häufigkeitsanalyse), keine Integrität (Nachrichten wurden manipuliert), der Bote war ein Doppelagent (keine Authentizität), und die Existenz der Kommunikation war bekannt.

---

## 2. Klassische Kryptographie
### 2.1 Häufigkeitsanalyse

Einfache Substitutionschiffren lassen sich durch **Häufigkeitsanalyse** brechen: Man zählt die Häufigkeit von Symbolen im Geheimtext und vergleicht sie mit der bekannten Buchstabenhäufigkeit der Sprache.

- Im Englischen ist **E** der häufigste Buchstabe (~11,16 %), gefolgt von A, R, I, O
- Samuel Morse nutzte dasselbe Prinzip für sein Morsealphabet

### 2.2 Caesar-Chiffre

**Definition:** Jeder Buchstabe wird um eine feste Zahl *n* im Alphabet verschoben.

- **Verschlüsselung:** `E_n(x) = (x + n) mod 26`
- **Entschlüsselung:** `D_n(x) = (x - n) mod 26`

**Beispiel (n = 3):** A → D, B → E, Z → C

**Schwäche:** Nur 25 mögliche Schlüssel → trivial per Brute-Force brechbar.

### 2.3 Vigenère-Chiffre

**Definition:** Polyalphabetische Substitution. Ein Schlüsselwort wird wiederholt über den Klartext gelegt. Jeder Buchstabe bekommt einen anderen Caesar-Shift.

- **Verschlüsselung:** `C_i = (M_i + K_i) mod 26`
- **Entschlüsselung:** `M_i = (C_i - K_i) mod 26`

**Beispiel:** Klartext „attackatdawn" + Schlüssel „LEMON" (wiederholt: „LEMONLEMONLE") → Geheimtext „LXFOPVEFRNHR"

**Schwäche:** Der **Kasiski-Test** ermittelt die Schlüssellänge. Wiederholen sich Muster im Klartext an Positionen, die ein Vielfaches der Schlüssellänge auseinanderliegen, entstehen identische Muster im Geheimtext. Der ggT der Abstände dieser Muster ist oft die Schlüssellänge.

### 2.4 Homophone Chiffren

Jedem Buchstaben werden mehrere Symbole zugeordnet (proportional zur Häufigkeit), um die Häufigkeitsverteilung zu glätten. Bieten keinen vollständigen Schutz.

---

## 3. Informationstheoretische Sicherheit

### 3.1 Informationsgehalt und Entropie

**Informationsgehalt** eines Zeichens x mit Wahrscheinlichkeit p_x:
```
I(x) = -log₂(p_x) = log₂(1/p_x)
```
Je seltener ein Zeichen, desto größer sein Informationsgehalt (in Bit).

**Entropie H(X)** – mittlerer Informationsgehalt einer Zufallsvariable:
```
H(X) = -∑_x p_x · log₂(p_x)
```
Die Entropie ist maximal, wenn alle Zeichen gleich wahrscheinlich sind.

**Bedingte Entropie:** `H(X|Y) = H(X,Y) - H(Y)`

### 3.2 Perfekte Sicherheit (Shannon Perfect Secrecy)

**Definition (Claude Shannon, 1949):** Ein Verschlüsselungssystem hat **perfekte Sicherheit**, wenn gilt:
```
H(M|E) = H(M)
```
Das bedeutet: Die bedingte Entropie der Nachricht M gegeben den Geheimtext E ist gleich der Entropie von M. Der Geheimtext verrät **keinerlei Information** über den Klartext. M und E sind stochastisch unabhängig.

**Äquivalente Formulierung:** Jeder Geheimtext ist unabhängig vom Klartext gleich wahrscheinlich.

**Konsequenz:** Für perfekte Sicherheit muss der Schlüssel **mindestens so lang wie die Nachricht** sein.

### 3.3 One-Time Pad (OTP)

**Definition:** Das einzige Verfahren, das perfekte Sicherheit erreicht.

- **Verschlüsselung:** `E = P ⊕ K` (bitweise XOR von Klartext und Schlüssel)
- **Entschlüsselung:** `P = E ⊕ K`

**Bedingungen für perfekte Sicherheit:**
1. Der Schlüssel muss **echt zufällig** erzeugt werden
2. Der Schlüssel muss **mindestens so lang** sein wie die Nachricht
3. Der Schlüssel darf **nur einmal** verwendet werden (daher „One-Time")

**Problem in der Praxis:** Der Schlüssel muss genauso lang sein wie die Nachricht und über einen sicheren Kanal übertragen werden – unpraktisch.

**Was passiert bei zweifacher Verwendung desselben OTP-Schlüssels?**
```
C₁ = M₁ ⊕ K  und  C₂ = M₂ ⊕ K
→ C₁ ⊕ C₂ = M₁ ⊕ M₂
```
Ein Angreifer erhält XOR der beiden Klartexte – mit Häufigkeitsanalyse oft lösbar.

---

## 4. Kryptographische Primitive

### 4.1 Einwegfunktionen (One-Way Functions, OWF)

**Definition:** Eine Funktion `f: {0,1}* → {0,1}*` ist eine Einwegfunktion, wenn:
1. **Leicht zu berechnen:** Es gibt einen Polynomialzeit-Algorithmus, der f(x) berechnet.
2. **Schwer umzukehren:** Für jeden effizienten Algorithmus A' und alle hinreichend großen n gilt:
   ```
   Pr[A'(f(x)) = x'] < 1/p(n)
   ```
   mit beliebigem Polynom p(n). Das heißt, die Umkehrung gelingt nur mit vernachlässigbarer Wahrscheinlichkeit.

**Anschaulich:** x → f(x) ist schnell und einfach. f(x) → x ist praktisch unmöglich.

**Beispiele:** Multiplikation zweier Primzahlen (leicht), Faktorisierung des Produkts (schwer).

### 4.2 Pseudo-Zufallszahlengeneratoren (PRG/PRNG)

**Definition:** Eine Funktion `G: {0,1}^n → {0,1}^{l(n)}` ist ein PRG, wenn:
1. G ist in Polynomialzeit berechenbar.
2. Die Ausgabe ist **länger** als die Eingabe: `l(n) > n` (Streckung).
3. Die Verteilungen `{G(U_n)}` (Ausgabe auf zufälligem Seed) und `{U_{l(n)}}` (echte Zufallsbits) sind **berechnungsmäßig ununterscheidbar**.

**Amplifikation:** Hat man einen PRG mit Streckung n+1, kann man für jedes Polynom l(n) einen PRG mit Streckung l(n) konstruieren, indem man G iteriert anwendet.

### 4.3 Berechnungsmäßige Ununterscheidbarkeit (Computational Indistinguishability)

**Definition:** Zwei Wahrscheinlichkeitsensembles {X_n} und {Y_n} sind **berechnungsmäßig ununterscheidbar**, wenn für jeden probabilistischen Polynomialzeit-Algorithmus D (Distinguisher) und jedes Polynom p(·) ab einem N gilt:
```
|Pr[D(X_n) = 1] - Pr[D(Y_n) = 1]| < 1/p(n)
```

**Umgangssprachlich:** Kein effizienter Algorithmus kann mit nicht-vernachlässigbarem Vorteil entscheiden, ob er eine Ausgabe von G oder echte Zufallsbits sieht.

### 4.4 Zusammenhang OWF ↔ PRG

> **Theorem:** Pseudo-Zufallszahlengeneratoren existieren **genau dann**, wenn Einwegfunktionen existieren.

- **PRG → OWF:** Aus einem PRG `G: {0,1}^n → {0,1}^{2n}` konstruiert man eine OWF: `f(x||y) = G(x)` wobei |x| = |y| = n. Die Funktion „vergisst" die Hälfte der Eingabe.
- **OWF → PRG:** Über ein **Hardcore-Prädikat (HCP)**. Ein HCP ist leicht zu berechnen, aber aus f(x) allein nicht vorhersagbar.

---

## 5. Bit Commitment

**Definition:** Ein Zwei-Phasen-Protokoll, bei dem sich Alice auf einen Wert (z.B. ein Bit b) festlegt (**Commit**), ohne dass Bob ihn kennt. Später enthüllt Alice den Wert (**Reveal**).

**Eigenschaften:**
- **Hiding:** Bob kann b vor der Reveal-Phase nicht bestimmen.
- **Binding:** Alice kann b nach dem Commit nicht mehr ändern.

**Naiver Ansatz (mit PRG) – funktioniert NICHT:**
- Alice wählt Seed s, sendet `G_m(s)` und `B_{m+1}(s) ⊕ b`
- **Problem:** Alice könnte zwei Seeds s, s' finden, die in den ersten m Bits übereinstimmen, aber im (m+1)-ten Bit differieren → Betrug möglich.

**Verbessertes Protokoll – funktioniert:**
1. Bob sendet zufälligen Vektor `R = (r₁, ..., r_{3n})`
2. Alice wählt Seed s und sendet:
   - `d_i = B_i(s)` falls `r_i = 0`
   - `d_i = B_i(s) ⊕ b` falls `r_i = 1`
3. Reveal: Alice sendet s und b, Bob verifiziert.

**Warum sicher?** Die Wahrscheinlichkeit, dass Alice betrügen kann (zwei Seeds finden, die dieselben d_i erzeugen, aber verschiedenes b liefern), ist höchstens `2^{-n}`.

---

## 6. Symmetrische Verschlüsselung

**Definition:** Sender und Empfänger verwenden **denselben geheimen Schlüssel** zum Ver- und Entschlüsseln.

### 6.1 Stromchiffren

**Prinzip:** Ein kurzer Schlüssel (Seed) wird durch einen PRNG zu einem langen Schlüsselstrom gestreckt. Dieser wird per XOR mit dem Klartext verknüpft.

```
Schlüsselstrom = PRNG(Seed)
Geheimtext = Klartext ⊕ Schlüsselstrom
```

### 6.2 ChaCha20 – Parameter und Funktionsweise

**ChaCha20** ist eine moderne, weit verbreitete Stromchiffre (z.B. in TLS 1.3, WireGuard).

**Parameter:**
| Parameter | Größe | Bedeutung |
|---|---|---|
| **Schlüssel** | 256 Bit | Geheimer Schlüssel |
| **Zähler** | 32 Bit | Block-Zähler (verhindert Wiederholung) |
| **Nonce** | 96 Bit | Number-used-once (verhindert IV-Wiederverwendung) |
| **Klartext** | beliebig | Zu verschlüsselnde Daten |

**Kernoperation – Quarter Round** (arbeitet auf 4 Wörtern a, b, c, d je 32 Bit):
```
a += b; d ^= a; d <<<= 16
c += d; b ^= c; b <<<= 12
a += b; d ^= a; d <<<= 8
c += d; b ^= c; b <<<= 7
```

**Inner Block:** 8 Quarter Rounds (4 Spalten + 4 Diagonalen)

**Block-Erzeugung:** 4×4-Matrix aus [Konstanten | Key | Zähler | Nonce] wird 10× durch inner_block gejagt, dann zum Ausgangszustand addiert.

### 6.3 Blockchiffren

**Definition:** Verschlüsselt einen Klartextblock **fester Größe** (z.B. 128 Bit) in einen Geheimtextblock gleicher Größe. Für längere Nachrichten werden **Betriebsmodi** benötigt.

### 6.4 Feistel-Netzwerk (Feistel Cipher)

**Grundprinzip:** Der Block wird in zwei gleiche Hälften L, R aufgeteilt. Pro Runde gilt:
```
L_{i+1} = R_i
R_{i+1} = L_i ⊕ F(R_i, K_i)
```
Die Funktion F muss **nicht invertierbar** sein, weil die Entschlüsselung durch Anwenden der Rundenschlüssel in umgekehrter Reihenfolge funktioniert.

**Beispiel:** DES (Data Encryption Standard, 1977) ist ein 16-Runden-Feistel-Netzwerk.
- Blockgröße: 64 Bit, Schlüssellänge: 56 Bit (effektiv) → **heute unsicher**

---

## 7. AES – Advanced Encryption Standard

**Definition:** Symmetrische Blockchiffre, seit 2001 Standard (NIST).
- **Blockgröße:** 128 Bit
- **Schlüssellängen:** 128 Bit (10 Runden), 192 Bit (12 Runden), 256 Bit (14 Runden)
- **Gilt als sicher**

### 7.1 Die 4 Phasen von AES-128

Der Zustand ist eine 4×4-Matrix von Bytes (128 Bit).

**Algorithmus:**
1. Schlüsselexpansion: Aus dem Hauptschlüssel werden 11 Rundenschlüssel K₀, ..., K₁₀ abgeleitet.
2. Initiales XOR: `s ← M ⊕ K₀`
3. Für jede Runde r = 1 bis 10:
   1. **SubBytes** – nichtlineare Byte-Substitution (S-Box)
   2. **ShiftRows** – zeilenweises Verschieben
   3. **MixColumns** – spaltenweise Mischung (nicht in Runde 10)
   4. **AddRoundKey** – XOR mit Rundenschlüssel K_r

**Die vier Transformationen im Detail:**

| Phase | Beschreibung | Zweck |
|---|---|---|
| **SubBytes** | Jedes Byte wird durch sein mult. Inverses in GF(2⁸) ersetzt + affine Transformation | Konfusion (non-linearity) |
| **ShiftRows** | Zeile 0: kein Shift; Zeile 1: 1 Byte; Zeile 2: 2 Bytes; Zeile 3: 3 Bytes zyklisch links | Diffusion (Bytes werden „gemischt") |
| **MixColumns** | Jede Spalte wird als Polynom über GF(2⁸) mit einem festen Polynom multipliziert | Diffusion (algebraische Mischung) |
| **AddRoundKey** | XOR des aktuellen Zustands mit dem Rundenschlüssel | Schlüsseleinbindung |

### 7.2 AES S-Box – Mathematik in GF(2⁸)

AES arbeitet im endlichen Körper **GF(2⁸)** (Galois-Körper mit 256 Elementen) mit dem **irreduziblen Polynom:**
```
m(x) = x⁸ + x⁴ + x³ + x + 1
```

**Operationen in GF(2⁸):**
- **Addition:** XOR der Koeffizienten (entspricht XOR der Byte-Werte)
- **Multiplikation:** Polynommultiplikation **modulo m(x)**
- **Multiplikatives Inverses:** Berechnung mit dem **erweiterten euklidischen Algorithmus**: Finde `a(x)`, `c(x)` sodass `b(x)·a(x) + m(x)·c(x) = 1`

**S-Box-Konstruktion (zweistufig):**
1. Berechne das multiplikative Inverse von b in GF(2⁸): `b⁻¹`
2. Affine Transformation: `s = A · b⁻¹ + c` (Matrixmultiplikation über GF(2) + Konstantenvektor)

**Beispiel:** Um zwei Bytes zu multiplizieren, werden sie als Polynome behandelt (Bit 0 = Koeffizient von x⁰, Bit 7 = Koeffizient von x⁷), multipliziert und modulo m(x) reduziert.

---

## 8. Betriebsmodi (Modes of Operation)

Betriebsmodi bestimmen, wie eine Blockchiffre auf lange Nachrichten angewendet wird.

### 8.1 ECB (Electronic Codebook Mode)

**Funktionsweise:** Jeder Block wird **unabhängig** mit demselben Schlüssel verschlüsselt.

```
C_i = Enc(K, M_i)
```

**Problem:** Identische Klartextblöcke → identische Geheimtextblöcke. Muster bleiben sichtbar (bekanntes „ECB-Pinguin-Bild"). **ECB ist NICHT IND-CPA-sicher.**

### 8.2 CBC (Cipher Block Chaining)

**Funktionsweise:** Jeder Klartextblock wird **vor** der Verschlüsselung mit dem vorherigen Geheimtextblock XOR-verknüpft. Der erste Block wird mit einem **Initialization Vector (IV)** verknüpft.

```
C_0 = IV
C_i = Enc(K, M_i ⊕ C_{i-1})
Entschlüsselung: M_i = Dec(K, C_i) ⊕ C_{i-1}
```

**Vorteil:** Gleiche Klartextblöcke ergeben unterschiedliche Geheimtextblöcke (bei verschiedenem IV).
**Nachteil:** Sequenziell (nicht parallelisierbar). Anfällig für **Padding Oracle Attack**.

### 8.3 CTR (Counter Mode)

**Funktionsweise:** Wandelt eine Blockchiffre in eine Stromchiffre um. Nonce + fortlaufender Zähler werden verschlüsselt und per XOR mit dem Klartext verknüpft.

```
C_i = M_i ⊕ Enc(K, Nonce || Counter_i)
```

**Vorteile:** Parallelisierbar, kein Padding nötig, wahlfreier Zugriff möglich.

### 8.4 OFB (Output Feedback)

```
O_0 = IV, O_i = Enc(K, O_{i-1})
C_i = M_i ⊕ O_i
```
Der Schlüsselstrom ist **unabhängig vom Klartext**.

### 8.5 CFB (Cipher Feedback)

```
C_i = M_i ⊕ Enc(K, C_{i-1})
```
Ähnlich wie OFB, aber der **Geheimtext** (statt des Verschlüsselungsoutputs) wird als nächster Eingabeblock verwendet.

### 8.6 Cipher Text Stealing (CTS)

**Problem:** Blockchiffren benötigen Padding, wenn die Nachricht kein Vielfaches der Blockgröße ist.

**CTS-Lösung:** Kein Padding nötig. Die letzten beiden Blöcke werden geschickt kombiniert:
- Der vorletzte (vollständige) und der letzte (unvollständige) Block werden vertauscht und kombiniert.
- Die Gesamtlänge des Geheimtexts entspricht exakt der Klartextlänge.

### 8.7 Padding Oracle Attack

**Kontext:** CBC-Modus mit PKCS#7-Padding.

**PKCS#7-Padding:** Fehlen zum letzten Block n Bytes, werden n Bytes mit dem Wert n angehängt (z.B. 3 fehlende Bytes → `03 03 03`).

**Angriff:** Ein Angreifer kann den Klartext rekonstruieren, **ohne den Schlüssel zu kennen**, wenn:
1. Er beliebige Geheimtexte zur Entschlüsselung einreichen kann
2. Das System **unterschiedliche Fehlermeldungen** für Padding-Fehler vs. andere Fehler zurückgibt (das „Oracle")

**Ablauf (vereinfacht für einen Block):**
- Der Angreifer modifiziert Bytes des vorherigen Geheimtextblocks und beobachtet, ob das Padding korrekt ist.
- Durch systematisches Ausprobieren kann er Byte für Byte den Klartext ermitteln.

**Gegenmaßnahmen:** Einheitliche Fehlermeldungen, Encrypt-then-MAC (AEAD), TLS 1.3 (verwendet kein CBC mehr).

---

## 9. Angriffsmodelle & IND-CPA

### 9.1 Angriffstypen (aufsteigend nach Stärke)

| Angriffstyp | Fähigkeit des Angreifers |
|---|---|
| **Ciphertext-only** | Kennt nur den Geheimtext |
| **Known Plaintext (KPA)** | Kennt Paare von Klartext und Geheimtext |
| **Chosen Plaintext (CPA)** | Kann beliebige Klartexte verschlüsseln lassen |
| **Adaptive Chosen Plaintext** | Wie CPA, aber Anfragen können adaptiv gestellt werden |
| **Chosen Ciphertext (CCA)** | Kann beliebige Geheimtexte entschlüsseln lassen |
| **Adaptive Chosen Ciphertext (CCA2)** | Wie CCA, adaptiv (stärkstes Modell) |

### 9.2 IND-CPA-Sicherheit

**Definition:** Ein Verschlüsselungsschema ist **IND-CPA-sicher** (Indistinguishability under Chosen Plaintext Attack), wenn kein effizienter Angreifer mit nicht-vernachlässigbarem Vorteil entscheiden kann, welche von zwei Nachrichten verschlüsselt wurde.

**Das „Find-then-Guess"-Spiel:**
1. Challenger erzeugt Schlüssel k und Bit b ∈ {0,1}
2. Angreifer A darf beliebig viele Klartexte verschlüsseln lassen (Orakelzugriff)
3. A wählt zwei Nachrichten M₀, M₁ gleicher Länge
4. Challenger verschlüsselt M_b und gibt Geheimtext c zurück
5. A muss b erraten

**Sicher, wenn:** `Adv(A) = |Pr[b = b'] - 1/2| ≤ negl(n)` (vernachlässigbar)

**Warum ECB nicht IND-CPA-sicher ist:** A wählt M₀ = „AA...A" und M₁ = „AA...AB". Im ECB-Modus sind gleiche Blöcke im Klartext auch gleiche Blöcke im Geheimtext → A kann erkennen, welche Nachricht verschlüsselt wurde.

**Warum Determinismus IND-CPA bricht:** Bei deterministischer Verschlüsselung kann A M₀ selbst verschlüsseln und mit c vergleichen → sofort erkennbar, ob b=0.

---

## 10. MAC, HMAC & AEAD

### 10.1 Message Authentication Code (MAC)

**Definition:** Ein MAC (Message Authentication Code) ist ein kurzer **Tag** t, der mit einem symmetrischen Schlüssel k aus einer Nachricht m berechnet wird:
```
t = MAC(k, m)
```

**Bietet:** Integrität und Authentizität – aber **keine Vertraulichkeit**.

### 10.2 Angriffsvektoren auf MACs

| Stärke | Angriff | Beschreibung |
|---|---|---|
| Stärkster | **Total Break** | Angreifer rekonstruiert den Schlüssel oder kann beliebige MACs erzeugen |
| Mittel | **Selective Forgery** | MAC für eine Nachricht, die **vor** dem Angriff gewählt wurde |
| Schwächster | **Existential Forgery** | MAC für **irgendeine** Nachricht erzeugbar (auch sinnlos) |

### 10.3 Warum naive MAC-Konstruktionen unsicher sind

1. **Kein Schlüssel:** Angreifer kann eigene Blöcke einfügen
2. **Jeder Block unabhängig MACen** `t_i = MAC(k, m_i)`: Reihenfolge der Blöcke vertauschbar
3. **Mit Blocknummer** `t_i = MAC(k, i || m_i)`: Blöcke aus verschiedenen Nachrichten mischbar
4. **Mit Nachrichten-ID** `t_i = MAC(k, id || i || m_i)`: Letzter Block weglassbar (Truncation)
5. **Länge im letzten Block kodiert:** Dann erst sicher (CBC-MAC-Variante)

### 10.4 Eigenschaften kryptographischer Hashfunktionen

1. **Effizienz:** Schnell berechenbar
2. **Einwegfunktion:** Schwer zu invertieren
3. **Kollisionsresistenz:** Schwer, zwei verschiedene Eingaben mit gleichem Hash zu finden
4. **Lawineneffekt:** Kleine Eingabeänderung → große Ausgabeänderung

### 10.5 HMAC (Hash-MAC)

**Definition:** HMAC kombiniert eine Hashfunktion mit einem Schlüssel in einer doppelt-genesteten Konstruktion.

```
HMAC(k, m) = H( (k ⊕ opad) || H( (k ⊕ ipad) || m ) )
```

- `H` = kryptographische Hashfunktion (z.B. SHA-256)
- `opad` = Outer Padding (0x5c 5c 5c ...)
- `ipad` = Inner Padding (0x36 36 36 ...)

**Sicherheit:** Durch die Verschachtelung ist HMAC widerstandsfähig gegen Length-Extension-Angriffe.

### 10.6 Kombination Verschlüsselung + MAC

| Variante | Schema | Empfehlung |
|---|---|---|
| **Encrypt-then-MAC** | c = Enc(k₁, m); t = MAC(k₂, c) | ✅ Empfohlen (TLS 1.3) |
| **MAC-then-Encrypt** | t = MAC(k₂, m); c = Enc(k₁, m\|t) | ⚠️ Problematisch (Padding Oracle in altem TLS) |
| **Encrypt-and-MAC** | c = Enc(k₁, m); t = MAC(k₂, m) | ⚠️ MAC kann Klartextinfo leaken |

**Warum Encrypt-then-MAC sicher ist:** Der MAC schützt den Geheimtext – manipulierte Ciphertexte werden **vor** der Entschlüsselung erkannt.

### 10.7 AEAD (Authenticated Encryption with Associated Data)

**Definition:** AEAD kombiniert Verschlüsselung und Authentifizierung in **einem einzigen Algorithmus**.

```
(c, t) = AEAD_Enc(k, nonce, m, aad)
m      = AEAD_Dec(k, nonce, c, t, aad)   (gibt ⊥ bei Authentifizierungsfehler)
```

- `m` = Plaintext (wird verschlüsselt **und** authentifiziert)
- `aad` = Associated Authenticated Data (z.B. IP-/MAC-Adressen, Header – wird **nur authentifiziert**, nicht verschlüsselt)

**Beispiele:**
- **ChaCha20-Poly1305:** ChaCha20 (Stromchiffre) + Poly1305 (MAC) – Standard in TLS 1.3, WireGuard
- **AES-GCM:** AES im CTR-Mode + GHASH (MAC über GF(2¹²⁸)) – Standard für AES in TLS 1.3

**AEAD ist in TLS 1.3 der einzige Standard für Datenintegrität.**

---

## 11. Public-Key-Kryptographie

### 11.1 Das Schlüsselaustauschproblem

Bei symmetrischer Kryptographie brauchen beide Parteien denselben geheimen Schlüssel. Das Problem: Wie überträgt man diesen sicher über einen unsicheren Kanal?

**Merkle Puzzle (1974):** Alice erzeugt n verschlüsselte Rätsel; Bob löst zufällig eines (O(n) Aufwand). Angreifer muss alle n/2 lösen (O(n)). Praktisch ineffizient.

### 11.2 Diffie-Hellman-Schlüsselaustausch

**Definition:** Ermöglicht zwei Parteien, über einen **öffentlichen Kanal** ein gemeinsames Geheimnis zu vereinbaren, ohne dieses direkt zu übertragen.

**Protokoll:**
```
Öffentlich: Primzahl p, Generator g (Basis)

Alice wählt  a (geheim)  →  sendet  A = g^a mod p
Bob   wählt  b (geheim)  →  sendet  B = g^b mod p

Gemeinsames Geheimnis: K = g^(ab) mod p
  Alice berechnet: K = B^a mod p = (g^b)^a mod p = g^(ab) mod p
  Bob   berechnet: K = A^b mod p = (g^a)^b mod p = g^(ab) mod p
```

**Sicherheit:** Basiert auf dem **Diskreten-Logarithmus-Problem (DLP)**: Aus g^a mod p ist es schwer, a zu berechnen.

### 11.3 Diskretes-Logarithmus-Problem (DLP)

**Definition:** Gegeben Gruppe G, Generator g, Element y = g^x: Bestimme x = log_g(y).

- **Berechnung von g^x:** effizient – O(log x) Multiplikationen (schnelle Exponentiation)
- **Umkehrung (diskreter Logarithmus):** für große Gruppen **schwer** (kein effizienter klassischer Algorithmus bekannt)

### 11.4 ModP-Gruppe (Einheitengruppe)

**Definition:** Die Menge `ℤ_p* = {1, 2, ..., p-1}` mit Multiplikation modulo p (p prim) bildet eine **zyklische Gruppe** der Ordnung p-1.

- Es gibt einen **Generator g**, sodass `{g⁰, g¹, ..., g^(p-2)} = ℤ_p*`
- **Fermat'scher kleiner Satz:** `a^(p-1) ≡ 1 (mod p)` für alle a mit ggT(a,p) = 1
- Für Diffie-Hellman braucht man p mit mindestens **2048 Bit** (heutige Empfehlung)

### 11.5 Elliptische Kurven (EC)

Elliptische Kurven bieten dieselbe Sicherheit wie ModP-Gruppen, aber mit **viel kleineren Schlüsseln** (256 Bit ECDH ≈ 3072 Bit DH in klassischer Sicherheit).

**Kurvendefinition (Weierstraß-Form):**
```
y² = x³ + ax + b   mit  4a³ + 27b² ≠ 0 (keine Singularitäten)
```

**Gruppengesetz:** Punkte auf der Kurve bilden eine abelsche Gruppe:
- **Neutrales Element:** Punkt im Unendlichen O
- **Addition P + Q:** Schneide Gerade durch P, Q mit der Kurve; reflektiere dritten Schnittpunkt
- **Verdoppelung 2P:** Tangente an P; reflektiere zweiten Schnittpunkt

**ECDLP:** Gegeben P und Q = k·P, finde k. Gilt als schwerer als DLP in ModP → kleinere Schlüssel.

**ECDH:** Wie DH, aber mit Punktmultiplikation statt Exponentiation.

---

## 12. RSA-Kryptosystem

### 12.1 Schlüsselgenerierung

```
1. Wähle zwei große Primzahlen p, q  (je 1024–2048 Bit)
2. n = p · q                          (öffentlicher Modulus)
3. φ(n) = (p-1) · (q-1)              (Eulersche Phi-Funktion, geheim!)
4. Wähle e mit ggT(e, φ(n)) = 1      (öffentlicher Exponent, oft e = 65537)
5. Berechne d = e⁻¹ mod φ(n)         (privater Exponent)

Öffentlicher Schlüssel: (n, e)
Privater Schlüssel:     (n, d)
```

### 12.2 Ver- und Entschlüsselung

```
Verschlüsselung: c = m^e mod n
Entschlüsselung: m = c^d mod n
```

**Korrektheit:** Folgt aus dem **Satz von Euler**: `m^φ(n) ≡ 1 (mod n)`, daher `m^(e·d) = m^(1 mod φ(n)) ≡ m (mod n)`.

### 12.3 Beispielrechnung

**Gegeben:** p = 11, q = 13

```
n = 11 · 13 = 143
φ(n) = 10 · 12 = 120
Wähle e = 7  (ggT(7, 120) = 1 ✓)
d = 7⁻¹ mod 120 = 103  (denn 7 · 103 = 721 = 6·120 + 1 ✓)

Öffentlicher Schlüssel: (143, 7)
Privater Schlüssel:     (143, 103)

Verschlüsseln von m = 5:
c = 5^7 mod 143 = 78125 mod 143 = 47

Entschlüsseln von c = 47:
m = 47^103 mod 143 = 5  ✓
```

### 12.4 Faktorisierungsproblem

**Definition:** Gegeben n = p · q (p, q prim), finde p und q.

- **Multiplikation** p · q → n: effizient, O(log²n)
- **Faktorisierung** n → p, q: schwer (bester klassischer Algorithmus: **Zahlkörpersieb**, subexponentiell, aber nicht polynomial)

**Wichtig:** Die Sicherheit von RSA basiert auf der Annahme, dass Faktorisierung schwer ist. Es ist jedoch **nicht bewiesen**, dass RSA-Brechen äquivalent zur Faktorisierung ist.

---

## 13. ElGamal-Verschlüsselung

**Definition:** Auf Diffie-Hellman basierendes Public-Key-Verfahren (Taher Elgamal, 1985). Der Sender macht einen einmaligen DH-Austausch mit dem öffentlichen Schlüssel des Empfängers.

### Schlüsselgenerierung

```
Öffentliche Parameter: zyklische Gruppe G der Ordnung n, Generator α
Privater Schlüssel:    a (zufällig, 1 ≤ a ≤ n-1)
Öffentlicher Schlüssel: (α, α^a)
```

### Verschlüsselung (probabilistisch)

```
Wähle zufälliges k (1 ≤ k ≤ n-1)    ← jedes Mal neu!
γ = α^k                               ← "einmaliger DH-Anteil" des Senders
δ = m · (α^a)^k                       ← Nachricht maskiert mit DH-Geheimnis
Ciphertext: (γ, δ)
```

### Entschlüsselung

```
Berechne γ^a = (α^k)^a = α^(ka)      ← gemeinsames DH-Geheimnis
m = δ · (γ^a)^(-1) = δ · γ^(-a)
```

**Korrektheit:** `δ · γ^(-a) = m · α^(ak) · α^(-ak) = m ✓`

**Sicherheit:** Basiert auf der **DDH-Annahme** (Decisional Diffie-Hellman). ElGamal ist IND-CPA-sicher, aber **NICHT IND-CCA-sicher** (Malleability: Aus (γ, δ) kann man (γ, δ·m') erzeugen, das m·m' verschlüsselt).

**Nachteil:** Ciphertext (γ, δ) ist **doppelt so lang** wie die Nachricht.

---

## 14. IND-CCA, IND-CCA2 & Padding

### 14.1 IND-CCA-Sicherheit

**Definition:** **Indistinguishability under Chosen Ciphertext Attack** – das stärkste gängige Sicherheitsmodell für Public-Key-Verschlüsselung.

Erweiterung des IND-CPA-Spiels: Der Angreifer erhält zusätzlich ein **Entschlüsselungsorakel**.

```
Phase 1: Angreifer sendet beliebige Ciphertexte und bekommt Klartexte zurück
Challenge: Challenger verschlüsselt M_b → Angreifer bekommt c
Phase 2: Angreifer darf weiter entschlüsseln – ABER nicht c selbst!
```

**IND-CCA** (nicht-adaptiv): Entschlüsselungsanfragen nur in Phase 1.
**IND-CCA2** (adaptiv): Entschlüsselungsanfragen in Phase 1 **und** Phase 2 (außer c selbst).

**Textbook RSA ist NICHT IND-CPA-sicher** (deterministisch!). Mit Padding-Schemata wird IND-CCA2 erreicht.

### 14.2 OAEP (Optimal Asymmetric Encryption Padding)

**Definition:** OAEP macht RSA probabilistisch und erreicht IND-CCA2-Sicherheit im Random-Oracle-Modell.

```
Eingabe: Nachricht m, zufälliger Seed r

X = (m || 0...0) ⊕ G(r)    (G = Pseudozufallsfunktion / Mask Generation Function)
Y = r ⊕ H(X)               (H = Hashfunktion)

RSA-Input: (X || Y)
Verschlüsselung: c = (X||Y)^e mod n
```

In der Praxis: **RSA-OAEP** aus PKCS#1 v2.x.

### 14.3 RSA-PSS (Probabilistic Signature Scheme)

**Warum RSA-PSS nötig ist:** Rohes RSA ohne Padding ist anfällig für **Existential Forgery**: Ein Angreifer wählt eine beliebige Signatur s und berechnet „die Nachricht" x = s^e mod n. Das Paar (x, s) ist eine gültige Signatur!

**RSA-PSS verhindert das durch Padding vor der Signatur:**
1. `mHash = H(M)`
2. `M' = [8×0x00 | mHash | salt]` → nochmals gehasht → `H`
3. `DB = [PS | 0x01 | salt]`
4. `maskedDB = DB ⊕ MGF(H)` (Mask Generation Function)
5. `EM = [maskedDB | H | 0xbc]`
6. Signatur: `s = EM^d mod n`

---

## 15. Digitale Signaturen

### 15.1 Grundprinzip

**Definition:** Eine digitale Signatur ermöglicht **Integrität**, **Authentizität** und **Non-Repudiation** (Nicht-Abstreitbarkeit).

**Ablauf:**
- **Signieren:** `σ = sign(m, sk)` – mit privatem Schlüssel signieren
- **Verifizieren:** `verify(σ, m, pk) → {true, false}` – mit öffentlichem Schlüssel prüfen

**Formale Algorithmen:**
```
keygen(1^k) → (sk, pk)     Schlüsselpaar erzeugen
sign(m, sk) → σ            Signatur erzeugen
verify(σ, m, pk) → d       Signatur verifizieren
```

**Wichtig:** Private Key ≠ Public Key! Der Sender signiert mit dem **privaten Schlüssel**, der Empfänger verifiziert mit dem **öffentlichen Schlüssel**. (Umgekehrt zur Verschlüsselung!)

### 15.2 Angriffsvektoren auf Signaturen

| Angriff | Beschreibung |
|---|---|
| **Total Break** | Angreifer leitet den privaten Schlüssel ab → kann beliebige Signaturen erzeugen |
| **Selective Forgery** | Gültige Signatur für eine Nachricht, die **vor** dem Angriff gewählt wurde |
| **Existential Forgery** | Gültige Signatur für **irgendeine** Nachricht (auch sinnlose) |

### 15.3 RSA-Signatur

```
Signatur:    s = m^d mod n     (mit privatem Schlüssel d)
Verifikation: m' = s^e mod n   (mit öffentlichem Schlüssel e)
Gültig wenn: m' = m
```

**Existential Forgery gegen Textbook RSA:**
Oscar wählt s → berechnet x = s^e mod n → präsentiert (x, s) als gültige Signatur. Alice verifiziert: s^e ≡ x ✓. **Deshalb ist RSA-PSS notwendig.**

### 15.4 ECDSA (Elliptic Curve Digital Signature Algorithm)

**Signieren** (Nachricht m, privater Schlüssel d_A, Basispunkt G, Gruppenordnung n):
```
1. e = H(m)   (Hash der Nachricht)
2. z = linkste L_n Bits von e
3. Wähle zufälliges k ∈ [1, n-1]
4. (x₁, y₁) = k × G   (Skalarmultiplikation auf EC)
5. r = x₁ mod n
6. s = k⁻¹ · (z + r · d_A) mod n
Signatur: (r, s)
```

**Verifizieren** (mit öffentlichem Schlüssel Q_A = d_A · G):
```
1. e = H(m), z = linkste L_n Bits
2. u₁ = z · s⁻¹ mod n
3. u₂ = r · s⁻¹ mod n
4. (x₁, y₁) = u₁ × G + u₂ × Q_A
5. Gültig wenn r ≡ x₁ (mod n)
```

### 15.5 Fiat-Shamir Transformation

**Definition:** Die Fiat-Shamir-Transformation (Fiat & Shamir, 1986) wandelt ein **interaktives Zero-Knowledge-Protokoll** in einen **nicht-interaktiven Beweis** (oder eine digitale Signatur) um.

**Grundidee:** Die zufällige Challenge des Verifiers wird durch den Output einer **kryptographischen Hashfunktion** ersetzt:
```
Challenge = H(Commitment, public_data)    [bei ZK-Proof]
Challenge = H(Commitment, Nachricht)      [bei Signatur]
```

**Interaktives Protokoll → Nicht-interaktiv:**

*Original (interaktiv, 3 Schritte):*
1. Prover sendet Commitment C
2. Verifier sendet zufällige Challenge ch
3. Prover sendet Response r

*Fiat-Shamir (nicht-interaktiv):*
1. Prover berechnet Commitment C
2. Prover berechnet: `ch = H(C, öffentliche_Parameter)`
3. Prover berechnet Response r
4. Beweis: `(C, ch, r)` – kein Verifier nötig!

**Signaturschema aus ZK-Proof:**
- Die Nachricht wird in den Hash eingebaut: `ch = H(C, m)`
- Die Signatur ist das Tripel `(C, r)` (ch kann rekonstruiert werden)
- Sicherheit hängt von der Random-Oracle-Annahme ab (H verhält sich wie eine ideale Zufallsfunktion)

**Beispiel – Schnorr-Signatur (aus DLP-ZK-Proof):**
```
Schlüsselpaar: sk = x, pk = g^x mod p
Signieren von m:
  r = g^k mod p    (zufälliges k)
  e = H(r, m)
  s = k - x·e mod (p-1)
Signatur: (s, e)

Verifizieren:
  r' = g^s · (g^x)^e mod p
  Gültig wenn H(r', m) = e
```

---

## 16. Zertifikate & PKI

### 16.1 Das Kernproblem

> Wie kann Bob sicher sein, dass ein Public Key wirklich zu Alice gehört und nicht zu einem Angreifer?

**Man-in-the-Middle-Angriff:** Oscar gibt sich sowohl gegenüber Alice als auch Bob als der jeweils andere aus und führt zwei separate DH-Austausche durch. Ohne Authentifizierung ist dies undetektierbar.

### 16.2 Certificate Authority (CA) und Zertifikate

**Lösung:** Eine **vertrauenswürdige Zertifizierungsstelle (CA)** bestätigt die Identität und signiert den Public Key.

**Inhalt eines X.509-Zertifikats:**
- Name, Organisation, Land
- Gültigkeitszeitraum (von/bis)
- Public Key des Inhabers
- Algorithmus und Parameter
- **Digitale Signatur der CA**

**Funktionsweise:**
1. Alice generiert Schlüsselpaar (sk, pk)
2. Alice gibt pk an die CA, beweist ihre Identität
3. CA erzeugt Zertifikat: `Cert = Sign(sk_CA, ID_Alice || pk_Alice || Gültigkeit)`
4. Jeder, der CA's Public Key kennt und ihr vertraut, kann das Zertifikat verifizieren

### 16.3 Zertifikatskette (Chain of Trust)

```
Endnutzer-Zertifikat (z.B. google.com)
    ↑ signiert von
Intermediate CA (z.B. Google Trust Services)
    ↑ signiert von
Root CA (z.B. GlobalSign, DigiCert)
    ↑ selbst-signiert (Vertrauensanker, im Browser vorinstalliert)
```

**Root CAs** sind die letzte Vertrauensbasis. Ihre öffentlichen Schlüssel sind in Betriebssystemen und Browsern vorinstalliert.

### 16.4 Zertifikatswiderruf

**CRL (Certificate Revocation List):**
- Liste aller zurückgezogenen Zertifikate, periodisch von der CA veröffentlicht
- Nachteil: Kein Echtzeit-Update, kann veraltet sein

**OCSP (Online Certificate Status Protocol):**
- Echtzeitabfrage des Zertifikatstatus bei einem **OCSP-Responder** (Server der CA)
- Vorteil: Aktuell; Nachteil: Datenschutz (CA erfährt, welche Sites besucht werden)
- **OCSP Stapling:** Server fragt selbst den Status ab und hängt die Antwort an den TLS-Handshake

---

## 17. TLS (Transport Layer Security)

### 17.1 Einordnung im OSI-Modell

TLS liegt zwischen **Anwendungsschicht** und **Transportschicht** (OSI Layer 4/5):
```
Anwendung (Layer 7) → TLS → TCP (Layer 4) → IP (Layer 3) → ...
```
TLS läuft **über TCP**, nicht im Kernel/Netzwerkstack.

### 17.2 TLS-Ziele (RFC 8446, TLS 1.3)

- **Authentifizierung:** Server wird immer authentifiziert, Client optional
- **Vertraulichkeit:** Daten nur für Endpunkte sichtbar
- **Integrität:** Manipulationen werden erkannt

### 17.3 TLS-Komponenten

| Komponente | Aufgabe |
|---|---|
| **Record Layer** | Fragmentierung, Authentifizierung, Verschlüsselung der Nutzdaten |
| **Handshake Protocol** | Aushandeln von Algorithmen, Zertifikatsaustausch, Key Exchange |
| **Alert Protocol** | Fehlermeldungen und Verbindungsabschluss |
| **Change Cipher Spec** | (nur Kompatibilität in TLS 1.3) |

### 17.4 TLS 1.3 Handshake (vereinfacht)

```
Client                              Server
  ClientHello (supported ciphers,
  key_share, random)          →
                              ← ServerHello (chosen cipher, key_share)
                              ← {EncryptedExtensions}
                              ← {Certificate}
                              ← {CertificateVerify}
                              ← {Finished}
  {Finished}                  →
  [Application Data]         ↔   [Application Data]
```

Key Exchange erfolgt mit **(EC)DHE** – Forward Secrecy ist damit garantiert.

### 17.5 TLS 1.3 Sicherheitsmerkmale

- Nur **AEAD-Cipher** erlaubt: AES-GCM, AES-CCM, ChaCha20-Poly1305
- Kein CBC, kein RC4, kein 3DES
- **Perfect Forward Secrecy (PFS)** durch ephemere DH-Schlüssel
- Reduzierte RTT (Round-Trip-Time) durch 0-RTT oder 1-RTT

### 17.6 TLS-Versionshistorie

| Version | Jahr | Status |
|---|---|---|
| SSL 2.0 | 1995 | Veraltet (2011) |
| SSL 3.0 | 1996 | Veraltet (2015) |
| TLS 1.0 | 1999 | Veraltet (2021) |
| TLS 1.1 | 2006 | Veraltet (2021) |
| TLS 1.2 | 2008 | Noch genutzt |
| **TLS 1.3** | **2018** | **Aktuell** |

---

## 18. IPSec

**Einordnung im OSI-Modell:** IPSec arbeitet auf **Layer 3 (Netzwerkschicht)** – direkt im IP-Stack.

**Vergleich mit TLS:** TLS schützt Anwendungsdaten (Layer 7), IPSec schützt IP-Pakete (Layer 3).

### Betriebsmodi

| Modus | Beschreibung |
|---|---|
| **Transportmodus** | Nur der Payload des IP-Pakets wird geschützt; IP-Header bleibt sichtbar |
| **Tunnelmodus** | Das gesamte ursprüngliche IP-Paket wird verschlüsselt und in ein neues IP-Paket eingebettet (Gateway-zu-Gateway, VPN) |

### Protokolle

| Protokoll | Bietet | Schützt |
|---|---|---|
| **AH (Authentication Header)** | Integrität + Authentizität | Header + Daten (kein Payload-Encrypt) |
| **ESP (Encapsulating Security Payload)** | Verschlüsselung + Authentifizierung | Nur Payload-Daten |

---

## 19. Quantencomputer & Kryptographie

### 19.1 Quantenmechanische Grundlagen

| Phänomen | Bedeutung für Krypto |
|---|---|
| **Superposition** | Qubit = gleichzeitig 0 und 1 → parallele Berechnungen |
| **Verschränkung (Entanglement)** | Qubits sind korreliert, unabhängig von Distanz |
| **Nondeterminismus** | Messung ergibt zufälliges Ergebnis → Echte Zufallszahlengeneratoren (QRNG) |
| **No-Cloning-Theorem** | Quantenzustände können nicht kopiert werden → Sicherheit von QKD |

### 19.2 BB84-Protokoll (Quantum Key Distribution)

**Erfinder:** Charles Bennett & Gilles Brassard (1984)

**Ablauf:**
1. **Alice** wählt zufällige Bits und kodiert sie in Photonen mit zufällig gewählten Basen (+, ×)
2. **Bob** misst die Photonen mit zufällig gewählten Basen
3. **Öffentlicher Abgleich:** Alice und Bob vergleichen ihre Basen (nicht die Bits!)
4. Bits mit **übereinstimmenden Basen** ergeben den **Sifted Key** (ca. 50% der Bits)
5. Stichproben prüfen Abhören: Eve-Messung stört den Quantenzustand

**Sicherheit:** Jede Messung durch Eve verändert den Quantenzustand (Messprinzip). Bei ~25% der Bits führt Eves Abhören zu einem Fehler → Eve ist **nachweisbar**.

**No-Cloning-Theorem:** Quantenzustände können nicht kopiert werden → klassische Repeater funktionieren nicht.

### 19.3 Shors Algorithmus

**Peter Shor (1994):** Löst **ganzzahlige Faktorisierung** und das **Diskrete-Logarithmus-Problem** in **polynomialer Zeit** auf einem Quantencomputer.

**Konsequenz für klassische Kryptographie:**

| Algorithmus | Klassische Sicherheit | Sicherheit mit Quantencomputer |
|---|---|---|
| RSA-3072 | 128 Bit | **gebrochen (0 Bit)** |
| DH-3072 | 128 Bit | **gebrochen (0 Bit)** |
| ECDH-256 | 128 Bit | **gebrochen (0 Bit)** |
| ECDSA-256 | 128 Bit | **gebrochen (0 Bit)** |

**Alle auf DLP oder Faktorisierung basierenden Verfahren werden durch Shor wertlos.**

### 19.4 Grovers Algorithmus

**Lov Grover:** Findet ein Element in einer Datenbank der Größe N in **O(√N)** Schritten (statt O(N) klassisch).

**Konsequenz für symmetrische Kryptographie:** Effektive Schlüssellänge wird **halbiert**.

| Algorithmus | Klassische Sicherheit | Mit Grover |
|---|---|---|
| AES-128 | 128 Bit | **64 Bit** (unsicher!) |
| AES-256 | 256 Bit | 128 Bit ✓ (noch sicher) |
| SHA-256 | 256 Bit* | 128 Bit* ✓ |

**Gegenmaßnahme:** Schlüssellängen **verdoppeln** (AES-256 statt AES-128).

### 19.5 Simons Algorithmus

**Simons Problem:** Gegeben eine Funktion f mit einer verborgenen Periode s, finde s.
- Klassisch: **Ω(2^(n/2))** Anfragen nötig
- Quantenalgorithmus: **O(n)** Anfragen (exponentiell schneller)

**Konsequenz:** Viele klassische kryptographische Konstruktionen werden durch Simons Algorithmus gebrochen (selbst wenn Grover/Shor nicht anwendbar sind):

Durch quantenbasierte Angriffe sind gebrochen: Even-Mansour, 3-Runden-Feistel, LRW, CBC-MAC, GMAC, PMAC, GCM, OCB und viele weitere symmetrische Konstruktionen.

---

## 20. Post-Quantum Kryptographie (PQC)

### 20.1 Warum PQC? – Moscas Theorem

Drei Zeitparameter:
- **x** = Wie lange müssen heutige Daten sicher bleiben?
- **y** = Wie lange dauert die Migration auf quantensichere Lösungen?
- **z** = Wann gibt es kryptographisch relevante Quantencomputer?

> **Moscas Theorem:** Falls **x + y > z**, muss **jetzt** gehandelt werden.

**„Harvest now, decrypt later":** Angreifer sammeln heute verschlüsselte Daten und entschlüsseln sie, sobald Quantencomputer verfügbar sind.

### 20.2 PQC-Strategien

| Ansatz | Basis | Vorteil | Nachteil |
|---|---|---|---|
| **Hash-based** | Nur kryptographische Hashfunktionen | Sehr gut verstanden, konservative Sicherheit | Signaturen sind groß, Schlüsselpaare oft einmalig |
| **Lattice-based (Gitter)** | Schwere Gitterprobleme (LWE, SIS) | Beste Performanz, stärkstes theoretisches Fundament | Komplex |
| **Code-based** | Schweres Dekodierungsproblem | Bewährt seit 1978 (McEliece) | Große Schlüssel |
| **Multivariate** | Unlösbarkeit quadratischer Gleichungssysteme (MQ-Problem) | Sehr schnelle Signaturen | Große Schlüssel, mehrere gebrochen |
| **Isogenien** | Schwierigkeit von Isogenieberechnungen | Kleine Schlüssel | SIKE 2022 gebrochen! |
| **MPC in the Head** | Sicherheit von ZK-Proofs | Minimale Annahmen | Größere Signaturen |

### 20.3 Hash-basierte Signaturen

**Grundprinzip:** Öffentlicher Schlüssel = Hash-Werte h(x)||h(y); Privater Schlüssel = (x, y).

**Lamport-OTS (One-Time Signature):** Einmalsignatur nur auf Basis von OWFs. Schlüssel darf nur **einmal** verwendet werden.

**Merkle-Baum:** Viele OTS-Schlüssel werden in einem binären Hash-Baum organisiert. Die Wurzel ist der öffentliche Schlüssel. Ein **Authentifizierungspfad** ermöglicht die Verifikation einzelner Blätter.

**XMSS/SPHINCS+:** Hierarchische Baumstrukturen für mehrfache Signaturen. **SPHINCS+** ist NIST-standardisiert.

### 20.4 Gitter-basierte Kryptographie (Lattice-based)

**Grundidee:** Gitter sind regelmäßige Punktgitter im n-dimensionalen Raum, aufgespannt durch Basisvektoren.

**Schwere Gitterprobleme:**
- **SVP (Shortest Vector Problem):** Finde den kürzesten Nicht-Null-Vektor im Gitter
- **CVP (Closest Vector Problem):** Finde den nächsten Gitterpunkt zu einem gegebenen Punkt
- **GapSVP_γ:** Entscheidungsversion von SVP mit Approximationsfaktor γ

**LWE (Learning With Errors):** Gegeben verrauschte Skalarprodukte `bᵢ ≈ ⟨aᵢ, s⟩ mod q`, finde s. Gilt als quantenresistentes schweres Problem.

**Worst-Case-zu-Average-Case-Reduktion:** Der entscheidende Vorteil: Wenn LWE im Durchschnitt leicht wäre, wäre GapSVP im schlimmsten Fall leicht. Das LWE-Problem ist daher so schwer wie das schlimmste Gitterproblem.

**Regev's Public-Key-Kryptosystem (LWE-Beispiel):**
```
Privater Schlüssel: s ∈ ℤ_q^n (zufällig)
Öffentlicher Schlüssel: m Paare (aᵢ, bᵢ) mit bᵢ = ⟨aᵢ, s⟩/q + eᵢ
                        (eᵢ = kleiner Fehler aus Fehlerverteilung χ)

Verschlüsselung von Bit x:
  Wähle zufällige Teilmenge S ⊆ [m]
  Enc(x) = (Σᵢ∈S aᵢ,  x/2 + Σᵢ∈S bᵢ)

Entschlüsselung:
  Prüfe ob  b - ⟨a, s⟩/q  näher an 0 (→ x=0) oder an 1/2 (→ x=1)
```

### 20.5 Isogenien-basierte Kryptographie

**Isogenie:** Ein Gruppenhomomorphismus `φ: E → E'` zwischen elliptischen Kurven, dargestellt durch rationale Funktionen.

**SIDH-Schlüsselaustausch (analog zu DH):**
- Alice berechnet Isogenie Φ_A(E) und sendet sie an Bob
- Bob berechnet Isogenie Φ_B(E) und sendet sie an Alice
- Gemeinsames Geheimnis: j-Invariante von Φ'_A(Φ_B(E)) = Φ'_B(Φ_A(E))

⚠️ **SIKE (konkrete Instanz) wurde im Juli 2022 vollständig gebrochen** – alle Isogenien-basierten Verfahren müssen neu bewertet werden.

### 20.6 Code-basierte Kryptographie

**Grundidee:** Sicherheit beruht auf der Schwierigkeit des **Syndrome-Decoding-Problems** (allgemeine Fehlerkorrektur ist NP-hart).

**McEliece-Kryptosystem (1978):**
- Öffentlicher Schlüssel: `H* = P · H · S` (permutierte und transformierte Prüfmatrix)
- Verschlüsselung: `c = m · H*` + absichtliche Fehler
- Entschlüsselung: Nur Besitzer von P, H, S kann effizient dekodieren

### 20.7 NIST PQC-Standardisierung

**Timeline:**
- 2017: Ausschreibung mit **69 Kandidaten** (1. Runde)
- 2022: Auswahl der ersten Standards

**Ausgewählte Algorithmen:**
| Algorithmus | Typ | Basis |
|---|---|---|
| **CRYSTALS-Kyber** (ML-KEM) | Key Encapsulation Mechanism | Gitter (Module-LWE) |
| **CRYSTALS-Dilithium** (ML-DSA) | Digitale Signatur | Gitter (Module-LWE) |
| **Falcon** | Digitale Signatur | Gitter (NTRU) |
| **SPHINCS+** (SLH-DSA) | Digitale Signatur | Hash-basiert |

---

## 21. Homomorphe Verschlüsselung

### 21.1 Grundidee

**Definition:** Homomorphe Verschlüsselung ermöglicht Berechnungen auf **verschlüsselten Daten**, ohne diese zu entschlüsseln.

```
Enc(m₁) ⋆ Enc(m₂) = Enc(m₁ ∘ m₂)
```
(⋆ = Operation auf Chiffretexten; ∘ = entsprechende Operation auf Klartexten)

**Kerngleichung:** Der Verarbeitende erhält `Enc(f(m))`, ohne m jemals zu sehen.

**Anwendung:** Cloud Computing – Daten bleiben beim Cloud-Anbieter verschlüsselt, werden aber trotzdem verarbeitet.

### 21.2 Klassifizierung

| Typ | Abk. | Fähigkeit | Performance |
|---|---|---|---|
| **Partially Homomorphic Encryption** | PHE | Eine Operation unbeschränkt oft | Hoch |
| **Somewhat Homomorphic Encryption** | SWHE | Zwei Operationen, mindestens eine beschränkt | Mittel |
| **Fully Homomorphic Encryption** | FHE | Beliebige Berechnungen, unbeschränkt | Niedrig |

### 21.3 RSA als Beispiel für PHE (multiplikativ homomorph)

```
E(M₁) · E(M₂) = M₁^e · M₂^e mod n = (M₁·M₂)^e mod n = E(M₁·M₂)
```
RSA ist **multiplikativ homomorph** – beliebig viele Multiplikationen auf Chiffretexten möglich.

### 21.4 Paillier-Kryptosystem (additiv homomorph, fast wie RSA)

**Definition:** Paillier (1999) ist ähnlich wie RSA aufgebaut, aber **additiv homomorph** statt multiplikativ.

**Schlüsselerzeugung:**
```
n = p · q          (zwei große Primzahlen)
g = n + 1          (öffentlicher Parameter)
λ = φ(n) = (p-1)(q-1)
μ = φ(n)⁻¹ mod n   (privater Schlüssel)

Öffentlicher Schlüssel: (n, g)
Privater Schlüssel:     (n, λ, μ)
```

**Verschlüsselung:**
```
c = g^m · r^n mod n²        (r zufällig, ggT(r,n) = 1)
```

**Entschlüsselung:**
```
m = L(c^λ mod n²) · μ mod n    mit L(x) = (x-1)/n
```

**Homomorphe Addition:**
```
D( E(m₁, r₁) · E(m₂, r₂) mod n² ) = m₁ + m₂ mod n
```
Das **Produkt zweier Chiffretexte** entspricht der **Summe der Klartexte**.

**Vergleich Paillier vs. RSA:**
- Beide basieren auf Faktorisierungsproblem
- Paillier: additiv homomorph; RSA: multiplikativ homomorph
- Paillier: probabilistisch; RSA (ohne Padding): deterministisch
- Paillier: Chiffretexte liegen in ℤ_{n²} statt ℤ_n

---

## 22. Multi-Party Computation (MPC)

### 22.1 Ziel und Motivation

**Definition:** MPC ermöglicht mehreren Parteien, gemeinsam eine Funktion **f(x₁, x₂, ..., x_n)** zu berechnen, ohne dass irgendeine Partei die Eingaben der anderen erfährt.

**Yao's Millionärsproblem (1982):** Zwei Millionäre wollen herausfinden, wer reicher ist, ohne ihr Vermögen preiszugeben.

**Ideales Modell:** Alle Parteien senden ihre Eingaben an eine vertrauenswürdige dritte Partei (Trusted Third Party), die f berechnet und das Ergebnis zurückgibt. **Ziel von MPC:** Das gleiche Ergebnis ohne vertrauenswürdige dritte Partei erreichen.

### 22.2 Oblivious Transfer (OT)

**Definition:** Ein Protokoll, bei dem der **Sender nicht weiß, welche** seiner Nachrichten der Empfänger erhalten hat.

**Drei Varianten:**

| Variante | Beschreibung |
|---|---|
| **OT (Rabin, 1981)** | Alice hat Bit b. Bob erhält b mit Prob. 1/2. Alice weiß nicht, ob Bob b erhalten hat. |
| **1-out-of-2 OT** | Alice hat b₀, b₁. Bob erhält genau eines (b_k). Alice weiß nicht, welches. |
| **p-OT** | Wie OT, aber Empfang mit beliebiger Wahrscheinlichkeit p. |

**Wofür ist OT gut?**
- Fundamentaler Baustein für MPC-Protokolle
- Ermöglicht es Parteien, Informationen auszutauschen, ohne vollständigen Einblick zu geben
- Garbled Circuits benötigen OT für Bobs Eingaben

**DH-basiertes 1-out-of-2 OT-Protokoll:**
```
Sender hat (M₀, M₁), Empfänger hat Auswahlbit c

Sender wählt a, sendet A = g^a
Empfänger wählt b:
  Falls c=0: sendet B = g^b
  Falls c=1: sendet B = A · g^b = g^(a+b)

Sender berechnet:
  k₀ = H(B^a)     k₁ = H((B/A)^a)
  Sendet: E(k₀, M₀), E(k₁, M₁)

Empfänger berechnet:
  k_R = H(A^b)
  Falls c=0: k_R = H(g^(ab)) = k₀  → entschlüsselt M₀
  Falls c=1: k_R = H(g^(ab)) = k₁  → entschlüsselt M₁
```

### 22.3 Garbled Circuits

**Definition:** Garbled Circuits (Yao, 1986) ermöglichen es, eine beliebige Boolesche Funktion als verschlüsselten Schaltkreis zwischen zwei Parteien sicher auszuwerten.

**Ablauf:**

1. **Alice (Garbler) erstellt den verschlüsselten Schaltkreis:**
   - Für jeden Draht werden zwei zufällige Labels erzeugt: L^0_i (für Bit 0) und L^1_i (für Bit 1)
   - Für jedes Gatter (AND, OR, XOR): Die Wahrheitstabelle wird mit den Input-Labels verschlüsselt
   - Die Zeilen der Wahrheitstabelle werden **zufällig permutiert** (kein Bit-Leak)

2. **Bob (Evaluator) wertet aus:**
   - Empfängt den „garbled circuit"
   - Kann pro Gatter genau **eine** Zeile entschlüsseln (die passende zu seinen Labels)
   - Lernt nur das Endergebnis, nicht die Zwischenwerte

3. **Eingaben:**
   - **Alice** gibt ihre Labels direkt weiter
   - **Bob** erhält seine Eingabe-Labels via **Oblivious Transfer** (Alice erfährt nicht, welche Bits Bob hat)

**Sicherheit:**
- Alice lernt nichts über Bobs Eingabe (durch OT)
- Bob lernt nichts über Alices Eingabe (Labels verraten keine Bits)
- Beide lernen nur f(A, B)

**Beispiel:** Boole'sche Funktion `f = AND(a, b)` als Garbled Circuit:
- Drähte erhalten Labels: Wire_a: (L^0_a, L^1_a); Wire_b: (L^0_b, L^1_b)
- Ausgabe-Labels: (L^0_out, L^1_out)
- Verschlüsselte Wahrheitstabelle (permutiert):
  - `Enc(L^1_a, L^1_b, L^1_out)` (1 AND 1 = 1)
  - `Enc(L^0_a, L^1_b, L^0_out)` (0 AND 1 = 0)
  - usw.

### 22.4 Additive Secret Sharing

**Definition:** Ein Geheimnis x wird so in n Anteile (Shares) aufgeteilt, dass jede echte Teilmenge der Shares **keine Information** über x verrät.

**Aufteilen (n Parteien):**
```
Wähle x₁, x₂, ..., x_{n-1} zufällig
Setze x_n = x - (x₁ + ... + x_{n-1}) mod q
Verteile [x] = (x₁, ..., x_n)
```

**Rekonstruktion:** `x = x₁ + x₂ + ... + x_n mod q`

**Sicherheit:** Informationstheoretisch – auch mit unbegrenzter Rechenleistung lässt sich aus n-1 Shares nichts ableiten.

**Addition trivial möglich:**
```
[x + y] = ([x] + [y]) = (x₁+y₁, ..., x_n+y_n)  ← jede Partei addiert lokal
[x + c] = (x₁+c, x₂, ..., x_n)                   ← nur der erste Share wird angepasst
```

**Multiplikation NICHT trivial:** Das Produkt zweier Shares ergibt kein Share des Produkts. Lösung: **Beaver Triples**.

### 22.5 Beaver Triples

**Definition:** Ein Beaver Triple ist ein vorberechnetes Tripel `([a], [b], [c])` mit `c = a · b`, wobei a und b zufällig sind.

**Multiplikationsprotokoll für [x · y]:**
1. Parteien öffnen (veröffentlichen): `d = x - a` und `e = y - b`
   (Da a und b zufällig sind, verraten d und e nichts über x und y)
2. Berechne:
   ```
   x · y = d·e + d·[b] + e·[a] + [c]
   ```
   - `d·e`: öffentliche Konstante
   - `d·[b]` und `e·[a]`: Multiplikation mit öffentlicher Konstante (einfach)
   - `[c]`: bereits als Share vorhanden

**Vorteil:** Die aufwändige Erzeugung der Triples kann in einer **Offline-Phase** vor der eigentlichen Berechnung stattfinden (z.B. mit Homomorpher Verschlüsselung oder OT).

**SPDZ-Protokoll (2012):** Kombiniert Additive Secret Sharing, Beaver Triples und MACs auf den Shares. Sicher gegen aktive Angreifer, die bis zu n-1 Parteien kontrollieren.

---

## 23. Zero Knowledge Proofs (ZKP)

### 23.1 Was ist Zero Knowledge?

**Definition:** Ein Zero-Knowledge-Beweis ermöglicht es einem **Prover**, einem **Verifier** zu beweisen, dass eine Aussage wahr ist, ohne **irgendwelche weiteren Informationen** preiszugeben – insbesondere nicht das Geheimnis, das die Wahrheit belegt.

**Motivationsbeispiele:**
- „Ich bin älter als 18" beweisen, ohne das Geburtsdatum preiszugeben
- „Ich kenne die Lösung dieses Rätsels" beweisen, ohne die Lösung zu zeigen
- „Ich habe die Signatur der Nachricht" beweisen, ohne den privaten Schlüssel zu zeigen

### 23.2 Drei Eigenschaften

| Eigenschaft | Bedeutung | Beschreibung |
|---|---|---|
| **Completeness (Vollständigkeit)** | Wenn die Aussage wahr ist, überzeugt der Prover den Verifier | Ein ehrlicher Prover mit dem Geheimnis wird immer akzeptiert |
| **Soundness (Korrektheit)** | Wenn die Aussage falsch ist, kann kein Prover den Verifier überzeugen | Ein betrügender Prover wird höchstens mit vernachlässigbarer Wahrscheinlichkeit akzeptiert |
| **Zero Knowledge** | Der Verifier lernt nichts außer der Tatsache, dass die Aussage wahr ist | Das Transkript des Protokolls kann vom Verifier selbst simuliert werden |

### 23.3 Beispiel: Graph-Isomorphismus

**Problem:** Prover kennt einen Isomorphismus π zwischen zwei Graphen G₀ und G₁ (d.h. G₁ = π(G₀)) und möchte das beweisen, ohne π preiszugeben.

**Protokoll (eine Runde):**
1. **Prover** wählt zufällige Permutation σ; berechnet H = σ(G_b) für zufälliges b ∈ {0,1}; sendet H
2. **Verifier** sendet Challenge-Bit c ∈ {0,1}
3. **Prover** antwortet:
   - Falls c = b: sendet σ (H = σ(G_b))
   - Falls c ≠ b: sendet σ ∘ π (bzw. σ ∘ π⁻¹)
4. **Verifier** prüft: Bildet die Antwort H korrekt auf G_c ab?

**Zero Knowledge?** Ja – der Prover wählt b zufällig. Der Verifier sieht immer nur eine zufällige Permutation eines der Graphen, was er selbst hätte erzeugen können.

**Soundness?** Ja – wenn G₀ und G₁ nicht isomorph sind, kann der Prover für genau eines von b=c und b≠c antworten. In 50% der Fälle wird er erwischt. Nach k Runden: Betrugswahrscheinlichkeit = (1/2)^k.

### 23.4 Diskreter Logarithmus als ZK-Proof (Schnorr-Protokoll)

**Problem:** Prover kennt x mit g^x = h mod p (diskreter Logarithmus).

**Protokoll:**
```
1. Prover wählt zufälliges r, berechnet Commitment: a = g^r mod p → sendet a
2. Verifier sendet zufällige Challenge c
3. Prover antwortet: z = r + c·x mod (p-1)
4. Verifier prüft: g^z ≡ a · h^c (mod p)
```

**Korrektheit:** `g^z = g^(r + cx) = g^r · (g^x)^c = a · h^c ✓`

**Zero Knowledge:** Simulierbar ohne x (Simulator wählt z und c zufällig, berechnet a = g^z / h^c rückwärts).

### 23.5 ZK-Proof für weitere Probleme

| Problem | Öffentlich | Geheim |
|---|---|---|
| Graph-Isomorphismus | G₀, G₁ | Isomorphismus π |
| Diskreter Logarithmus | g, h = g^x | x |
| Quadratischer Rest | n, y | x mit x² ≡ y mod n |
| Signatur-Schema | Public Key | Secret Key |

### 23.6 Fiat-Shamir Transformation (→ Signaturschema)

*(Vollständig beschrieben in Abschnitt 15.5)*

**Kernidee:** Challenge = H(Commitment, Nachricht). Macht interaktive ZK-Proofs nicht-interaktiv und ermöglicht digitale Signaturen aus ZK-Proofs.

### 23.7 MPC in the Head

**Definition:** Eine Technik, um Zero-Knowledge-Beweise aus MPC-Protokollen zu konstruieren.

**Idee:**
1. Prover **simuliert** ein MPC-Protokoll im Kopf (spielt alle Parteien selbst)
2. Teilt sein Geheimnis in Shares auf und führt das Protokoll virtuell durch
3. **Committet** auf alle Transkripte der virtuellen Parteien
4. Verifier wählt eine Teilmenge der Parteien aus → Prover öffnet deren Transkripte
5. **Zero Knowledge:** Verifier sieht nur einen Teil → kann Geheimnis nicht rekonstruieren
6. **Soundness:** Prover hat sich durch Commitments festgelegt → kein Betrug möglich

**Vorteil:** Jedes MPC-Protokoll kann automatisch in einen ZK-Proof umgewandelt werden. Grundlage für PICNIC (Post-Quantum-Signaturschema).

---

## 24. Differential Privacy

### 24.1 Motivation und Kernproblem

**Problem:** Wie kann man statistische Analysen auf sensiblen Daten veröffentlichen, ohne Individuen zu identifizieren?

**Naives Beispiel:** In einer Umfrage „Haben Sie schon einmal gestohlen?" lügen Befragte aus Angst vor Konsequenzen.

### 24.2 Randomized Response

**Lösung:** **Münzwurf-Technik** für plausible Abstreitbarkeit.

**Protokoll:**
1. Befragter wirft eine Münze (privat)
2. **Kopf** → Wahrheit sagen
3. **Zahl** → Lügen (entgegengesetzte Antwort)

**Analyse:** In 3/4 der Fälle steht die richtige Antwort (Kopf+Ja oder Zahl+Nein für einen Nein-Sager).

**Rückrechnung** des echten „Ja"-Anteils:
```
Echter "Ja"-Anteil = 2 × (Gemessener "Ja"-Anteil - 0,25)
```

**Beispiel:** 37,5% gemessene „Ja"-Antworten → echter Anteil = 2 × (0,375 - 0,25) = **25%**

**Vorteil:** Jede individuelle Antwort ist **plausibel abstreitbar** – niemand kann beweisen, ob eine Person die Wahrheit sagte.

### 24.3 Formale Definition (ε-Differential Privacy)

**Definition:** Ein Mechanismus M erfüllt **ε-Differential Privacy**, wenn für alle benachbarten Datensätze D, D' (die sich in genau einem Eintrag unterscheiden) und alle möglichen Ausgaben S gilt:
```
Pr[M(D) ∈ S] ≤ e^ε · Pr[M(D') ∈ S]
```

**Parameter ε (Privacy Budget):**
- **Kleines ε** → mehr Privatsphäre, weniger Genauigkeit
- **Großes ε** → weniger Privatsphäre, mehr Genauigkeit
- Typisch: ε ≤ 1 für starke Privacy

**Sensitivität** einer Funktion f: Wie stark ändert sich f, wenn ein einzelner Datensatz entfernt wird?
```
Δf = max_{D,D' benachbart} ||f(D) - f(D')||
```
Bestimmt die Stärke des Rauschens.

### 24.4 Mechanismen

| Mechanismus                    | Beschreibung                                          | Anwendung                       |
| ------------------------------ | ----------------------------------------------------- | ------------------------------- |
| **Laplace-Mechanismus**        | Addiert Rauschen ~ Laplace(0, Δf/ε)                   | Numerische Abfragen             |
| **Gaußscher Mechanismus**      | Addiert Gaußsches Rauschen; benötigt (ε, δ)-DP        | Wenn etwas Lockerung akzeptabel |
| **Exponentieller Mechanismus** | Wählt Ergebnis mit exp-gewichteter Wahrscheinlichkeit | Nicht-numerische Ausgaben       |

---

## 25. Trusted Execution Environments (TEE)

### 25.1 Motivation

**Virtual Black Box Obfuscator (Ideallösung):** Ein Programm so verschleiern, dass man es ausführen, aber nicht verstehen kann. **Problem:** Unmöglich zu konstruieren (Barak et al., 2001).

**TEE als praktischer Kompromiss:** Statt Software-Obfuskation nutzt man Hardware-Isolation.

### 25.2 TEE-Architektur (Enklave)

**Definition:** Ein **Trusted Execution Environment** ist ein hardware-geschützter Bereich (Enklave) auf einem Prozessor, in dem Code und Daten sicher verarbeitet werden.

**Schlüsseleigenschaften:**
- **Hardware-Isolation:** Selbst ein kompromittiertes Betriebssystem hat keinen Zugriff auf Enklaven-Daten
- **Verschlüsselter Speicher:** Alle Daten werden beim Verlassen der Enklave verschlüsselt
- **Attestierung:** Die Hardware kann kryptographisch beweisen, welcher Code in der Enklave läuft

**Ablauf:**
```
Externe Partei  →  Verschlüsselte Daten  →  Enklave
                                              ↓ (nur hier entschlüsselt)
                                         Attestierter Code
                                              ↓
                                         Verschlüsselte Ergebnisse  →  Externe Partei
```

**Beispiele:** Intel SGX, ARM TrustZone, AMD SEV

**Attestierung:** Externe Parteien können prüfen, dass tatsächlich der korrekte Code in der Enklave läuft (kryptographische Signatur der Hardware). Verhindert, dass der Betreiber manipulierten Code einschleust.

**Einschränkungen:** Side-Channel-Angriffe (z.B. SGX wurde mehrfach durch Spectre-ähnliche Angriffe kompromittiert), TEE vertraut der Hardware des Herstellers.

---

## 26. Privacy-Schutzziele & Technologien

### 26.1 Drei Dimensionen von Datenschutz

| Zustand             | Schutzziel                                 | Beispiel                  |
| ------------------- | ------------------------------------------ | ------------------------- |
| **Data at Rest**    | Vertraulichkeit, Integrität                | Verschlüsselte Festplatte |
| **Data in Transit** | Vertraulichkeit, Integrität, Authentizität | TLS                       |
| **Data in Use**     | Vertraulichkeit während Verarbeitung       | HE, MPC, TEE              |

### 26.2 Erweiterte Privacy-Ziele

| Ziel | Bedeutung |
|---|---|
| **Input Privacy** | Eingabedaten der Datenlieferanten werden geschützt |
| **Output Privacy** | Ergebnisse schützen Informationen über Individuen |
| **Policy Enforcement** | Nutzungsregeln werden technisch/rechtlich durchgesetzt |

### 26.3 Privacy Enhancing Technologies (PET) – Gesamtübersicht

| Technologie | Input Privacy | Output Privacy | Policy Enforcement |
|---|---|---|---|
| **MPC** | ✅ | — | — |
| **TEE** | ✅ | — | — |
| **Homomorphe Verschlüsselung (HE/FHE)** | ✅ | — | — |
| **Zero Knowledge Proofs** | ✅ | — | — |
| **Differential Privacy** | — | ✅ | — |
| **Aggregation** | — | ✅ | — |
| **Non-Disclosure Agreements (NDA)** | — | — | ✅ |

---

## Schnellreferenz: Wichtige Formeln

| Konzept                      | Formel                              |
| ---------------------------- | ----------------------------------- |
| Caesar                       | E(x) = (x+n) mod 26                 |
| Vigenère                     | C_i = (M_i + K_i) mod 26            |
| OTP                          | E = P ⊕ K                           |
| Shannon Perfect Secrecy      | H(M\|E) = H(M)                      |
| Entropie                     | H(X) = -Σ p_x · log₂(p_x)           |
| RSA Verschlüsselung          | c = m^e mod n                       |
| RSA Entschlüsselung          | m = c^d mod n                       |
| RSA Signatur                 | s = m^d mod n                       |
| DH gemeinsames Geheimnis     | K = g^(ab) mod p                    |
| HMAC                         | H((k⊕opad) \|\| H((k⊕ipad)\|\|m))   |
| Beaver Triple Multiplikation | xy = de + d[b] + e[a] + [c]         |
| Fiat-Shamir Challenge        | ch = H(Commitment, Nachricht)       |
| DP Formel                    | Pr[M(D)∈S] ≤ e^ε · Pr[M(D')∈S]      |
| DP Rückrechnung              | Echter Anteil = 2×(gemessen - 0,25) |
| AES irreduzibles Polynom     | m(x) = x⁸ + x⁴ + x³ + x + 1         |
| Paillier Verschlüsselung     | c = g^m · r^n mod n²                |
| Paillier Homomorphie         | D(E(m₁)·E(m₂)) = m₁+m₂ mod n        |

---

## Schnellreferenz: Wichtige Definitionen

| Begriff                        | Kurzdefinition                                                                                                  |
| ------------------------------ | --------------------------------------------------------------------------------------------------------------- |
| **Perfect Secrecy**            | Geheimtext verrät keinerlei Information über Klartext (H(M\|E) = H(M))                                          |
| **OWF**                        | Leicht zu berechnen, praktisch unmöglich umzukehren                                                             |
| **PRG**                        | Streckt kurzen Seed zu ununterscheidbarem langen Pseudozufallsstring                                            |
| **Comp. Indistinguishability** | Kein effizienter Algorithmus kann zwei Verteilungen mit messbarem Vorteil unterscheiden                         |
| **IND-CPA**                    | Angreifer kann bei Zugriff auf Verschlüsselungsorakel nicht unterscheiden, welche Nachricht verschlüsselt wurde |
| **IND-CCA2**                   | Wie IND-CPA + adaptiver Zugriff auf Entschlüsselungsorakel (außer Challenge-CT)                                 |
| **MAC**                        | Kurzer Tag, der Integrität und Authentizität (nicht Vertraulichkeit) sichert                                    |
| **AEAD**                       | Kombiniert Verschlüsselung + Authentifizierung in einem Algorithmus                                             |
| **Feistel-Netzwerk**           | Blockchiffre-Struktur: L_{i+1}=R_i, R_{i+1}=L_i⊕F(R_i,K_i); F muss nicht invertierbar sein                      |
| **Padding Oracle Attack**      | Angriff auf CBC: nutzt Unterscheidung zwischen Padding-Fehlern aus                                              |
| **Cipher Text Stealing**       | Vermeidet Padding, indem letzter vollständiger + unvollständiger Block kombiniert werden                        |
| **Shors Algorithmus**          | Löst Faktorisierung und DLP in polynomialer Zeit → bricht RSA, DH, ECDH                                         |
| **Grovers Algorithmus**        | Suche in O(√N) → halbiert effektive Schlüssellänge symmetrischer Verfahren                                      |
| **LWE**                        | Learning With Errors: schweres Gitterproblem, Basis für PQC                                                     |
| **Oblivious Transfer**         | Sender weiß nicht, welche seiner Nachrichten der Empfänger erhalten hat                                         |
| **Garbled Circuit**            | Verschlüsselter Boole'scher Schaltkreis; ermöglicht sichere Zweikparteienberechnung                             |
| **Beaver Triple**              | Vorberechnetes (a, b, c=ab)-Tripel für effiziente MPC-Multiplikation                                            |
| **ZK-Proof (Zero Knowledge)**  | Beweis der Wahrheit einer Aussage ohne Preisgabe weiterer Informationen                                         |
| **Fiat-Shamir**                | Macht interaktive ZK-Proofs nicht-interaktiv durch H(Commitment, Nachricht) als Challenge                       |
| **Differential Privacy**       | Statistischer Datenschutz: Pr[M(D)∈S] ≤ e^ε·Pr[M(D')∈S] für benachbarte D, D'                                   |
| **TEE/Enklave**                | Hardware-geschützter Ausführungsbereich; auch kompromittiertes OS hat keinen Zugriff                            |
| **Zertifikat (X.509)**         | Digitale Bestätigung einer CA: bindet Public Key an Identität                                                   |
| **Chain of Trust**             | Hierarchische Vertrauenskette: Endnutzer-Zertifikat ← CA ← Root CA                                              |
| **CRL**                        | Liste widerrufener Zertifikate, periodisch veröffentlicht                                                       |
| **OCSP**                       | Echtzeitabfrage des Zertifikatstatus bei einem Responder-Server                                                 |
| **BB84**                       | Quantenschlüsselaustausch; sicher durch No-Cloning-Theorem; Eve-Abhören detektierbar                            |
| **MPC in the Head**            | ZK-Proofs durch Simulation eines MPC-Protokolls im Kopf des Provers                                             |

---

*Tags: #Kryptographie #HWR #Klausur #Zusammenfassung #Kryptografische_Primitive #Symmetrisch #Asymmetrisch #AES #RSA #TLS #PostQuantum #MPC #ZeroKnowledge #DifferentialPrivacy #TEE*