Zdvojnásobení Doche – Icart – Kohelova křivka - Doubling-oriented Doche–Icart–Kohel curve - Wikipedia

Zdvojnásobení Doche-Icart-Kohelova křivka rovnice

{ displaystyle y ^ {2} = x ^ {3} -x ^ {2} -16x}

v matematika, křivka Doche – Icart – Kohel zaměřená na zdvojnásobení je forma, ve které eliptická křivka lze psát. Jedná se o speciální případ Weierstrassova forma a je také důležité v kryptografie eliptické křivky protože zdvojnásobení se značně zrychluje (výpočet jako složení 2isogeny a jeho dvojí ). Představili jej Christophe Doche, Thomas Icart a David R. Kohel Efektivní skalární násobení isogenymi rozklady.^[1]

Definice

Nechat ${ displaystyle K}$ být pole a nechte ${ displaystyle a v K}$ . Potom se zdvojnásobí Doche – Icart – Kohelova křivka s parametr A v afinní souřadnice je reprezentován:

${ displaystyle y ^ {2} = x ^ {3} + ax ^ {2} + 16ax}$

Ekvivalentně v projektivní souřadnice:

${ displaystyle ZY ^ {2} = X ^ {3} + aZX ^ {2} + 16aXZ ^ {2},}$

s ${ displaystyle x = { frac {X} {Z}}}$ a ${ displaystyle y = { frac {Y} {Z}}}$ .

Všimněte si, že protože tato křivka je zvláštním případem Weierstrassova forma, transformace na nejběžnější formu eliptické křivky (Weierstrassova forma) nejsou nutné.

Skupinové právo

Je zajímavé analyzovat skupinové právo v kryptografie eliptické křivky, definující vzorce pro sčítání a zdvojnásobení, protože tyto vzorce jsou nezbytné pro výpočet násobků bodů [n] P (vidět Umocňování čtvercem ). Obecně platí, že zákon o skupině je 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 se tedy zákony skupiny liší pro každý tvar křivky.

V tomto případě, protože tyto křivky jsou speciálními případy Weierstrassových křivek, je přidání pouze standardním doplněním Weierstrassových křivek. Na druhou stranu lze pro zdvojnásobení bodu použít standardní vzorec zdvojení, ale nebylo by to tak rychlé. V tomto případě neutrální prvek je ${ displaystyle theta = (0: 1: 0)}$ (v projektivních souřadnicích), pro které ${ displaystyle theta = - theta}$ . Pak, pokud ${ displaystyle P = (x, y)}$ je netriviální prvek ( ${ displaystyle P! = O}$ ), pak inverzní hodnota tohoto bodu (přidáním) je –P = (x, -y).

Přidání

V tomto případě, afinní souřadnice bude použit k definování vzorce přidání:

(X₁, y₁) + (x.)₂, y₂) = (x.)₃, y₃) kde

X₃ = (-x₁³+ (x₂-sekera₁²+ (x₂²+ 2ax₂)X₁+ (r₁²-2r₂y₁+ (- x₂³-sekera₂²+ y₂²)))/(X₁²-2x₂X₁+ x₂²)

y₃ = ((-y₁+ 2 roky₂)X₁³+ (- ay₁+ (- 3 r₂X₂+ ay₂))X₁²+ ((3x₂²+ 2ax₂) y₁-2ay₂X₂)X₁+ (r₁³-3 roky₂y₁²+ (- 2x₂³-sekera₂²+ 3 roky₂²) y₁+ (r₂X₂³+ ay₂X₂²-y₂³)))/(-X₁³+ 3x₂X₁²-3x₂²X₁+ x₂³)

Zdvojnásobení

2 (x₁, y₁) = (x.)₃, y₃)

X₃ = 1 / (4r₁²)X₁⁴-8a / r₁²X₁²+ 64a2 / r₁²

y₃ = 1 / (8r₁³)X₁⁶+ ((- a²+ 40a) / (4r₁³))X₁⁴+ ((ay.)₁²+ (16a.)³-640a²)) / (4r₁³))X₁²+ ((- - 4a²y₁²-512a³) / r₁³)

Algoritmy a příklady

Přidání

