Jacobian kurva

Inom matematiken är Jacobi -kurvan en representation av en elliptisk kurva som skiljer sig från den vanliga som definieras av Weierstrass-ekvationen . Ibland används den i kryptografi istället för Weierstrass-formen eftersom den kan ge ett försvar mot enkla och SPA-attacker. det är faktiskt möjligt att använda den allmänna additionsformeln också för att fördubbla en punkt på en elliptisk kurva av denna form: på detta sätt blir de två operationerna omöjliga att skilja från viss sidokanalinformation. Jacobi-kurvan erbjuder också snabbare aritmetik jämfört med Weierstrass-kurvan.

Jacobi-kurvan kan vara av två typer: Jacobi-skärningen , som ges av en skärning av två ytor, och Jacobi-kvartiken .

Elliptiska kurvor: Grunderna

Givet en elliptisk kurva är det möjligt att göra några "operationer" mellan dess punkter: till exempel kan man lägga till två punkter P och Q för att erhålla punkten P + Q som hör till kurvan ; givet en punkt P på den elliptiska kurvan är det möjligt att "dubbla" P, det vill säga hitta [2] P = P + P (hakparenteserna används för att indikera [n]P , punkten P läggs till n gånger), och även hitta negationen av P , det betyder hitta – P . På detta sätt bildar punkterna i en elliptisk kurva en grupp . Observera att gruppoperationens identitetselement inte är en punkt på det affina planet, det visas bara i de projektiva koordinaterna: då O = (0: 1: 0) "punkten i oändligheten", det vill säga det neutrala elementet i grupplagen . _ Att lägga till och dubbla formler är också användbara för att beräkna [n]P , den n :e multipeln av en punkt P på en elliptisk kurva: denna operation anses vara den mest i elliptisk kurvkryptografi .

En elliptisk kurva E , över ett fält K kan sättas i Weierstrassformen y ² = x ³ + ax + b , med a , b i K . Vad som kommer att vara av betydelse senare är ordningspunkt 2 , det vill säga P på E så att [2] P = O och P ≠ O . Om P = ( p , 0) är en punkt på E , så har den ordning 2; mer generellt motsvarar ordningspunkterna 2 rötterna av polynomet f(x) = x ³ + ax + b .

Från och med nu kommer vi att använda E _a,b för att beteckna den elliptiska kurvan med Weierstrass form y ² = x ³ + ax + b .

Om E _a,b är sådant att det kubiska polynomet x ³ + ax + b har tre distinkta rötter i K och b = 0 kan vi skriva E _a,b i Legendre normalform :

