Elliptische Kurve

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

Beispiel einer elliptischen Kurve über dem Körper der reellen Zahlen

Elliptische Kurven über dem Körper der reellen Zahlen können als die Menge aller Punkte $(x,y) \in \mathbb{R}^2$ angesehen werden, die die Gleichung

$y^2 = x^3 + ax + b \,$

erfüllen. Die (reellen) Koeffizienten a und b müssen dabei die Bedingung $4a^3 + 27b^2 \neq 0$ erfüllen (um Singularitäten auszuschließen). Im Allgemeinen wird man sich bei der Betrachtung der angegebenen Gleichung aber nicht auf den Fall reeller Koeffizienten und Lösungen beschränken, sondern vielmehr den Fall betrachten, dass Koeffizienten und Lösungen aus einem beliebigen Körper stammen. Interessant sind hierbei insbesondere die Körper der komplexen und der rationalen Zahlen sowie endliche Körper und die Frage, welche Beziehungen zwischen elliptischen Kurven bestehen, bei denen die gleiche Formel über verschiedene Körper interpretiert wird.

Elliptische Kurven sind für die Mathematik von Bedeutung, da mit ihrer Hilfe Verbindungen zwischen unterschiedlichen Bereichen der Mathematik geschaffen werden konnten. Der Mathematiker Andrew Wiles bewies im Jahre 1994 den Modularitätssatz, aus dem das bekannte zahlentheoretischen Problem des großen fermatschen Satzes gefolgert werden konnte. Praktische Anwendung finden elliptische Kurven in einigen modernen Verschlüsselungsverfahren (Elliptische-Kurven-Kryptosystem), da mit ihrer Hilfe sogenannte Einwegfunktionen definiert werden können. Weitere Anwendungen finden sich bei der Faktorisierung natürlicher Zahlen.

Der Name der elliptischen Kurven leitet sich historisch davon ab, dass sie elliptische Integrale parametrisieren. Sie sind von Ellipsen zu unterscheiden.

Elliptische Kurven über den reellen Zahlen

Schaubild der Kurven y² = x³ − x und y² = x³ − x + 1

Wir definieren elliptische Kurven über dem Körper der reellen Zahlen als die Menge aller Punkte $(x,y) \in \mathbb{R}^2$, die für reelles a und b die Gleichung

$y^2 = x^3 + ax + b \,$

lösen. Um die Entstehung von Singularitäten (d.h. von Stellen, an denen sich die Kurve selbst schneidet bzw. scharfe Spitzen oder isolierte Punkte ausbildet) zu verhindern, stellen wir zudem an die Koeffizienten die Bedingung

$\Delta := -(4a^3 + 27b^2) \neq 0$.

Die Größe Δ ist die Diskriminante des rechts stehenden kubischen Polynoms x³ + ax + b der elliptischen Kurve und hat eine weitere Bedeutung: Für Δ > 0 besteht das Schaubild der elliptischen Kurve aus zwei Komponenten (siehe linkes Bild), für Δ < 0 hingegen nur aus einer einzigen Komponente (rechtes Bild).

Elliptische Kurven über den komplexen Zahlen

Interpretiert man wie üblich die komplexen Zahlen als Elemente der Gaußschen Zahlenebene, so stellen elliptische Kurven über den komplexen Zahlen eine zweidimensionale Fläche dar, die in den vierdimensionalen $\mathbb{C}^2$ eingebettet ist. Obwohl sich solche Flächen der Anschauung entziehen, lassen sich dennoch Aussagen über ihre Gestalt treffen, wie zum Beispiel über das Geschlecht der Fläche.

Komplexe Tori

Es sei Γ ein (vollständiges) Gitter in der komplexen Zahlenebene $\mathbb C$. Die Faktorgruppe $\mathbb C/\Gamma$ ist eine eindimensionale abelsche kompakte komplexe Liegruppe, die als reelle Liegruppe isomorph zum Torus $S^1\times S^1$ ist. Für eine Veranschaulichung kann man Erzeuger v,w von Γ wählen; der Quotient $\mathbb C/\Gamma$ ergibt sich dann aus der Grundmasche

$\{\lambda v+\mu w\mid 0\leq\lambda,\mu\leq1\},$

indem man jeweils gegenüberliegende Seiten verklebt.

Bezug zu ebenen Kubiken

Ist Γ ein Gitter in der komplexen Zahlenebene, so definieren die zugehörige weierstraßsche p-Funktion und ihre Ableitung eine Einbettung

