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-Hellman ermö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) 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$.
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 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$ zu berechnen, wenn nur $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 aufwenig, dass es praktisch nicht lösbar ist.
Damit der Algorithmus funktioniert, ist es außerdem wichtig, das 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.
