Edwardskromme

In de wiskunde is een Edwardskromme een soort elliptische kromme. Edwardskrommen werden geïntroduceerd door Harold M. Edwards in 2007. Het concept van elliptische krommen over een eindig lichaam wordt veel gebruikt in de cryptografie. Deze toepassingen van Edwardskrommen in cryptografie zijn voornamelijk ontworpen door Bernstein en Lange: zij toonden aan dat de Edwardsvorm enkele voordelen heeft ten opzichte van de bekende Weierstrassvorm. Versleutelingen gebaseerd op elliptische krommen zijn in opkomst binnen de cryptografie, omdat ze sneller kunnen plaatsvinden.

Definitie[bewerken | brontekst bewerken]

Edwardskromme met vergelijking x² + y² = 1 − d ·x²·y² over de reële getallen voor d = 300 (rood), d = √8 (geel) en d = −0.9 (blauw)

De vergelijking behorende bij een Edwards kromme over een lichaam K welke niet karakteristiek 2 heeft is:

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

voor een scalar $d\in K\setminus \{0,1\}$ . Verder wordt de volgende vorm met parameters c en d ook een Edwardskromme genoemd:

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

waarbij c, d ∈ K met cd(1 − c⁴·d) ≠ 0.

Zonder verlies van algemeenheid kan men elliptische krommen, geschreven in de vorm van een Edwardskromme, definiëren met c = 1, en we zullen dat vanaf hier dan ook aannemen.

Operaties op punten van een Edwardskromme[bewerken | brontekst bewerken]

Het is mogelijk verschillende operaties uit te voeren op de punten van een elliptische kromme, zoals optelling, vermenigvuldiging, etc. Zo ook op de punten van een Edwardskromme, al gaat het hier iets anders in zijn werk. In de volgende secties zal steeds een operatie worden uitgelegd en voorgedaan aan de hand van een uitgewerkt voorbeeld.

Sommeren/Optellen[bewerken | brontekst bewerken]

Op een Edwardskromme is het, net als op iedere andere elliptische kromme, mogelijk punten op te tellen om op deze manier een ander punt te krijgen dat ook op de kromme ligt. Om het concept van optelling van punten op een kromme beter te begrijpen, is het nuttig eens te kijken naar het voorbeeld van punten op een cirkel met straal 1.

Neem de cirkel met straal 1,

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

en neem twee punten op deze cirkel: P₁=(x₁,y₁), P₂=(x₂,y₂). Laat a en b hoeken zijn zodanig dat:

P_{1}=(x_{1},y_{1})=(\sin {a},\cos {a})

P_{2}=(x_{2},y_{2})=(\sin {b},\cos {b})

De som van P₁ en P₂ wordt gegeven door de som van hun hoeken. Oftewel, het punt P₃=P₁+P₂ is een punt op de cirkel met coördinaten (x₃,y₃), waar

{\displaystyle }x_{3}=\sin(a+b)=\sin {a}\cos {b}+\sin {b}\cos {a}=x_{1}y_{2}+x_{2}y_{1}

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

Op deze manier wordt de formule voor het optellen van twee punten op de cirkel met radius 1 gelijk aan:

{\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})

.

Wanneer we hetzelfde willen doen voor twee punten op een Edwardskromme ((x₁, y₁) en (x₂, y₂)), is het resultaat een ander punt op de Edwardskromme, met coördinaten

(x_{1},y_{1})+(x_{2},y_{2})=\left({\frac {x_{1}y_{2}+y_{1}x_{2}}{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}}}\right)\,

Het neutrale element van deze optelling is (0,1). De inverse van een punt (x₁y₁) is (−x₁y₁).

Wanneer d geen kwadraat is in K, zijn er geen uitzonderingen op de regel: de noemers 1 + dx₁x₂y₁y₂ en 1 − dx₁x₂y₁y₂ zijn altijd ongelijk aan nul. Daarom is de Edwardsoptelling volledig, wanneer d geen kwadraat is in K. Dit betekent dat de formules werken voor elk paar van punten op de Edwardskromme, zonder uitzonderingen. In andere woorden, deze optelling is goed gedefinieerd voor alle paren van punten op de Edwardskromme over K en het resultaat is de som van de twee ingegeven punten.

