Elliptische Kurven über $\mathbb{R}\protect$

Um die Bedeutung elliptischer Kurven für die Kryptographie zu verstehen, betrachten wir zunächst elliptische Kurven über dem Körper der reellen Zahlen, da dieser eine sehr gute Anschauung bietet. In späteren Abschnitten können wir dann unsere Erkenntnisse auf einen beliebigen, vorzugsweise endlichen, Körper verallgemeinern.

Definition 1.1   Eine elliptische Kurve $E$ über $\mathbb{R}\protect$ (oder allgemeiner über einem Körper mit Charakterstik² $\neq 2,3$) ist eine Menge von Punkten $\left( x,y\right) \in \mathbb{R}^{2}$, die die folgende Gleichung erfüllen

$$y^{2} = x^{3}+ax+b\quad a,b\in \mathbb{R},$$ (1.1)

zusammen mit einem ,,unendlich fernen Punkt'', der mit $\O$ bezeichnet wird. Wir fordern zusätzlich, daß das Polynom $x^{3}+ax+b$ keine mehrfachen Nullstellen haben darf.

Die elliptische Kurve $y^{2}=x^{3}-x$

Die elliptische Kurve $y^{2}=x^{3}-3x+3$

Das entscheidene an dieser Ansammlung von Punkten in der affinen Ebene ist die Tatsache, daß wir auf diesen Punkten eine Gruppenoperation definieren können. Es war Jacobi (1835) der als erster in ,,De usu Integralium Ellipticorum et Integralium Abelianorum in Analysi Diophantea'' eine solche vorschlug.

Schauen wir uns zunächst eine Gerade $g:$

$$y=\alpha x+\beta$$

an, die zwei verschiedene Punkte $P=\left( x_{1},y_{1}\right)$ und $Q=\left( x_{2},y_{2}\right)$ der Ellipse schneidet.

Dann ist

$$\alpha = \frac{y_{2}-y_{1}}{x_{2}-x_{1}}$$

$$\beta = y_{1}-\alpha x_{1}$$

Ein Punkt von $g$, d.h. $\left( x,\alpha x+\beta \right)$, liegt nun genau dann auf der elliptischen Kurve $E$ (1.1), wenn

$$\left( \alpha x+\beta \right) ^{2}=x^{3}+ax+b.$$

Die Punkte von $g\cap E$ sind also die Nullstellen des kubischen Polynoms

$$x^{3}-\left( \alpha x+\beta \right) ^{2}+ax+b=0.$$

Zwei dieser Nullstellen kennen wir bereits, das sind die $x$-Koordinaten von $P=\left( x_{1},\alpha x_{1}+\beta \right)$ und $Q=\left( x_{2},\alpha x_{2}+\beta \right)$. Ist $x_{3}$ die dritte Nullstellen, dann läßt sich das Polynom in Linearfaktoren zerlegen und es gilt

$$x^{3}-\left( \alpha x+\beta \right) ^{2}+ax+b = \left( x-x_{1}\right) \left( x-x_{2}\right) \left( x-x_{3}\right)$$

Durch Koeffizientenvergleich (für den Koeffizienten vor $x^{2}$) erhalten wir dann

$$-x_{1}-x_{2}-x_{3}=-\alpha ^{2},$$

also $x_{3}=\alpha ^{2}-x_{1}-x_{2}$. Damit sind die Koordinaten eines dritten Punktes $\left( x_{3},y_{3}\right) \in g\cap E$ gegeben durch

$$x_{3} = \left( \frac{y_{2}-y_{1}}{x_{2}-x_{1}}\right) ^{2}-x_{1}-x_{2}$$ (1.2)

$$y_{3} = \alpha x_{3}+\beta =\alpha x_{3}+y_{1}-\alpha x_{1}=y_{1}+\frac{y_{2}-y_{1}}{x_{2}-x_{1}}\cdot \left( x_{3}-x_{1}\right)$$ (1.3)

Im Falle $x_{1}=x_{2}$, also falls die Gerade parallel zur $y$-Achse verläuft, bezeichnen wir $\left( x_{3},y_{3}\right)$ mit $\O$.

Diese Herleitung zeigt, daß zu zwei gegebenen Punkten $P$ und $Q$ auf $E$, ein dritter Schnittpunkt von $E$ mit der Geraden durch $P$ und $Q$ existiert. Dies liefert uns aber leider noch keine Gruppenoperation, wir müssen den erhaltenen dritten Schnittpunkt noch an der $x$-Achse spiegeln, damit die Gruppenaxiome erfüllt werden.

Die Begriffe Gerade und Tangente lassen sich auch rein algebraisch formulieren, so daß die oben hergeleitete Schnitteigenschaft auch über beliebigen Körpern erhalten bleibt. Dann bleibt auch die folgende definierte Operation im allgemeinen Fall (mit leichten Modifikationen) erhalten.

Definition 1.2   Sei $E$ eine elliptische Kurve über einem Körper $\mathbb{K}$ (mit Charakteristik $\neq 2,3$). Seien $P$ und $Q$ beliebige Punkte auf $E,$ $\O$ der unendlich ferne Punkt. Dann sei

1. $\O +P:=P$ und $P+\O :=P$ ($\O$ dient als neutrales Element.)
2. $-\O :=\O$
3. Ist $P=\left( x_{1},y_{1}\right) \neq \O$, dann setze $-P:=\left( x_{1},-y_{1}\right)$.
4. Ist $P=-Q$, so setze $P+Q:=\O$.
5. Sind $P,Q\neq \O ,\, P\neq -Q$ und $R$ der dritte Schnittpunkt der Geraden durch $P$ und $Q$ falls $P\neq Q$ bzw. der Tangenten an die Kurve im Punkt $P$ falls $P=Q$, mit der Kurve. Dann setze $P+Q:=-R$.

Theorem 1.3   $\left( E,+\right)$ ist eine abelsche Gruppe mit neutralem Element $\O$.