Schlüsseltausch nach Diffie-Hellman

Worum geht es?

Alice und Bob wollen eine sichere Verbindung aufbauen. Als Kommunikationsmöglichkeit haben sie allerdings nur einen unsicheren Kanal zur Verfügung. Sie wollen daher einen gemeinsamen Schlüssel $K$ vereinbaren, den sie für die Verschlüsselung ihrer Nachrichten verwenden können.

Der Algorithmus von Diffie-Hellmanermöglicht es Alice und Bob, einen gemeinsamen Schlüssel zu vereinbaren, ohne dass sie diesen explizit über den unsicheren Kanal übertragen müssen.

Algorithmus zum Schlüsseltausch nach Diffie-Hellman mit modularen Potenzen

Alice und Bob wählen zunächst eine (große) gemeinsame Primzahl $p$ und eine gemeinsame natürliche Zahl $ g < p.$

Alice wählt anschließend eine nur ihre bekannte zufällige Zahl $a$ und berechnet $A = g^a \,\text{mod}\, p$.
Bob wählt ebenso eine nur ihm bekannte zufällige Zahl $b$ und berechnet $B = g^b \,\text{mod}\, p.$

Anschließend tauschen Alice und Bob ihre Zwischenergebnisse $A$ und $B$ aus. Alice berechnet $K_A = B^a \,\text{mod}\, p$ und Bob berechnet $K_B = A^b \,\text{mod}\, p.$

Wegen $$\begin{eqnarray} K_A &= B^a \, \text{mod} \, p = (g^b)^a \text{mod} \, p = g^{ab} \, \text{mod}\, p , \\ K_B &= A^b \, \text{mod} \, p = (g^a)^b \text{mod} \, p = g^{ab} \, \text{mod}\, p \end{eqnarray} $$ erhalten Alice und Bob den gleichen Schlüssel $K =K_A = K_B= g^{ab} \,\text{mod}\, p$.

Dieser gemeinsame Schlüssel $K$ kann nun von Alice und Bob für die Verschlüsselung und Entschlüsselung ihrer Nachrichten mit einem symmetrischen Verschlüsselungsverfahren verwendet werden.

Algorithmus von Diffie-Hellman mit konkreten Zahlenwerten

Hier kannst du den Algorithmus mit konkreten Zahlenwerten nachvollziehen. Zusätzlich ist ein Farben-Analogon dargestellt, bei dem sich Alice und Bob auf eine geheime Farbe einigen, ohne diese jedoch über den öffentlichen Kanal übertragen zu müssen.

Warum funktioniert der Algorithmus?

Alice und Bob verwenden eine sogenannte Einwegfunktion, die es schwierig macht, den Schlüssel $K$ aus den Zwischenergebnissen $A$ und $B$ zu berechnen.

Die Einwegfunktion ist hier die modulare Potenzfunktion $g^x \,\text{mod}\, p$. Die Bezeichnung Einwegfunktion bedeutet, dass es einfach ist, die modulare Potenz $g^x \,\text{mod}\, p$ zu berechnen, wenn $x$ gegeben ist. Es ist jedoch (besonders für große Zahlen) schwer, den Exponenten $x$ (also den Logarithmus) zu berechnen, wenn nur die Potzenz $g^x \,\text{mod}\, p$ gegeben ist.

Dieses Problem wird als diskretes Logarithmusproblem bezeichnet und ist für große Zahlen auch für einen Computer so aufwendig, dass es praktisch nicht lösbar ist.

Damit der Algorithmus funktioniert, ist es außerdem wichtig, dass die Potenzfunktion $(g^a)^b \,\text{mod}\, p$ kommutativ bezüglich der Exponenten $a$ und $b$ ist, d.h. es gilt: $g^{ab}\,\text{mod}\, p = g^{ba}\,\text{mod}\, p$.

Verallgemeinerung des Algorithmus

Eine interessante Beobachtung ist, dass der Algorithmus immer funktioniert, wenn Alice und Bob eine beliebige Einwegfunktion verwenden, die kommutativ bezüglich der geheim gewählten Zahlen ist.

Im weiteren Verlauf des Kapitels werden wir den Algorithmus von Diffie-Hellman auf sogenannte elliptische Kurven verallgemeinern. Dazu werden wir eine Einwegfunktionen auf elliptischen Kurven definieren und zeigen, dass diese kommutativ bezüglich der gewählten geheimen Zahlen ist.