Diffie Hellmann

Grundlagen

• Der Diffie-Hellman-Schlüsselaustausch ist ein Protokoll zur Schlüsselvereinbarung.
• Es ermöglicht, dass zwei Kommunikationspartner über eine öffentliche, abhörbare Leitung einen gemeinsamen geheimen Schlüssel in Form einer Zahl vereinbaren können, den nur diese kennen und ein potenzieller Lauscher nicht berechnen kann.
• Der dadurch vereinbarte Schlüssel kann anschließend für ein symmetrisches Kryptosystem verwendet werden.
• Unterschiedliche Varianten des Diffie-Hellman-Merkle-Verfahrens werden heute für die Schlüsselverteilung in den Kommunikations- und Sicherheitsprotokollen des Internet eingesetzt.

Veranschaulichung der Grundidee anhand gemischter Farben

Zunächst soll die Grundidee des Diffie-Hellman-Merkle-Schlüsselaustauschs anhand von „Farbmischen“ anschaulich dargestellt werden, wie es die Illustration links veranschaulicht. In Wirklichkeit wären die Farben Zahlen und das Mischen von Farben entspräche der diskreten Exponentialfunktion.

Das Mischen von Farben wird hier als eine Einwegfunktion aufgefasst: Es ist „leicht“, zwei oder mehrere verschiedene Farben zu mischen. Die Umkehrung, das Zerlegen einer Farbmischung in ihre ursprünglichen Farb-Komponenten, ist jedoch sehr aufwändig, das heißt nicht effizient durchführbar.

Alice und Bob einigen sich zunächst öffentlich auf eine gemeinsame Farbe (im Beispiel Gelb). Außerdem wählt jeder der beiden Kommunikationspartner für sich eine geheime Farbe (Alice Orange und Bob Türkis). Bob und Alice mischen nun jeweils die gemeinsame Farbe mit ihrer geheimen Farbe. Im Beispiel entsteht dabei für Alice Beige und für Bob Graublau. Diese Farbmischungen tauschen Alice und Bob nun über die abhörbare Leitung aus. Einer potenziellen Lauscherin Eve ist es nicht effizient möglich, aus den öffentlichen Informationen (gelb, beige, graublau) auf die geheimen Farben von Alice und Bob zu schließen.

In einem letzten Schritt mischen nun Alice und Bob die Farbmischung ihres Gegenübers mit ihrer eigenen geheimen Farbe. Daraus entsteht wiederum eine neue Farbe (im Beispiel Ockerbraun), die für beide Kommunikationspartner gleich ist (gelb + orange + türkis = gelb + türkis + orange = ockerbraun). Somit haben Alice und Bob eine gemeinsame geheime Farbe. Für Eve ist es unmöglich, diese herauszufinden, da sie Alices und Bobs geheime Farbzutaten nicht kennt.

Beispiel

Das folgende Beispiel dient zur Veranschaulichung und benutzt deshalb sehr kleine Zahlen. In der tatsächlichen Anwendung werden dagegen Zahlen mit mindestens mehreren hundert Stellen benutzt.

Berechnung

• Alice und Bob einigen sich auf die beiden öffentlichen Schlüssel $p=13$ und $g=2$.
• Alice wählt die Zufallszahl $a=5$ als geheimen Schlüssel.
• Nun berechnet Alice $A=g^{a}\ {\bmod {\ }}p=2^{5}\ {\bmod {\ }}13=6$
• Alice sendet $A$ an Bob.
• Bob wählt die Zufallszahl $b=8$ als geheimen Schlüssel
• Bob berechnet $B=g^{b}\ {\bmod {\ }}p=2^{8}\ {\bmod {\ }}13=9$
• Bob sendet $B$ an Alice.
• Alice berechnet $K_{1}=B^{a}\ {\bmod {\ }}p=9^{5}\ {\bmod {\ }}13=3$.
• Bob berechnet $K_{2}=A^{b}\ {\bmod {\ }}p=6^{8}\ {\bmod {\ }}13=3$.
• Beide erhalten das gleiche Ergebnis $K=K_{1}=K_{2}=3$.

Sicherheit

• Die Lauscherin Eve kann zwar die Zahlen 13, 2, 6 und 9 mithören,
• Das eigentliche gemeinsame Geheimnis von Alice und Bob $K=3$ bleibt ihr aber verborgen.
• $K=3$ kann als Schlüssel für die nachfolgende Kommunikation verwendet werden.

Lauschen

• Mit Hilfe der abgefangenen Nachrichten kann Eve immerhin die folgenden Gleichungen aufstellen:

  $6=2^{a}\ {\bmod {\ }}13$

  $9=2^{b}\ {\bmod {\ }}13$

• Daraus kann sie beispielsweise durch Ausprobieren die beiden geheimen Zahlen $a=5$ und $b=8$ bestimmen.
• Den vereinbarten Schlüssel $K$ von Alice und Bob kann sie nun mit

  $K=g^{ab}\ {\bmod {\ }}p$ berechnen.

• Wenn jedoch die Primzahl $p$ groß genug gewählt wird und $g$
• ein Generator der Gruppe $\mathbb {Z} _{p}^{*}$ ist, ist es für Eve zu aufwändig,
• um alle Zahlen zwischen $1$ und $p-1$ durchzuprobieren,
• die als Resultat der modularen Potenz $g^{a}\ {\bmod {\ }}p$ in Frage kommen

Script zum berechnen

• Diffie-Hellman-Script