Schlüsselaustausch nach Diffie-Hellman

Diffie und Hellman entwickelten ein Verfahren, um das Schlüsselaustauschproblem zu umgehen. Mit Hilfe des Verfahrens einigt man sich über einen unsicheren Kanal auf einen Schlüssel, ohne dass Dritte ebenfalls an den Schlüssel kommen können. Zur Verschlüsselung ist das Verfahren nicht geeignet - hier müssen herkömmliche Algorithmen verwendet werden - aber nachdem der Schlüssel ausschliesslich den beiden Kommunikationspartnern bekannt ist, ist das kein Problem, da jetzt problemlos auch symmetrische Algorithmen angewendet werden können.

Die Sicherheit des Verfahrens beruht auf dem Problem des ,,diskreten Logarithmus``. Bei folgender Gleichung ist es sehr schwer, bei gegebenen $p$, $w$ und $n$ den Exponenten $x$ zu bestimmen:

$$p^x \equiv w \pmod{n}$$ (3)

Eine weitere wichtige Tatsache ist, dass sich folgende Schritte auch auf Modulo-Exponentationen übertragen lassen:

$$(a^b)^c = a^{b \cdot c} = (a^c)^b \Longrightarrow (a^b)^c = a^{b \cdot c} = (a^c)^b \pmod{n}$$ (4)

Diffie und Hellman nutzen diese beiden Tatsachen aus, um zwei Parteien über einen unsicheren, öffentlichen Kanal einen gemeinsamen, geheimen Schlüssel zu berechnen. Zunächst einigen sich die Kommunikationspartner auf zwei Zahlen $p$ und $n$. Zusätzlich werden je noch eine geheime Zufallszahl $x_1$ bzw. $x_2$ benötigt, die jede Partei lokal erzeugt. Diese Zahlen $x_1$ und $x_2$ werden nicht ausgetauscht. Die Partner berechnen nun

$$p^{x_i} \bmod n = w_i$$ (5)

und tauschen die Ergebnisse $w_1$ bzw. $w_2$ aus. Nun müssen beide Parteien nur noch das erhaltene Ergebnis mit ihrem eigenen geheimen $x$ potenzieren (und um $n$ reduzieren) und erhalten so das selbe Ergebnis.

Einer dritten Person ist das Ergebnis nicht bekannt, selbst wenn sie die gesamte Kommunikation mitverfolgt hat, da die Zahlen $p$ und $n$ sowie das Ergebnis $w$ keinen Rückschluss auf die verwendeten Werte für $x$ zulassen.

Für die Zahlen $p$ und $n$ müssen ein paar Voraussetzungen erfüllt sein, damit dieses Verfahren auch sicher funktioniert. $n$ muss eine Primzahl sein und $p$ sollte idealerweise ein Generator der Gruppe $Z(p,\cdot)$ sein ([1], Seite 105). Für Anwender ist dieses Detail eher unwichtig, da $p$ und $n$ häufig fest vorgegeben sind und nur der Wert für $x$ jedesmal neu berechnet wird.