Krzywa Jakobianu

W matematyce krzywa Jacobiego jest reprezentacją krzywej eliptycznej różniącej się od zwykłej krzywej zdefiniowanej przez równanie Weierstrassa . Czasami jest używany w kryptografii zamiast formy Weierstrassa, ponieważ może zapewnić obronę przed prostą i różnicową analizą mocy ataki stylistyczne (SPA); rzeczywiście możliwe jest użycie ogólnego wzoru dodawania również do podwojenia punktu na krzywej eliptycznej tej postaci: w ten sposób te dwie operacje stają się nie do odróżnienia od niektórych informacji z kanału bocznego. Krzywa Jacobiego oferuje również szybsze działania arytmetyczne w porównaniu z krzywą Weierstrassa.

Krzywa Jacobiego może być dwojakiego rodzaju: przecięcie Jacobiego , które jest określone przez przecięcie dwóch powierzchni, oraz quartic Jacobiego .

Krzywe eliptyczne: podstawy

Biorąc pod uwagę krzywą eliptyczną, można wykonać pewne „operacje” między jej punktami: na przykład można dodać dwa punkty P i Q , uzyskując punkt P + Q należący do krzywej; mając punkt P na krzywej eliptycznej, można „podwoić” P, czyli znaleźć [2] P = P + P (nawiasy kwadratowe oznaczają [n]P , punkt P dodany n razy), a także znaleźć zaprzeczenie P , to znaczy znaleźć – P . W ten sposób punkty krzywej eliptycznej tworzą grupę . Zauważ, że element tożsamości operacji grupowej nie jest punktem na płaszczyźnie afinicznej, pojawia się tylko we współrzędnych rzutowych: wtedy O = (0: 1: 0) jest „punktem w nieskończoności”, czyli elementem neutralnym w prawo grupowe . Formuły dodawania i podwajania są również przydatne do obliczania [n]P , n -tej wielokrotności punktu P na krzywej eliptycznej: ta operacja jest uważana za najbardziej kryptografia krzywych eliptycznych .

Krzywą eliptyczną E na polu K można zapisać w postaci Weierstrassa y ² = x ³ + ax + b , gdzie a , b w K . Ważny będzie później punkt rzędu 2 , czyli P na E taki, że [2] P = O i P ≠ O . Jeśli P = ( p , 0) jest punktem na E , to ma rząd 2; bardziej ogólnie punkty rzędu 2 odpowiadają pierwiastkom wielomianu f (x) = x ³ + ax + b .

Od teraz będziemy używać E _a,b do oznaczania krzywej eliptycznej z postacią Weierstrassa y ² = x ³ + ax + b .

Jeśli E _a,b jest takie, że wielomian sześcienny x ³ + ax + b ma trzy różne pierwiastki w K i b = 0 , możemy zapisać E _{a, b} w postaci normalnej Legendre'a :

mi _{a, b} : y ² = x(x + 1)(x + j)

W tym przypadku mamy trzy punkty rzędu drugiego: (0, 0), (–1, 0), (– j , 0). W tym przypadku używamy notacji E[j] . Zauważ, że j można wyrazić za pomocą a , b .

Definicja: Skrzyżowanie Jacobiego

Krzywą eliptyczną w P ³ ( K ) można przedstawić jako przecięcie dwóch powierzchni czworobocznych :

${\ Displaystyle Q: \ {Q_ {1} (X_ {0},X_{1},X_{2},X_{3})=0\}\cap \{Q_{2}(X_{0},X_{1},X_{2},X_{3 })=0\}}$

Możliwe jest zdefiniowanie postaci Jacobiego krzywej eliptycznej jako przecięcia dwóch kwadratów. Niech E _a,b będzie krzywą eliptyczną w postaci Weierstrassa, zastosujemy do niej następującą mapę :

${\ Displaystyle \ Phi :( x, y) \ mapsto (X, Y, Z, T) =(x,y,1,x^{2})}$

zachodzi następujący układ równań :

${\ Displaystyle \ mathbf {S}: {\ rozpocząć {przypadki} X ^ {2} -TZ = 0 \\ Y ^{2}-aXZ-bZ^{2}-TX=0\end{przypadki}}}$

