Dark ITSec

Diffie-Hellman-Algorithmus

Im Zusammenhang mit Verschlüsselungssoftware wird neben den Verschlüsselungsalgorithmen RSA und ElGamal der Diffie-Hellmann-Schlüsselaustausch-Algorithmus erwähnt, der an dieser Stelle vorgestellt wird.

In der Tat eignet sich das 1976 beschriebene Verfahren nicht zur Ver- und Entschlüsselung, sondern vielmehr zum Austausch von Schlüsseln über "unsichere" Kanäle. Seine Sicherheit basiert wie ElGamal auf der Problematik, dass es keine eindeutigen, sicheren mathematischen Verfahren gibt, den diskreten Logarithmus zu berechnen.

1. Schritt
Wir bleiben bei unseren Protagonisten Alice und Bob, die miteinander verschlüsselt kommunizieren wollen. Dazu möchten sie gern die Schlüssel für den Verschlüsselungsvorgang miteinander austauschen. Leider besteht keine gesicherte Verbindung zwischen beiden und ein persönliches Treffen als sicherste Alternative ist nicht möglich. Also wählen sie folgende Vorgehensweise:

Zunächst denkt sich einer von beiden eine möglichst große Primzahl P sowie eine Zahl z aus. Für diese muss gelten, dass sie kleiner als P ist. (Tatsächlich gibt es noch eine weitere Einschränkung, die wir aber hier
vernachlässigen; bei weiterem Interesse verweisen wir auf die
oben genannten Links).

Diese Daten werden offen an den anderen Partner gesendet.

2. Schritt
Nun denkt sich jeder der beiden eine geheime Zahl aus; Alice nimmt a und Bob nimmt b.
Nun berechnet jeder:

Alice	Bob
X=za mod P	Y=zb mod P

Die Werte X und Y werden wie auch z und P miteinander ausgetauscht.
Die Werte a und b dagegen sind die geheimen Schlüssel.

Jeder der beiden berechnet daraus den Schlüssel:

Alice	Bob
KA=Ya mod P	KB=Xb mod P

Damit erhalten beide den gleichen Wert, denn es gilt:

(z^b mod P)^a = (z^a mod P)^b = z^(ab) mod P

Beispiel:
Alice denkt sich für P=11 und für z=4 aus. Dieses teilt sie Bob
mit. Ausserdem hat sie sich für a den Wert 3 ausgedacht, während
Bob seinen geheimen Schlüssel auf den Wert 5 gesetzt hat.

X	=	43	mod 11	Y	=	45	mod 11
	=	64	mod 11		=	1024	mod 11
	=	5	Rest  9		=	93	Rest  1

Alice teilt Bob noch den Wert für X mit (9) und Bob den Wert für
Y (1).

Nun kann jeder seinen Schlüssel berechnen:

KA	=	13	mod 11	KB	=	95	mod 11
	=	1	mod 11		=	59049	mod 11
	=	0	Rest  1		=	5368	Rest  1

Dieses Beispiel ist natürlich sehr vereinfacht und trivial gehalten. Es soll lediglich die Vorgehensweise und die Funktion von Diffie-Hellmann beschreiben. Aus diesem Zweck wurden unrealistisch kleine Werte eingesetzt und ggf. vorgegebene Restriktionen (s. weiter oben) nicht beachtet.