Schlüsseltauschverfahren

• Problem: Symmetrische Verschlüsselung braucht einen sicheren Kanal zur Schlüsselverteilung – der oft nicht existiert.
• Diffie-Hellman (DH): Zwei Parteien vereinbaren über einen unsicheren Kanal einen gemeinsamen Schlüssel, ohne ihn je zu übertragen.
• Grundlage: Diskretes Logarithmusproblem (DLP) – aus $g^a \bmod p$ den Exponenten $a$ zu berechnen ist hart.
• Formel: $K = g^{ab} \bmod p = A^b \bmod p = B^a \bmod p$.
• Schwäche: Ohne Authentizität ist DH anfällig für Man-in-the-Middle-Angriffe.
• Varianten: ECDH (elliptische Kurven, kürzere Schlüssel) und ephemeres DH (Perfect Forward Secrecy).

Das Schlüsselverteilungsproblem

Symmetrische Verfahren wie AES sind schnell und sicher – wenn beide Parteien denselben geheimen Schlüssel haben. Aber wie tauscht man diesen Schlüssel aus, wenn der Kommunikationskanal selbst unsicher ist? Persönliche Übergabe skaliert nicht (bei $n$ Teilnehmern braucht man $\binom{n}{2} = \frac{n(n-1)}{2}$ Schlüssel).

Die geniale Idee von Diffie & Hellman (1976): Man tauscht den Schlüssel gar nicht aus – man berechnet ihn auf beiden Seiten separat, sodass er nur den beiden Beteiligten bekannt ist.

Diffie-Hellman-Schlüsselaustausch

Öffentliche Parameter (dürfen alle wissen):

• eine große Primzahl $p$
• ein Generator (primitives Element) $g \in \mathbb{Z}_p^*$

Ablauf:

1. Alice wählt geheim $a \in \{1, \dots, p-2\}$ und berechnet $A = g^a \bmod p$. Sie sendet $A$ an Bob.
2. Bob wählt geheim $b \in \{1, \dots, p-2\}$ und berechnet $B = g^b \bmod p$. Er sendet $B$ an Alice.
3. Alice berechnet $K = B^a \bmod p$.
4. Bob berechnet $K = A^b \bmod p$.

Beide erhalten denselben Wert, denn:

$$K = B^a = (g^b)^a = g^{ab} = (g^a)^b = A^b \pmod{p}$$

Ein Angreifer sieht nur $p, g, A, B$ – aus diesen Werten $a$ oder $b$ zu berechnen ist das diskrete Logarithmusproblem.

Diskretes Logarithmusproblem (DLP)

Gegeben $g, p, y = g^x \bmod p$. Gesucht: $x$.

Für kleine $p$ trivial (Brute-Force), aber für $p$ mit 2048+ Bit praktisch nicht lösbar. Die besten bekannten Algorithmen (Index-Calculus) haben subexponentielle Laufzeit.

Man-in-the-Middle-Angriff

Klassisches DH bietet keine Authentizität. Ein Angreifer Mallory kann sich in die Mitte setzen:

• Alice sendet $A = g^a$ → Mallory fängt ab, sendet $A' = g^m$ an Bob.
• Bob sendet $B = g^b$ → Mallory fängt ab, sendet $B' = g^m$ an Alice.
• Alice und Mallory teilen $K_{AM} = g^{am}$.
• Bob und Mallory teilen $K_{BM} = g^{bm}$.

Mallory entschlüsselt, liest mit, verschlüsselt neu – niemand merkt es.

Gegenmaßnahmen: Authentisierung der öffentlichen Werte, z. B. durch digitale Signaturen (RSA, DSA) oder Zertifikate (X.509). → Authenticated Diffie-Hellman.

ECDH – Elliptic Curve Diffie-Hellman

DH lässt sich auf jeder zyklischen Gruppe definieren, in der das DLP schwer ist. Statt $\mathbb{Z}_p^*$ verwendet ECDH die Gruppe der Punkte einer elliptischen Kurve.

• Statt $A = g^a \bmod p$ berechnet man $A = a \cdot G$ (Skalarmultiplikation eines Basispunkts $G$).
• Gemeinsamer Schlüssel: $K = a \cdot B = b \cdot A = (ab) \cdot G$.
• Vorteil: bei gleicher Sicherheit deutlich kürzere Schlüssel (256 Bit ECDH ≈ 3072 Bit klassisches DH).

Perfect Forward Secrecy (PFS)

Bei ephemerem DH (DHE / ECDHE) werden $a$ und $b$ pro Sitzung neu und zufällig gewählt – und nach Sitzungsende gelöscht.