Als d wel een kwadraat is in K, dan zijn er wel uitzonderingspunten te bedenken voor de operatie. Dat wil zeggen, er kunnen paren van punten (x₁, y₁) en (x₂, y₂) zijn waar 1 + dx₁x₂y₁y₂ = 0 of 1 − dx₁x₂y₁y₂ = 0.

Voorbeeld van optelling:

Neem de elliptische curve in de Edwards vorm met d=2,

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

,

en het punt $P_{1}=(1,0)$ op deze kromme. Het is mogelijk te bewijzen dat de som van P₁met het neutrale element (0,1) opnieuw P₁ geeft. Gebruikmakend van de hierboven gegeven formule, worden de coördinaten van het nieuwe punt:

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

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

wat dus inderdaad opnieuw het punt P₁ geeft.

Verdubbeling[bewerken | brontekst bewerken]

Verdubbeling kan gedaan worden met precies dezelfde formule als optelling. Verdubbeling is het geval van optelling waarin de punten (x₁, y₁) en (x₂, y₂) hetzelfde zijn. Aangezien (x₁, y₁) op de Edwards kromme ligt, kun je de coëfficiënten d als volgt vervangen met (x₁² + y₁² − 1)/x₁²y₁²:

{\begin{aligned}2(x_{1},y_{1})&=(x_{1},y_{1})+(x_{1},y_{1})\\[6pt]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}}}\right)\\[6pt]&=\left({\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}}}\right)\end{aligned}}

Voorbeeld van verdubbeling

Neem opnieuw de elliptische curve in de Edwards vorm met d=2

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

en het punt P₁=(1,0). De coördinaten van het punt 2P₁ zijn:

$x_{3}={\frac {2x_{1}y_{1}}{1+dx_{1}^{2}y_{1}^{2}}}=0$

$y_{3}={\frac {y_{1}^{2}-x_{1}^{2}}{1-dx_{1}^{2}y_{1}^{2}}}=-1$

Het punt verkregen met verdubbeling van P₁ is dus P₃=(0,-1).

Verdrievoudiging[bewerken | brontekst bewerken]

Verdrievoudiging kan gedaan worden, door het punt eerst te verdubbelen en het resultaat hiervan dan op te tellen bij het punt zelf. Dit resulteert dan in de volgende formule:

