Edwards kurva

Edwards kurvor är en familj av elliptiska kurvor som används i elliptisk kurvkryptografi . Denna familj av kurvor introducerades först av Harold Edwards 2007 .

definition

Edwards kurvor med ekvation x ²  +  y ²  = 1 -  d  · x ² · y ² över de verkliga siffrorna med d  = 300 (röd), d  = √8 (gul) och d  = -0,9 (blå)

Edwards kurvor följer ekvationen

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

Faktorn beskriver en kurvningsfaktor för kurvan. Edwards-kurvor kan bäst föreställas som en krökt enhetscirkel , med cirkelns radie reducerad eller förstorad vid 45 °, 135 °, 225 ° och 315 ° beroende på faktorn . ${\ displaystyle d}$ ${\ displaystyle d}$

exempel

Ett exempel på en Edwards-kurva är kurvan ovanför kroppen med . ${\ displaystyle \ mathbb {F} _ {13}}$${\ displaystyle d = 5}$

Tillämpning i kryptografi

För kryptografiska applikationer definieras Edwards-kurvor över en ändlig kropp , till exempel med prim. Det bör säkerställas att egenskaperna hos olika från 2 och att är valt, annars med ekvationen reduceras till enhetscirkeln med fyra linjer fram. Dessutom finns det bör inte vara en kvadrat i , annars särskilda fall kan uppstå när lägga två punkter. ${\ displaystyle K}$${\ displaystyle K = \ mathbb {F} _ {q}}$${\ displaystyle q}$${\ displaystyle K}$${\ displaystyle d \ in \ mathbb {F} _ {q} \ setminus \ left \ {0,1 \ right \}}$${\ displaystyle d = 0}$${\ displaystyle d = 1}$${\ displaystyle d}$${\ displaystyle \ mathbb {F} _ {q}}$

tillägg

Precis som på enhetscirkeln är det neutrala elementet i en Edwards-kurva punkten (0, 1).

Summan av två punkter och ges av följande formel: ${\ displaystyle (x_ {1}, y_ {1})}$${\ displaystyle (x_ {2}, y_ {2})}$

${\ 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}}} \ höger)}$

Denna formel gör det också klart varför faktorn inte kan vara en kvadrat i . Annars kan eller gälla, och följaktligen skulle det finnas speciella fall av punktpar som måste läggas till på ett annat sätt. ${\ displaystyle d}$${\ displaystyle \ mathbb {F} _ {q}}$${\ displaystyle 1 + dx_ {1} x_ {2} y_ {1} y_ {2} = 0}$${\ displaystyle 1-dx_ {1} x_ {2} y_ {1} y_ {2} = 0}$

Det motsatta av en punkt ges av . ${\ displaystyle (x_ {1}, y_ {1})}$${\ displaystyle (-x_ {1}, y_ {1})}$

Fördubbling

En stor fördel med Edwards-kurvor jämfört med andra former av elliptiska kurvor är att samma formel används för att dubbla poäng som för att lägga till två punkter. Detta förenklar implementeringen av elliptisk kurvkryptografi och minskar samtidigt känsligheten för sidokanalattacker . Så en punkt på en Edwards-kurva kan fördubblas enligt följande:

${\ displaystyle {\ begin {align} 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}}} \ höger) \\ [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}}} \ höger) \ slut {justerad}}}$

Denna ekvation kan förenklas ytterligare genom att ersätta krökningsfaktorn med . Detta är möjligt eftersom punkten som ska fördubblas ligger på kurvan och därför gäller. Fördubblningsformeln blir då: ${\ displaystyle d}$${\ displaystyle d = (x_ {1} ^ {2} y_ {1} ^ {2} -1 / x_ {1} ^ {2} y_ {1} ^ {2})}$${\ displaystyle (x_ {1}, y_ {1})}$${\ displaystyle x_ {1} ^ {2} y_ {1} ^ {2} = 1 + dx_ {1} ^ {2} y_ {1} ^ {2}}$

${\ displaystyle {\ begin {align} 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}}} \ höger) \\ [6pt] & = \ vänster ({\ 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}}} \ höger) \ slut {Justerat}}}$

Förhållande till andra representationer

Twisted Edwards kurvor

Twisted Edwards-kurvor är en förlängning av Edwards-kurvorna. Dessa lägger till en extra faktor i ekvationen och har ekvationer med formen . Så varje Edwards-kurva är också en vriden Edwards-kurva samtidigt . ${\ displaystyle a}$${\ displaystyle ax ^ {2} + y ^ {2} = 1 + dx ^ {2} y ^ {2}}$${\ displaystyle a = 1}$

Montgomery kurvor

Bernstein och Lange har också visat att vilken som helst Edwards-kurva också kan representeras som en Montgomery-kurva .

En tvinnad Edwards-kurva kan omvandlas till en ekvivalent Montgormery-kurva med hjälp av ekvationen med följande formel : ${\ displaystyle By ^ {2} = x ^ {3} + Ax ^ ^ {2} + x}$

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

Weierstrass kurva

Varje kurva i Montgomery-form kan också representeras i Weierstrass-form , den mest allmänna representationen av elliptiska kurvor. Eftersom varje Edwards-kurva kan omvandlas till en tvinnad Edwards-kurva och varje tvinnad Edwards-kurva också kan omvandlas till en Montgomery-kurva, kan varje Edwards-kurva också omvandlas till en Weierstrass-kurva. Följande ekvation visar hur Montgomery-formen kan omvandlas till (kort) Weierstrass-form:

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

Individuella bevis

1. ↑ Harold M. Edwards: En normal form för elliptiska kurvor (=  Bulletin of the American Mathematical Society . Volym 44 ). American Mathematical Society, 2007, sid. 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 .