Edwardsova křivka - Edwards curve

v matematika, Edwardsovy křivky jsou rodina eliptické křivky studoval Harold Edwards v roce 2007. Koncept eliptických křivek konečná pole je široce používán v kryptografie eliptické křivky. Aplikace Edwardsových křivek na kryptografie byly vyvinuty Daniel J. Bernstein a Tanja Lange: poukázali na několik výhod Edwardsovy formy ve srovnání se známějšími Weierstrassova forma.
Definice
Rovnice Edwardsovy křivky nad a pole K. který nemá charakteristika 2 je:
pro některé skalární .Také následující formulář s parametry C a d se nazývá Edwardsova křivka:
kde C, d ∈ K. s CD(1 − C4·d) ≠ 0.
Každá Edwardsova křivka je birationally ekvivalent na eliptickou křivku v Weierstrassova forma, a tak připouští algebraický skupinový zákon, jakmile si člověk zvolí bod, který bude sloužit jako neutrální prvek. Li K. je konečný, pak značný zlomek všech eliptických křivek K. lze psát jako Edwardsovy křivky. Často jsou eliptické křivky ve formě Edwards definovány s c = 1, bez ztráty obecnosti. V následujících částech se předpokládá, že c = 1.
Zákon o skupině
(Viz také Zákon o skupině Weierstrassovy křivky )
Body na eliptické křivce tvoří abelianskou skupinu: lze přidávat body a brát celočíselné násobky jednoho bodu. Když je eliptická křivka popsána ne-singulární kubickou rovnicí, pak součet dvou bodů P a Q, označeno P + Q, přímo souvisí s třetím průsečíkem mezi křivkou a přímkou, která prochází P a Q. Ale u singulárních křivek vyššího stupně, jako jsou Edwardsovy křivky, je situace poněkud komplikovanější. Geometrické vysvětlení zákona sčítání na Edwardsových křivkách najdete v článku „Rychlejší výpočet párování Tate“ od Arene et al.[1]
Edwardsův zákon
Na libovolné eliptické křivce, kterou se rozumí křivka rodu 1 a bod vybraný pro obsluhu neutrálního prvku, je součet dvou bodů dán racionálním vyjádřením souřadnic bodů, i když obecně je možné použít několik vzorců pro pokrytí všech možných párů. Pro Edwardsovu křivku vezměte neutrální prvek být bod (0, 1), součet bodů (X1, y1) a (X2, y2) je dán vzorcem
Převrácená hodnota libovolného bodu (X1, y1) je (-X1, y1). Lze zkontrolovat, zda má bod (0, -1) řád 2 a že body (± 1,0) mají řád 4. Zejména Edwardsova křivka má vždy bod řádu 4 se souřadnicemi v K..
Li d není čtverec v K. a , pak neexistují žádné výjimečné body: jmenovatelé 1 +dx1X2y1y2 a 1 -dx1X2y1y2 jsou vždy nenulové. Proto je Edwardsův dodatkový zákon kompletní, když d není čtverec v K.. To znamená, že vzorce fungují pro všechny páry vstupních bodů na Edwardsově křivce bez výjimek pro zdvojnásobení, bez výjimky pro neutrální prvek, bez výjimky pro negativy atd.[2] Jinými slovy, je definován pro všechny páry vstupních bodů na Edwardsově křivce K. a výsledek udává součet vstupních bodů.
Li d je čtverec v K., pak stejná operace může mít výjimečné body, tj. mohou existovat páry (X1, y1) a (X2, y2) kde 1 +dx1X2y1y2 = 0 nebo 1 -dx1X2y1y2 = 0.
Jednou z atraktivních vlastností zákona o Edwardsově dodatku je, že je silně sjednocený tj. lze jej také použít k zdvojnásobení bodu, což zjednodušuje ochranu proti útok bočním kanálem. Výše uvedený vzorec přidání je rychlejší než jiné sjednocené vzorce a má silnou vlastnost úplnosti[2]
Příklad zákona o sčítání :
Zvažte eliptickou křivku ve formě Edwards s d=2
a pointa na to. Je možné prokázat, že součet P1 s neutrálním prvkem (0,1) dává opět P1. Ve skutečnosti pomocí výše uvedeného vzorce jsou souřadnice bodu daného tímto součtem:
Analog na kruhu

