4.1 Übersicht

In den bisherigen Kapiteln wurden elliptische Kurven und unterschiedliche Kryptoverfahren vorgestellt. In diesem Kapitel soll es nun um die Kombination von beidem gehen. Mit elliptischen Kurven lassen sich asymmetrische Krypto-Verfahren ähnlich der Diffie-Hellman-Schlüsselvereinbarung realisieren. In "IEEE P1363: Standard Specifications For Public Key Cryptography" werden Krypto-Verfahren basierend auf elliptischen Kurven beschrieben und es wird eine Normung vorgenommen. Allerding ist diese Normung immer noch in der Entwicklung, aber kurz vor dem Abschluß (Stand: 9.99). Im weiteren werden sich die Ausführungen stark an dieser Spezifikation orientieren, da sich die dort beschriebenen Verfahren wohl als Standard durchsetzen werden.

Benötigte Parameter

Grundvoraussetzung, um ein Krypto-Verfahren basierend auf elliptischen Kurven zu nutzen, ist es sich auf folgende Parameter unter den teilnehmenden Parteien zu einigen. Die Parameter seien im folgenden durch den Begriff ECC-Parameter (Elliptic Curve Cyptography) zusammengefaßt.

E	eine elliptische Kurve nach Gl.2.1.3 über Zp
p	Die Größe des zugrundeliegenden Körpers Zp
a, b	Die Koeffizienten der elliptischen Kurve E; a,b Î Zp
G	Ein Punkt der elliptischen Kurve E
r	Die Ordnung des Punktes G, r muß Primzahl sein.

Anmerkung: Auf die Ordnung von G und dessen Bedeutung wird an späterer Stelle eingegangen.

Dazu muß jede teilnehmende Partei einzeln noch ein Schlüsselpaar erzeugen.

Wobei s eine ganze, zufällig gewählte Zahl modulo r ist und W sich aus G und s berechnet mit

[P1363_98]7.1.2. W ist also ein Punkt der elliptischen Kurve. Da W der öffentliche Schlüssel ist, muß natürlich sichergestellt sein, daß es nicht möglich ist, den privaten Schlüssel s aus W zu berechnen. Doch das Auflösen der Gleichung 4.1.1 nach s ist nicht möglich, da für zwei Punkte einer elliptischen Kurve keine Division existiert. Andersherum könnte man versuchen, solange G auf sich selbst zu addieren, bis W erreicht wird. Bei kleinen s ist das sicherlich auch möglich, da aber gerade für große s eine effektive Methode der Vielfachaddition von G existiert (Kapitel 2.5), ist das s so zu wählen, daß die nicht optimierte Addition von G + G + ... + G (s mal) nicht in annehmbarer Zeit zu berechnen ist. Allerdings muß s auch so klein gewählt werden, daß mit einer optimierten Methode W relativ schnell zu berechnen ist, damit die Schlüsselpaar-Generierung nicht zu lange dauert.
Obwohl die Gruppenoperation für E(K) additiv geschrieben wird, hat das obige Problem viel Ähnlichkeit mit dem Lösen des diskreten Logarithmus, daher wird auch in diesem Fall vom DLP gesprochen.

Beispiel:

Angenommen W soll bei der Schlüsselgenerierung innerhalb von 10 Sekunden berechnet werden, allerdings soll das Berechnen von W unoptimiert ungefähr 1,5 Jahre (»47.000.000 sec) dauern, also 4.700.000 mal so lange. Es stehen also s Additionen 2z Additionen, mit z = log₂ s gegenüber (s.Gl.2.5.2 u. Gl.2.5.3 ), also muß

s eine Zahl mit 28 Bit Länge sein.

Anmerkung: Hier ist oft die Rede von großen Zahlen oder annehmbarer Zeit. Die Frage, warum hier keine konkreten Werte genannt werden, ist berechtigt, dazu ist aber zu sagen, daß diese Angabe sehr stark von der Implementierung und der momentanen Leistung der Computer abhängt. Dieses sind aber Faktoren, die sich sehr schnell ändern können und daher keine Allgemeingültigkeit haben.