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+d{x}^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 ${𝔽}_{13}$ mit $d=5$.

Anwendung in der Kryptografie

Für kryptografische Anwendungen werden Edwards-Kurven über einem endlichen Körper $K$, zum Beispiel $K={𝔽}_q$ mit $q$ prim, definiert. Hierbei ist darauf zu achten, dass die Charakteristik von $K$ ungleich 2 ist und dass $d\in {𝔽}_q\setminus \{0,1\}$ 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 ${𝔽}_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)=(\frac{x_1{y}_2+x_2{y}_1}{1+d{x}_1{x}_2{y}_1{y}_2},\frac{y_1{y}_2-x_1{x}_2}{1-d{x}_1{x}_2{y}_1{y}_2})$

Anhand dieser Formel wird auch deutlich, warum der Faktor $d$ kein Quadrat in ${𝔽}_q$ sein darf. Andernfalls könnte $1+d{x}_1{x}_2{y}_1{y}_2=0$ oder $1-d{x}_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{array}{cc}2(x_1,y_1)& =(x_1,y_1)+(x_1,y_1)\\ & =(\frac{x_1{y}_1+x_1{y}_1}{1+d{x}_1{x}_1{y}_1{y}_1},\frac{y_1{y}_1-x_1{x}_1}{1-d{x}_1{x}_1{y}_1{y}_1})\\ & =(\frac{2x_1{y}_1}{1+d{x}_1^2{y}_1^2},\frac{y_1^2-x_1^2}{1-d{x}_1^2{y}_1^2})\end{array}$

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+d{x}_1^2{y}_1^2$ gilt. Die Dopplungsformel wird dann:

$\begin{array}{cc}2(x_1,y_1)& =(\frac{2x_1{y}_1}{1+d{x}_1^2{y}_1^2},\frac{y_1^2-x_1^2}{1-d{x}_1^2{y}_1^2})\\ & =(\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})\end{array}$

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 $a{x}^2+y^2=1+d{x}^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 $B{y}^2=x^3+A{x}^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)$.