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 x2 + y2 = 1 − d ·x2·y2 über den reellen Zahlen mit d = 300 (rot), d = √8 (gelb) und d = −0,9 (blau)

Edwards-Kurven folgen der Gleichung

x2+y2=1+dx2y2

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∈𝔽q∖{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 (x1,y1) und (x2,y2) wird gegeben durch die folgende Formel:

(x1,y1)+(x2,y2)=(x1y2+x2y11+dx1x2y1y2,y1y2−x1x21−dx1x2y1y2)

Anhand dieser Formel wird auch deutlich, warum der Faktor d kein Quadrat in 𝔽q sein darf. Andernfalls könnte 1+dx1x2y1y2=0 oder 1−dx1x2y1y2=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 (x1,y1) ist gegeben durch (−x1,y1).

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:

2(x1,y1)=(x1,y1)+(x1,y1)=(x1y1+x1y11+dx1x1y1y1,y1y1−x1x11−dx1x1y1y1)=(2x1y11+dx12y12,y12−x121−dx12y12)

Diese Gleichung kann weiter vereinfacht werden, indem man den Krümmungsfaktor d ersetzt durch d=(x12y12−1/x12y12). Dies ist möglich, da der zu verdoppelnde Punkt (x1,y1) auf der Kurve liegt und demnach x12y12=1+dx12y12 gilt. Die Dopplungsformel wird dann:

2(x1,y1)=(2x1y11+dx12y12,y12−x121−dx12y12)=(2x1y1x12+y12,y12−x122−x12−y12)

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 ax2+y2=1+dx2y2. 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 Montgomery-Kurve mit der Gleichung By2=x3+Ax2+x transformiert werden:

4a−dy2=x3+2(a+d)a−dx2+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:

y2=x3+(3−A23B2)x+(2A3−9A27B3).