Hessisk form av en elliptisk kurva

Inom geometrin är den hessiska kurvan en plan kurva som liknar Descartes folium . Den är uppkallad efter den tyske matematikern Otto Hesse . Denna kurva föreslogs för tillämpning i elliptisk kurvkryptografi , eftersom aritmetik i denna kurvrepresentation är snabbare och kräver mindre minne än aritmetik i standard Weierstrass-form .

Definition

En hessisk kurva med ekvation $x^{3}+y^{3}+1=0,3xy$

Låt $K$ vara ett fält och betrakta en elliptisk kurva $E$ i följande specialfall av Weierstrass-form över $K$ :

$$Y^{2}+a_{1}XY+a_{3}Y=X^{3}$$

där kurvan har diskriminant $\Delta =\left(a_{3}^{3}\left(a_{1}^{3}-27a_{3}\right)\right)=a_{3}^{3}\delta .$ Då har punkten $P=(0,0)$ ordning 3.

För att bevisa att $P=(0,0)$ har ordning 3, notera att tangenten till $E$ vid $P$ är linjen $Y =0$ som skär $E$ med multiplicitet 3 vid $P$ .

Omvänt, givet en punkt $P$ av ordningen 3 på en elliptisk kurva $E$ båda definierade över ett fält $K$ kan man sätta kurvan i Weierstrass-form med ${ \displaystyle P=(0,0)}$ så att tangenten vid $P$ är linjen $Y=0$ . Då är ekvationen för kurvan $Y^{2}+a_{1}XY+a_{3}Y=X^{3}$ med $a_{1},a_{3}\in K$ .

För att få den hessiska kurvan är det nödvändigt att göra följande transformation :

Låt först $\mu$ beteckna en rot av polynomet

$$T^{3}-\delta T^{2}+{\delta ^{2} \over 3}T+a_ {3}\delta ^{2}=0.$$

Sedan

$$\mu ={\delta -a_{1}\delta ^{2/3} \över 3}.$$

Observera att om $K$ har ett ändligt ordningsfält $q\equiv 2{\pmod {3}}$ så har varje element i $K$ en unik kubrot ; i allmänhet $\mu$ i ett förlängningsfält av K .

Genom att nu definiera följande värde ${\textstyle D={\frac {(\mu -\delta )}{\mu }}}$ erhålls en annan kurva, C, som är birationellt ekvivalent med E:

$$C:x^{3}+y^{3}+z^{3}=3Dxyz$$

som kallas kubisk hessisk form (i projektiva koordinater )

$$C:x^{3}+y^{3}+1=3Dxy$$

i det affina planet (tillfredsställer ${\textstil x={\frac {X}{Z}}}$ och ${\textstil y={\frac {Y}{Z}}} )$ .

Dessutom, $D^{3}\neq 1$ (annars skulle kurvan vara singular ).

Utgående från den hessiska kurvan ges en birationellt ekvivalent Weierstrass-ekvation av

$$v^{2}=u^{3}-27D\left(D^{ 3}+8\höger)u+54\vänster(D^{6}-20D^{3}-8\höger),$$

under omvandlingarna:

$$(x,y)=\left(\eta \left(u+ 9D^{2}\höger),-1+\eta \left(3D^{3}-Dx-12\höger)\höger)$$

och

$$(u,v)=\left(-9D^{2}+\varepsilon x,3\varepsilon \ vänster(y-1\höger)\höger)$$

var:

$$\eta ={\ frac {6\left(D^{3}-1\right)\left(v+9D^{3}-3Du-36\right)}{\left(u+9D^{2}\right)^{ 3}+\left(3Dd-Du-12\right)^{3}}}$$

och

$$\varepsilon ={\frac {12\left(D^{3}-1\right)}{Dx+y+1}}$$

Grupprätt

Det är intressant att analysera grupplagen för den elliptiska kurvan, definiera additions- och dubbleringsformlerna (eftersom SPA- och DPA -attackerna är baserade på körtiden för dessa operationer). Dessutom, i det här fallet behöver vi bara använda samma procedur för att beräkna addition, dubblering eller subtraktion av poäng för att få effektiva resultat, som sagt ovan. I allmänhet definieras grupplagen på följande sätt: om tre punkter ligger på samma linje så summerar de till noll . Så med den här egenskapen är grupplagarna olika för varje kurva.