E _a,b : y2 = x(x + 1)(x + j ⁾

I det här fallet har vi tre ordningspunkter två: (0, 0), (–1, 0), (– j , 0). I det här fallet använder vi notationen E[j] . Observera att j kan uttryckas i termer av a , b .

Definition: Jacobi korsning

En elliptisk kurva i P ³ ( K ) kan representeras som skärningspunkten mellan två kvadratiska ytor :

$Q:\{Q_{1}(X_ {0},X_{1},X_{2},X_{3})=0\}\cap \{Q_{2}(X_{0},X_{1},X_{2},X_{3 })=0\}$

Det är möjligt att definiera Jacobi-formen av en elliptisk kurva som skärningspunkten mellan två kvadriker. Låt E _a,b vara en elliptisk kurva i Weierstrass-formen, vi tillämpar följande karta på den:

$\Phi :(x,y)\mapsto (X,Y,Z,T) =(x,y,1,x^{2})$

Vi ser att följande ekvationssystem gäller:

$\mathbf {S} :{\begin{cases}X^{2}-TZ=0\\Y ^{2}-aXZ-bZ^{2}-TX=0\end{cases}}$

Kurvan E[j] motsvarar följande skärningspunkt mellan ytor i P ³ ( K ):

$\mathbf {S} 1:{\begin{cases}X^{2}+Y^{2} -T^{2}=0\\kX^{2}+Z^{2}-T^{2}=0\end{fall}}$ .

Det "speciella fallet", E[0] , den elliptiska kurvan har en dubbelpunkt och är därför singularis .

S1 erhålls genom att tillämpa transformationen på E [j ] :

ψ: E[j] → S1

$(x,y)\mapsto (X,Y,Z,T)=(-2y,x^{2}-j,x^{2}+2jx+j,x^{2}+2x +j)$

$O=(0:1:0)\mapsto (0,1,1,1)$

Grupprätt

För S1 är det neutrala elementet i gruppen punkten (0, 1, 1, 1), det vill säga bilden av O = (0: 1: 0) under ψ.

Tillägg och fördubbling

Givet P ₁ = ( X ₁ , Y ₁ , Z ₁ , T ₁ ) och P ₂ = ( X ₂ , Y ₂ , Z ₂ , T ₂ ), två punkter på S1 , koordinaterna för punkten P ₃ = P ₁ + P ₂ är:

$X_{3}=T_{1}Y_{2}X_{1}Z_{2}+Z_{1}X_ {2}Y_{1}T_{2}$

$Y_{3}=T_{1}Y_{2}Y_{ 1}T_{2}-Z_{1}X_{2}X_{1}Z_{2}$

$Z_{ 3}=T_{1}Z_{1}T_{2}Z_{2}-kX_{1}Y_{1}X_{2}Y_{2}$

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

Dessa formler är också giltiga för dubblering: det räcker med att ha P ₁ = P ₂ . Så att addera eller dubbla poäng i S1 är operationer som båda kräver 16 multiplikationer plus en multiplikation med en konstant ( k ).

Det är också möjligt att använda följande formler för att dubbla punkten P ₁ och hitta P ₃ = [2] P ₁ :

$X_{3}=2Y_{1}T_{1}Z_{1}X_{1}$

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

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

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

Med dessa formler behövs 8 multiplikationer för att dubbla en poäng. Det finns dock ännu mer effektiva "strategier" för dubblering som bara kräver 7 multiplikationer. På så sätt är det möjligt att tredubbla en punkt med 23 multiplikationer; faktiskt [3] P ₁ kan erhållas genom att addera P ₁ med [2] P ₁ med en kostnad av 7 multiplikationer för [2] P ₁ och 16 för P ₁ + [2] P ₁

Exempel på addition och fördubbling

Låt K = R eller C och betrakta fallet:

$\mathbf {S} 1:{\begin{cases}X^{2}+Y^{2} -T^{2}=0\\4X^{2}+Z^{2}-T^{2}=0\end{fall}}$

Betrakta punkterna $P_{1}=(1,{\sqrt {3}},0,2)$ och $P_{2}=(1,2,1,{\sqrt {5}})$ : det är lätt att verifiera att P ₁ och P ₂ tillhör S1 (det räcker att se att dessa punkter uppfyller båda ekvationerna i systemet S1 ).

Med hjälp av formlerna ovan för att addera två punkter, koordinaterna för P ₃ , där P ₃ = P ₁ + P ₂ är:

$X_{3}=T_{1}Y_{2}X_{1}Z_{2}+Z_{1 }X_{2}Y_{1}T_{2}=4$

$Y_{3}=T_{1 }Y_{2}Y_{1}T_{2}-Z_{1}X_{2}X_{1}Z_{2}=4{\sqrt {15}}$

$Z_{3}=T_{1}Z_{1}T_{2}Z_{2}-kX_{1}Y_{1}X_{ 2}Y_{2}=-8{\sqrt {3}}$

$T_{3}=(T_{1} Y_{2})^{2}+(Z_{1}X_{2})^{2}=16$

Den resulterande punkten är $P_{3}=(4,4{\sqrt {15}},-8{\sqrt {3}},16 )$ .

Med formlerna ovan för fördubbling är det möjligt att hitta punkten P ₃ = [2] P ₁ :

$X_{3}=2Y_{1}T_{1}Z_{1}X_{1}=0$

$Y_{3}=(T_{1}Y_{1})^{2}-(T_{1}Z_{1} )^{2}+(Z_{1}Y_{1})^{2}=12$

$Z_{3}=(T_{1}Z_{1})^{2}-(T_{1}Y_{1})^{2}+(Z_{1}Y_{1}) ^{2}=-12$

$T_{3}=(T_{1}Z_ {1})^{2}+(T_{1}Y_{1})^{2}-(Z_{1}Y_{1})^{2}=12$

Så i det här fallet P ₃ = [2] P ₁ = (0, 12, –12, 12).

Negation

Givet punkten P ₁ = ( X ₁ , Y ₁ , Z ₁ , T ₁ ) i S1 är dess negation − P ₁ = (− X ₁ , Y ₁ , Z ₁ , T ₁ )

Addition och dubblering i affina koordinater

Givet två affinpunkter P ₁ = ( x ₁ , y ₁ , z ₁ ) och P ₂ = ( x ₂ , y ₂ , z ₂ ), är deras summa en punkt P ₃ med koordinater:

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

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

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

Dessa formler är giltiga även för dubblering med villkoret P ₁ = P ₂ .

Utökade koordinater

Det finns ett annat slags koordinatsystem med vilket en punkt i Jacobi-korsningen kan representeras. Med tanke på följande elliptiska kurva i Jacobi-korsningsformen:

$\mathbf {S} 1:{\begin{cases}x^{2}+y^{2}=1\\ kx^{2}+z^{2}=1\end{case}}$

de utökade koordinaterna beskriver en punkt P = (x, y, z) med variablerna X, Y, Z, T, XY, ZT , där:

$x=X/T$

$y=Y/T$

$z=Z/T$

${\ displaystyle XY=X\cdot Y}$

$ZT=Z\cdot T$

Ibland används dessa koordinater, eftersom de är mer praktiska (i termer av tidskostnad) i vissa specifika situationer. För mer information om operationerna baserade på användningen av dessa koordinater, se http://hyperelliptic.org/EFD/g1p/auto-jintersect-extended.html

Definition: Jacobi quartic

En Jacobi-kvartal av ekvation $y^{2}=x^{4}-1,9x^{2}+1$

En elliptisk kurva i Jacobi-kvartform kan erhållas från kurvan E _a,b i Weierstrass-formen med minst en ordningspunkt 2. Följande transformation f skickar varje punkt i E _a,b till en punkt i Jacobi-koordinaterna, där (X: Y: Z) = (sX: s2 ^Y : sZ) .

f: E _a,b → J

$(p,0)\mapsto (0:-1:1)$

$(x,y)\neq (p,0)\mapsto (2(xp):( 2x+p)(xp)^{2}-y^{2}:y)$

$O\mapsto (0:1:1)$

Genom att applicera f på E _a,b får man en kurva i J av följande form:

$C:\ Y^{2}=eX^{4}-2dX^{2}Z^{2}+Z^{ 4}$

var:

$e={\frac {-(3p^{2}+4a)}{16}},\ \ d={\frac {3p}{4}}$ .

är element i K . C representerar en elliptisk kurva i Jacobi- kvartformen, i Jacobi-koordinater.

Jacobi-kvartal i affina koordinater

Den allmänna formen av en Jacobi-kvartskurva i affina koordinater är:

$y^{2}=ex^{4}+2ax^{2}+1$ ,

där ofta e = 1 antas.

Grupprätt

Det neutrala elementet i grupplagen för C är den projektiva punkten (0: 1: 1).

Addition och dubblering i affina koordinater

Givet två affinpunkter $P_{1}=(x_{1},y_{1})$ och $P_{ 2}=(x_{2},y_{2})$ , deras summa är en punkt $P_{3}=(x_{3},y_{3})$ , så att:

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

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

Liksom i Jacobi-korsningarna är det även i detta fall möjligt att använda denna formel för fördubbling också.

Addition och dubblering i projektiva koordinater

Givet två punkter P ₁ = ( X ₁ : Y ₁ : Z ₁ ) och P ₂ = ( X ₂ : Y ₂ : Z ₂ ) i C′ , koordinaterna för punkten P ₃ = ( X ₃ : Y ₃ : Z ) ₃ ), där P ₃ = P ₁ + P ₂ , ges i termer av P ₁ och P ₂ av formlerna:

$X_{3}=X_{1}Z_{1}Y_{2}+Y_{1}X_{2}Z_{2}$

$Y_{3}=\left(Z_{1}^{2}Z_{2}^{2}+eX_{1}^{2}X_{ 2}^{2}\right)\left(Y_{1}Y_{2}-2aX_{1}X_{2}Z_{1}Z_{2}\right)\ +\ 2eX_{1}X_{2 }Z_{1}Z_{2}\left(X_{1}^{2}Z_{2}^{2}+Z_{1}^{2}X_{2}^{2}\right)$

$Z_{3}=Z_{1}^{2}Z_{2}^{2}-eX_{1}^{2}X_ {2}^{2}$

Man kan använda denna formel även för dubblering, med villkoret att P ₂ = P _{1 : på detta sätt} erhålls punkten P ₃ = P ₁ + P ₁ = [2] P _{1 .}

Antalet multiplikationer som krävs för att addera två punkter är 13 plus 3 multiplikationer med konstanter: i synnerhet finns det två multiplikationer med konstanten e och en med konstanten a .

Det finns några "strategier" för att minska de operationer som krävs för att addera och dubbla poäng: antalet multiplikationer kan minskas till 11 plus 3 multiplikationer med konstanter (se avsnitt 3 för mer information).

Antalet multiplikationer kan reduceras genom att arbeta med konstanterna e och d : den elliptiska kurvan i Jacobi-formen kan modifieras för att få ett mindre antal operationer för addering och dubblering. Så, till exempel, om konstanten d i C är signifikant liten, kan multiplikationen med d avbrytas; det bästa alternativet är dock att reducera e : om det är litet försummas inte bara en utan två multiplikationer.

