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.

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

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

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

Beispiel

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

Anwendung in der Kryptografie

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

$(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 $d$ kein Quadrat in $\mathbb {F} _{q}$ sein darf. Andernfalls könnte $1+dx_{1}x_{2}y_{1}y_{2}=0$ oder $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 $(x_{1},y_{1})$ ist gegeben durch $(-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:

${\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 $d$ ersetzt durch $d=(x_{1}^{2}y_{1}^{2}-1/x_{1}^{2}y_{1}^{2})$. Dies ist möglich, da der zu verdoppelnde Punkt $(x_{1},y_{1})$ auf der Kurve liegt und demnach $x_{1}^{2}y_{1}^{2}=1+dx_{1}^{2}y_{1}^{2}$ gilt. Die Dopplungsformel wird dann:

${\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. Diese fügen einen zusätzlichen Faktor $a$ zu der Gleichung hinzu und haben Gleichungen mit der Form $ax^{2}+y^{2}=1+dx^{2}y^{2}$. Jede Edwards-Kurve ist also gleichzeitig auch eine verdrehte Edwards-Kurve mit $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 $By^{2}=x^{3}+Ax^{2}+x$ transformiert werden:

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

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:

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