I det här fallet är det korrekta sättet att använda Cauchy-Desboves formler och erhåller punkten vid oändligheten θ = (1 : −1 : 0), det vill säga det neutrala elementet (inversen av θ är θ igen). Låt P = ( x ₁ , y ₁ ) vara en punkt på kurvan. Linjen $y=-x+(x_{1}+y_{1})$ innehåller punkten P och punkten i oändligheten θ . Därför − P den tredje punkten i skärningspunkten mellan denna linje och kurvan. Genom att skära den elliptiska kurvan med linjen erhålls följande villkor $x_{2}-(x_{1}+y_{1 })\cdot x+x_{1}\cdot y_{1}=\theta$

Eftersom $x_{1}+y_{1}+D$ inte är noll (eftersom D ³ är distinkt från 1), är x -koordinaten för − P y ₁ och y - koordinaten för − P är x ₁ , dvs. $-P=(y_{1},x_{1})$ eller i projektiva koordinater $-P=(Y_{1}:X_{1}:Z_{1})$ .

I vissa tillämpningar av elliptisk kurvkryptografi och den elliptiska kurvan faktorisering ( ECM ) är det nödvändigt att beräkna skalära multiplikationer av P , säg [ n ] P för något heltal n , och de är baserade på dubbel-och-lägg-metoden ; dessa operationer kräver additions- och dubbleringsformler.

Fördubbling

Nu, om $P=(X_{1}:Y_{1}:Z_{1})$ är en punkt på den elliptiska kurvan, är det möjligt att definiera en "dubblering" med Cauchy-Desboves formler:

$$[2 ]P=\left(Y_{1}\cdot \left(X_{1}^{3}-Z_{1}^{3}\right):X_{1}\cdot \left(Z_{1}^ {3}-Y_{1}^{3}\right):Z_{1}\cdot \left(Y_{1}^{3}-X_{1}^{3}\right)\right)$$

Tillägg

På samma sätt, för två olika punkter, säg $P=(X_{1}:Y_{1}:Z_{1})$ och ${\displaystyle Q=(X_{2}:Y_{2}:Z_{2})} ,$ det är möjligt att definiera additionsformeln. Låt R beteckna summan av dessa punkter, R = P + Q , då ges dess koordinater av:

$$R=\left(Y_{1}^{2}\cdot X_{2}\cdot Z_{2}-Y_{2}^{2} \cdot X_{1}\cdot Z_{1}:X_{1}^{2}\cdot Y_{2}\cdot Z_{2}-X_{2}^{2}\cdot Y_{1}\cdot Z_{1}:Z_{1}^{2}\cdot X_{2}\cdot Y_{2}-Z_{2}^{2}\cdot X_{1}\cdot Y_{1}\right)$$

Algoritmer och exempel

Det finns en algoritm som kan användas för att lägga till två olika punkter eller för att dubbla; den ges av Joye och Quisquater . Sedan ger följande resultat möjligheten att erhålla dubbleringsoperationen genom addition:

Proposition . Låt P = ( X,Y,Z ) vara en punkt på en hessisk elliptisk kurva E ( K ) . Sedan:

$$2(X:Y:Z)=(Z:X:Y)+(Y:Z:X )$$

 

 

 

 

()

Dessutom har vi ( Z : X : Y ) ≠ ( Y : Z : X ) .

Slutligen, i motsats till andra parametreringar , finns det ingen subtraktion för att beräkna negationen av en punkt. Därför kan denna additionsalgoritm också användas för att subtrahera två punkter P = ( X ₁ : Y ₁ : Z ₁ ) och Q = ( X ₂ : Y ₂ : Z ₂ ) på en hessisk elliptisk kurva:

$$(X_{1 }:Y_{1}:Z_{1})-(X_{2}:Y_{2}:Z_{2})=(X_{1}:Y_{1}:Z_{1})+(Y_{ 2}:X_{2}:Z_{2})$$

 

 

 

 

()

Sammanfattningsvis, genom att anpassa ordningen på inmatningarna enligt ekvation (2) eller (3), kan additionsalgoritmen som presenteras ovan användas likgiltigt för: Addera 2 (diff.) punkter, Fördubbla en punkt och subtrahera 2 punkter med endast 12 multiplikationer och 7 hjälpvariabler inklusive de 3 resultatvariablerna. Före uppfinningen av Edwards-kurvor representerar dessa resultat den snabbaste kända metoden för att implementera den elliptiska kurvan skalär multiplikation mot motstånd mot sidokanalattacker .

