IMP 10 · Kryptologie und Rechner

Diffie-Hellman

Cäsar und Co. haben ein Problem: Wie kommt der Schlüssel zum Empfänger, wenn jemand mithört? Whitfield Diffie und Martin Hellman fanden 1976 einen Weg. Alice und Bob tauschen nur Öffentliches aus und kennen danach beide denselben Schlüssel, den Eve nicht kennt. Der Trick ist eine Rechnung, die in eine Richtung leicht und rückwärts schwer ist.

So gehst du vor

1Gehe das Farbspiel mit „Weiter“ durch und wähle selbst Farben.
2Stelle unten p, g, a und b ein und rechne eine Zeile von Hand nach.
3Beobachte, wie die Potenzen auf dem Zahlenkreis springen.
4Lass Eve probieren und bearbeite die Aufträge.

Mit Farben: leicht zu mischen, kaum zu entmischen

Alice

Offene Leitung (Eve hört mit)

Bob

Grundfarbe

Schritt 1: Alice und Bob einigen sich offen auf eine Grundfarbe. Jeder kann sie sehen.

Mit Zahlen: leicht zu potenzieren, kaum rückwärts zu rechnen

Die Linie verbindet g¹, g², g³, … modulo p. Gefüllte Punkte sind Reste, die als Potenz von g vorkommen.

Primzahl p

Basis g

Geheimzahl a von Alice

Geheimzahl b von Bob

Rechnung

Alice sendet A = g^a mod p = 5⁶ mod 23 = 8

Bob sendet B = g^b mod p = 5¹⁵ mod 23 = 19

Alice rechnet K = B^a mod p = 19⁶ mod 23 = 2

Bob rechnet K = A^b mod p = 8¹⁵ mod 23 = 2

Beide erhalten denselben Schlüssel, denn (g^b)^a = g^{a · b} = (g^a)^b.

g = 5 erzeugt alle 22 Reste von 1 bis 22. So hat Eve am meisten zu suchen.

Eve probiert

Eve kennt p = 23, g = 5, A = 8 und B = 19. Sie sucht einen Exponenten mit 5^k ≡ 8 (mod 23).

Mit p unter 100 ist Eve sofort fertig. In der Praxis hat p über 600 Stellen. Dann gibt es mehr Exponenten, als sich je durchprobieren lassen, während Alice und Bob mit Quadrieren und Multiplizieren nur wenige Tausend Rechenschritte brauchen.

Aufträge

Berechne von Hand für p = 23, g = 5, a = 6, b = 15 die Zahlen A, B und K. Reduziere nach jedem Schritt modulo 23.
Ordne zu: Was entspricht im Zahlenspiel der Grundfarbe, den Geheimfarben, den Mischungen und der gemeinsamen Farbe? Was entspricht dem Entmischen?
Stelle p = 23 ein und vergleiche g = 5 mit g = 2. Bestimme, wie viele verschiedene Reste jeweils vorkommen. Warum ist 5 die bessere Wahl?
Lass Eve bei drei verschiedenen Primzahlen probieren. Wie viele Versuche braucht sie höchstens? Schätze: Wie lange bräuchte sie bei einer Zahl mit 30 Stellen und einer Milliarde Versuchen je Sekunde?
Eve hört jetzt nicht nur zu, sondern fängt die Nachrichten ab und schickt eigene Zahlen weiter. Beschreibe, was dann passiert. Was fehlt dem Verfahren?