Krzywa E[j] odpowiada następującemu przecięciu powierzchni w P ³ ( K ):

${\ Displaystyle \ mathbf {S} 1: {\ rozpocząć {przypadki} X ^ {2} + Y ^ {2} -T^{2}=0\\kX^{2}+Z^{2}-T^{2}=0\end{przypadki}}}$ .

„Specjalny przypadek”, E[0] , krzywa eliptyczna ma podwójny punkt, a zatem jest pojedyncza .

S1 otrzymujemy stosując do E [j] transformację :

ψ: E[j] → S1

${\ Displaystyle (x, y) \ mapsto (X, Y, Z, T) = (-2y, x ^ {2} -j, x ^ {2} + 2jx + j, x ^ {2} + 2x + j)}$

${\ Displaystyle O = (0: 1: 0) \ mapsto (0,1,1,1)}$

Prawo grupowe

Dla S1 neutralnym elementem grupy jest punkt (0, 1, 1, 1), czyli obraz O = (0: 1: 0) pod ψ.

Dodawanie i podwajanie

Biorąc pod uwagę P ₁ = ( X ₁ , Y ₁ , Z ₁ , T ₁ ) i P ₂ = ( X ₂ , Y ₂ , Z ₂ , T ₂ ), dwa punkty na S1 , współrzędne punktu P ₃ = P ₁ + P ₂ to:

${\ Displaystyle X_ {3} = T_ {1} Y_ {2} X_ {1} Z_ {2} + Z_ {1} X_ {2} Y_ {1} T_ {2}}$

${\ Displaystyle Y_ {3} = T_ {1} Y_ {2} Y_ { 1}T_{2}-Z_{1}X_{2}X_{1}Z_{2}}$

${\ Displaystyle Z_ {3} = T_ {1} Z_ {1} T_ {2} Z_ {2} -kX_ {1} Y_ { 1} X_ {2} Y_ {2}}$

${\ Displaystyle T_ {3} = (T_ {1} Y_ {2}) ^ {2 }+(Z_{1}X_{2})^{2}}$

Formuły te są również ważne dla podwojenia: wystarczy mieć P ₁ = P ₂ . Tak więc dodawanie lub podwajanie punktów w S1 to operacje, które wymagają 16 mnożeń plus jedno pomnożenie przez stałą ( k ).

Możliwe jest również użycie następujących wzorów do podwojenia punktu P ₁ i znalezienia P ₃ = [2] P ₁ :

${\ Displaystyle X_ {3} = 2Y_ {1} T_ {1} Z_ {1} X_ {1}}$

${\ Displaystyle Y_ {3} = (T_ {1} Y_ {1}) ^ {2} - (T_ {1} Z_ {1}) ^ {2} +(Z_{1}Y_{1})^{2}}$

${\ Displaystyle Z_ {3} = (T_ {1} Z_ {1}) ^ {2} - (T_ {1} Y_ {1})^{2}+(Z_{1}Y_{1})^{2}}$

${\ Displaystyle T_ {3} = (T_ {1} Z_ {1}) ^ {2} + (T_ {1} Y_ {1}) ^ {2} - (Z_ {1} Y_ {1}) ^ { 2}}$

Korzystając z tych wzorów, aby podwoić punkt, potrzeba 8 mnożeń. Istnieją jednak jeszcze skuteczniejsze „strategie” podwajania, które wymagają tylko 7 mnożeń. W ten sposób możliwe jest potrojenie punktu za pomocą 23 mnożeń; rzeczywiście [3] P ₁ można otrzymać dodając P ₁ z [2] P ₁ kosztem 7 mnożeń dla [2] P ₁ i 16 dla P ₁ + [2] P ₁

Przykład dodawania i podwajania

Niech K = R lub C i rozważ przypadek:

${\ Displaystyle \ mathbf {S} 1: {\ rozpocząć {przypadki} X ^ {2} + Y ^ {2} -T^{2}=0\\4X^{2}+Z^{2}-T^{2}=0\end{przypadki}}}$

Rozważ punkty ${\ Displaystyle P_ {1} = (1, {\ sqrt {3}}, 0,2)}$ i ${\ Displaystyle P_ {2} = (1,2,1, {\ sqrt {5}})}$ : łatwo sprawdzić, czy P ₁ i P ₂ należą do S1 (wystarczy zobaczyć, że punkty te spełniają oba równania układ S1 ).