$\mathbb C/\Gamma\to\mathbb P^2(\mathbb C),\quad z\mapsto(1:\wp(z):\wp'(z)),$

deren Bild die nichtsinguläre Kubik

y² = 4x³ − g₂(Γ)x − g₃(Γ)

ist. Jede nichtsinguläre ebene Kubik ist isomorph zu einer Kubik, die auf diese Weise entsteht.

Klassifikation

Zwei eindimensionale komplexe Tori $\mathbb C/\Gamma_1$ und $\mathbb C/\Gamma_2$ für Gitter Γ₁,Γ₂ sind genau dann isomorph (als komplexe Liegruppen), wenn die beiden Gitter ähnlich sind, d. h. durch eine Drehstreckung auseinander hervorgehen. Jedes Gitter ist zu einem Gitter der Form $\langle1,\tau\rangle_{\mathbb Z}$ ähnlich, wobei τ ein Element der oberen Halbebene $\mathbb H=\{z\in\mathbb C\mid \operatorname{Im}z>0\}$ ist; sind v,w Erzeuger, so kann τ als v / w oder w / v gewählt werden. Die verschiedenen Wahlen für Erzeuger entsprechen der Operation der Gruppe $\mathrm{SL}_2(\mathbb Z)$ auf der oberen Halbebene, die durch

$\begin{pmatrix}a&b\\c&d\end{pmatrix}\tau=\frac{a\tau+b}{c\tau+d}$

gegeben ist. Zwei Elemente τ₁,τ₂ der oberen Halbebene definieren genau dann isomorphe elliptische Kurven $\mathbb C/\langle1,\tau_1\rangle$ und $\mathbb C/\langle1,\tau_2\rangle$, wenn τ₁ und τ₂ in derselben $\mathrm{SL}_2(\mathbb Z)$-Bahn liegen; die Menge der Isomorphieklassen elliptischer Kurven entspricht damit dem Quotientenraum

$\mathrm{SL}_2(\mathbb Z)/\mathbb H;$

dieser Quotient wird von der j-Funktion bijektiv auf $\mathbb C$ abgebildet; dabei ist der Wert der j-Funktion gleich der j-Invarianten der oben angegebenen Kubik.

Elliptische Kurven über den rationalen Zahlen

Die Theorie elliptischer Kurven über dem Körper der rationalen Zahlen ist ein aktives Forschungsgebiet der Zahlentheorie mit einigen berühmten offenen Vermutungen wie der Vermutung von Birch und Swinnerton-Dyer.

Elliptische Kurven über endlichen Körpern

Statt über den rationalen Zahlen kann man auch elliptische Kurven über endlichen Körpern betrachten. In diesem Falle besteht die Ebene, genauer gesagt die projektive Ebene, in der die elliptische Kurve liegt, nur noch aus endlich vielen Punkten. Daher kann auch die elliptische Kurve selbst höchstens noch endlich viele Elemente enthalten, was viele Betrachtungen einfacher machen kann. Von einer Kurve im anschaulichen Sinne kann jedoch keine Rede mehr sein.

Elliptische Kurven über endlichen Körpern werden z. B. in der Kryptographie (Elliptische-Kurven-Kryptosystem) eingesetzt.

Die (bisher noch unbewiesene) Vermutung von Birch und Swinnerton-Dyer versucht, Aussagen über gewisse Eigenschaften elliptischer Kurven über den rationalen Zahlen zu erhalten, indem entsprechende Eigenschaften elliptischer Kurven über endlichen Körpern (sogenannte "reduzierte elliptische Kurven") untersucht werden.

Rechenregeln

Geometrische Interpretation

Aus der Gitterstruktur im Komplexen folgt auch für elliptische Kurven E über den rationalen Zahlen bzw. über endlichen Körpern eine Gruppenstruktur.

Für die rationalen Punkte der elliptischen Kurve (falls sie existieren), wird eine Gruppenstruktur mit „Addition“ angegeben. Geometrisch ist sie so definiert: Der Punkt im Unendlichen ist das neutrale Element $\infty$. Die Spiegelung eines Punktes P an der x-Achse liefert wieder einen rationalen Punkt der Kurve, das Inverse -P von P. Die Gerade durch die rationalen Punkte P, Q schneidet die Kurve in einem dritten Punkt, Spiegelung dieses Punktes an der x-Achse liefert den rationalen Punkt P + Q.

Im Fall einer Tangente an den Punkt P (also dem Grenzfall Q gegen P auf der Kurve) erhält man mit dieser Konstruktion (Schnittpunkt Tangente mit Kurve, dann Spiegelung) den Punkt P + P. Lassen sich keine entsprechenden Schnittpunkte finden, wird der Punkt im Unendlichen zuhilfe genommen, und man hat z. B. im Fall der Tangente ohne zweiten Schnittpunkt: $P + \infty = P.$

Man kann zeigen, dass diese „Addition“ sowohl kommutativ als auch assoziativ ist, sodass sie tatsächlich die Gesetze einer abelschen Gruppe erfüllt.

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 kann auf diese Weise jeder Punkt der Kurve E erreicht werden (d. h. zu jedem Punkt Q auf der Kurve existiert eine natürliche Zahl k mit Q = kP), wenn man die richtigen Erzeugenden P der Gruppe kennt.

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, dass 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).

