Hesenská forma eliptické křivky - Hessian form of an elliptic curve
v geometrie, Hessianova křivka je rovinná křivka podobný folium Descartova. Je pojmenována po německém matematikovi Otto Hesse.Tato křivka byla navržena pro použití v kryptografie eliptické křivky, protože aritmetika v této křivce je rychlejší a vyžaduje méně paměti než aritmetika ve standardu Weierstrassova forma.[1]
Definice

Nechat být pole a zvážit eliptická křivka v následujícím zvláštním případě Weierstrassova forma přes :
kde má křivka diskriminujícíPak bod má objednávku 3.
Dokázat to má pořadí 3, všimněte si, že tečna k na je čára který se protíná s multiplicitou 3 na .
Naopak, daný bod řádu 3 na eliptické křivce oba definované přes pole jeden může dát křivku do Weierstrassform s takže tečna v je čára . Pak je rovnice křivky s .
Nyní, abychom získali hesenskou křivku, je nutné udělat následující proměna:
Nejprve nechte označit a vykořenit polynomu
Pak
Všimněte si, že pokud má konečné pole řádu (mod 3), pak každý prvek má jedinečný třetí odmocnina; obecně, leží v rozšiřujícím poli K..
Nyní definováním následující hodnoty získá se další křivka C, tj birationally ekvivalent prst:
- :
který se nazývá kubický pytlovitý tvar (v projektivní souřadnice )
- :
v afinní letadlo (uspokojující a ).
Dále (jinak by křivka byla jednotné číslo ).
Počínaje hesiánskou křivkou, a birationally ekvivalent Weierstrassova rovnice darováno
pod transformacemi:
a
kde:
a
Skupinové právo
Je zajímavé analyzovat skupinové právo eliptické křivky, definující vzorce sčítání a zdvojení (protože LÁZNĚ a DPA útoky jsou založeny na době běhu těchto operací). Kromě toho v tomto případě stačí použít stejný postup k výpočtu sčítání, zdvojnásobení nebo odčítání bodů, abychom získali efektivní výsledky, jak je uvedeno výše. Obecně je zákon o skupině definován následujícím způsobem: pokud tři body leží ve stejné linii, sečtou se až nula. Díky této vlastnosti jsou tedy zákony skupiny pro každou křivku odlišné.
V tomto případě je správným způsobem použití Cauchy-Desbovesových vzorců, získání bodu v nekonečnu = (1: -1: 0), tj neutrální prvek (inverzní k je znovu). Nechť P = (x1, y1) být bodem na křivce. Linie obsahuje bod a bod v nekonečnu . Proto je -P třetím bodem průsečíku této přímky s křivkou. Protínající eliptickou křivku s přímkou je získána následující podmínka
Od té doby je nenulová (protože je odlišná od 1), souřadnice x je a souřadnice y je , tj., nebo v projektivních souřadnicích .
V některých aplikacích kryptografie eliptické křivky a metoda faktorizace eliptické křivky (ECM ) je nutné vypočítat skalární násobení P, řekněme [n] P pro některé celé číslo n, a jsou založeny na metoda dvojitého přidání; tyto operace vyžadují vzorce pro sčítání a zdvojnásobení.
Zdvojnásobení
Teď když je bod na eliptické křivce, je možné definovat operaci "zdvojnásobení" pomocí Cauchy-Desbovesových vzorců:
Přidání
Stejným způsobem, řekněme pro dva různé body a , je možné definovat sčítací vzorec. Nechat označit součet těchto bodů, , pak jsou jeho souřadnice dány vztahem:
Algoritmy a příklady
Jeden je algoritmus který lze použít k přidání dvou různých bodů nebo ke zdvojnásobení; je to dáno Joye a Quisquater. Následující výsledek pak dává možnost získat operaci zdvojení přidáním:
Tvrzení. Nechat P = (X, Y, Z) být bodem na hesenské eliptické křivce E (K). Pak: 2 (X: Y: Z) = (Z: X: Y) + (Y: Z: X) (2). Kromě toho máme (Z: X: Y) ≠ (Y: Z: X).
Nakonec, na rozdíl od ostatních parametrizace, neexistuje žádné odčítání pro výpočet negace bodu. Tento sčítací algoritmus lze tedy také použít k odečtení dvou bodů a na hesenské eliptické křivce:
( X1: Y1: Z1) - ( X2: Y2: Z2) = (X1: Y1: Z1) + (Y2:X2: Z2) (3)
Abychom to shrnuli, úpravou pořadí vstupů podle rovnice (2) nebo (3) lze výše uvedený adiční algoritmus použít lhostejně pro: Přidání 2 (rozdílových) bodů, Zdvojnásobení bodu a Odečtení 2 bodů pouze 12 multiplikací a 7 pomocných proměnných včetně 3 výsledných proměnných. Před vynálezem Edwardsovy křivky, tyto výsledky představují nejrychleji známou metodu implementace skalárního násobení eliptické křivky směrem k odporu proti útoky postranními kanály.
Pro některé algoritmy ochrana před útoky postranními kanály není nutná. Takže zdvojnásobení může být rychlejší. Vzhledem k tomu, že existuje mnoho algoritmů, jsou zde uvedeny pouze nejlepší vzorce pro sčítání a zdvojení, přičemž pro každý z nich je uveden jeden příklad:
Přidání
Ať P1 = (X1: Y1: Z1) a P2 = (X2: Y2: Z2) být dva body odlišné od . Za předpokladu, že Z1= Z2= 1, pak je algoritmus dán vztahem:
A = X1 Y2
B = Y1 X2
- X3 = B Y1-Y2 A
- Y3 = X1 A-B X2
- Z3 = Y2 X2-X1 Y1
Potřebná cena je 8 násobení a 3 sčítání náklady na sčítání 7 násobení a 3 sčítání, v závislosti na prvním bodě.
- Příklad
Vzhledem k následujícím bodům v křivce pro d = -1 P1= (1: 0: -1) a P2= (0: -1: 1), pak pokud P3= P1+ P2 my máme:
- X3 = 0-1=-1
- Y3 = -1-0=-1
- Z3 = 0-0=0
Pak: P3 = (-1:-1:0)
Zdvojnásobení
Nechat P = (X1 : Y1 : Z1) být bod, pak je zdvojnásobující vzorec dán vztahem:
- A = X12
- B = Y12
- D = A + B
- G = (X1 + Y1)2 − D
- X3 = (2Y1 − G) × (X1 + A + 1)
- Y3 = (G − 2X1) × (Y1 + B + 1)
- Z3 = (X1 − Y1) × (G + 2D)
Cena tohoto algoritmu je tři násobení + tři čtverce + 11 sčítání + 3 × 2.
- Příklad
Li je bod nad hesenskou křivkou s parametrem d = -1, pak souřadnice jsou dány:
X = (2. (- 1) -2) (- 1 + 1 + 1) = -4
Y = (-4-2. (- 1)) ((- 1) + 1 + 1) = -2
Z = (-1 - (- 1)) ((- 4) +2,2) = 0
To znamená,
Rozšířené souřadnice
Existuje další souřadnicový systém, pomocí kterého lze reprezentovat hesiánskou křivku; tyto nové souřadnice se nazývají rozšířené souřadnice. Mohou zrychlit přidávání a zdvojnásobení. Další informace o operacích s rozšířenými souřadnicemi naleznete v:
http://hyperelliptic.org/EFD/g1p/auto-hessian-extended.html#addition-add-20080225-hwcd
a jsou zastoupeny splňující následující rovnice:
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
externí odkazy
Poznámky
- ^ Cauchy-Desboveovy vzorce: Hessian-eliptické křivky a útoky bočním kanálem, Marc Joye a Jean-Jacques Quisquarter
Reference
- 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). "Hessianské eliptické křivky a útoky bočním kanálem". Kryptografický hardware a vestavěné systémy - CHES 2001. Přednášky z informatiky. 2162. Springer-Verlag Berlin Heidelberg 2001. str. 402–410. doi:10.1007/3-540-44709-1_33. ISBN 978-3-540-42521-2.
- N. P. Smart (2001). „Hessianská forma eliptické křivky“. Kryptografický hardware a vestavěné systémy - CHES 2001. Přednášky z informatiky. 2162. Springer-Verlag Berlin Heidelberg 2001. str. 118–125. doi:10.1007/3-540-44709-1_11. ISBN 978-3-540-42521-2.