3(x_{1},y_{1})=\left({\frac {(x_{1}^{2}+y_{1}^{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(x_{1})^{2}}{-4(y_{1}^{2}-1)y_{1}^{2}+(x_{1}^{2}-y_{1}^{2})^{2}}}y_{1}\right).\,

Voorbeeld van verdrievoudiging

Gegeven de Edwards kromme met d=2, verdrievoudiging van het punt P₁=(1,0), geeft het punt 3P₁ met coördinaten:

$x_{3}={\frac {(x_{1}^{2}+y_{1}^{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(x_{1})^{2}}{-4(y_{1}^{2}-1)y_{1}^{2}+(x_{1}^{2}-y_{1}^{2})^{2}}}y_{1}=0$

Dus, 3P₁=(-1,0)=P-₁. Hetzelfde resultaat wordt gevonden via het verdubbelings-voorbeeld: 2P₁=(0,1), dus 3P₁ = 2P₁ + P₁ = (0,-1) + P₁ = -P₁.

Het berekenen van de orde[bewerken | brontekst bewerken]

De orde van een punt op de Edwards kromme, is het aantal keer dat je het punt bij zichzelf moet optellen om het neutrale element te krijgen als uitkomst, plus 1. Het neutrale element is (0,1). Het punt (0,-1), heeft bijvoorbeeld orde 2. Dit betekent dat dit punt 1x bij zichzelf optellen, het neutrale element (0,1) als uitkomst heeft, oftewel: 2(0,-1)=(0,1). Nog een eenvoudiger voorbeeld is de orde van het neutrale element zelf, deze is uiteraard 1.

Wanneer je op zoek bent naar de orde van een willekeurig punt op de Edwards kromme, kun je dit op twee manieren aanpakken.

Je kunt het punt bij zichzelf optellen en kijken of dit resulteert in het neutrale punt. Wanneer dit niet zo is, te je bij de uitkomst opnieuw het punt op. Dit doe je totdat het resultaat, je neutrale element is. Het aantal bewerkingen dat je hebt gedaan plus 1, geeft je de orde van het punt.
In sommige gevallen kun je de situatie ook voor jezelf visualiseren met behulp van het eerder gegeven voorbeeld van de klok. Welke hoek maakt het punt met het neutrale element en hoe vaak moet ik deze hoek nemen om voor het eerst een geheel veelvoud van 360 graden te krijgen?

Voorbeeld van het berekenen van de orde

We gaan met beide hierboven beschreven manieren, de orde bepalen van het punt P₁=(1,0), op de Edwards kromme

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

We beginnen met de eerste beschreven methode: Eerder hebben we dit punt al verdubbeld en verdrievoudigd, wat beide resulteerde in een punt ongelijk aan het neutrale element. De verdrievoudiging leverde:

$x_{3}={\frac {(x_{1}^{2}+y_{1}^{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(x_{1})^{2}}{-4(y_{1}^{2}-1)y_{1}^{2}+(x_{1}^{2}-y_{1}^{2})^{2}}}y_{1}=0$

Dus, 3P₁=(-1,0). We gaan hier opnieuw het punt P₁=(1,0) bij optellen. Met behulp van de formule voor optelling, krijgen we:

x_{4}={\frac {x_{1}y_{3}+y_{1}x_{3}}{1+dx_{1}x_{3}y_{1}y_{3}}}=0

y_{4}={\frac {y_{1}y_{3}-x_{1}x_{3}}{1-dx_{1}x_{3}y_{1}y_{3}}}=1

Hieruit volgt dat 4P₁=(0,1), wat gelijk is aan het neutrale element. We kunnen dus concluderen dat de orde van het punt P₁=(1,0) gelijk is aan 4.

Een goede check is, of we met de tweede beschreven methode hetzelfde resultaat vinden:

Het punt P₁=(1,0), maakt een hoek van 90 graden met het neutrale element. 90 graden past precies 4 keer in 360 graden. Hieruit kunnen we concluderen dat de orde van het punt P₁=(1,0), gelijk is aan 4. Dit komt overeen met wat we eerder vonden.

Omschrijven van een Edwards kromme, naar een Montgomery kromme[bewerken | brontekst bewerken]

Kies $K$ een lichaam met een karakteristiek anders dan 2.

Een elliptische kromme in de Montgomery vorm is

$M_{A,B}$ : $Bv^{2}=u^{3}+Au^{2}+u$

met $A\in K\backslash \{-2,2\}$ , $B\in K\backslash \{0\}$

Kies $E_{a,d}$ een elliptische kromme in de (gedraaide) Edwards vorm:

E_{a,d}\ :\ ax^{2}+y^{2}=1+dx^{2}y^{2},\,

met $a,d\in K\backslash \{0\}$ , $a\neq d$ .

Dan is de elliptische kromme in (gedraaide) Edwards vorm $E_{a,d}$ te schrijven als een elliptische kromme in de Montgomery vorm $M_{A,B}$ waarin $A={\frac {2(a+d)}{a-d}}$ en $B={\frac {4}{a-d}}$ .

De map is als volgt:

\psi \,:\,E_{a,d}\rightarrow M_{A,B}

(x,y)\mapsto (u,v)=\left({\frac {1+y}{1-y}},{\frac {1+y}{(1-y)x}}\right)

met inverse:

\psi ^{-1}

:

M_{A,B}\rightarrow E_{a,d}

(u,v)\mapsto (x,y)=\left({\frac {u}{v}},{\frac {u-1}{u+1}}\right)

Omschrijven van een Edwards kromme, naar een Weierstrass kromme[bewerken | brontekst bewerken]

Elke elliptische kromme is birationaal equivalent met een elliptische kromme in Weierstrass vorm. Als K eindig is, dan kan een noemenswaardig deel van alle elliptische krommen over K, geschreven worden als een Edwards kromme en door middel van de hierboven beschreven omschrijving, dus als een Weierstrass kromme.

Neem de betreffende Edwards kromme en schrijf hem eerst in de Montgomery vorm zoals hierboven beschreven. Dit resulteert in een elliptische kromme in de Montgomery vorm:

$M_{A,B}$ : $By^{2}=x^{3}+Ax^{2}+x$ ,

Deze kan dan op de volgende manier in Weierstrass vorm geschreven worden: Deel elke term van de vergelijking voor $M_{A,B}$ door $B^{3}$ en substitueer de variablene x en y, met $u={\frac {x}{B}}$ en $v={\frac {y}{B}}$ . Dit resulteert in: