Diffie-Hellman/Funktionsweise

Funktionsweise

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 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.

Mathematische Funktionsweise

Prinzip des Diffie-Hellman-Merkle-Schlüsselaustauschs
a: privater Schlüssel von Alice
b: privater Schlüssel von Bob
p: öffentlich bekannte Primzahl
g: öffentlich bekannte natürliche Zahl kleiner als p
A: öffentlicher Schlüssel von Alice
B: öffentlicher Schlüssel von Bob
K: geheimer Sitzungs-Schlüssel für Alice und Bob

Die beiden Kommunikationspartner Alice und Bob wollen über ein unsicheres Medium, etwa eine Kabel- oder Funkverbindung, verschlüsselt kommunizieren. Dazu soll ein symmetrisches Kryptosystem eingesetzt werden, für das beide jedoch zunächst einen gemeinsamen geheimen Schlüssel benötigen. Das DHM-Kommunikationsprotokoll sorgt dafür, dass sie einen geheimen Schlüssel berechnen können, ohne dass Dritte (Eve) diesen erfahren können. Den auf diese Weise errechneten Schlüssel können sie dann in Zukunft verwenden, um verschlüsselt mit einem symmetrischen Kryptosystem zu kommunizieren.

1. Alice und Bob einigen sich zunächst öffentlich auf eine große Primzahl $p$ und eine natürliche Zahl $g$, die kleiner als $p$ ist. Sich öffentlich darauf einigen bedeutet, dass jeder diese beiden Zahlen kennen darf (also auch potenzielle Lauscher wie Eve). Idealerweise handelt es sich bei $g$ um einen Erzeuger der zyklischen Gruppe $\mathbb {Z} _{p}$, das Verfahren funktioniert aber auch, wenn $g$ einen anderen Wert kleiner $p$ annimmt. In der Praxis ist es ohnehin meist so, dass $g$ und $p$ vorgegeben sind und von vielen Anwendern verwendet werden.
2. Alice und Bob erzeugen jeweils eine geheimzuhaltende Zufallszahl (privater Schlüssel) $a$ bzw. $b$ aus der Menge $\{1,\ldots ,p-1\}$. $a$ und $b$ werden nicht übertragen, bleiben also potenziellen Lauschern, aber auch dem jeweiligen Kommunikationspartner, unbekannt. Nur Alice kennt die Zahl $a$ und nur Bob kennt die Zahl $b$.
3. Alice berechnet mit ihrer geheimen Zahl den öffentlichen Schlüssel $A=g^{a}\ {\bmod {\ }}p$ und schickt $A$ an Bob. Bob berechnet mit seiner geheimen Zahl den öffentlichen Schlüssel $B=g^{b}\ {\bmod {\ }}p$ und schickt $B$ an Alice.
4. Alice erhält $B$ von Bob und berechnet mit ihrem privaten Schlüssel $a$ die Zahl $K_{1}=B^{a}\ {\bmod {\ }}p$. Bob berechnet mit dem erhaltenen $A$ und seinem privaten Schlüssel $b$ ebenfalls die Zahl $K_{2}=A^{b}\ {\bmod {\ }}p$. Die beiden haben die gleiche Zahl $K_{1}=K_{2}$ berechnet. Diese ist somit der gesuchte gemeinsame Schlüssel $K$.

Nur Alice und Bob kennen $K$. Eve kann aus der abgehörten Kommunikation $K$ nicht berechnen. Dazu müsste sie den diskreten Logarithmus lösen, was nach heutigem Kenntnisstand nicht effizient möglich ist, wenn die Zahlen groß genug sind. Alice und Bob können also $K$ gefahrlos für eine symmetrische Kryptografie nutzen.

Dass beide Kommunikationspartner denselben Wert für $K$ berechnen, zeigen die folgenden beiden Restklassengleichungen:

$K_{1}=B^{a}\ {\bmod {\ }}p=(g^{b}\ {\bmod {\ }}p)^{a}\ {\bmod {\ }}p=(g^{b})^{a}\ {\bmod {\ }}p=g^{ba}\ {\bmod {\ }}p$.

$K_{2}=A^{b}\ {\bmod {\ }}p=(g^{a}\ {\bmod {\ }}p)^{b}\ {\bmod {\ }}p=(g^{a})^{b}\ {\bmod {\ }}p=g^{ab}\ {\bmod {\ }}p$.

Da die Multiplikation kommutativ ist, gilt des Weiteren

$g^{ba}\ {\bmod {\ }}p=g^{ab}\ {\bmod {\ }}p$

und somit

$K_{1}=K_{2}$.

Alice und Bob erhalten also nach ihren jeweiligen Berechnungen die genau gleiche Zahl, nämlich den geheimen Schlüssel $K=K_{1}=K_{2}$.

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.

1. Alice und Bob einigen sich auf die beiden öffentlichen Schlüssel $p=13$ und $g=2$ ($2$ ist ein Generator der Gruppe $\mathbb {Z} _{13}^{*}$, siehe Abschnitt „Gruppentheorie“).
2. Alice wählt die Zufallszahl $a=5$ als geheimen Schlüssel und Bob $b=8$.
3. Nun berechnet Alice $A=g^{a}\ {\bmod {\ }}p=2^{5}\ {\bmod {\ }}13=6$ und sendet $A$ an Bob. Bob berechnet $B=g^{b}\ {\bmod {\ }}p=2^{8}\ {\bmod {\ }}13=9$ und sendet $B$ an Alice.
4. 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$.
5. Beide erhalten das gleiche Ergebnis $K=K_{1}=K_{2}=3$.

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.

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$

ausrechnen.

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.

Programmierung

Das folgende Programm in der Programmiersprache Python zeigt die Implementierung des Diffie-Hellman-Schlüsselaustauschs für $p=107$ und $g=3$.

from random import randint

# Festlegung der Gruppe:
p = 107

g = 3
# Zufällige Wahl der geheimen Schlüssel von Alice und Bob:

a = randint(1,p-1)
b = randint(1,p-1)
# Berechnung der Öffentlichen Schlüssel:

A = pow(g, a, p)
B = pow(g, b, p)

print(f'Öffentlicher Schlüssel von Alice: {A=}')
print(f'Öffentlicher Schlüssel von Bob:   {B=}')
# Berechnung des gemeinsamen Geheimnisses:

k_a = pow(B, a, p)
k_b = pow(A, b, p)

print(f'{k_a=}')
print(f'{k_b=}')