Korzystając z podanych powyżej wzorów dodawania dwóch punktów, współrzędne dla P ₃ , gdzie P ₃ = P ₁ + P ₂ są następujące:

${\ Displaystyle X_ {3} = T_ {1} Y_ {2} X_ {1} Z_ {2} + Z_ {1 }X_{2}Y_{1}T_{2}=4}$

${\ Displaystyle Y_ {3} = T_ {1} Y_ {2} Y_ {1} T_ {2} -Z_ {1} X_ {2} X_ {1} Z_ {2} = 4 {\ sqrt {15}} }$

${\ Displaystyle Z_ {3} = T_ {1} Z_ {1} T_ {2} Z_ {2} -kX_{1}Y_{1}X_{2}Y_{2}=-8{\sqrt {3}}}$

${\ Displaystyle T_ {3} = (T_ {1} Y_ {2}) ^ {2} + (Z_ {1} X_ {2}) ^ {2} = 16}$

Otrzymany punkt to ${\ Displaystyle P_ {3} = (4,4 {\ sqrt {15}}, -8 {\ sqrt {3}}, 16 )}$ .

Za pomocą podanych powyżej wzorów na podwojenie możliwe jest znalezienie punktu P ₃ = [2] P ₁ :

${\ Displaystyle X_ {3} = 2Y_ {1} T_ {1} Z_ {1} X_ {1} = 0}$

${\ Displaystyle Y_ {3} = (T_ {1} Y_ {1}) ^ {2} - (T_ {1} Z_ {1} )^{2}+(Z_{1}Y_{1})^{2}=12}$

${\ Displaystyle Z_ {3} = (T_ {1} Z_ {1}) ^ {2} -(T_{1}Y_{1})^{2}+(Z_{1}Y_{1})^{2}=-12}$

${\ Displaystyle T_ {3} = (T_ {1} Z_ {1}) ^ {2} + (T_ {1} Y_ {1}) ^ {2} - ( Z_ { 1}Y_{1})^{2}=12}$

Zatem w tym przypadku P ₃ = [2] P ₁ = (0, 12, –12, 12).

Negacja

Biorąc pod uwagę punkt P ₁ = ( X ₁ , Y ₁ , Z ₁ , T ₁ ) w S1 , jego negacją jest − P ₁ = (− X ₁ , Y ₁ , Z ₁ , T ₁ )

Dodawanie i podwajanie we współrzędnych afinicznych

Mając dane dwa punkty afiniczne P ₁ = ( x ₁ , y ₁ , z ₁ ) i P ₂ = ( x ₂ , y ₂ , z ₂ ), ich suma jest punktem P ₃ o współrzędnych:

${\ Displaystyle x_ {3} = {\ Frac {y_ {2} x_ {1} z_ {2}+z_{1}x_{2}y_{1}}{(y_{2}^{2}+(z_{1}x_{2})^{2})}}}$

${\ Displaystyle y_ {3} = {\ Frac {y_ {2} y_ {1} -z_ {1} x_ {2} x_ {1} z_ {2} }{(y_{2}^{2}+(z_{1}x_{2})^{2})}}}$

${\ Displaystyle z_ {3} = {\ Frac {z_ {1} z_ {2} -ax_ {1} y_ {1} x_ {2} y_ {2}} {(y_ {2} ^ {2} + ( z_{1}x_{2})^{2})}}}$

Wzory te są ważne również dla podwojenia z warunkiem P ₁ = P ₂ .

Rozszerzone współrzędne

Istnieje inny rodzaj układu współrzędnych, za pomocą którego można przedstawić punkt na przecięciu Jacobiego. Biorąc pod uwagę następującą krzywą eliptyczną w postaci przecięcia Jacobiego:

${\ Displaystyle \ mathbf {S} 1: {\ rozpocząć {przypadki} x ^ {2} + y ^ {2} = 1 \\ kx^{2}+z^{2}=1\end{przypadki}}}$

współrzędne rozszerzone opisują punkt P = (x, y, z) ze zmiennymi X, Y, Z, T, XY, ZT , gdzie:

${\ Displaystyle x = X/T}$

${\ Displaystyle y = Y/T}$

${\ Displaystyle z = Z/T}$

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

${\ Displaystyle ZT = Z \ cdot T}$

Czasami te współrzędne są używane, ponieważ są wygodniejsze (pod względem czasu i kosztów) w niektórych określonych sytuacjach. Aby uzyskać więcej informacji na temat operacji opartych na wykorzystaniu tych współrzędnych, zobacz http://hyperelliptic.org/EFD/g1p/auto-jintersect-extended.html

Definicja: kwarc Jacobiego

Kwartał Jacobiego równania ${\ Displaystyle y ^ {2} = x ^ {4} -1,9x ^ {2} + 1}$

Krzywą eliptyczną w postaci kwartalnej Jacobiego można otrzymać z krzywej E _{a, b} w postaci Weierstrassa z co najmniej jednym punktem rzędu 2. Następująca transformacja f wysyła każdy punkt E _{a, b} do punktu we współrzędnych Jacobiego, gdzie (X: Y: Z) = (sX: s ² Y: sZ) .

fa: mi _{za, b} → jot

${\ Displaystyle (p, 0) \ mapsto (0: -1: 1)}$

${\ Displaystyle (x, y) \ neq (p, 0) \ mapsto (2 (xp): (2x + p) (xp) ^ {2} -y ^ {2}: y)}$

${\ Displaystyle O \ mapsto (0: 1: 1)}$

Stosując f do E _a,b otrzymujemy krzywą w J o postaci:

${\ Displaystyle C: \ Y ^ {2} = eX ^ {4} -2dX ^ {2} Z ^ {2} + Z ^ { 4}}$

Gdzie:

${\ Displaystyle e = {\ Frac {- (3p ^ {2} + 4a)} {16}}, \ \ d = {\ Frac {3p}{4}}}$ .

są elementami w K . C reprezentuje krzywą eliptyczną w formie kwartalnej Jacobiego we współrzędnych Jacobiego.

Kwartyk Jacobiego we współrzędnych afinicznych

Ogólna postać krzywej kwartalnej Jacobiego we współrzędnych afinicznych to:

${\ Displaystyle y ^ {2} = ex ^ {4} + 2ax ^ {2} + 1}$ ,

gdzie często zakłada się e = 1.

Prawo grupowe

Neutralnym elementem prawa grupowego C jest punkt rzutowy (0: 1: 1).

Dodawanie i podwajanie we współrzędnych afinicznych

Biorąc pod uwagę dwa punkty afiniczne ${\$ Displaystyle $} 2} = (x_ {2}, y_ {2})}$ , ich suma to punkt ${\ Displaystyle P_ {3} = (x_ {3}, y_ {3}) }$ , takie, że:

${\ Displaystyle x_ {3} = {\ Frac {x_ {1} y_ {2} + y_ {1} x_ {2 }}{1-e(x_{1}x_{2})^{2}}}}$

${\ Displaystyle y_ {3} = {\ Frac {((1 + e(x_{1}x_{2})^{2})(y_{1}y_{2}+2ax_{1}x_{2})+2ex_{1}x_{2}({x_{1} }^{2}+{x_{2}}^{2}))}{(1-e(x_{1}x_{2})^{2})^{2}}}}$

Podobnie jak w przypadku przecięć Jacobiego, również w tym przypadku możliwe jest zastosowanie tego wzoru do podwojenia.

Dodawanie i podwajanie we współrzędnych rzutowych

Biorąc pod uwagę dwa punkty P ₁ = ( X ₁ : Y ₁ : Z ₁ ) i P ₂ = ( X ₂ : Y ₂ : Z ₂ ) w C′ , współrzędne punktu P ₃ = ( X ₃ : Y ₃ : Z ₃ ), gdzie P ₃ = P ₁ + P ₂ , są podane w kategoriach P ₁ i P ₂ wzorami:

${\ Displaystyle X_ {3} = X_ {1} Z_ {1} Y_ {2} + Y_ {1} X_ {2} Z_ {2}}$

