Diffie-Hellman
Wie sich Alia und Ben vor der ganzen Klasse auf einen geheimen Schlüssel einigen
Alia und Ben wollen sich geheime Botschaften schicken, etwa mit einem Codewort. Dafür brauchen beide denselben Schlüssel. Aber wie einigen sie sich darauf, wenn die ganze Klasse mithört? Whitfield Diffie und Martin Hellman haben 1976 einen Weg gefunden: Beide rechnen mit Potenzen im Kreis, also modulo einer Primzahl p. Dabei hilft eine besondere Eigenschaft: gᵃ mod p auszurechnen geht schnell, aber aus dem Ergebnis a zurückzugewinnen ist schwer.
Schritt für Schritt
Du kannst alle Zahlen ändern: Wähle eine andere Primzahl, oder lass dir neue Geheimzahlen zufällig aussuchen.
Alia und Ben einigen sich vor der ganzen Klasse auf eine Primzahl p und einen g.
Ein Erzeuger ist eine Zahl g, deren Potenzen g¹, g², g³, … modulo p alle Zahlen von 1 bis p − 1 treffen, bevor sie sich wiederholen. Je mehr Zahlen herauskommen können, desto mehr muss ein Lauscher ausprobieren.
Öffentlich – das hört die ganze Klasse mit
Jeder wählt eine geheime Zahl und verrät sie niemandem: Alia wählt a, Ben wählt b.
Alia
erlaubt: 2 bis 27
🔒 kennt nur Alia
Ben
erlaubt: 2 bis 27
🔒 kennt nur Ben
Alia rechnet A = gᵃ mod p, Ben rechnet B = gᵇ mod p. Beide rufen ihr Ergebnis laut in die Klasse.
Alia
Ben
Jetzt hört die ganze Klasse: A = und B = .
Wie rechnet man das aus?
Alia rechnet Bᵃ mod p, Ben rechnet Aᵇ mod p.
Alia
Ben
Gemeinsamer Schlüssel:
Zweimal dieselbe Zahl – Zufall? Nein: Ab = (ga)b = ga·b = (gb)a = Ba, und das gilt auch, wenn man nach jedem Schritt nur den Rest modulo p behält.
Der Lauscher hat alles mitgehört. Für den Schlüssel bräuchte er a oder b. Findet er sie heraus?
Er kennt p = , g = , A = und B = . Er kennt nicht a, b und den Schlüssel. Er kann aber alle Exponenten ausprobieren, bis gx mod p = A herauskommt.
Weiter
Arbeitsblätter zu Diffie-Hellman und RSA stehen bei RSA & Primzahlen.