Edwards-Kurve

Edwards-Kurven sind eine Familie von elliptischen Kurven, die in der Elliptische-Kurven-Kryptografie genutzt werden. Diese Familie von Kurven wurde im Jahr 2007 von Harold Edwards zum ersten Mal vorgestellt.<ref name="Edwards" />

Definition

Datei:Edward-curves.svg

Edwards-Kurven mit Gleichung x² + y² = 1 − d ·x²·y² über den reellen Zahlen mit d = 300 (rot), d = √8 (gelb) und d = −0,9 (blau)

Edwards-Kurven folgen der Gleichung

<math> x^2 + y^2 = 1 + dx^2y^2 </math>

Hierbei beschreibt der Faktor <math>d</math> einen Krümmungsfaktor der Kurve. Edwards-Kurven kann man sich am besten als gekrümmten Einheitskreis vorstellen, wobei der Radius des Kreises bei 45°, 135°, 225° und 315° abhängig vom Faktor <math>d</math> verkleinert beziehungsweise vergrößert wird.

Beispiel

Ein Beispiel für eine Edwards-Kurve ist die Kurve über dem Körper <math>\mathbb{F}_{13}</math> mit <math>d = 5</math>.

Anwendung in der Kryptografie

Für kryptografische Anwendungen werden Edwards-Kurven über einem endlichen Körper <math>K</math>, zum Beispiel <math>K = \mathbb{F}_q</math> mit <math>q</math> prim, definiert. Hierbei ist darauf zu achten, dass die Charakteristik von <math>K</math> ungleich 2 ist und dass <math>d \in \mathbb{F}_q \setminus\left\{0, 1\right\}</math> gewählt wird, da sich die Gleichung andernfalls mit <math>d = 0</math> zum Einheitskreis reduziert und mit <math>d = 1</math> vier Geraden entstehen. Außerdem sollte <math>d</math> kein Quadrat in <math>\mathbb{F}_q</math> sein, da andernfalls Sonderfälle bei der Addition zweier Punkte auftreten könnten.

Addition

Genau wie auf dem Einheitskreis ist das neutrale Element einer Edwards-Kurve der Punkt (0, 1).

Die Summe zweier Punkte <math>(x_1, y_1)</math> und <math>(x_2, y_2)</math> wird gegeben durch die folgende Formel:

<math> (x_1, y_1) + (x_2, y_2) = \left(\frac{x_1y_2 + x_2y_1}{1 + dx_1x_2y_1y_2}, \frac{y_1y_2 - x_1x_2}{1 - dx_1x_2y_1y_2}\right) </math>

Anhand dieser Formel wird auch deutlich, warum der Faktor <math>d</math> kein Quadrat in <math>\mathbb{F}_q</math> sein darf. Andernfalls könnte <math>1 + dx_1x_2y_1y_2 = 0</math> oder <math>1 - dx_1x_2y_1y_2 = 0</math> gelten, und es gäbe dementsprechend Sonderfälle von Punktpaaren, die auf eine andere Art und Weise addiert werden müssen.

Die Inverse eines Punktes <math>(x_1, y_1)</math> ist gegeben durch <math>(-x_1, y_1)</math>.

Dopplung

Ein großer Vorteil von Edwards-Kurven gegenüber anderen Formen elliptischer Kurven ist, dass für die Verdopplung von Punkten die gleiche Berechnungsformel verwendet wird wie für die Addition zweier Punkte. Dies erleichtert die Implementation von Elliptischer-Kurven-Kryptografie und mindert gleichzeitig die Anfälligkeit für Seitenkanalattacken. Ein Punkt auf einer Edwards-Kurve kann also wie folgt verdoppelt werden:

<math>

\begin{align} 2(x_1, y_1) &= (x_1, y_1) + (x_1, y_1) \\[6pt]

&= \left(\frac{x_1y_1 + x_1y_1}{1 + dx_1x_1y_1y_1}, \frac{y_1y_1 - x_1x_1}{1 - dx_1x_1y_1y_1}\right) \\[6pt]
&= \left(\frac{2x_1y_1}{1 + dx_1^2y_1^2}, \frac{y_1^2-x_1^2}{1 - dx_1^2y_1^2}\right)

\end{align} </math>

Diese Gleichung kann weiter vereinfacht werden, indem man den Krümmungsfaktor <math>d</math> ersetzt durch <math>d = (x_1^2y_1^2 - 1 / x_1^2y_1^2)</math>. Dies ist möglich, da der zu verdoppelnde Punkt <math>(x_1, y_1)</math> auf der Kurve liegt und demnach <math>x_1^2y_1^2 = 1 + dx_1^2y_1^2</math> gilt. Die Dopplungsformel wird dann:

<math>

\begin{align} 2(x_1, y_1) &= \left(\frac{2x_1y_1}{1 + dx_1^2y_1^2}, \frac{y_1^2-x_1^2}{1 - dx_1^2y_1^2}\right) \\[6pt]

&= \left(\frac{2x_1y_1}{x_1^2 + y_1^2}, \frac{y_1^2 - x_1^2}{2 - x_1^2 - y_1^2}\right)

\end{align} </math>

Beziehung zu anderen Repräsentationen

Verdrehte Edwards-Kurven

Verdrehte Edwards-Kurven sind eine Erweiterung der Edwards-Kurven.<ref name="Bernstein" /> Diese fügen einen zusätzlichen Faktor <math>a</math> zu der Gleichung hinzu und haben Gleichungen mit der Form <math>ax^2 + y^2 = 1 + dx^2y^2</math>. Jede Edwards-Kurve ist also gleichzeitig auch eine verdrehte Edwards-Kurve mit <math>a = 1</math>.

Montgomery-Kurven

Bernstein und Lange haben auch gezeigt, dass jede Edwards-Kurve auch als Montgomery-Kurve repräsentiert werden kann.

Eine verdrehte Edwards-Kurve kann mithilfe der folgenden Formel in eine äquivalente Montgomery-Kurve mit der Gleichung <math>By^2 = x^3 + Ax^2 + x</math> transformiert werden:

<math>\frac{4}{a-d}y^2 = x^3 + \frac{2(a+d)}{a-d}x^2 + x</math>

Weierstraß-Kurve

Jede Kurve in Montgomery-Form kann auch in Weierstraß-Form, der generellsten Darstellungsform von elliptischen Kurven, dargestellt werden. Da jede Edwards-Kurve in eine verdrehte Edwards-Kurve transformiert werden kann und jede verdrehte Edwards-Kurve auch in eine Montgomery-Kurve transformiert werden kann, kann jede Edwards-Kurve auch in eine Weierstraß-Kurve transformiert werden. Die folgende Gleichung zeigt, wie die Montgomery-Form in die (kurze) Weierstraß-Form transformiert werden kann:

<math>y^2 = x^3 + \left(\frac{3-A^2}{3B^2}\right)x + \left(\frac{2A^3-9A}{27B^3}\right)</math>.

Einzelnachweise

<references> <ref name="Edwards"> Harold M. Edwards: A normal form for elliptic curves (= Bulletin of the American Mathematical Society. Band 44). American Mathematical Society, 2007, S. 393–422, doi:10.1090/s0273-0979-07-01153-6.  </ref> <ref name="Bernstein"> Daniel J. Bernstein, Marc Joye, Tanja Lange, Peter Birkner, Christiane Peters: Twisted Edwards Curves.  </ref> </references>