Exempel på addition och fördubbling

Betrakta den elliptiska kurvan E _4,0 , den har en punkt P av ordningen 2: P = ( p , 0) = (0, 0). Därför är a = 4, b = p = 0 så vi har e = 1 och d = 1 och den associerade Jacobi-kvartformen är:

$C:\ Y^{2}=X^{4}+Z^{4}$

Att välja två punkter $P_{1}=(1:{\sqrt {2}}:1)$ och ${\displaystyle P_ {2}=(2:{\sqrt {17}}:1)} ,$ det är möjligt att hitta deras summa P ₃ = P ₁ + P ₂ med hjälp av formlerna för addering ovan:

$X_{3}=1\cdot 1\cdot {\sqrt {17}}+{\sqrt {2}}\cdot 2\cdot 1={\sqrt {17}}+2{\sqrt {2}}$

$Y_(1}^={{3}^ 2}\cdot 1^{2}+1\cdot 1^{2}\cdot 2^{2}\right)\left({\sqrt {2}}\cdot {\sqrt {17}}-2\ cdot 0\cdot 1\cdot 2\cdot 1\cdot 1\right)+2\cdot 1\cdot 1\cdot 2\cdot 1\cdot 1\left(1^{2}\cdot 1^{2}+ 1^{2}\cdot 2^{2}\right)=5{\sqrt {34}}+20$

$Z_ {3}=1^{2}\cdot 1^{2}-1\cdot 1^{2}\cdot 2^{2}=-3$ .

Så

