Bei Koblitz [K2] p.131 ist ein elliptic curve cryptosystem beschrieben,
das ausnutzt, daß durch die elliptischen Kurven ein großer Vorrat
spezieller kommutativer Gruppen geliefert wird. Diesem Verfahren liegt der
folgende von Diffie-Hellman 1976 zunächst für die multiplikative
Gruppe
vorgeschlagene Schlüsselaustausch zugrunde.
Es sei eine elliptische Kurve E über dem endlichen Körper
fixiert und eine Vorschrift, etwa die x-Koordinate eines Punktes
in eine ganze Zahl zu verwandeln. Überdies sei ein Punkt
(öffentlich) bekannt. Benutzerin Alice wählt nun (geheim) eine
Zufallszahl
und berechnet
, die sie an den zweiten Benutzer Bob sendet. Ebenso wählt Bob
und sendet
an Alice. Der geheime Schlüssel ist nun
.
Alice berechnet P, indem sie Bobs Sendung
mit ihrem
multipliziert und Bob entsprechend umgekehrt. Ein unauthorisiert Neugieriger
müßte nun
aus der Kenntnis von
bestimmen, ohne
und
zu kennen. Diese Aufgabe wird das Diffie-Hellman Problem für
elliptische Kurven genannt. Es steht in engem Zusammenhang zum Problem
des diskreten Logarithmus, das weiter unten noch beschrieben werden soll.
Zunächst soll gezeigt werden, wie hier eine Nachrichtenübermittlung
vonstatten gehen kann. Das benutzt eine Idee von ElGamal von 1985: Die Buchstaben
oder Zeichen des zu übermittelnden Textes werden durch eine bestimmte
Weise mit Punkten der Kurve E identifiziert (das geht !). Bob möchte
nun
übermitteln. Alice und Bob haben schon
und
ausgetauscht. Dann wählt Bob eine andere Zufallszahl
und sendet Alice das Punktpaar
. Um die Botschaft zu entschlüsseln, multipliziert Alice den ersten
Punkt im Paar mit ihrem geheimen
und subtrahiert das Ergebnis vom zweiten Punkt im Paar.