Hessian postać krzywej eliptycznej

W geometrii krzywa Hesji jest płaską krzywą podobną do folii Kartezjusza . Jej nazwa pochodzi od niemieckiego matematyka Otto Hessego . Krzywa ta została zaproponowana do zastosowania w kryptografii krzywych eliptycznych , ponieważ arytmetyka w tej reprezentacji krzywej jest szybsza i wymaga mniej pamięci niż arytmetyka w standardowej postaci Weierstrassa .

Definicja

Krzywa Hessego z równania

{\ Displaystyle x ^ {3} + y ^ {3} + 1 = 0,3xy}

Niech będzie polem i rozważmy krzywą eliptyczną w następującym szczególnym przypadku $formy$ Weierstrassa nad ${$ $displaystyle K$ }

{\ Displaystyle Y ^ {2} + a_ {1} XY + a_ {3} Y = X ^ {3}}

gdzie krzywa ma wyróżnik

{\ Displaystyle \ Delta = \ lewo (a_ {3} ^ {3} \ lewo (a_ {1} ^ {3} -27a_ {3} \ prawo) \ prawo) = a_ {3} ^ {3} \ delta .}

Wtedy punkt ma rząd 3.

{\ Displaystyle P = (0,0)}

Aby udowodnić, że ma $rząd 3$ zauważ , że styczna do P $)$ $\ Displaystyle P$ $=$ $krotnością$ który przecina się z 3 $.$

$,$ pod uwagę punkt rzędu 3 na krzywej eliptycznej $oba$ $zdefiniowane$ na polu ${$ umieścić krzywą w postaci Weierstrassa z $\ displaystyle P = (0,0)} tak$ $,$ że styczna w punkcie linią ${\ displaystyle Y = 0}$ . Wtedy równanie krzywej to ${\ Displaystyle Y ^ {2} + a_ {1} XY + a_ {3} Y = X ^ {3}}$ z ${\ Displaystyle a_ {1} ,a_{3}\w K}$ .

Aby uzyskać krzywą Hessego, należy wykonać następujące przekształcenie :

Najpierw $_$ oznacza pierwiastek wielomianu

{\ Displaystyle T ^ {3} - \ delta T ^ {2} + {\ delta ^ {2} \ ponad 3} T + a_ {3}\delta ^{2}=0.}

Następnie

{\ Displaystyle \ mu = {\ delta -a_ {1} \ delta ^ {2/3} \ ponad 3}.}

$}$ jeśli porządku to każdy element $ma$ K $displaystyle K$ unikalny pierwiastek sześcienny ; ogólnie $rozszerzenia$ w polu K .

, definiując następującą wartość, $kolejną$ krzywą która MI:

{\ Displaystyle C: x ^ {3} + y ^ {3} + z ^ {3} = 3Dxyz}

co nazywa się sześcienną formą Hesji (we współrzędnych rzutowych )

{\ Displaystyle C: x ^ {3} + y ^ {3} + 1 = 3Dxy}

na płaszczyźnie afinicznej (satysfakcjonującej i $}$ ${\ frac {Y}{Z}$ )

Ponadto ${\ Displaystyle D ^ {3} \ neq 1}$ (w przeciwnym razie krzywa byłaby osobliwa ).

Wychodząc z krzywej Hessego, biracjonalnie równoważne równanie Weierstrassa jest podane przez

{\ Displaystyle v ^ {2} = u ^ {3} -27D \ lewo (D ^ { 3}+8\prawo)u+54\lewo(D^{6}-20D^{3}-8\prawo),}

w ramach przekształceń:

{\ Displaystyle (x, y) = \ lewo (\ eta \ lewo (u + 9D^{2}\right),-1+\eta \left(3D^{3}-Dx-12\right)\right)}

I

{\ Displaystyle (u, v) = \ lewo (-9D ^ {2} + \ varepsilon x, 3 \ varepsilon \ lewo(y-1\prawo)\prawo)}

Gdzie:

{\ Displaystyle \ eta = {\ frac {6\lewo(D^{3}-1\prawo)\lewo(v+9D^{3}-3Du-36\prawo)}{\lewo(u+9D^{2}\prawo)^{ 3}+\lewo(3Dd-Du-12\prawo)^{3}}}}

I

{\ Displaystyle \ varepsilon = {\ Frac {12 \ lewo (D ^ {3} -1 \ prawo)} {Dx + y + 1}}}

Prawo grupowe

