Diffie-Hellman-Schlüsselaustausch

Der Diffie-Hellman-Schlüsselaustausch ist kein Verschlüsselungsverfahren, sondern beschreibt die Möglichkeit, Schlüssel sicher über unsichere Kanäle auszuhandeln. Hierbei handelt es sich um Schlüssel, wie sie in der Kryptografie verwendet werden.

Bei dem Verfahren werden Eigenschaften diskreter Logarithmen ausgenutzt. Es ist nicht zuletzt die Grundlage für das Elgamal-Kryptosystem. Das Verfahren ermöglicht es nicht, einen bestimmten Schlüssel auszutauschen. Es ermöglicht es den Kommunikationspartnern jedoch, aus den ausgetauschten Informationen den selben Schlüssel zu generieren.

Geschichte

Der Algorithmus wurde von Martin Hellman gemeinsam mit Whitfield Diffie und Ralph Merkle an der Universität von Stanford (Kalifornien) entwickelt und 1976 veröffentlicht.

Wie erst 1997 bekannt wurde, hatte das britische Government Communications Headquarters (GCHQ) schon in den 1960er Jahren den Auftrag erteilt, aufgrund der hohen Kosten bei der damals üblichen Schlüsselverteilung einen anderen Weg für die Schlüsselverteilung zu finden.

Die von James Ellis, Clifford Cocks und Malcolm Williamson geäußerten Ideen ähnelten dem Diffie-Helmann-Verfahren. Das GCHQ hat einerseits wegen der Geheimhaltung und andererseits wegen des für die Briten aus Sicht der frühen 1970er Jahre fraglichen Nutzens nie ein Patent beantragt.

Funktionsweise

Zwei Kommunikationspartner wollen über ein unsicheres Medium, etwa eine Kabel- oder Funkleitung, verschlüsselt kommunizieren. Sie wollen ein symmetrisches Kryptosystem einsetzen. Dazu benötigen beide jedoch zunächst einen Schlüssel, den sie über den Diffie-Hellman-Schlüsselaustausch austauschen.

1. Die Kommunikationspartner einigen sich zunächst auf eine Primzahl $p$ und eine Primitivwurzel $g\,mod\,p$ mit $2\leq g\leq p-2$. Diese Parameter müssen nicht geheim bleiben, können also insbesondere auch über ein unsicheres Medium übertragen werden.
2. Beide Kommunikationspartner erzeugen jeweils eine geheim zu haltende Zufallszahl $a$ bzw. $b$ aus der Menge $\{0,...,p-2\}$. $a$ und $b$ werden nicht übertragen, bleiben also dem jeweiligen Kommunikationspartner, aber auch potenziellen Lauschern unbekannt.
3. Die Kommunikationspartner berechnen $A=g^{a}\,mod\,p$ bzw. $B=g^{b}\,mod\,p$. Nun werden $A$ und $B$ über das unsichere Medium übertragen.
4. Die Kommunikationspartner berechnen nun $B^{a}=(g^{b})^{a}=(g^{a})^{b}=A^{b}=K$. Das Ergebnis K ist für beide Partner gleich und kann als Schlüssel für die weitere Kommunikation verwendet werden.

Beispiel

Die Kommunikationspartner seien Alice und Bob. Das Beispiel benutzt sehr kleine Zahlen. In der tatsächlichen Anwendung werden Zahlen mit mehreren Hundert Dezimalstellen benutzt.

1. Alice und Bob einigen sich auf $p=13$ und $g=2$
2. Alice wählt $a=5$. Bob wählt $b=7$
3. Alice berechnet $A=2^{5}\,mod\,13=6$. Bob berechnet $A=2^{7}\,mod\,13=11$. Beide senden das Ergebnis an die jeweilige Gegenstelle.
4. Alice berechnet $K=11^{5}\,mod\,13$, Bob berechnet $K=6^{7}\,mod\,13$. Beide erhalten das gleiche Ergebnis $K=7$

Sicherheit

Die Sicherheit des Verfahrens basiert auf der Verwendung einer sogenannten Einwegfunktion. Hierbei macht man sich die Tatsache zunutze, dass es zwar sehr einfach ist eine Zahl zu potenzieren, dass es jedoch nur mit sehr großem Aufwand möglich ist, den diskreten Logarithmus einer Zahl zu berechnen. In der Praxis werden sehr große Primzahlen verwendet, die Sicherheit kann weiter erhöht werden, wenn $g=(p-1)/2$ ebenfalls eine Primzahl ist (g ist dann eine Sophie-Germain-Primzahl).

Potenzielle Lauscher erfahren zwar $p$, $g$, $A$ und $B$. $a$ und $b$ bleiben hingegen unbekannt.

Das Diffie-Hellman-Problem, $K=g^{ab}\,mod\,p$ zu berechnen, ist lösbar, wenn man diskrete Logarithmen $mod\,p$ berechnen kann. Eine andere Lösungsmethode ist nicht bekannt.

Das Verfahren gilt als sicher gegen passives Abhören ("Eavesdropping"), da die im Klartext übertragenen Informationen nicht zur Konstruktion des Schlüssels K ausreichen. Wenn der Angreifer jedoch aktiv Datenpakete abfangen und verändert weiterschicken kann, besteht die Möglichkeit des Man-In-The-Middle-Angriffs: Der Angreifer M vereinbart mit Partner A den Schlüssel K_AM und mit Partner B den Schlüssel K_MB, wobei A und B davon ausgehen, der Austausch fände mit dem berechtigten Kommunikationspartner statt. Auch die folgende symmetrisch verschlüsselte Kommunikation wird über den Angreifer M umgeleitet. Daten von A an B werden von A mit K_AM verschlüsselt und können von M gelesen werden, bevor sie mit K_MB verschlüsselt an B weitergeschickt werden (und umgekehrt). Dabei kann der Nachrichteninhalt sogar unbemerkt verändert werden. Diesem Problem kann durch elektronische Unterschrift und ähnliche Maßnahmen erfolgreich begegnet werden.

Literatur

• Johannes Buchmann: Einführung in die Kryptographie, 2., erweiterte Auflage. Springer, Berlin u. a. 2001 ISBN 3540412832
• E. Rescorla: RFC 2631, Diffie-Hellman Key Agreement Method, Juni 1999. www.ietf.org/rfc/rfc2631.txt (englisch)

Weblinks

• Beispiel für den Diffie-Hellman-Algorithmus