För vissa algoritmer är skydd mot sidokanalattacker inte nödvändigt. Så för dessa fördubblingar kan vara snabbare. Eftersom det finns många algoritmer ges bara det bästa för additions- och dubbleringsformlerna här, med ett exempel för var och en:

Tillägg

Låt P ₁ = ( X ₁ : Y ₁ : Z ₁ ) och P ₂ = ( X ₂ : Y ₂ : Z ₂ ) vara två punkter skilda från θ . Om vi ​​antar att Z ₁ = Z ₂ = 1 så ges algoritmen av:

A = X ₁ Y ₂

B = Y ₁ X ₂

X ₃ = B Y ₁ - Y ₂ A

Y ₃ = X ₁ A - B X ₂

Z ₃ = Y ₂ X ₂ - X ₁ Y ₁

Kostnaden som behövs är 8 multiplikationer och 3 additioner läskostnad för 7 multiplikationer och 3 additioner, beroende på den första punkten.

Exempel

Givet följande punkter i kurvan för d = −1 P ₁ = (1:0:−1) och P ₂ = (0:−1:1) , så har vi om P ₃ = P ₁ + P _{2 :}

X ₃ = 0 − 1 = −1

Y ₃ = −1−0 = −1

Z ₃ = 0 − 0 = 0

Sedan: P ₃ = (−1:−1:0)

Fördubbling

Låt P = ( X ₁ : Y ₁ : Z ₁ ) vara en punkt, då ges dubbleringsformeln av:

• A = X ₁ ²
• B = Y ₁ ²
• D = A + B
• G = ( X ₁ + Y ₁ ) ² − D
• X ₃ = (2 Y ₁ − G ) × ( X ₁ + A + 1)
• Y ₃ = ( G − 2 X ₁ ) × ( Y ₁ + B + 1)
• Z ₃ = ( X ₁ − Y ₁ ) × ( G + 2 D )

Kostnaden för denna algoritm är tre multiplikationer + tre kvadrater + 11 additioner + 3×2.

Exempel

Om $P=(-1:-1:1)$ är en punkt över den hessiska kurvan med parametern d = −1 , då är koordinaterna för $2P=(X:Y:Z)$ ges av:

X = (2 . (−1) − 2) (−1 + 1 + 1) = −4

Y = (−4 − 2 . (−1)) ((−1) + 1 + 1) = −2

Z = (−1 − (−1)) ((−4) + 2 . 2) = 0

Det vill säga $2P=(-4:-2:0)$

Utökade koordinater

Det finns ett annat koordinatsystem med vilket en hessisk kurva kan representeras; dessa nya koordinater kallas utökade koordinater . De kan påskynda tillägget och fördubblingen. För mer information om operationer med de utökade koordinaterna, se:

http://hyperelliptic.org/EFD/g1p/auto-hessian-extended.html#addition-add-20080225-hwcd

$x$ och $y$ representeras av $X,Y,Z,XX, YY,ZZ,XY,YZ,XZ$ som uppfyller följande ekvationer:

• $x=X/Z$
• $y=Y/Z$
• $XX=X\cdot X$
• $YY=Y\cdot Y$
• $ZZ=Z\cdot Z$
• $XY=2\cdot X\cdot Y$
• $YZ=2\cdot Y\cdot Z$
• $XZ=2\cdot X\cdot Z$

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
• Vridna hessiska kurvor

externa länkar

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

Anteckningar

• Otto Hesse (1844), "Über die Elimination der Variabeln aus drei algebraischen Gleichungen vom zweiten Grade mit zwei Variabeln", Journal für die reine und angewandte Mathematik , 10, s. 68–96
•   Marc Joye, Jean-Jacques Quisquater (2001). "Hessiska elliptiska kurvor och sidokanalattacker". Kryptografisk hårdvara och inbyggda system — CHES 2001 . Föreläsningsanteckningar i datavetenskap. Vol. 2162. Springer-Verlag Berlin Heidelberg 2001. s. 402–410. doi : 10.1007/3-540-44709-1_33 . ISBN 978-3-540-42521-2 .
•   NP Smart (2001). "Den hessiska formen av en elliptisk kurva". Kryptografisk hårdvara och inbyggda system — CHES 2001 . Föreläsningsanteckningar i datavetenskap. Vol. 2162. Springer-Verlag Berlin Heidelberg 2001. s. 118–125. doi : 10.1007/3-540-44709-1_11 . ISBN 978-3-540-42521-2 .