${\ Displaystyle Y_ {3} = \ lewo (Z_ {1} ^ {2} Z_ {2}^{2}+eX_{1}^{2}X_{2}^{2}\prawo)\lewo(Y_{1}Y_{2}-2aX_{1}X_{2}Z_{1 }Z_{2}\right)\ +\ 2eX_{1}X_{2}Z_{1}Z_{2}\left(X_{1}^{2}Z_{2}^{2}+Z_{1 }^{2}X_{2}^{2}\right)}$

${\ Displaystyle Z_ {3} = Z_ {1} ^ {2} Z_ {2} ^ {2} -eX_ {1} ^ {2} X_ {2} ^ {2} }}$

Można użyć tego wzoru również do podwojenia, pod warunkiem, że P ₂ = P _{1 : w ten sposób} otrzymuje się punkt P ₃ = P ₁ + P ₁ = [2] P _{1 .}

Liczba mnożeń wymaganych do dodania dwóch punktów wynosi 13 plus 3 mnożenia przez stałe: w szczególności są dwa mnożenia przez stałą e i jedno przez stałą a .

Istnieją pewne „strategie” zmniejszające liczbę operacji wymaganych do dodawania i podwajania punktów: liczbę mnożeń można zmniejszyć do 11 plus 3 mnożenia przez stałe (więcej szczegółów w rozdziale 3).

Liczbę mnożeń można zmniejszyć, pracując nad stałymi e i d : krzywą eliptyczną w postaci Jacobiego można zmodyfikować, aby mieć mniejszą liczbę operacji dodawania i podwajania. Na przykład, jeśli stała d w C jest znacznie mała, mnożenie przez d można anulować; jednak najlepszą opcją jest zmniejszenie e : jeśli jest małe, pomija się nie tylko jedno, ale dwa mnożenia.

Przykład dodawania i podwajania

Rozważmy krzywą eliptyczną E _4,0 , ma ona punkt P rzędu 2: P = ( p , 0) = (0, 0). Dlatego a = 4, b = p = 0, więc mamy e = 1 i d = 1, a powiązana forma kwartalna Jacobiego to:

${\ Displaystyle C: \ Y ^ {2} = X ^ {4} + Z ^ {4}}$

Wybór dwóch punktów ${\ Displaystyle P_ {1} = (1: {\ sqrt {2}}: 1)}$ i ${\ Displaystyle P_ {2}=(2:{\sqrt {17}}:1)}$ , można znaleźć ich sumę P ₃ = P ₁ + P ₂ korzystając z podanych powyżej wzorów na dodawanie:

${\ Displaystyle X_ {3} = 1 \ cdot 1 \ cdot {\ sqrt {17}} + {\ sqrt {2}} \ cdot 2\cdot 1={\sqrt {17}}+2{\sqrt {2}}}$

${\ Displaystyle Y_ {3} = \ lewo (1 ^ {2} \ cdot 1 ^ {2} + 1 \ cdot 1 ^ {2} \ cdot 2 ^ {2} \ prawo) \ lewo ({\ sqrt {2 }}\cdot {\sqrt {17}}-2\cdot 0\cdot 1\cdot 2\cdot 1\cdot 1\right)+2\cdot 1\cdot 1\cdot 2\cdot 1\cdot 1\lewo (1^{2}\cdot 1^{2}+1^{2}\cdot 2^{2}\right)=5{\sqrt {34}}+20}$

${\ Displaystyle Z_ {3} = 1 ^ {2} \ cdot 1 ^ {2} -1 \ cdot 1 ^ {2} \ cdot 2 ^ {2} = -3}$ .

Więc

${\ Displaystyle P_ {3} = ({\ sqrt {17}} + 2 {\ sqrt {2}}: 5 {\ sqrt {34} }+20:-3)}$ .

otrzymuje się punkt P ₄ = [2] P _{1 :}

${\ Displaystyle X_ {3} = 1 \ cdot 1 \ cdot {\ sqrt {2}} + {\ sqrt {2}} \ cdot 1 \ cdot 1=2{\sqrt {2}}}$

${\ Displaystyle Y_ {3} = \ lewo (1 + 1 \ cdot 1 \ prawo) \ lewo ({\ sqrt {2}} \ cdot {\ sqrt {2}}-2\cdot 0\cdot 1\cdot 1\cdot 1\cdot 1\right)+2\cdot 1\left(1^{2}\cdot 1^{2}+1^{2 } \ cdot 1 ^ {2} \ prawej) = 8}$

