Elliptische Kurve

aus Wikipedia, der freien Enzyklopädie

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

Elliptische Kurve über dem Körper der reellen Zahlen

Von besonderem Interesse z. B. für die Faktorisierung natürlicher Zahlen sind aufgrund ihrer einfachen Struktur elliptische Kurven E der Form $\, cy^2 = x^3 + ax + b$ mit $c \neq 0$ und $2^2a^3 + 3^3b^2 \neq 0$ . Einige moderne Verschlüsselungsverfahren basieren auf solchen Kurven. Der Name leitet sich historisch davon ab, dass sie elliptische Integrale parametrisieren.

Siehe auch: Elliptische-Kurven-Kryptosystem

Inhaltsverzeichnis

1 Elliptische Kurven über den komplexen Zahlen
2 Elliptische Kurven über endlichen Körpern und über den rationalen Zahlen
3 Weblinks

[Bearbeiten] Elliptische Kurven über den komplexen Zahlen

[Bearbeiten] 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.

[Bearbeiten] 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 2 = 4 x 3 - g 2 (Γ) x - g 3 (Γ)

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

[Bearbeiten] Klassifikation

Zwei eindimensionale komplexe Tori $\mathbb C/\Gamma_1$ und $\mathbb C/\Gamma_2$ für Gitter $Γ 1,Γ 2$ 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 $τ 1,τ 2$ der oberen Halbebene definieren genau dann isomorphe elliptische Kurven $\mathbb C/\langle1,\tau_1\rangle$ und $\mathbb C/\langle1,\tau_2\rangle$ , wenn $τ 1$ und $τ 2$ in derselben $\mathrm{SL}_2(\mathbb Z)$ -Bahn liegen; die Menge der Isomorphieklassen elliptischer Kurven entspricht damit dem Quotientenraum

$\mathrm{SL}_2(\mathbb Z)\backslash\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.

[Bearbeiten] Elliptische Kurven über endlichen Körpern und über den rationalen Zahlen

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: Die Gerade durch die rationalen Punkte P, Q schneidet die Kurve im dritten Punkt, Spiegelung an der x-Achse liefert den rationalen Punkt P + Q. Die Spiegelung eines Punktes P an der x-Achse liefert wieder einen rationalen Punkt der Kurve, das Inverse -P von P. Der Punkt im Unendlichen ist das neutrale Element „0“.

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 („0“) zuhilfe genommen, und man hat z. B. im Fall der Tangente ohne zweiten Schnittpunkt: P + 0 = P.

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

Statt über den rationalen Zahlen kann man auch elliptische Kurven über endlichen Körpern betrachten. Sie werden z. B. in der Kryptografie eingesetzt.

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

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.

[Bearbeiten] 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
$\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)$

[Bearbeiten] Addition zweier verschiedener Punkte

$R = P \oplus Q = (x_R,y_R)$
$s = (y P - y Q) / (x P - x Q)$
$x R = s 2 - x P - x Q$
$y R = - y P + s (x P - x R)$

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=\frac{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.

[Bearbeiten] 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)$ … $a$ wird aus der Kurvengleichung ( $c y 2 = x 3 + a x + b$ ) herangezogen
$x R = s 2 - 2 x 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$

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

[Bearbeiten] 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.

[Bearbeiten] Weblinks

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

Elliptische Kurve

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis

[Bearbeiten] Elliptische Kurven über den komplexen Zahlen

[Bearbeiten] Komplexe Tori

[Bearbeiten] Bezug zu ebenen Kubiken

[Bearbeiten] Klassifikation

[Bearbeiten] Elliptische Kurven über endlichen Körpern und über den rationalen Zahlen

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

[Bearbeiten] Addition zweier verschiedener Punkte

[Bearbeiten] Verdoppelung eines Punktes

[Bearbeiten] Skalare Multiplikation eines Punktes

[Bearbeiten] Weblinks

Ansichten

Persönliche Werkzeuge

Suche

Navigation

Mitmachen

Werkzeuge

Andere Sprachen