Edwards kurva

Edwards kurvor av ekvation x ² + y ² = 1 − d · x ² · y ² över de reella talen för d = 300 (röd), d = √ 8 (gul) och d = −0,9 (blå)

Inom matematik är Edwards -kurvorna en familj av elliptiska kurvor som studerades av Harold Edwards 2007. Begreppet elliptiska kurvor över ändliga fält används ofta i elliptisk kurvkryptografi . Tillämpningar av Edwards-kurvor till kryptografi utvecklades av Daniel J. Bernstein och Tanja Lange : de påpekade flera fördelar med Edwards-formen i jämförelse med den mer välkända Weierstrass-formen ^{[ exempel behövs ]} .

Definition

Ekvationen för en Edwards-kurva över ett fält K som inte har karakteristik 2 är:

x^{2}+y^{2}=1+dx^{2}y^{2}\,

för vissa skalär $d\in K\setminus \{0,1\}$ . Även följande form med parametrarna c och d kallas en Edwards-kurva:

x^{2}+y^{2}=c^{2}(1+dx^{2}y^{2} )\,

där c , d ∈ K med cd (1 − c ⁴ · d ) ≠ 0.

Varje Edwards-kurva är birationellt likvärdig med en elliptisk kurva i Montgomery-form , och medger således en algebraisk grupplag när man väl väljer en punkt att fungera som ett neutralt element. Om K är ändlig, kan en betydande del av alla elliptiska kurvor över K skrivas som Edwards-kurvor. Ofta definieras elliptiska kurvor i Edwards form med c=1, utan förlust av generalitet. I de följande avsnitten antas att c=1.

Grupplagen

(Se även Weierstrass curve group law )

Varje Edwards-kurva $x^{2}+y^{2}=1+dx^{2}y^{2}$ över fält K med karakteristik inte lika med 2 med $d\neq 1$ är birationellt ekvivalent med en elliptisk kurva över samma fält: ${ \displaystyle (1/e)v^{2}=u^{3}+(4/e-2)u^{2}+u} ,$ där $e=1-d,u={\frac {1+y}{1-y}},v={\frac {2(1 +y)}{x(1-y)}}$ och punkten $P=(0,1)$ mappas till oändligheten O . Denna birationella kartläggning inducerar en grupp på valfri Edwards-kurva.

Edwards tilläggslag

På varje elliptisk kurva ges summan av två punkter genom ett rationellt uttryck av punkternas koordinater, även om man i allmänhet kan behöva använda flera formler för att täcka alla möjliga par. För Edwards-kurvan, om det neutrala elementet är punkten (0, 1), summan av punkterna $(x_{1},y_{1})$ och $(x_{2},y_{2})$ ges av formeln

(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)\,

Motsatsen till vilken punkt som helst $(x,y)$ är $(-x,y)$ . Punkten $(0,-1)$ har ordning 2, och punkterna $(\pm 1,0)$ har ordning 4. I synnerhet en Edwards-kurva har alltid en ordningspunkt 4 med koordinater i K .

Om d inte är en kvadrat i K och ${\displaystyle \{(x_{1},y_{1}),(x_{2},y_{2})\}\in \{( x,y)|x^{2}+y^{2}=1+dx^{2}y^{2}\}^{2}} ,$ då finns det inga undantagspunkter: nämnarna $1+dx_{1}x_{2}y_{1}y_{2}$ och $1-dx_{1} x_{2}y_{1}y_{2}$ är alltid noll. Därför är Edwards additionslag fullständig när d inte är en kvadrat i K . Detta innebär att formlerna fungerar för alla par av ingångspunkter på Edwards-kurvan utan undantag för dubblering, inget undantag för det neutrala elementet, inget undantag för negativa, etc. Med andra ord, det är definierat för alla par av ingångspunkter på Edwardskurvan över K och resultatet ger summan av ingångspunkterna.

Om d är en kvadrat i K så kan samma operation ha exceptionella punkter, dvs det kan finnas par av punkter $(x_{1},y_{1}),(x_{2},y_{2})\in \{(x,y)| x^{2}+y^{2}=1+dx^{2}y^{2}\}$ så att en av nämnarna blir noll: antingen $1+dx_{1}x_{2}y_{1}y_{2}=0$ eller $1-dx_{1}x_{2}y_ {1}y_{2}=0$ .

En av de attraktiva egenskaperna hos Edwards Addition-lagen är att den är starkt enhetlig , dvs den kan också användas för att dubbla en poäng, vilket förenklar skyddet mot sidokanalangrepp . Tilläggsformeln ovan är snabbare än andra enhetliga formler och har den starka egenskapen att vara fullständig

Exempel på tilläggslag :

Betrakta den elliptiska kurvan i Edwards-formen med d =2

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

