Schlüsseltausch mit elliptischen Kurven

Worum geht es?

Alice und Bob wollen eine sichere Verbindung aufbauen. Als Kommunikationsmöglichkeit haben sie 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.

Algorithmus zum Schlüsseltausch mit elliptischen Kurven nach Diffie und Hellman

Alice und Bob wählen zunächst eine gemeinsame elliptische Kurve und einen gemeinsamen Punkt $P$ auf der Kurve.

Alice wählt anschließend eine nur ihre bekannte sehr große zufällige Zahl $N_A$ und berechnet $A = N_A\, P$.

Bob wählt ebenso eine nur ihm bekannte sehr große zufällige Zahl $N_B$ und berechnet $B = N_B\, P$.

Anschließend tauschen Alice und Bob ihre Zwischenergebnisse $A$ und $B$ aus. Alice berechnet $K_A = N_A\, B$ und Bob berechnet $K_B = N_B\, A$. Sowohl Alice als auch Bob führen sämtliche Additionen auf der elliptischen Kurve mit dem Double and Add-Verfahren durch, so dass alle Berechnungen sehr effizient möglich sind.

Wegen der Rechengesetze der Multiplikation auf elliptischen Kurven gilt: $$\begin{eqnarray} K_A &= N_A\, B = N_A\, (N_B\, P) = N_A\, N_B\, P = N_B\, N_A\, P = N_B\, A = K_B \end{eqnarray}$$

Damit erhalten Alice und Bob den gleichen Schlüssel $K = K_A = K_B = N_A\, N_B\, P$ und haben auf diese Weise also ein gemeinsames Geheimnis vereinbart, ohne dieses explizit über den unsicheren Kanal übertragen zu müssen.