Interesujące jest przeanalizowanie prawa grupowego krzywej eliptycznej, zdefiniowanie formuł dodawania i podwajania (ponieważ ataki SPA i DPA opierają się na czasie wykonywania tych operacji). Co więcej, w tym przypadku musimy tylko użyć tej samej procedury, aby obliczyć dodawanie, podwajanie lub odejmowanie punktów, aby uzyskać wydajne wyniki, jak wspomniano powyżej. Ogólnie rzecz biorąc, prawo grupowe jest zdefiniowane w następujący sposób: jeśli trzy punkty leżą na tej samej prostej, to sumują się do zera . Tak więc, dzięki tej własności, prawa grupowe są różne dla każdej krzywej.

W tym przypadku właściwym sposobem jest użycie wzorów Cauchy'ego-Desbovesa, uzyskując punkt w nieskończoności $θ = (1 : -1 : 0)$ , czyli element neutralny (odwrotnością $θ$ jest znowu $θ$ ). Niech $P = (x 1, y 1)$ będzie punktem na krzywej. Linia ${\ Displaystyle y = - x + (x_ {1} + y_ {1})}$ zawiera punkt $P$ i punkt w nieskończoności $θ$ . Zatem $- P$ jest trzecim punktem przecięcia tej prostej z krzywą. Przecinając krzywą eliptyczną z linią, uzyskuje się następujący warunek ${\ Displaystyle x_ {2} - (x_ {1} + y_ {1 })\cdot x+x_{1}\cdot y_{1}=\theta }$

Ponieważ ${\ Displaystyle x_ {1} + y_ {1} + D}$ jest niezerowe (ponieważ $D 3$ różni się od 1), współrzędna $x$ $- P$ to $y 1$ , a $y$ - współrzędna $- P$ to $x 1$ , tj. ${\ Displaystyle -P = (y_ {1}, x_ {1})}$ lub we współrzędnych rzutowych ${\ Displaystyle -P = (Y_ {1}: X_ {1}: Z_ {1})}$ .

W niektórych zastosowaniach kryptografii krzywych eliptycznych i metody faktoryzacji krzywych eliptycznych ( ECM ) konieczne jest obliczenie skalarnych mnożeń $P$ , powiedzmy $[n] P$ dla pewnej liczby całkowitej $n$ , i są one oparte na metodzie podwój i dodaj ; operacje te wymagają formuł dodawania i podwajania.

Podwojenie

$_$ jeśli _ operacja „podwojenia” przy użyciu wzorów Cauchy'ego-Desbovesa:

{\ Displaystyle [2] P = \ lewo (Y_ {1} \ cdot \ lewo (X_ {1} ^ {3} -Z_ {1} ^ {3} \ prawo): X_ {1} \ cdot \ lewo ( Z_{1}^{3}-Y_{1}^{3}\right):Z_{1}\cdot \left(Y_{1}^{3}-X_{1}^{3}\right) \Prawidłowy)}

Dodatek

W ten sam sposób, dla dwóch różnych punktów, powiedzmy ${\ Displaystyle P = (X_ {1}: Y_ {1}: Z_ {1})}$ i ${\ Displaystyle Q = (X_ {2}: Y_ {2}: Z_ {2})}$ , możliwe jest zdefiniowanie formuły dodawania. Niech $R$ oznacza sumę tych punktów, $R = P + Q$ , to jego współrzędne są określone wzorem:

{\ Displaystyle R = \ lewo (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}\right)}

Algorytmy i przykłady

Istnieje jeden algorytm , którego można użyć do dodania dwóch różnych punktów lub podwojenia; podaje Joye i Quisquater . Wówczas następujący wynik daje możliwość uzyskania operacji podwojenia przez dodawanie:

Propozycja . Niech $P = (X,Y,Z)$ będzie punktem na eliptycznej krzywej Hesji $E (K)$ . Następnie:

{\ Displaystyle 2 (X: Y: Z) = (Z: X: Y) + (Y: Z: X )}

()

Ponadto mamy $(Z : X : Y) \neq (Y : Z : X)$ .

Wreszcie, w przeciwieństwie do innych parametrów , nie ma odejmowania, aby obliczyć negację punktu. Dlatego ten algorytm dodawania może być również użyty do odjęcia dwóch punktów $P = (X 1 : Y 1 : Z 1)$ i $Q = (X 2 : Y 2 : Z 2)$ na eliptycznej krzywej Hesji:

{\ Displaystyle (X_ {1 }:Y_{1}:Z_{1})-(X_{2}:Y_{2}:Z_{2})=(X_{1}:Y_{1}:Z_{1})+(Y_{ 2}:X_{2}:Z_{2})}

()

