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.^[1]

Definition

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

${\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}$

Hierbei beschreibt der Faktor ${\displaystyle d}$ 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 ${\displaystyle d}$ verkleinert beziehungsweise vergrößert wird.

Beispiel

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

Anwendung in der Kryptografie

Für kryptografische Anwendungen werden Edwards-Kurven über einem endlichen Körper ${\displaystyle K}$, zum Beispiel ${\displaystyle K=\mathbb {F} _{q}}$ mit ${\displaystyle q}$ prim, definiert. Hierbei ist darauf zu achten, dass die Charakteristik von ${\displaystyle K}$ ungleich 2 ist und dass ${\displaystyle d\in \mathbb {F} _{q}\setminus \left\{0,1\right\}}$ gewählt wird, da sich die Gleichung andernfalls mit ${\displaystyle d=0}$ zum Einheitskreis reduziert und mit ${\displaystyle d=1}$ vier Geraden entstehen. Außerdem sollte ${\displaystyle d}$ kein Quadrat in ${\displaystyle \mathbb {F} _{q}}$ 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 ${\displaystyle (x_{1},y_{1})}$ und ${\displaystyle (x_{2},y_{2})}$ wird gegeben durch die folgende Formel:

${\displaystyle (x_{1},y_{1})+(x_{2},y_{2})=\left({\frac {x_{1}y_{2}+x_{2}y_{1}}{1+dx_{1}x_{2}y_{1}y_{2}}},{\frac {y_{1}y_{2}-x_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}\right)}$

Anhand dieser Formel wird auch deutlich, warum der Faktor ${\displaystyle d}$ kein Quadrat in ${\displaystyle \mathbb {F} _{q}}$ sein darf. Andernfalls könnte ${\displaystyle 1+dx_{1}x_{2}y_{1}y_{2}=0}$ oder ${\displaystyle 1-dx_{1}x_{2}y_{1}y_{2}=0}$ 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 ${\displaystyle (x_{1},y_{1})}$ ist gegeben durch ${\displaystyle (-x_{1},y_{1})}$.

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:

${\displaystyle {\begin{aligned}2(x_{1},y_{1})&=(x_{1},y_{1})+(x_{1},y_{1})\\[6pt]&=\left({\frac {x_{1}y_{1}+x_{1}y_{1}}{1+dx_{1}x_{1}y_{1}y_{1}}},{\frac {y_{1}y_{1}-x_{1}x_{1}}{1-dx_{1}x_{1}y_{1}y_{1}}}\right)\\[6pt]&=\left({\frac {2x_{1}y_{1}}{1+dx_{1}^{2}y_{1}^{2}}},{\frac {y_{1}^{2}-x_{1}^{2}}{1-dx_{1}^{2}y_{1}^{2}}}\right)\end{aligned}}}$

Diese Gleichung kann weiter vereinfacht werden, indem man den Krümmungsfaktor ${\displaystyle d}$ ersetzt durch ${\displaystyle d=(x_{1}^{2}y_{1}^{2}-1/x_{1}^{2}y_{1}^{2})}$. Dies ist möglich, da der zu verdoppelnde Punkt ${\displaystyle (x_{1},y_{1})}$ auf der Kurve liegt und demnach ${\displaystyle x_{1}^{2}y_{1}^{2}=1+dx_{1}^{2}y_{1}^{2}}$ gilt. Die Dopplungsformel wird dann:

${\displaystyle {\begin{aligned}2(x_{1},y_{1})&=\left({\frac {2x_{1}y_{1}}{1+dx_{1}^{2}y_{1}^{2}}},{\frac {y_{1}^{2}-x_{1}^{2}}{1-dx_{1}^{2}y_{1}^{2}}}\right)\\[6pt]&=\left({\frac {2x_{1}y_{1}}{x_{1}^{2}+y_{1}^{2}}},{\frac {y_{1}^{2}-x_{1}^{2}}{2-x_{1}^{2}-y_{1}^{2}}}\right)\end{aligned}}}$

Beziehung zu anderen Repräsentationen

Verdrehte Edwards-Kurven

Verdrehte Edwards-Kurven sind eine Erweiterung der Edwards-Kurven.^[2] Diese fügen einen zusätzlichen Faktor ${\displaystyle a}$ zu der Gleichung hinzu und haben Gleichungen mit der Form ${\displaystyle ax^{2}+y^{2}=1+dx^{2}y^{2}}$. Jede Edwards-Kurve ist also gleichzeitig auch eine verdrehte Edwards-Kurve mit ${\displaystyle a=1}$.

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 Montgormery-Kurve mit der Gleichung ${\displaystyle By^{2}=x^{3}+Ax^{2}+x}$ transformiert werden:

${\displaystyle {\frac {4}{a-d}}y^{2}=x^{3}+{\frac {2(a+d)}{a-d}}x^{2}+x}$

Weierstrass-Kurve

Jede Kurve in Montgomery-Form kann auch in Weierstrass-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 Weierstrass-Kurve transformiert werden. Die folgende Gleichung zeigt, wie die Montgomery-Form in die (kurze) Weierstrass-Form transformiert werden kann:

${\displaystyle y^{2}=x^{3}+\left({\frac {3-A^{2}}{3B^{2}}}\right)x+\left({\frac {2A^{3}-9A}{27B^{3}}}\right)}$.

Einzelnachweise

1. ↑ 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. 
2. ↑ Daniel J. Bernstein, Marc Joye, Tanja Lange, Peter Birkner, Christiane Peters: Twisted Edwards Curves.