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

Hessianova křivka rovnice ${ displaystyle x ^ {3} + y ^ {3} + 1 = 0,3xy}$

Nechat ${ displaystyle K}$ být pole a zvážit eliptická křivka ${ displaystyle E}$ v následujícím zvláštním případě Weierstrassova forma přes ${ displaystyle K}$:

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

kde má křivka diskriminující${ displaystyle Delta = (a_ {3} ^ {3} (a_ {1} ^ {3} -27a_ {3})) = a_ {3} ^ {3} delta.}$Pak bod ${ displaystyle P = (0,0)}$ má objednávku 3.

Dokázat to ${ displaystyle P = (0,0)}$ má pořadí 3, všimněte si, že tečna k ${ displaystyle E}$na ${ displaystyle P}$ je čára ${ displaystyle Y = 0}$ který se protíná${ displaystyle E}$ s multiplicitou 3 na ${ displaystyle P}$.

Naopak, daný bod ${ displaystyle P}$ řádu 3 na eliptické křivce ${ displaystyle E}$oba definované přes pole ${ displaystyle K}$ jeden může dát křivku do Weierstrassform s ${ displaystyle P = (0,0)}$ takže tečna v ${ displaystyle P}$je čára ${ displaystyle Y = 0}$. Pak je rovnice křivky${ displaystyle Y ^ {2} + a_ {1} XY + a_ {3} Y = X ^ {3}}$ s ${ displaystyle a_ {1}, a_ {3} v K}$.

Nyní, abychom získali hesenskou křivku, je nutné udělat následující proměna:

Nejprve nechte ${ displaystyle mu}$ označit a vykořenit polynomu

${ displaystyle T ^ {3} - delta T ^ {2} + { delta ^ {2} přes 3} T + a_ {3} delta ^ {2} = 0.}$

Pak

${ displaystyle mu = { delta -a_ {1} delta ^ {2/3} nad 3}.}$

Všimněte si, že pokud ${ displaystyle K}$ má konečné pole řádu${ displaystyle q equiv 2}$ (mod 3), pak každý prvek ${ displaystyle K}$ má jedinečný třetí odmocnina; obecně, ${ displaystyle mu}$ leží v rozšiřujícím poli K..

Nyní definováním následující hodnoty ${ displaystyle D = { frac {3 ( mu - delta)} { mu}}}$ získá se další křivka C, tj birationally ekvivalent prst:

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

který se nazývá kubický pytlovitý tvar (v projektivní souřadnice )

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

v afinní letadlo (uspokojující ${ displaystyle x = { frac {X} {Z}}}$ a ${ displaystyle y = { frac {Y} {Z}}}$ ).

Dále ${ displaystyle D ^ {3} neq 1}$ (jinak by křivka byla jednotné číslo ).

Počínaje hesiánskou křivkou, a birationally ekvivalent Weierstrassova rovnice darováno

${ displaystyle v ^ {2} = u ^ {3} -27D (D ^ {3} +8) u + 54 (D ^ {6} -20D ^ {3} -8), ,}$

pod transformacemi:

${ displaystyle (x, y) = ( eta (u + 9D ^ {2}), - 1+ eta (3D ^ {3} -Dx-12)) ,}$

a

${ displaystyle (u, v) = (- 9D ^ {2} + varepsilon x, 3 varepsilon (y-1)) ,}$

kde:

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

a

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

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 ${ displaystyle theta}$ = (1: -1: 0), tj neutrální prvek (inverzní k ${ displaystyle theta}$ je ${ displaystyle theta}$ znovu). Nechť P = (x₁, y₁) být bodem na křivce. Linie ${ displaystyle y = -x + (x_ {1} + y_ {1})}$ obsahuje bod ${ displaystyle P}$ a bod v nekonečnu ${ displaystyle theta}$. 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 ${ displaystyle x_ {2} - (x_ {1} + y_ {1}) cdot x + x_ {1} cdot y_ {1} = theta}$

Od té doby ${ displaystyle x_ {1} + y_ {1} + D}$ je nenulová (protože ${ displaystyle D ^ {3}}$ je odlišná od 1), souřadnice x ${ displaystyle -P}$ je ${ displaystyle y_ {1}}$ a souřadnice y ${ displaystyle -P}$ je ${ displaystyle x_ {1}}$, tj., ${ displaystyle -P = (y_ {1}, x_ {1})}$ nebo v projektivních souřadnicích ${ displaystyle -P = (Y_ {1}: X_ {1}: Z_ {1})}$ .

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ž ${ displaystyle P = (X_ {1}: Y_ {1}: Z_ {1})}$ je bod na eliptické křivce, je možné definovat operaci "zdvojnásobení" pomocí Cauchy-Desbovesových vzorců:

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

Přidání

Stejným způsobem, řekněme pro dva různé body ${ displaystyle P = (X_ {1}: Y_ {1}: Z_ {1})}$ a ${ displaystyle Q = (X_ {2}: Y_ {2}: Z_ {2})}$, je možné definovat sčítací vzorec. Nechat ${ displaystyle R}$ označit součet těchto bodů, ${ displaystyle R = P + Q}$, pak jsou jeho souřadnice dány vztahem:

${ displaystyle R = (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})}$

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ů ${ displaystyle P = (X_ {1}: Y_ {1}: Z_ {1})}$ a ${ displaystyle Q = (X_ {2}: Y_ {2}: Z_ {2})}$ na hesenské eliptické křivce:

( X₁: Y₁: Z₁) - ( X₂: Y₂: Z₂) = (X₁: Y₁: Z₁) + (Y₂:X₂: Z₂) (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ť P₁ = (X₁: Y₁: Z₁) a P₂ = (X₂: Y₂: Z₂) být dva body odlišné od ${ displaystyle theta}$. Za předpokladu, že Z₁= Z₂= 1, pak je algoritmus dán vztahem:

A = X₁ Y₂

B = Y₁ X₂

X₃ = B Y₁-Y₂ A

Y₃ = X₁ A-B X₂

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

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 P₁= (1: 0: -1) a P₂= (0: -1: 1), pak pokud P₃= P₁+ P₂ my máme:

X₃ = 0-1=-1

Y₃ = -1-0=-1

Z₃ = 0-0=0

Pak: P₃ = (-1:-1:0)

Zdvojnásobení

Nechat P = (X₁ : Y₁ : Z₁) být bod, pak je zdvojnásobující vzorec dán vztahem:

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

Cena tohoto algoritmu je tři násobení + tři čtverce + 11 sčítání + 3 × 2.

Příklad

Li ${ displaystyle P = (- 1: -1: 1)}$ je bod nad hesenskou křivkou s parametrem d = -1, pak souřadnice ${ displaystyle 2P = (X: Y: Z)}$ 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á, ${ displaystyle 2P = (- 4: -2: 0)}$

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

${ displaystyle x}$ a ${ displaystyle y}$ jsou zastoupeny ${ displaystyle X, Y, Z, XX, YY, ZZ, XY, YZ, XZ}$ splňující následující rovnice:

${ displaystyle x = X / Z}$

${ displaystyle y = Y / Z}$

${ displaystyle XX = X cdot X}$

${ displaystyle YY = Y cdot Y}$

${ displaystyle ZZ = Z cdot Z}$

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

${ displaystyle YZ = 2 cdot Y cdot Z}$

${ displaystyle XZ = 2 cdot X cdot Z}$

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

Zkroucené hesiánské křivky

externí odkazy

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

Poznámky

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.