Edwards-Kurve

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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]

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

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

Ein Beispiel für eine Edwards-Kurve ist die Kurve über dem Körper mit .

Anwendung in der Kryptografie

[Bearbeiten | Quelltext bearbeiten]

Für kryptografische Anwendungen werden Edwards-Kurven über einem endlichen Körper , zum Beispiel mit prim, definiert. Hierbei ist darauf zu achten, dass die Charakteristik von ungleich 2 ist und dass gewählt wird, da sich die Gleichung andernfalls mit zum Einheitskreis reduziert und mit vier Geraden entstehen. Außerdem sollte kein Quadrat in sein, da andernfalls Sonderfälle bei der Addition zweier Punkte auftreten könnten.

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

Die Summe zweier Punkte und wird gegeben durch die folgende Formel:

Anhand dieser Formel wird auch deutlich, warum der Faktor kein Quadrat in sein darf. Andernfalls könnte oder 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 ist gegeben durch .

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:

Diese Gleichung kann weiter vereinfacht werden, indem man den Krümmungsfaktor ersetzt durch . Dies ist möglich, da der zu verdoppelnde Punkt auf der Kurve liegt und demnach gilt. Die Dopplungsformel wird dann:

Beziehung zu anderen Repräsentationen

[Bearbeiten | Quelltext bearbeiten]

Verdrehte Edwards-Kurven

[Bearbeiten | Quelltext bearbeiten]

Verdrehte Edwards-Kurven sind eine Erweiterung der Edwards-Kurven.[2] Diese fügen einen zusätzlichen Faktor zu der Gleichung hinzu und haben Gleichungen mit der Form . Jede Edwards-Kurve ist also gleichzeitig auch eine verdrehte Edwards-Kurve mit .

Montgomery-Kurven

[Bearbeiten | Quelltext bearbeiten]

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 transformiert werden:

Weierstraß-Kurve

[Bearbeiten | Quelltext bearbeiten]

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:

.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  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.