och punkten $P_{1}=(1,0)$ på den. Det är möjligt att bevisa att summan av P ₁ med det neutrala elementet (0,1) återigen ger P ₁ . Med hjälp av formeln ovan är koordinaterna för punkten som ges av denna summa:

x_{3}={\frac {x_{1}y_{2}+y_{1} x_{2}}{1+2x_{1}x_{2}y_{1}y_{2}}}=1

y_{3}={\frac {y_{1}y_{2}-x_{1}x_{2}}{1-2x_{1}x_{2}y_{1}y_{ 2}}}=0

En analog på cirkeln

Klockgrupp

För att bättre förstå begreppet "addition" av punkter på en kurva ges ett bra exempel av den klassiska cirkelgruppen:

ta cirkeln med radie 1

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

och betrakta två punkter P ₁ =(x ₁ ,y ₁ ), P ₂ =(x ₂ , y ₂ ) på den. Låt α ₁ och α ₂ vara vinklarna så att:

{\displaystyle }P_{1}=(x_{1},y_{1})=(\sin { \alpha _{1}},\cos {\alpha _{1}})

{\displaystyle }P_ {2}=(x_{2},y_{2})=(\sin {\alpha _{2}},\cos {\alpha _{2}})

Summan av P ₁ och P ₂ ges således av summan av "deras vinklar". Det vill säga, punkten P ₃ =P ₁ + P ₂ är en punkt på cirkeln med koordinater (x ₃ ,y ₃ ), där:

{\displaystyle }x_{3 }=\sin({\alpha }_{1}+{\alpha }_{2})=\sin {\alpha }_{1}\cos {\alpha }_{2}+\sin {\alpha }_{2}\cos {\alpha }_{1}=x_{1}y_{2}+x_{2}y_{1}

{\displaystyle }y_{3}=\cos({\alpha }_{1}+{\alpha }_{2})=\cos {\alpha }_{1}\cos {\alpha } _{2}-\sin {\alpha }_{1}\sin {\alpha }_{2}=y_{1}y_{2}-x_{1}x_{2}.

På detta sätt är additionsformeln för punkter på cirkeln med radie 1:

{\displaystyle }(x_{1}, y_{1})+(x_{2},y_{2})=(x_{1}y_{2}+x_{2}y_{1},y_{1}y_{2}-x_{1} x_{2})

.

Tillägg på Edwards kurvor

Summan av två punkter på Edwards-kurvan med d = -30

Dubbla en punkt på Edwards-kurvan med d=-30

Punkterna på en elliptisk kurva bildar en abelisk grupp: man kan lägga till punkter och ta heltalsmultiplar av en enda punkt. När en elliptisk kurva beskrivs av en icke-singular kubikekvation, då är summan av två punkter P och Q , betecknade P + Q , direkt relaterad till den tredje skärningspunkten mellan kurvan och linjen som går genom P och Q .

Birational mappningen mellan en Edwards-kurva och motsvarande kubiska elliptiska kurva kartlägger de räta linjerna i koniska sektioner $Axy+Bx+Cy+D=0$ . Med andra ord, för Edwards-kurvorna ligger de tre punkterna $P$ , $Q$ och $-(P+Q)$ på en hyperbel .

Givet två distinkta icke-identitetspunkter ${\displaystyle P_{1}=(x_{1},y_{ 1}),P_{2}=(x_{2},y_{2}),P_{1}\neq P_{2}} ,$ koefficienterna för den kvadratiska formen är (upp till skalärer):

$A=(x_{1}-x_{2})+(x_{1}y_{2}-x_{ 2}y_{1})$ ,

$B=(x_{2}y_{2}-x_{1}y_{1})+ y_{1}y_{2}(x_{2}-x_{1})$ ,

$C=x_{1}x_{2}(y_{1}-y_{2}),D=C$

Vid dubblering av en punkt ${\displaystyle P=(x,y)} ligger$ den inversa punkten $-2P$ på koniken som rör kurvan i punkten $P$ . Koefficienterna för den kvadratiska formen som definierar den koniska är (upp till skalärer [ ^{förtydligande behövs ]} ):

$A=dx^{2}y-1$ ,

$B=yx^{2}$ ,

$C=x(1-y),D=C$

Projektiva homogena koordinater

I samband med kryptografi används homogena koordinater för att förhindra fältinversioner som förekommer i den affina formeln. För att undvika inversioner i Edwards ursprungliga additionsformler kan kurvekvationen skrivas i projektiva koordinater som:

$(X^{2}+Y^{2})Z^{2}=Z^{4}+dX^{2 }Y^{2}$ .

En projektiv punkt $(X:Y:Z)$ motsvarar den affina punkten $(X/Z:Y/Z)$ på Edwards kurva.

Identitetselementet representeras av $(0:1:1)$ . Inversen av $(X:Y:Z)$ är $(-X:Y:Z)$ .