Reasumując, dostosowując kolejność wejść zgodnie z równaniem (2) lub (3), przedstawiony powyżej algorytm dodawania można stosować obojętnie do: Dodawania 2 (różn.) punktów, Podwajania punktu i Odejmowania 2 punktów tylko 12 mnożeń i 7 zmiennych pomocniczych, w tym 3 zmienne wynikowe. Przed wynalezieniem krzywych Edwardsa wyniki te reprezentują najszybszą znaną metodę implementacji mnożenia skalarnego krzywej eliptycznej w kierunku odporności na ataki kanałów bocznych .

W przypadku niektórych algorytmów ochrona przed atakami typu side-channel nie jest konieczna. Więc dla tych podwojeń może być szybciej. Ponieważ istnieje wiele algorytmów, podano tutaj tylko najlepsze dla formuł dodawania i podwajania, z jednym przykładem dla każdego z nich:

Dodatek

Niech $P 1 = (X 1 : Y 1 : Z 1)$ i $P 2 = (X 2 : Y 2 : Z 2)$ będą dwoma punktami różnymi od $θ$ . Zakładając, że $Z 1 = Z 2 = 1$ to algorytm jest dany wzorem:

$ZA = X 1 Y 2$

$B = Y 1 X 2$

X 3 = B Y 1 - Y 2 A

Y 3 = X 1 A - B X 2

Z 3 = Y 2 X 2 - X 1 Y 1

Potrzebny koszt to 8 mnożeń i 3 dodania. Koszt ponownego dodania 7 mnożeń i 3 dodań, w zależności od pierwszego punktu.

Przykład

Biorąc pod uwagę następujące punkty krzywej dla $d = -1 P 1 = (1:0:-1)$ i $P 2 = (0:-1:1)$ , to jeśli $P 3 = P 1 + P 2$ mamy:

X 3 = 0 - 1 = -1

Y 3 = -1 - 0 = -1

Z 3 = 0 - 0 = 0

Wtedy: $P 3 = (-1:-1:0)$

Podwojenie

Niech $P = (X 1 : Y 1 : Z 1)$ będzie punktem, wtedy wzór na podwojenie ma postać:

$ZA = X 12$
$B = Y 12$
$re = A + B$
$sol = (X 1 + Y 1) 2 - re$
$X 3 = (2 Y 1 - sol) \times (X 1 + ZA + 1)$
$Y 3 = (sol - 2 X 1) \times (Y 1 + b + 1)$
$Z 3 = (X 1 - Y 1) \times (sol + 2 re)$

Koszt tego algorytmu to trzy mnożenia + trzy podniesienia do kwadratu + 11 dodań + 3×2.

Przykład

Jeśli $_$ punktem ${\ Displaystyle 2P = (X: Y: Z)}$ $d_$ , są podane przez:

$X = (2 . (-1) - 2) (-1 + 1 + 1) = -4$

$Y = (-4 - 2 . (-1)) ((-1) + 1 + 1) = -2$

$Z = (-1 - (-1)) ((-4) + 2 . 2) = 0$

$2 P = (-4: -2: 0)}$ -

Rozszerzone współrzędne

Istnieje inny układ współrzędnych, za pomocą którego można przedstawić krzywą Hessego; te nowe współrzędne nazywane są współrzędnymi rozszerzonymi . Mogą przyspieszyć dodawanie i podwajanie. Aby uzyskać więcej informacji na temat operacji z rozszerzonymi współrzędnymi, zobacz:

http://hyperelliptic.org/EFD/g1p/auto-hessian-extended.html#addition-add-20080225-hwcd

${\ Displaystyle x}$ i ${\ Displaystyle y}$ są reprezentowane przez ${\ Displaystyle X, Y, Z, XX, YY,ZZ,XY,YZ,XZ}$ spełniające następujące równania:

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

Zobacz też

Więcej informacji o wymaganym czasie pracy w konkretnym przypadku zawiera Tabela kosztów operacji na krzywych eliptycznych
Skręcone krzywe Hesji

Linki zewnętrzne

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

Notatki

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). „Krzywe eliptyczne Hesji i ataki z kanału bocznego”. Sprzęt kryptograficzny i systemy wbudowane — CHES 2001 . Notatki z wykładów z informatyki. Tom. 2162. Springer-Verlag Berlin Heidelberg 2001. s. 402–410. doi : 10.1007/3-540-44709-1_33 . ISBN 978-3-540-42521-2 .
NP Inteligentny (2001). „Hessian forma krzywej eliptycznej”. Sprzęt kryptograficzny i systemy wbudowane — CHES 2001 . Notatki z wykładów z informatyki. Tom. 2162. Springer-Verlag Berlin Heidelberg 2001. s. 118–125. doi : 10.1007/3-540-44709-1_11 . ISBN 978-3-540-42521-2 .