Effekt: Wird der Langzeitschlüssel eines Servers später kompromittiert, sind bereits abgefangene und gespeicherte Sitzungen weiterhin geschützt, weil die Session-Keys nicht rekonstruierbar sind.

Aus diesem Grund verwendet TLS 1.3 ausschließlich ephemere Verfahren (ECDHE).

Karte 1 · Der DHKE-Ablauf in Miller-Notation

Öffentliche Parameter sind eine Primzahl $p$ und ein Erzeuger $s$ (Primitivwurzel modulo $p$). Miller schreibt $s$ statt $g$ und benutzt für die öffentlichen Werte griechische Buchstaben.

1. Vereinbarung: Alice und Bob einigen sich öffentlich auf $p$ und $s$.
2. Alice: wählt ihre geheime Zahl $a$ und berechnet $\varepsilon = s^a \bmod p$.
3. Bob: wählt seine geheime Zahl $b$ und berechnet $\vartheta = s^b \bmod p$.
4. Austausch: Alice sendet $\varepsilon$ an Bob, Bob sendet $\vartheta$ an Alice.
5. Gemeinsamer Schlüssel: $K = \vartheta^{\,a} \bmod p = \varepsilon^{\,b} \bmod p$.

Öffentlich (jeder darf sehen)	Geheim (nur der Besitzer)
$p$, $s$, $\varepsilon$, $\vartheta$	$a$ (bei Alice), $b$ (bei Bob), $K$ (bei beiden)

Karte 2 · Warum funktioniert das? Korrektheitsbeweis

Beide Seiten kommen auf denselben Wert, weil das Kommutativgesetz im Exponenten gilt:

$$\vartheta^{\,a} = (s^b)^a = s^{ab} = (s^a)^b = \varepsilon^{\,b} \pmod{p}.$$

Alice rechnet $\vartheta^{\,a}$, Bob rechnet $\varepsilon^{\,b}$ – beide Ausdrücke sind gleich $s^{ab} \bmod p$. Ein Lauscher sieht nur $\varepsilon$ und $\vartheta$, müsste aber $a$ oder $b$ aus $\varepsilon = s^a \bmod p$ zurückrechnen (diskreter Logarithmus).

Karte 3 · Primitivwurzel-Test

Variante 1 – Brute-Force (Millers Rezept, Folie S.70)

1. $x := 1$, $n := 1$
2. $x := x \cdot s \bmod p$, $n := n + 1$
3. falls $x \neq 1$ → zurück zu (2)
4. falls $n = p$ → $s$ ist Primitivwurzel von $p$

Miller merkt an: leider für grosse Zahlen sehr aufwändig.

Variante 2 – Sichere Primzahl ($p = 2q+1$ mit $q$ prim)

• $|\{\text{PW}\}| = \varphi(p-1) = q-1$
• falls $s^2 \equiv 1 \bmod p$ oder $s^q \equiv 1 \bmod p$ → keine Primitivwurzel
• sonst → Primitivwurzel

Konkretes Beispiel – $s=3$ ist Primitivwurzel von $p=7$

Wir potenzieren $3$ modulo $7$ und beobachten, ob alle Werte $\{1,\dots,6\}$ erzeugt werden:

$$3^1 \equiv 3,\ 3^2 \equiv 2,\ 3^3 \equiv 6,\ 3^4 \equiv 4,\ 3^5 \equiv 5,\ 3^6 \equiv 1 \pmod{7}.$$

Alle $6 = p-1$ Restklassen kommen genau einmal vor → $3$ ist Primitivwurzel von $7$.

Gegenbeispiel – $s=2$ ist keine Primitivwurzel von $p=7$

$$2^1 \equiv 2,\ 2^2 \equiv 4,\ 2^3 \equiv 1 \pmod{7}.$$

Schon nach drei Schritten wiederholt sich der Zyklus, es werden nur $\{1,2,4\}$ erzeugt. $2$ hat Ordnung $3 \neq p-1 = 6$ → keine Primitivwurzel.

Karte 4 · Klausur-Aufgabe komplett gelöst – $p=17$, $s=7$, $a=5$, $b=6$

(a) Ist $s = 7$ eine Primitivwurzel von $p = 17$?

Brute-Force nach Variante 1: berechne $7^n \bmod 17$ für $n = 1, \dots, 16$.

