Diffie-Hellman-Schlüsselaustausch

Symmetrische Verschlüsselungsverfahren bieten vor allem im Bezug auf die Geschwindigkeit einen großen Vorteil. Ein zentrales Problem ist dabei aber die große Anzahl von Schlüsseln und deren sicherer Austausch zwischen den Kommunkationspartnern.

Die zentrale Frage ist: Kann man einen Schlüssel über ein unsicheres Medium austauschen?
Die Wissenschaflter Whitfield Diffie und Martin Hellman haben 1976 festgestellt: Ja, man kann.

Der Algorithmus in Farbe

Die Mathematik hinter dem Algorithmus ist leider nicht ganz einfach zu verstehen. Dafür gibt es aber eine schöne Analogie mit Farben, die man zum Verständnis nutzen kann.

Der Ablauf:

1. Alice und Bob einigen sich auf eine gemeinsame (öffentliche) Farbe.
2. Jeder wählt sich zudem eine geheime weitere Farbe.
3. Alice und Bob mischen sich aus ihrer geheimen und der öffentlichen Farbe eine weitere Farbe.

Sie schicken jeweils die neu gemischte Farbe zu ihrem Kommunikationspartner.

Am Ende mischt jeder seine geheime Farbe in die zuvor ausgetauschten Mischfarbe.

Die gemeinsame Farbe am Ende des Prozesses besteht also aus drei gemischten Farben. Und Eve in der Mitte?
Sie hat nur die öffentliche Farbe und zwei gemischte Farben. Und wie du vielleicht aus dem Kunstunterricht weißt, ist es ziemlich schwierig, aus einer Mischfarbe zu erkennen, welche Ausgangsfarben genau darin stecken.

Du kannst das hier einmal selbst nachspielen:

Der Algorithmus mit Zahlen

Das mathematische Verfahren beruht auf dem sog. "modularen Potenzieren", das du vielleicht noch im Kapitel zum RSA-Verfahren kennenlernen wirst. Auch wenn der mathematische Hintergrund nicht so einfach zu verstehen ist, kannst du das Verfahren aber sicherlich einmal hier nachvollziehen. Die wesentlichen Schritte sind (ganz analog zu den Farben oben) die Folgenden:
(Zur Erinnerung: Modulo (mod) ist eine Funktion, die den Rest einer Division berechnet.)

1. Alice und Bob einigen sich auf zwei öffentliche Zahlen: Eine (in der Wirklichkeit sehr große) Primzahl p und eine (kleinere) Zahl g.
2. Beide wählen sich jeweils eine zufällige Zahl (Alice: x und Bob: y).
3. Aus der öffentlichen und ihrer geheimen Zahl berechnen beide jeweils eine neue Zahl
   Alice: a = g^x mod p
   Bob: b = g^y mod p
4. Diese Zahlen werden wieder ausgetauscht und damit können dann beide den gemeinsamen Schlüssel berechnen:
   Alice: schlüssel = b^x mod p
   Bob: schlüssel = a^y mod p

Du kannst das hier einmal ausprobieren:

Aufgabe

Versuche einmal mit einem Python-Dialog diese Rechnung nachzuvollziehen.
Beachte vor allem, welche riesigen Zahlen bei den Potenzen entstehen.

Hintergrund: Um diese zu vermeiden, gibt es besonderes Verfahren zum schnellen modularen Potenzieren, das du ebenfalls im Kapitel zu RSA kennenlernen kannst.

Gemeinsame Zahlen (Öffentlicher Schlüssel)
p (Primzahl):
g (< p):
Alice x (zufällig)
Bob y (zufällig):
Berechnete öffentliche Werte:
Alice	a = gx mod p = gx mod p = #Wert
Bob	b = gy mod p = gy mod p = #Wert
Berechnete Schlüsselwerte:
Alice	schlüssel = bx mod p = bx mod p = #Wert
Bob	schlüssel = ay mod p = ay mod p = #Wert