Verfahren von Diffie und Hellman

Der 1976 von Whitfield Diffie und Martin Hellman veröffentlichte Algorithmus realisiert den Schlüsseltausch zwischen zwei Kommunikationspartnern über einen unsicheren Kanal. Die Sicherheit des Verfahrens beruht darauf, dass es zwar sehr einfach ist, eine Zahl zu potenzieren, es jedoch nur mit sehr großem Aufwand möglich ist, den diskreten Logarithmus einer Zahl zu berechnen.

Zwei Kommunikationspartner $\text{[math]}$ und $\text{[math]}$ können sich auf einen gemeinsamen Schlüssel einigen, indem sie wie folgt vorgehen. Zunächst tauschen $\text{[math]}$ und $\text{[math]}$ eine Primzahl $\text{[math]}$ und ein primitives Element $\text{[math]}$ . Die beiden Zahlen $\text{[math]}$ und $\text{[math]}$ können dabei öffentlich bekannt sein. Anschließend wählen $\text{[math]}$ und $\text{[math]}$ geheime Zahlen $\text{[math]}$ und $\text{[math]}$ , für die gilt

\text{[math]}

User $\text{[math]}$ berechnet nun

\text{[math]}

und schickt das Ergebnis $\text{[math]}$ an User $\text{[math]}$ . Analog dazu berechnet $\text{[math]}$

\text{[math]}

und schickt das Ergebnis $\text{[math]}$ an $\text{[math]}$ .

Der geheime Schlüssel $\text{[math]}$ ergibt sich, indem $\text{[math]}$ und $\text{[math]}$ das jeweils erhaltene Ergebnis mit ihrer geheimen Zahl $\text{[math]}$ beziehungsweise $\text{[math]}$ potenzieren:

\text{[math]}

Ein Angreifer, der $\text{[math]}$ und $\text{[math]}$ kennt, müsste zur Bestimmung des geheimen Schlüssels $\text{[math]}$ das Diskrete Logarithmus Problem lösen, welches algorithmisch schwierig ist.