Addition zweier verschiedener Punkte

Seien P: = (x_P,y_P) und Q = (x_Q,y_Q) die Komponenten der Punkte P und Q. Mit R wird das Ergebnis der Addition $R \colon{=} P \oplus Q \colon{=} (x_R,y_R)$ bezeichnet. Dieser Punkt R hat also die Komponenten (x_R,y_R). Außerdem setze s = (y_P − y_Q) / (x_P − x_Q). Dann ist die Addition $P \oplus Q \colon{=} (x_R,y_R)$ durch

• x_R: = s² − x_P − x_Q und
• y_R: = − y_P + s(x_P − x_R)

definiert.

Die beiden Punkte P und Q dürfen nicht dieselbe X-Koordinate besitzen, da es sonst nicht möglich ist, die Steigung s zu berechnen, da dann entweder P = Q oder P = − Q gilt. Bei der Addition $P \oplus (-P)$ erhält man $s=\tfrac{2y_P}{0}$, wodurch das Ergebnis als $\infty$ (neutrales Element) definiert ist. Dadurch ergibt sich auch, dass P und − P zueinander invers bezüglich der Punktaddition sind. Ist P = Q, handelt es sich um eine Punktverdoppelung.

Verdoppelung eines Punktes

Für die Punktverdoppelung (Addition eines Punktes zu sich selbst) existieren zwei Fälle.

Fall 1: $y_P \neq 0$

• $P \oplus P = R = (x_R,y_R)$
• $s = (3x_P^2 + a)/(2y_P)$. Dabei wird a aus der Kurvengleichung (cy² = x³ + ax + b) herangezogen.
• x_R = s² − 2x_P
• y_R = − y_P + s(x_P − x_R)

Der einzige Unterschied zur Addition von zwei verschiedenen Punkten liegt in der Berechnung der Steigung.

Fall 2: y_P = 0

• $P \oplus P = \infty$

Wegen $y_P=0 \Rightarrow P = (-P)$ ist klar erkennbar, dass P zu sich selbst invers ist.

Rechenregeln für die „Addition“ von Punkten der Kurve

Analytische Beschreibung über die Koordinaten:

Seien

• P,Q zwei verschiedene Punkte
• P = (x_P,y_P)
• Q = (x_Q,y_Q)
• $x_P \neq x_Q$
• $\oplus$ die Addition zweier Punkte und
• $\infty$ das neutrale Element (auch Unendlichkeitspunkt genannt)

Es gelten folgende Regeln:

• $P \oplus Q = Q \oplus P$
• $P \oplus (-P) = \infty$
• $P \oplus \infty = P$
• − P = (x_P, − y_P)
• $(P \oplus Q) \oplus R = P \oplus (Q \oplus R)$

Skalare Multiplikation eines Punktes

Bei der skalaren Multiplikation $n\cdot P$ handelt es sich lediglich um die wiederholte Addition dieses Punktes.

• $n\cdot P = P \oplus \cdots \oplus P$

Diese Multiplikation kann unter Zuhilfenahme eines angepassten Square-&-Multiply-Verfahrens effizient gelöst werden.

Bei einer elliptischen Kurve über dem endlichen Körper GF(q) läuft die Punktaddition rechnerisch auf analoge Weise wie bei der Berechnung über $\mathbb{R}$, jedoch werden die Koordinaten über GF(q) berechnet.

Literatur

• Peter Meier, Jörn Steuding und Rasa Steuding: Elliptische Kurven und eine kühne Vermutung in Spektrum der Wissenschaft Dossier: „Die größten Rätsel der Mathematik“ (6/2009), ISBN 978-3-941205-34-5, Seite 40–47.

Weblinks

• Einfache Einführung in elliptische Kurven (in Zusammenhang mit ECC) (englisch)
• Umfassende Einführung in elliptische Kurven und ECC (englisch)
• Software zur Veranschaulichung von elliptischen Kurven und deren Gruppenstruktur