${\ Displaystyle Z_ {3} = 1 ^ {2} \ cdot 1 ^ {2 }-1\cdot 1^{2}\cdot 1^{2}=0}$

Więc

${\ Displaystyle P_ {4} = (2 {\ sqrt {2}}: 8: 0)}$ .

Negacja

Negacją punktu P ₁ = ( X ₁ : Y ₁ : Z ₁ ) jest: − P ₁ = (− X ₁ : Y ₁ : Z ₁ )

Alternatywne współrzędne kwartyku Jacobiego

Istnieją inne układy współrzędnych, których można użyć do przedstawienia punktu w kwarcu Jacobiego: w niektórych przypadkach są one używane do uzyskiwania szybkich obliczeń. Aby uzyskać więcej informacji na temat kosztu czasu wymaganego w operacjach z tymi współrzędnymi, zobacz http://hyperelliptic.org/EFD/g1p/auto-jquartic.html

Biorąc pod uwagę afiniczny kwartyk Jacobiego

${\ Displaystyle y ^ {2} = x ^ {4} + 2 topór ^ {2} + 1}$

współrzędne XXYZZ zorientowane na podwojenie taki wprowadzają dodatkowy parametr krzywej c spełniający a ² + c ² = 1 i reprezentują punkt (x, y) jako (X, XX, Y, Z, ZZ, R) , że:

${\ Displaystyle x = X/Z}$

${\ Displaystyle y = Y/ZZ}$

${\ Displaystyle XX = X ^ {2}}$

${\ Displaystyle ZZ = Z ^ {2}}$

${\ Displaystyle R = 2 \ cdot X \ cdot Z}$

podwojone spełniającymi współrzędne XYZ , przy tym samym dodatkowym założeniu ( a ² + c ² = 1), reprezentują punkt (x, y) z (X, Y, Z) następujące równania:

${\ Displaystyle x = X/Z}$

${\ Displaystyle y = Y / Z ^ {2}}$

Używając współrzędnych XXYZZ nie ma dodatkowego założenia i reprezentują one punkt (x, y) jako (X, XX, Y, Z, ZZ) takie, że:

${\ Displaystyle x = X/Z}$

${\ Displaystyle y = Y/ZZ}$

${\ Displaystyle XX = X ^ {2}}$

${\ Displaystyle ZZ = Z ^ {2}}$

podczas gdy współrzędne XXYZZR reprezentują (x, y) jako (X, XX, Y, Z, ZZ, R) takie, że:

${\ Displaystyle x = X/Z}$

${\ Displaystyle y = Y/ZZ}$

${\ Displaystyle XX = X ^ {2}}$

${\ Displaystyle ZZ = Z ^ {2}}$

${\ Displaystyle R = 2 \ cdot X \ cdot Z}$

ze współrzędnymi XYZ punkt (x, y) jest określony wzorem (X, Y, Z) , przy czym:

${\ Displaystyle x = X/Z}$

${\ Displaystyle y = Y / Z ^ {2}}$ .

Zobacz też

Aby uzyskać więcej informacji na temat czasu pracy wymaganego w konkretnym przypadku, zobacz Tabela kosztów operacji na krzywych eliptycznych .

Notatki

•   Olivier Billet, Marc Joye (2003). „Model Jacobiego krzywej eliptycznej i analizy kanałów bocznych”. Model Jacobiego krzywej eliptycznej i analiza kanału bocznego . Notatki z wykładów z informatyki. Tom. 2643. Springer-Verlag Berlin Heidelberg 2003. s. 34–42. doi : 10.1007/3-540-44828-4_5 . ISBN 978-3-540-40111-7 .
•   PY Liardet, NP Smart (2001). „Zapobieganie SPA / DPA w systemach ECC przy użyciu formularza Jacobi”. Sprzęt kryptograficzny i systemy wbudowane — CHES 2001 . Notatki z wykładów z informatyki. Tom. 2162. Springer-Verlag Berlin Heidelberg 2001. s. 391–401. doi : 10.1007/3-540-44709-1_32 . ISBN 978-3-540-42521-2 .
• http://hyperelliptic.org/EFD/index.html

Linki zewnętrzne

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