Elliptische Kurve

In der Zahlentheorie ist eine elliptische Kurve eine singularitätenfreie algebraische Kurve der Ordnung 3 in der projektiven Ebene.

Von besonderem Interesse z.B. für die Faktorisierung natürlicher Zahlen sind aufgrund ihrer einfachen Struktur elliptische Kurven der Form cy² = x³ + ax + b mit c ≠ 0 und 4a³ + 27b² ≠ 0. Einige moderne Verschlüsselungsverfahren basieren auf solchen Kurven. Der Name leitet sich historisch davon ab, dass diese Kurven durch elliptische Integrale parametrisiert werden können.

Elliptische Kurven über endlichen Körpern werden in der Kryptografie eingesetzt. Dazu wird ausgenutzt, dass eine Gerade (lineare Funktion), die zwei Schnittpunkte P und Q mit einer Elliptischen Kurve hat, diese auch in einem 3. Punkt schneidet. Der Punkt, der aus dem letzteren durch Verkehren des Vorzeichens der Y-Koordinate (wenn die Kurve die oben angegebene Form hat) entsteht, wird P+Q genannt. Man kann zeigen, daß diese Punktaddition (P und Q werden addiert, das Ergebnis ist der Punkt P+Q) sowohl kommutativ als auch assoziativ ist. Ergänzt man die Elliptische Kurve um einen weiteren Punkt 0 (genannt Punkt im Unendlichen), so bildet sie zusammen mit der (etwas erweiterten) Punktaddition eine abelsche Gruppe.

Sei nun P ein Punkt der Elliptischen Kurve. Der Punkt P+P wird mit 2P bezeichnet, entsprechend definiert man kP=P+...+P als k-fache Addition des Punktes P. Ist P nicht der 0-Punkt und ist die Ordnung der Elliptischen Kurve prim, so kann auf diese Weise jeder Punkt der Kurve erreicht werden (d.h. zu jedem Punkt Q auf der Kurve existiert eine natürliche Zahl k mit Q=kP). Die Aufgabe, aus gegebenen Punkten P,Q diesen Wert k zu ermitteln, wird als Diskretes Logarithmus-Problem der Elliptischen Kurven (kurz ECDLP) bezeichnet. Es wird angenommen, daß das ECDLP (bei geeigneter Kurvenwahl) schwer ist, d.h. nicht effizient gelöst werden kann. Damit bieten sich Elliptische Kurven an, um auf ihnen asymmetrische Kryptosysteme zu realisieren (etwa einen Diffie-Hellman-Schlüsselaustausch oder ein Elgamal-Kryptosystem).

Eine weitere Form der elliptischen Kurve erhält man, wenn man auf der komplexen Ebene ein Gitter <v, w>(Z) mit zwei Vektoren v und w aufspannt und alle Gittermaschen auf die Grundmasche abbildet. Wird dann eine "Verklebung" der jeweils gegenüberliegenden Ränder durchgeführt erhält man zunächst einen Zylinder und anschließend (durch nochmaliges "Verkleben") einen Torus, der äquivalent zu einer elliptischen Kurve über den komplexen Zahlen ist. Elliptische Kurven über den komplexen Zahlen lassen sich eindeutig auf ein Gitter der Form < $\tau$ ,1> (mit $\tau$ in der oberen Halbebene) zurückführen.

Siehe auch: Elliptische-Kurven-Kryptosystem

Weblinks

Einfache Einführung in elliptische Kurven (in Zusammenhang mit ECC) (englisch)