Nejrychlejším přidáním je následující (ve srovnání s výsledky uvedenými v: http://hyperelliptic.org/EFD/g1p/index.html ), a náklady, které to vyžaduje, jsou 4 násobení, 4 druhé mocniny a 10 sčítání.

A = Y₂-Y₁

AA = A²

B = X₂-X₁

CC = B²

F = X₁CC

Z₃ = 2CC

D = X₂Z₃

ZZ₃ = Z₃²

X₃ = 2 (AA-F) -aZ₃-D

Y₃ = ((A + B)²-AA-CC) (D-X₃) -Y₂ZZ₃

Příklad

Nechat ${ displaystyle K = mathbb {Q}}$ . Nechť P = (X₁, Y₁) = (2,1), Q = (X₂, Y₂) = (1, -1) a a = 1 tedy

A = 2

AA = 4

B = 1

CC = 1

F = 2

Z₃=4

D = 4

ZZ₃=16

X₃=-4

Y₃=336

P + Q = (- 4: 336: 4)

Zdvojnásobení

Následující algoritmus je nejrychlejší (pro porovnání viz následující odkaz: http://hyperelliptic.org/EFD/g1p/index.html ), a cena, kterou to vyžaduje, je 1 násobení, 5 čtverců a 7 sčítání.

A = X₁²

B = A-a16

C = a₂A

YY = Y₁²

YY₂ = 2RR

Z₃ = 2RR₂

X₃ = B²

V = (Y₁+ B) 2-RR-X₃

Y₃ = V (X₃+ 64 C + a (RR₂-C))

ZZ₃ = Z₃²

Příklad

Nechat ${ displaystyle K = mathbb {Q}}$ a = 1. Nechť P = (- 1,2), pak Q = [2] P = (x3, y3) je dáno vztahem:

A = 1

B = -15

C = 2

YY = 4

YY₂=8

Z₃=16

X₃=225

V = 27

Y₃=9693

ZZ₃=256

Q = (225: 9693: 16).

Rozšířené souřadnice

Sčítání a zdvojnásobení výpočtů by mělo být co nejrychlejší, takže je vhodnější použít následující reprezentaci souřadnic:

${ displaystyle x, y}$ jsou zastoupeny ${ displaystyle X, Y, Z, ZZ}$ splňující následující rovnice:

${ displaystyle x = { frac {X} {Z}}}$

${ displaystyle y = { frac {Y} {ZZ}}}$

${ displaystyle ZZ = Z ^ {2}}$

Poté je křivka Dochlingově orientované Doche – Icart – Kohel dána následující rovnicí:

${ displaystyle Y ^ {2} = ZX ^ {3} + aZ ^ {2} X ^ {2} + 16aZ ^ {3} X}$ .

V tomto případě, ${ displaystyle P = (X: Y: Z: ZZ)}$ je obecný bod s inverzní funkcí ${ displaystyle -P = (X: -Y: Z: ZZ)}$ Body nad křivkou dále splňují: ${ displaystyle (X: Y: Z: Z ^ {2}) = ( lambda X: lambda ^ {2} Y: lambda Z: lambda ^ {2} Z ^ {2})}$ pro všechny ${ displaystyle lambda}$ nenulové.

Rychlejší vzorce pro zdvojnásobení těchto křivek a vzorce se smíšeným přidáváním představili Doche, Icart a Kohel; ale dnes tyto vzorce vylepšují Daniel J. Bernstein a Tanja Lange (viz níže odkaz na EFD).

Interní odkaz

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 Doche, Thomas Icart a David R. Kohel, Efektivní skalární násobení isogenymi rozklady

Reference

Christophe Doche, Thomas Icart a David R. Kohel (2006). "Efektivní skalární násobení isogenymi rozklady". Kryptografie veřejného klíče - PKC 2006. Přednášky z informatiky. 3958. Springer Berlin / Heidelberg. 191–206. doi:10.1007/11745853_13. ISBN 978-3-540-33851-2.

Daniel J. Bernstein a Tanja Lange (2008). Analýza a optimalizace jednoduchého skalárního násobení eliptické křivky. ISBN 9780821857892.

externí odkazy

[1] Christophe Doche, Thomas Icart a David R. Kohel, Efektivní skalární násobení isogenymi rozklady

[1]