$n$	$7^n \bmod 17$	Rechnung
1	7	$7$
2	15	$49 = 2\cdot17 + 15$
3	3	$15\cdot7 = 105 = 6\cdot17 + 3$
4	4	$3\cdot7 = 21 = 17 + 4$
5	11	$4\cdot7 = 28 = 17 + 11$ → $\varepsilon$
6	9	$11\cdot7 = 77 = 4\cdot17 + 9$ → $\vartheta$
7	12	$9\cdot7 = 63 = 3\cdot17 + 12$
8	16	$12\cdot7 = 84 = 4\cdot17 + 16$
9	10	$16\cdot7 = 112 = 6\cdot17 + 10$
10	2	$10\cdot7 = 70 = 4\cdot17 + 2$
11	14	$2\cdot7 = 14$
12	13	$14\cdot7 = 98 = 5\cdot17 + 13$
13	6	$13\cdot7 = 91 = 5\cdot17 + 6$
14	8	$6\cdot7 = 42 = 2\cdot17 + 8$
15	5	$8\cdot7 = 56 = 3\cdot17 + 5$
16	1	$5\cdot7 = 35 = 2\cdot17 + 1$

Alle $16 = p-1$ Restklassen $\{1,\dots,16\}$ werden getroffen, $7^{16} \equiv 1$ erst am Schluss. → $s = 7$ ist Primitivwurzel von $p = 17$, die Parameter sind geeignet.

(b) Öffentliche Werte und gemeinsamer Schlüssel

Aus der Tabelle lesen wir ab:

$$\varepsilon = 7^5 \bmod 17 = 11, \qquad \vartheta = 7^6 \bmod 17 = 9.$$

Alice rechnet $K = \vartheta^{\,a} = 9^5 \bmod 17$ per Square-and-Multiply:

$$9^2 = 81 \equiv 13,\quad 9^4 = 13^2 = 169 \equiv 16,\quad 9^5 = 9^4 \cdot 9 = 16 \cdot 9 = 144 \equiv 8 \pmod{17}.$$

Bob rechnet $K = \varepsilon^{\,b} = 11^6 \bmod 17$:

$$11^2 = 121 \equiv 2,\quad 11^4 = 2^2 = 4,\quad 11^6 = 11^4 \cdot 11^2 = 4 \cdot 2 = 8 \pmod{17}.$$

$K = 8$

(c) Verschiebe-Chiffre mit $k = 8$ auf m = NOTSECRET

Alphabet A=0, …, Z=25, jeder Buchstabe $+8 \bmod 26$:

Klartext	N	O	T	S	E	C	R	E	T
Index	13	14	19	18	4	2	17	4	19
$+8 \bmod 26$	21	22	1	0	12	10	25	12	1
Chiffrat	v	w	b	a	m	k	z	m	b

c = vwbamkzmb

(d) Brute-Force-Angriff: aus $\varepsilon = 11$ die geheime Zahl $a$ zurückrechnen

Der Angreifer testet $a \in \{2, 3, \dots, 15\}$, ob $7^a \equiv 11 \bmod 17$ gilt. Aus der Tabelle in (a) sieht man: $7^5 \equiv 11$ – also enthüllt $a = 5$. Bei $p = 17$ genügen also höchstens $14$ Versuche. In realen Anwendungen ist $p$ jedoch mehrere hundert Stellen lang; dann ist das Bruteforcen nicht mehr durchführbar.

(e) Warum sind $a = 1$ und $a = p-1 = 16$ verboten?

• $a = 1$: dann ist $\varepsilon = s^1 = s$, also gleich dem öffentlich bekannten Erzeuger. Ein Angreifer sieht auf einen Blick, dass $a = 1$ ist.
• $a = p-1 = 16$: nach dem kleinen Satz von Fermat gilt $s^{p-1} \equiv 1 \bmod p$, also $\varepsilon = 1$. Auch das ist sofort erkennbar.

Zulässig sind daher nur geheime Exponenten $a \in \{2, 3, \dots, p-2\}$.

Karte 5 · Ägyptisches Potenzieren (Square-and-Multiply)

Miller nennt das Verfahren ägyptisches Potenzieren. Man schreibt den Exponenten binär, liest ihn von links (MSB) nach rechts (LSB), quadriert bei jedem Schritt und multipliziert zusätzlich mit $s$, wenn das aktuelle Bit $1$ ist. Nach jedem Schritt reduziert man modulo $p$.

Rezept

1. Setze $r := 1$.
2. Für jedes Bit des Exponenten (von MSB nach LSB): $r := r^2 \bmod p$; falls Bit $=1$, zusätzlich $r := r \cdot s \bmod p$.
3. Am Ende ist $r = s^a \bmod p$.

Mini-Beispiel – $7^5 \bmod 17$

Der Exponent $5 = 101_2$ hat die Bits MSB $1, 0, 1$ LSB.

