Ein Kryptosystem zu einer elliptischen Kurve

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 tex2html_wrap_inline842 vorgeschlagene Schlüsselaustausch zugrunde.

Es sei eine elliptische Kurve E über dem endlichen Körper tex2html_wrap_inline720 fixiert und eine Vorschrift, etwa die x-Koordinate eines Punktes tex2html_wrap_inline820 in eine ganze Zahl zu verwandeln. Überdies sei ein Punkt tex2html_wrap_inline852 (öffentlich) bekannt. Benutzerin Alice wählt nun (geheim) eine Zufallszahl tex2html_wrap_inline854 und berechnet tex2html_wrap_inline856 , die sie an den zweiten Benutzer Bob sendet. Ebenso wählt Bob tex2html_wrap_inline858 und sendet tex2html_wrap_inline860 an Alice. Der geheime Schlüssel ist nun tex2html_wrap_inline862 .
Alice berechnet P, indem sie Bobs Sendung tex2html_wrap_inline860 mit ihrem tex2html_wrap_inline868 multipliziert und Bob entsprechend umgekehrt. Ein unauthorisiert Neugieriger müßte nun tex2html_wrap_inline862 aus der Kenntnis von tex2html_wrap_inline872 bestimmen, ohne tex2html_wrap_inline868 und tex2html_wrap_inline858 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 tex2html_wrap_inline880 übermitteln. Alice und Bob haben schon tex2html_wrap_inline882 und tex2html_wrap_inline860 ausgetauscht. Dann wählt Bob eine andere Zufallszahl tex2html_wrap_inline886 und sendet Alice das Punktpaar tex2html_wrap_inline888 . Um die Botschaft zu entschlüsseln, multipliziert Alice den ersten Punkt im Paar mit ihrem geheimen tex2html_wrap_inline868 und subtrahiert das Ergebnis vom zweiten Punkt im Paar.