$P_{3}=({\sqrt {17}}+2{\sqrt {2}}:5{\sqrt {34} }+20:-3)$ .

erhålls punkten P ₄ = [2] P _{1 :}

$X_{3}=1\cdot 1\cdot {\sqrt {2}}+{\sqrt {2}}\cdot 1\ cdot 1=2{\sqrt {2$

$Y_{3}=\left(1+1\cdot 1\right)\left({\sqrt {2}}\cdot {\sqrt {2}}-2\cdot 0\cdot 1\cdot 1\cdot 1\cdot 1\right)+2\cdot 1\left(1^{2}\cdot 1^{2}+1^{2}\cdot 1^{2}\ höger)=8$

$Z_{3}=1^{2}\cdot 1^{2}-1\cdot 1^{2 }\cdot 1^{2}=0$

Så

$P_{4}=(2{\sqrt {2}}:8:0)$ .

Negation

Negationen av en punkt P ₁ = ( X ₁ : Y ₁ : Z ₁ ) är: − P ₁ = (− X ₁ : Y ₁ : Z ₁ )

Alternativa koordinater för Jacobi-kvartalet

Det finns andra koordinatsystem som kan användas för att representera en punkt i en Jacobi-kvartik: de används för att få snabba beräkningar i vissa fall. För mer information om den tidskostnad som krävs i operationerna med dessa koordinater, se http://hyperelliptic.org/EFD/g1p/auto-jquartic.html

Givet en affin Jacobi-kvartik

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

de fördubblingsorienterade XXYZZ - koordinaterna introducerar en ytterligare kurvparameter c som uppfyller a ² + c ² = 1 och de representerar en punkt (x, y) som (X, XX, Y, Z, ZZ, R) , så att:

$x=X/Z$

$y=Y/ZZ$

$XX=X^{2}$

$ZZ=Z^{2}$

$R=2\cdot X\cdot Z$

de fördubblingsorienterade XYZ - koordinaterna , med samma ytterligare antagande ( a ² + c ² = 1), representerar en punkt (x, y) med (X, Y, Z) som uppfyller följande ekvationer:

$x=X/Z$

$y=Y/Z^{2}$

Genom att använda XXYZZ- koordinaterna finns det inget ytterligare antagande, och de representerar en punkt (x, y) som (X, XX, Y, Z, ZZ) så att:

$x=X/Z$

$y=Y/ZZ$

$XX=X^{2}$

$ZZ=Z^{2}$

medan XXYZZR-koordinaterna representerar (x, y) som (X, XX, Y, Z, ZZ, R) så att:

$x=X/Z$

$y=Y/ZZ$

$XX=X^{2}$

$ZZ=Z^{2}$

$R=2\cdot X\cdot Z$

med XYZ-koordinaterna ges punkten (x, y) av (X, Y, Z) , med:

$x=X/Z$

$y=Y/Z^{2}$ .

Se även

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

•   Olivier Billet, Marc Joye (2003). "Jacobi-modellen av en elliptisk kurva och sidokanalanalys". Jacobi-modellen av en elliptisk kurva och sidokanalanalys . Föreläsningsanteckningar i datavetenskap. Vol. 2643. Springer-Verlag Berlin Heidelberg 2003. s. 34–42. doi : 10.1007/3-540-44828-4_5 . ISBN 978-3-540-40111-7 .
•   PY Liardet, NP Smart (2001). "Förhindra SPA/DPA i ECC-system med hjälp av Jacobi-formuläret". Kryptografisk hårdvara och inbyggda system — CHES 2001 . Föreläsningsanteckningar i datavetenskap. Vol. 2162. Springer-Verlag Berlin Heidelberg 2001. s. 391–401. doi : 10.1007/3-540-44709-1_32 . ISBN 978-3-540-42521-2 .
• http://hyperelliptic.org/EFD/index.html

externa länkar

• http://hyperelliptic.org/EFD/g1p/index.html