Bit	Quadrieren	Multiplizieren (falls Bit=1)	$r \bmod 17$
1 (MSB)	$1^2 = 1$	$1 \cdot 7 = 7$	7
0	$7^2 = 49 \equiv 15$	–	15
1 (LSB)	$15^2 = 225 \equiv 4$	$4 \cdot 7 = 28 \equiv 11$	11

Ergebnis: $7^5 \bmod 17 = 11$ – stimmt mit der Tabelle aus Aufgabe (a) überein.

Karte 6 · Middle-Person-Attacke

Miller nennt den Angriff Middle-Person-Attacke (nicht MITM). Der Angreifer Mallory setzt sich unbemerkt in die Leitung zwischen Alice und Bob und führt zwei getrennte DHKE-Läufe: einen mit Alice (in dem er sich als Bob ausgibt) und einen mit Bob (als Alice).

1. Mallory wählt eine eigene geheime Zahl $x$ und berechnet $\varepsilon_M = s^x \bmod p$.
2. Alice sendet $\varepsilon$ Richtung Bob, Mallory fängt ab und schickt Alice sein $\varepsilon_M$ zurück. Alice glaubt, das sei $\vartheta$ von Bob, und rechnet $K_{A} = \varepsilon_M^{\,a} = s^{xa}$.
3. Umgekehrt genauso mit Bob: Mallory schickt ihm $\varepsilon_M$ statt Alices $\varepsilon$; Bob rechnet $K_{B} = \varepsilon_M^{\,b} = s^{xb}$.
4. Mallory kennt $x$ und aus dem echten $\varepsilon, \vartheta$ berechnet er $\varepsilon^{\,x} = s^{ax}$ (denselben Schlüssel wie Alice) und $\vartheta^{\,x} = s^{bx}$ (denselben wie Bob). Er entschlüsselt alles, liest mit und re-verschlüsselt an den jeweils anderen weiter.

Abwehr: Öffentliches Schlüsselverzeichnis (Repository der $\varepsilon$-Werte). Miller weist aber darauf hin, dass auch dieses Repository selbst angreifbar ist – die eigentliche Lösung ist eine authentifizierte Variante wie signiertes bzw. stationäres DH.

Karte 7 · DHE (Ephemeral) und Perfect Forward Secrecy

Was heisst Perfect Forward Secrecy? Ein Angreifer, der später den Langzeit-Schlüssel (z.B. den privaten RSA-Schlüssel eines Servers) erbeutet, kann damit trotzdem keine alten Sitzungen entschlüsseln, weil der Sitzungsschlüssel $K$ ausschliesslich aus den flüchtigen (ephemeralen) $a$ und $b$ abgeleitet wurde – und die sind nach dem Ende der Sitzung gelöscht worden.

Klausur-Frage (Übungsaufg. 17): Lässt sich Perfect Forward Secrecy bei RSA-Schlüsseltausch erreichen? Antwort: nein, weil das RSA-Schlüsselpaar statisch ist. Wer später den privaten Schlüssel bekommt, kann alle mit ihm ausgetauschten Sitzungsschlüssel rückwirkend entschlüsseln. PFS liefert ausschliesslich ephemerales DH (DHE bzw. ECDHE).

Karte 8 · Klausur-Checkliste für eine DHKE-Aufgabe

1. Parameter notieren: $p$, $s$, $a$, $b$ – Miller-Notation verwenden, nicht $g, A, B$.
2. Primitivwurzel prüfen (Variante 1 Brute-Force, für sichere Primzahlen Variante 2).
3. $\varepsilon = s^a \bmod p$ und $\vartheta = s^b \bmod p$ ausrechnen, per ägyptischem Potenzieren.
4. Gemeinsamen Schlüssel $K$ von beiden Seiten rechnen und vergleichen ($\vartheta^{\,a}$ vs. $\varepsilon^{\,b}$).
5. Anschluss-Teilaufgaben: Verschiebe-Chiffre mit $k = K$, Brute-Force auf $a$, verbotene Exponenten.

Typische Fallen:

• Notation vergessen: $s$ statt $g$, $\varepsilon$ statt $A$, $\vartheta$ statt $B$.
• Bit-Reihenfolge beim Square-and-Multiply verwechselt – Miller liest von MSB nach LSB.
• Kleiner Satz von Fermat übersehen: $a = p-1$ ist verboten, weil $\varepsilon = 1$ wird.
• $a = 1$ verboten, weil $\varepsilon = s$ verrät den geheimen Exponenten direkt.
• Modulo-Reduktion nach jedem Schritt vergessen – Zahlen explodieren sonst.