Pro lepší pochopení pojmu „sčítání“ bodů na křivce je pěkný příklad uveden v klasické kružnici:
vezměte kruh o poloměru 1
a zvažte dva body P1= (x1, y1), P2= (x2, y2) na to. Nechť α1 a α2 být takové úhly, aby:
Součet P1 a P2 je tedy dán součtem „jejich úhlů“. To znamená, že bod P3= P1+ P2 je bod na kružnici se souřadnicemi (x3, y3), kde:
Tímto způsobem je součtový vzorec pro body na kružnici o poloměru 1:
- .
Projektivní homogenní souřadnice
V kontextu kryptografie homogenní souřadnice se používají k prevenci inverze pole které se objevují v afinním vzorci. Aby se zabránilo inverzi v původních vzorcích Edwardsova přidání, lze zapsat rovnici křivky projektivní souřadnice tak jako:
.
Projektivní bod (X1 : Y1 : Z1) odpovídá afinní bod (X1/Z1, Y1/Z1) na Edwardsově křivce.
Prvek identity je reprezentován (0: 1: 1). Inverzní (X1 : Y1 : Z1) je (-X1 : Y1 : Z1).
Sčítací vzorec v projektivních homogenních souřadnicích je dán vztahem: [ty jsou zjevně neadekvátní, protože když P1 = P2 pro zdvojnásobení bodu, výsledek jde na X3 = 0, Y3 = 0, Z3 = 0]
- (X3 : Y3 : Z3) = (X1 : Y1 : Z1) + (X2 : Y2 : Z2)
kde
- X3 = Z1Z2(X1Y2 − Y1X2)(X1Y1Z22 + Z12X2Y2)
- Y3 = Z1Z2(X1X2 + Y.1Y2)(X1Y1Z22 - Z12X2Y2)
- Z3 = kZ12Z22(X1X2 + Y.1Y2)(X1Y2 - Y1X2) s k = 1/C.
Algoritmus
Pomocí následujícího algoritmu X3, Y3, Z3 lze psát jako: X3→ GJ, Y3→ HK, Z3→ kJK.d
kde: A → X1Z2,
B → Y1Z2,
C → Z1X2,
D → Z1Y2,
E → AB,
F → CD,
G → E + F,
H → E-F,
J → (A-C) (B + D) -H,
K → (A + D) (B + C) -G
Zdvojnásobení
Zdvojnásobení lze provést s přesně stejným vzorcem jako sčítání. Zdvojnásobení odkazuje na případ, kdy vstupy (X1, y1) a (X2, y2) je známo, že jsou si rovni. Od té doby (X1, y1) je na Edwardsově křivce, lze koeficient nahradit (X12 + y12 − 1)/X12y12 jak následuje:
Tím se sníží stupeň jmenovatele ze 4 na 2, což se projeví rychlejším zdvojnásobením. Obecný přírůstek v souřadnicích Edwards trvá 10M + 1S + 1C + 1D + 7A a zdvojnásobení nákladů 3M + 4S + 3C + 6A kde M je množení polí, S je pole kvadratury, D je cena vynásobení volitelným parametrem křivky a A je přidání pole.
- Příklad zdvojnásobení
Stejně jako v předchozím příkladu pro zákon sčítání zvažte Edwardsovu křivku s d = 2:
a bod P1= (1,0). Souřadnice bodu 2P1 jsou:
Bod získaný zdvojnásobením P1 je tedy P3=(0,-1).
Smíšené přidání
Smíšené přidání je v případě, že Z2 je známo, že je 1. V takovém případě A = Z1.Z2 lze eliminovat a celkové náklady se sníží na 9M+1S+1C+1D+7A
Algoritmus
A = Z1.Z2 // jinými slovy, A = Z1
B = Z12
C = X1.X2
D = Y1.Y2
E = d.C.D
F = B-E
G = B + E
X3= A.F ((XJá+ Y.1).(X2+ Y.2)-CD)
Y3= A.G.(DC)
Z3= C..F.G
Ztrojnásobení
Ztrojnásobení lze provést nejprve zdvojnásobením bodu a následným přidáním výsledku k sobě. Aplikováním křivkové rovnice jako při zdvojnásobení získáme
Pro tuto operaci existují dvě sady vzorců ve standardních souřadnicích Edwards. První stojí 9M + 4S zatímco druhá potřebuje 7M + 7S. Pokud S / M poměr je velmi malý, konkrétně pod 2/3, pak je lepší druhá sada, zatímco pro větší poměry se dává přednost první.[3]Pomocí vzorce pro sčítání a zdvojení (jak je uvedeno výše) je bod (X1 : Y1 : Z1) se symbolicky počítá jako 3 (X1 : Y1 : Z1) a ve srovnání s (X3 : Y3 : Z3)
- Příklad ztrojnásobení
Dát Edwardsovu křivku s d = 2 a bod P1= (1,0), bod 3P1 má souřadnice:
Takže 3P1= (- 1,0) = P-1. Tento výsledek lze také nalézt s ohledem na zdvojnásobující příklad: 2P1= (0,1), tedy 3P1 = 2P1 + P1 = (0, -1) + P1 = -P1.
- Algoritmus
A = X12
B = Y12
C = (2Z1)2
D = A + B
E = D2
F = 2D. (A-B)
G = E-B.C.
H = E-AC
I = F + H
J = F-G
X3= G.J.X1
Y3= H.I.Y1
Z3= I.J.Z1
Tento vzorec stojí 9M + 4S
Obrácené souřadnice Edwards
Bernstein a Lange představili ještě rychlejší souřadnicový systém pro eliptické křivky zvané Obrácené souřadnice Edwarda[4] ve kterém jsou souřadnice (X : Y : Z) uspokojí křivku (X2 + Y2)Z2 = (dZ4 + X2Y2) a odpovídá afinnímu bodu (Z/X, Z/Y) na Edwardsově křivce X2 + y2 = 1 + dx2y2 s XYZ ≠ 0.
Obrácené souřadnice Edwards, na rozdíl od standardních souřadnic Edwards, nemají úplné vzorce pro sčítání: s některými body, například s neutrálním prvkem, se musí zacházet samostatně. Ale vzorce přidání mají stále tu výhodu silného sjednocení: mohou být použity beze změny k zdvojnásobení bodu.
Další informace o operacích s těmito souřadnicemi viz http://hyperelliptic.org/EFD/g1p/auto-edwards-inverted.html
Rozšířené souřadnice pro Edwardovy křivky
Existuje další souřadnicový systém, pomocí kterého lze znázornit Edwardsovu křivku; tyto nové souřadnice se nazývají rozšířené souřadnice[5] a jsou dokonce rychlejší než obrácené souřadnice. Další informace o časových nákladech požadovaných při operacích s těmito souřadnicemi najdete na:http://hyperelliptic.org/EFD/g1p/auto-edwards.html
Viz také
Další informace o době běhu požadované v konkrétním případě najdete v části Tabulka nákladů na operace v eliptických křivkách.
Poznámky
- ^ Christophe Arene; Tanja Lange; Michael Naehrig; Christophe Ritzenthaler (2009). „Rychlejší výpočet párování Tate“. arXiv:0904.0854. Bibcode:2009arXiv0904.0854A. Citováno 28. února 2010.
- ^ A b Danieli. J. Bernstein, Tanja Lange, pag. 3, Rychlejší sčítání a zdvojnásobení na eliptických křivkách
- ^ Bernstein a kol., Optimalizace dvojité báze eliptické křivky single-skalární multiplikace
- ^ Daniel J. Bernstein. Tanja Lange, str.2, Obrácené souřadnice Edwarda
- ^ H. Hisil, K. K. Wong, G. Carter, E. Dawson Rychlejší skupinové operace na eliptických křivkách
Reference
- Bernstein, Daniel; Lange, Tanja (2007), Rychlejší sčítání a zdvojnásobení na eliptických křivkách (PDF)
- Edwards, Harold M. (9. dubna 2007), „Normální forma pro eliptické křivky“, Bulletin of the American Mathematical Society, 44 (3): 393–422, doi:10.1090 / s0273-0979-07-01153-6, ISSN 0002-9904
- Rychlejší skupinové operace na eliptických křivkách, H. Hisil, K. K. Wong, G. Carter, E. Dawson
- DJ Bernstein, P.Birkner. T. Lange, C.Peters, Optimalizace dvojité základny eliptické křivky s jedním skalárním násobením (PDF)CS1 maint: více jmen: seznam autorů (odkaz)
- Washington, Lawrence C. (2008), Eliptické křivky: teorie čísel a kryptografie, Diskrétní matematika a její aplikace (2. vydání), Chapman & Hall / CRC, ISBN 978-1-4200-7146-7
- Bernstein, Daniel; Lange, Tanja, Obrácené souřadnice Edwards (PDF)