Adderingsformeln i homogena koordinater ges av: $(X_{1} :Y_{1}:Z_{1})+(X_{2}:Y_{2}:Z_{2})=(X_{3}:Y_{3}:Z_{3})$

var

$X_{3}=Z_{1}Z_{ 2}(X_{1}Y_{2}+X_{2}Y_{1})(Z_{1}^{2}Z_{2}^{2}-dX_{1}X_{2}Y_{1 }Y_{2})$

$Y_{3}=Z_{1}Z_{ 2}(Y_{1}Y_{2}-X_{1}X_{2})(Z_{1}^{2}Z_{2}^{2}+dX_{1}X_{2}Y_{1 }Y_{2})$

$Z_{3}=(Z_{ 1}^{2}Z_{2}^{2}-dX_{1}X_{2}Y_{1}Y_{2})(Z_{1}^{2}Z_{2}^{2}+ dX_{1}X_{2}Y_{1}Y_{2})$

Algoritm

Addition av två punkter på Edwards-kurvan skulle kunna beräknas mer effektivt i den utökade Edwards-formen ${\displaystyle (X:Y:Z:T)} ,$ där ${\ displaystyle T=XY/Z}$ : $(X_{3}:Y_{3}:Z_{3}:T_{3})=(X_{1}:Y_{1}:Z_{1}:T_{1})+(X_{2} }:Y_{2}:Z_{2}:T_{2})$

$A=X_{1}X_{2};B=Y_{1}Y_{2};C=dT_{1}T_{2};D=Z_{1}Z_{2};$

$E=(X_{1}+Y_{1})(X_{2}+Y_{2})-AB;F=DC;G=D+C;H=BA;$

$X_{3}=E\cdot F;Y_{3}=G\cdot H;Z_{3}=F\cdot G;T_{3}=E\cdot H;$

Fördubbling

Fördubbling kan utföras med exakt samma formel som addition. Fördubbling avser det fall då ingångarna ( x ₁ , y ₁ ) och ( x ₂ , y ₂ ) är lika.

Dubbla en punkt $P=(x,y)$ :

${\begin{aligned}(x,y)+(x,y)&=\left({\frac {2xy}{1+dx^{2} y^{2}}},{\frac {y^{2}-x^{2}}{1-dx^{2}y^{2}}}\right)\\[6pt]&=\ vänster({\frac {2xy}{x^{2}+y^{2}}},{\frac {y^{2}-x^{2}}{2-x^{2}-y^ {2}}}\right)\end{aligned}}$

Nämnarna förenklades baserat på kurvekvationen $x^{2}+y^{2}=1+dx^{2}y^{2}$ . Ytterligare snabbhet uppnås genom att beräkna $2xy$ som $(x+y)^{2}-x^{2}-y^{2 }$ . Detta minskar kostnaden för att fördubbla homomorfa koordinater till 3 M + 4 S + 3 C + 6 a , medan allmän addition kostar 10 M + 1 S + 1 C + 1 D + 7 a . Här M fältmultiplikationer, S är fältkvadrering, D är kostnaden för att multiplicera med kurvparametern d och a är fältaddition.

Exempel på fördubbling

Som i föregående exempel för additionslagen, betrakta Edwards-kurvan med d=2:

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

och punkten $P=(1,0)$ . Koordinaterna för punkten $P_{2}=2P_{1}$ är:

$x_{2}={\frac {2xy}{x^{2}+y^{2}}}=0$

$y_{2}={\frac {y^{2}-x^{2}}{2-(x^ {2}+y^{2})}}=-1$

Punkten som erhålls från dubblering av P är alltså $P_{2}=(0,-1)$ .

Blandad tillsats

Blandad addition är fallet när Z ₂ är känd för att vara 1. I ett sådant fall A=Z ₁^. Z ₂ kan elimineras och den totala kostnaden minskar till 9 M +1 S +1 C +1 D +7 a

Algoritm

A= _Zi^. Z ₂ // med andra ord, A= Z ₁

B= Z ₁²

_C = _X1.X2 _

D= _Yi^. Y ₂

E=d ^. C ^. D

F=BE

G=B+E

X3 ⁼ A. _{_} F((XI ₊ Y1 ₎ . ⁽ X2 ₊ Y2 ₎ -CD)

Y3 ⁼ A. _{_} G ^. (DC)

Z3 ₌ C ^. F ^. G

Tredubbling

Tredubbling kan göras genom att först dubbla poängen och sedan lägga till resultatet till sig självt. Genom att tillämpa kurvekvationen som vid fördubbling får vi

3(x_{1},y_{1})=\left({\frac {(x_{1}^{2}+y_{1}^{2})^{2}-(2y_{ 1})^{2}}{4(x_{1}^{2}-1)x_{1}^{2}-(x_{1}^{2}-y_{1}^{2}) ^{2}}}x_{1},{\frac {(x_{1}^{2}+y_{1}^{2})^{2}-(2x_{1})^{2}} {-4(y_{1}^{2}-1)y_{1}^{2}+(x_{1}^{2}-y_{1}^{2})^{2}}}y_ {1}\höger).\,

Det finns två uppsättningar formler för denna operation i standard Edwards-koordinater. Den första kostar 9 M + 4 S medan den andra behöver 7 M + 7 S . Om S/M- förhållandet är mycket litet, närmare bestämt under 2/3, är den andra uppsättningen bättre, medan den första är att föredra för större förhållande. Med hjälp av additions- och dubbleringsformlerna (som nämnts ovan) beräknas punkten ( X ₁ : Y ₁ : Z _{1 ) symboliskt som 3(} X ₁ : Y ₁ : Z ₁ ) och jämförs med ( X ₃ : Y ₃ : Z ₃ )

Exempel på tredubbling

Genom att ge Edwards-kurvan med d=2 och punkten P ₁ =(1,0), har punkten 3P ₁ koordinater:

$x_{3}={\frac {(x_{1}^{2}+y_{1}^{2})^{2}-(2y_{1})^{2}}{4(x_{1 }^{2}-1)x_{1}^{2}-(x_{1}^{2}-y_{1}^{2})^{2}}}x_{1}=-1$

$y_ {3}={\frac {(x_{1}^{2}+y_{1}^{2})^{2}-2(x_{1})^{2}}{-4(y_{ 1}^{2}-1)y_{1}^{2}+(x_{1}^{2}-y_{1}^{2})^{2}}}y_{1}=0$

Så, 3P1 ₌ (-1,0)=P- ₁ . Detta resultat kan också hittas med tanke på dubbleringsexemplet: 2P ₁ =(0,1), så 3P ₁ = 2P ₁ + P ₁ = (0,-1) + P ₁ = -P ₁ .

Algoritm

A=X ₁²

B=Y ₁²

C=( _2Z1 ) ²

D=A+B

E=D ²

F=2D.(AB)

G=EB.C

H=EA.C

I=F+H

J=FG

X3 ₌ GJX1

Y3 ₌ HIY1

Z3 ₌ IJZl

Denna formel kostar 9 M + 4 S

Inverterade Edwards-koordinater

Bernstein och Lange introducerade ett ännu snabbare koordinatsystem för elliptiska kurvor som kallas Inverted Edward-koordinaterna där koordinaterna ( X : Y : Z ) uppfyller kurvan ( X ² + Y ² ) Z ² = ( dZ ⁴ + X ² Y ² ) och motsvarar den affina punkten ( Z / X , Z / Y ) på Edwards-kurvan x ² + y ² = 1 + dx ² y ² med XYZ ≠ 0.

Inverterade Edwards-koordinater , till skillnad från standard-Edwards-koordinater, har inga kompletta additionsformler: vissa punkter, som det neutrala elementet, måste hanteras separat. Men tilläggsformlerna har fortfarande fördelen av stark förening: de kan användas utan förändring för att dubbla en poäng.

För mer information om operationer med dessa koordinater, se http://hyperelliptic.org/EFD/g1p/auto-edwards-inverted.html

Utökade koordinater för Edward Curves

Det finns ett annat koordinatsystem med vilket en Edwards-kurva kan representeras; dessa nya koordinater kallas utökade koordinater och är till och med snabbare än inverterade koordinater. För mer information om den tidskostnad som krävs i operationerna med dessa koordinater, se: http://hyperelliptic.org/EFD/g1p/auto-edwards.html

Se även

Vriden Edwards-kurva

För mer information om den löptid som krävs i ett specifikt fall, se Tabell över kostnader för operationer i elliptiska kurvor .

Anteckningar

Bernstein, Daniel ; Lange, Tanja (2007), Snabbare tillägg och fördubbling på elliptiska kurvor ( PDF)
Edwards, Harold M. (9 april 2007), "A normal form for elliptic curves", Bulletin of the American Mathematical Society , 44 (3): 393–422, doi : 10.1090/s0273-0979-07-01153-6 , ISSN 0002-9904
Faster Group Operations on elliptic curves , H. Hisil, KK Wong, G. Carter, E. Dawson
DJBernstein, P. Birkner. T. Lange, C.Peters, Optimizing Double-Base Elliptic-Curve Single-Scalar Multiplication (PDF) {{ citation }} : CS1 underhåll: flera namn: lista över författare ( länk )
Washington, Lawrence C. (2008), Elliptic Curves: Number Theory and Cryptography , Discrete Mathematics and its Applications (2nd ed.), Chapman & Hall/CRC, ISBN 978-1-4200-7146-7
Bernstein, Daniel ; Lange, Tanja, Inverterade Edwards-koordinater (PDF)

externa länkar