The ztrojnásobená Doche – Icart – Kohelova křivka je forma eliptická křivka který byl v poslední době použit v kryptografie ; je to konkrétní typ Weierstrassova křivka . Za určitých podmínek některé operace , protože sčítání, zdvojnásobení nebo ztrojnásobení bodů se pomocí tohoto formuláře počítá rychleji. 3DIK byl představen Christophe Doche, Thomas Icart a David R. Kohel v [1]
Definice Trojnásobně orientovaná Doche – Icart – Kohelova křivka rovnice
y 2 = X 3 − 3 X 2 − 6 X − 3 { displaystyle y ^ {2} = x ^ {3} -3x ^ {2} -6x-3} Nechat K. { displaystyle K} pole z charakteristický různé formy 2 a 3.
Eliptická křivka v ztrojnásobená forma Doche – Icart – Kohel je definován rovnice :
T A : y 2 = X 3 + 3 A ( X + 1 ) 2 { displaystyle T_ {a} : y ^ {2} = x ^ {3} + 3a (x + 1) ^ {2}} s A ∈ K. { displaystyle a v K}
Generál směřovat P na T A { displaystyle T_ {a}} afinní souřadnice ( X , y ) { displaystyle (x, y)} neutrální prvek pro skupinový zákon a je napsán v projektivní souřadnice jako O = (0: 1: 0). Negace bodu P = (X , y ) s ohledem na tento neutrální prvek je -P = (X , −y ).
Zákon o skupině Uvažujme eliptickou křivku ve formě Trichově orientované Doche-Icart-Kohel afinní souřadnice :
T A : y 2 = X 3 + 3 A ( X + 1 ) 2 , A ≠ 0 , 9 4 . { displaystyle T_ {a}: quad y ^ {2} = x ^ {3} + 3a (x + 1) ^ {2}, qquad a neq 0, { tfrac {9} {4}} .} Stejně jako v jiných formách eliptických křivek je možné definovat některé „operace“ mezi body, například přidání bodů nebo zdvojení (viz také Zákon o skupině ). V následujících částech jsou uvedeny vzorce pro přidání, negaci a zdvojnásobení. Sčítací a zdvojovací vzorce se často používají pro jiné operace: daný bod P na eliptické křivce je možné počítat [n] P , kde n je celé číslo , pomocí sčítání a zdvojnásobení; výpočet násobků bodů je důležitý v kryptografie eliptické křivky a v Faktorizace eliptické křivky Lenstra .
Přidání Dáno P 1 = ( X 1 , y 1 ) { displaystyle P_ {1} = (x_ {1}, y_ {1})} P 2 = ( X 2 , y 2 ) { displaystyle P_ {2} = (x_ {2}, y_ {2})} T A { displaystyle T_ {a}} P 3 = ( X 3 , y 3 ) = P 1 + P 2 { displaystyle P_ {3} = (x_ {3}, y_ {3}) = P_ {1} + P_ {2}}
X 3 = 1 ( X 2 − X 1 ) 2 { − X 1 3 + ( X 2 − 3 A ) X 1 2 + ( X 2 2 + 6 A X 2 ) X 1 + ( y 1 2 − 2 y 2 y 1 + ( − X 2 3 − 3 A X 2 2 + y 2 2 ) ) } y 3 = 1 ( X 2 − X 1 ) 3 { ( − y 1 + 2 y 2 ) X 1 3 + ( − 3 A y 1 − 3 y 2 X 2 + 3 A y 2 ) X 1 2 + ( 3 X 2 2 y 1 + 6 A X 2 y 1 − 6 A y 2 X 2 ) X 1 + ( y 1 3 − 3 y 2 y 1 2 + ( − 2 X 2 3 − 3 A X 2 2 + 3 y 2 2 ) y 1 + ( y 2 X 2 3 + 3 A y 2 X 2 2 − y 2 3 ) ) } { displaystyle { begin {aligned} x_ {3} & = { frac {1} {(x_ {2} -x_ {1}) ^ {2}}} left {- x_ {1} ^ { 3} + (x_ {2} -3a) x_ {1} ^ {2} + (x_ {2} ^ {2} + 6ax_ {2}) x_ {1} + (y_ {1} ^ {2} - 2y_ {2} y_ {1} + (- x_ {2} ^ {3} -3ax_ {2} ^ {2} + y_ {2} ^ {2})) right } y_ {3} & = { frac {1} {(x_ {2} -x_ {1}) ^ {3}}} left {(- y_ {1} + 2y_ {2}) x_ {1} ^ {3} + (-3ay_ {1} -3y_ {2} x_ {2} + 3ay_ {2}) x_ {1} ^ {2} + (3x_ {2} ^ {2} y_ {1} + 6ax_ {2} y_ { 1} -6ay_ {2} x_ {2}) x_ {1} doprava. & qquad qquad qquad qquad left. + (Y_ {1} ^ {3} -3r_ {2} y_ { 1} ^ {2} + (- 2x_ {2} ^ {3} -3ax_ {2} ^ {2} + 3y_ {2} ^ {2}) y_ {1} + (y_ {2} x_ {2} ^ {3} + 3ay_ {2} x_ {2} ^ {2} -y_ {2} ^ {3})) right } end {zarovnáno}}} Zdvojnásobení Daný bod P 1 = ( X 1 , y 1 ) { displaystyle P_ {1} = (x_ {1}, y_ {1})} T A { displaystyle T_ {a}} P 3 = ( X 3 , y 3 ) = 2 P 1 { displaystyle P_ {3} = (x_ {3}, y_ {3}) = 2P_ {1}}
X 3 = 9 4 y 1 2 X 1 4 + 9 y 1 2 A X 1 3 + ( 9 y 1 2 A 2 + 9 y 1 2 A ) X 1 2 + ( 18 y 1 2 A 2 − 2 ) X 1 + 9 y 1 2 A 2 − 3 A y 3 = − 27 8 y 1 3 X 1 6 − 81 4 y 1 3 A X 1 5 + ( − 81 2 y 1 3 A 2 − 81 4 y 1 3 A ) X 1 4 + ( − 27 y 1 3 A 3 − 81 y 1 3 A 2 + 9 2 y 1 ) X 1 3 + ( − 81 y 1 3 A 3 − 81 2 y 1 3 A 2 + 27 2 y 1 A ) X 1 2 + ( − 81 y 1 3 A 3 + 9 y 1 A 2 + 9 y 1 A ) X 1 + ( − 27 y 1 3 A 3 + 9 y 1 A 2 − y 1 ) { displaystyle { begin {aligned} x_ {3} & = { frac {9} {4y_ {1} ^ {2} x_ {1} ^ {4}}} + { frac {9} {y_ { 1} ^ {2} ax_ {1} ^ {3}}} + vlevo ({ frac {9} {y_ {1} ^ {2} a ^ {2}}} + { frac {9} { y_ {1} ^ {2} a}} doprava) x_ {1} ^ {2} + vlevo ({ frac {18} {y_ {1} ^ {2} a ^ {2}}} - 2 right) x_ {1} + { frac {9} {y_ {1} ^ {2} a ^ {2} -3a}} y_ {3} & = - { frac {27} {8y_ { 1} ^ {3} x_ {1} ^ {6}}} - { frac {81} {4y_ {1} ^ {3} ax_ {1} ^ {5}}} + left (- { frac {81} {2y_ {1} ^ {3} a ^ {2}}} - { frac {81} {4y_ {1} ^ {3} a}} vpravo) x_ {1} ^ {4} + left (- { frac {27} {y_ {1} ^ {3} a ^ {3}}} - { frac {81} {y_ {1} ^ {3} a ^ {2}}} + { frac {9} {2y_ {1}}} vpravo) x_ {1} ^ {3} + vlevo (- { frac {81} {y_ {1} ^ {3} a ^ {3}} } - { frac {81} {2y_ {1} ^ {3}}} a ^ {2} + { frac {27} {2y_ {1} a}} right) x_ {1} ^ {2} & qquad qquad qquad qquad + left (- { frac {81} {y_ {1} ^ {3} a ^ {3}}} + { frac {9} {y_ {1} a ^ {2}}} + { frac {9} {y_ {1} a}} vpravo) x_ {1} + vlevo (- { frac {27} {y_ {1} ^ {3} a ^ {3}}} + { frac {9} {y_ {1} a ^ {2}}} - y_ {1} right) end {zarovnáno}}} Negace Daný bod P 1 = ( X 1 , y 1 ) { displaystyle P_ {1} = (x_ {1}, y_ {1})} T A { displaystyle T_ {a}} negace s ohledem na neutrální prvek ( 0 : 1 : 0 ) { displaystyle (0: 1: 0)} − P 1 = ( X 1 , − y 1 ) { displaystyle -P_ {1} = (x_ {1}, - y_ {1})}
Existují také další vzorce uvedené v [2]
Nové Jacobian souřadnice Pro výpočet na těchto křivkách jsou body obvykle reprezentovány v nové Jacobské souřadnice (Jn ):
bod v nových Jacobských souřadnicích má tvar P = ( X : Y : Z : Z 2 ) { displaystyle P = (X: Y: Z: Z ^ {2})}
P = ( X : Y : Z : Z 2 ) = ( λ 2 X : λ 3 Y : λ Z : λ 2 Z 2 ) , { displaystyle P = (X: Y: Z: Z ^ {2}) = ( lambda ^ {2} X: lambda ^ {3} Y: lambda Z: lambda ^ {2} Z ^ {2 }),} pro všechny λ ∈ K. { displaystyle lambda v K}
To například znamená, že jde o to P = ( X : Y : Z : Z 2 ) { displaystyle P = (X: Y: Z: Z ^ {2})} Q = ( 4 X : 8 Y : 2 Z : 4 Z 2 ) { displaystyle Q = (4X: 8Y: 2Z: 4Z ^ {2})} λ = 2 { displaystyle lambda = 2}
Takže afinní bod P = ( X , y ) { displaystyle P = (x, y)} T A { displaystyle T_ {a}} P = ( X : Y : Z : Z 2 ) { displaystyle P = (X: Y: Z: Z ^ {2})} X = X / Z 2 { displaystyle x = X / Z ^ {2}} y = Y / Z 3 { displaystyle y = Y / Z ^ {3}} T A { displaystyle T_ {a}}
T A : Y 2 = X 3 + 3 A Z 2 ( X + Z 2 ) 2 . { displaystyle T_ {a} : Y ^ {2} = X ^ {3} + 3aZ ^ {2} (X + Z ^ {2}) ^ {2}.} Termín Z 2 { displaystyle Z ^ {2}} přidání (to je součet mezi dvěma body v různých soustavy souřadnic ) Efektivnější.
The neutrální prvek v nových Jacobian souřadnicích je ( 1 : 1 : 0 : 0 ) { displaystyle (1: 1: 0: 0)}
Algoritmy a příklady Přidání Následující algoritmus představuje součet dvou bodů P 1 { displaystyle P_ {1}} P 2 { displaystyle P_ {2}} P 3 = ( X 3 , Y 3 , Z 3 , Z Z 3 ) { displaystyle P_ {3} = (X_ {3}, Y_ {3}, Z_ {3}, ZZ_ {3})} Z 2 = 1 { displaystyle Z_ {2} = 1} A 3 = 3 A { displaystyle a_ {3} = 3a} 3 , add představuje počet požadovaných přidání.
A = X 2 Z Z 1 { displaystyle A = X_ {2} ZZ_ {1}}
B = Y 2 Z Z 1 Z 1 { displaystyle B = Y_ {2} ZZ_ {1} Z_ {1}}
C = X 1 − A { displaystyle C = X_ {1} -A}
D = 2 ( Y 1 − B ) { displaystyle D = 2 (Y_ {1} -B)}
F = C 2 { displaystyle F = C ^ {2}}
F 4 = 4 F { displaystyle F_ {4} = 4F}
Z 3 = ( Z 1 + C ) 2 − Z Z 1 − F { displaystyle Z_ {3} = (Z_ {1} + C) ^ {2} -ZZ_ {1} -F}
E = Z 3 2 { displaystyle E = {Z_ {3}} ^ {2}}
G = C F 4 { displaystyle G = CF_ {4}}
H = A F 4 { displaystyle H = AF_ {4}}
X 3 = D 2 − G − 2 H − A 3 E { displaystyle X_ {3} = D ^ {2} -G-2H-a_ {3} E}
Y 3 = D ( H − X 3 ) − 2 B G { displaystyle Y_ {3} = D (H-X_ {3}) - 2BG}
Z Z 3 = E { displaystyle ZZ_ {3} = E}
Příklad Nechat P 1 = ( 1 , 13 ) { displaystyle P_ {1} = (1, { sqrt {13}})} P 2 = ( 0 , 3 ) { displaystyle P_ {2} = (0, { sqrt {3}})} R { displaystyle mathbb {R}}
y 2 = X 3 + 3 ( X + 1 ) 2 { displaystyle y ^ {2} = x ^ {3} +3 (x + 1) ^ {2}}
Pak:
A = X 2 Z Z 1 = 0 { displaystyle A = X_ {2} ZZ_ {1} = 0}
B = Y 2 Z Z 1 Z 1 = 3 { displaystyle B = Y_ {2} ZZ_ {1} Z_ {1} = { sqrt {3}}}
C = X 1 − A = 1 { displaystyle C = X_ {1} -A = 1}
D = 2 ( Y 1 − B ) = 2 ( 13 − 3 ) { displaystyle D = 2 (Y_ {1} -B) = 2 ({ sqrt {13}} - { sqrt {3}})}
F = C 2 = 1 { displaystyle F = C ^ {2} = 1}
F 4 = 4 F = 4 { displaystyle F_ {4} = 4F = 4}
Z 3 = ( Z 1 + C ) 2 − Z Z 1 − F = 2 { displaystyle Z_ {3} = (Z_ {1} + C) ^ {2} -ZZ_ {1} -F = 2}
E = Z 3 2 = 4 { displaystyle E = {Z_ {3}} ^ {2} = 4}
G = C F 4 = 4 { displaystyle G = CF_ {4} = 4}
H = A F 4 = 0 { displaystyle H = AF_ {4} = 0}
X 3 = D 2 − G − 2 H − A 3 E = 48 − 8 39 { displaystyle X_ {3} = D ^ {2} -G-2H-a_ {3} E = 48-8 { sqrt {39}}}
Y 3 = D ( H − X 3 ) − 2 B G = 296 3 − 144 13 { displaystyle Y_ {3} = D (H-X_ {3}) - 2BG = 296 { sqrt {3}} - 144 { sqrt {13}}}
Z Z 3 = E = 4 { displaystyle ZZ_ {3} = E = 4}
Všimněte si, že v tomto případě Z 1 = Z 2 = 1 { displaystyle Z_ {1} = Z_ {2} = 1} P 3 = ( X 3 , Y 3 , Z 3 , Z Z 3 ) = ( 48 − 8 39 , 296 3 − 144 13 , 2 , 4 ) { displaystyle P_ {3} = (X_ {3}, Y_ {3}, Z_ {3}, ZZ_ {3}) = (48-8 { sqrt {39}}, 296 { sqrt {3}} -144 { sqrt {13}}, 2,4)} P 3 = ( 12 − 2 39 , 37 3 − 18 13 ) { displaystyle P_ {3} = (12-2 { sqrt {39}}, 37 { sqrt {3}} - 18 { sqrt {13}})}
Zdvojnásobení Následující algoritmus představuje zdvojnásobení bodu P 1 { displaystyle P_ {1}} A 3 = 3 A { displaystyle a_ {3} = 3a} A 2 = 2 A { displaystyle a_ {2} = 2a} 2 a a3 respektive a add označuje přidání.
A = X 1 2 { displaystyle A = {X_ {1}} ^ {2}}
B = A 2 Z Z 1 ( X 1 + Z Z 1 ) { displaystyle B = a_ {2} ZZ_ {1} (X_ {1} + ZZ_ {1})}
C = 3 ( A + B ) { displaystyle C = 3 (A + B)}
D = Y 1 2 { displaystyle D = {Y_ {1}} ^ {2}}
E = D 2 { displaystyle E = D ^ {2}}
Z 3 = ( Y 1 + Z 1 ) 2 − D − Z Z 1 { displaystyle Z_ {3} = (Y_ {1} + Z_ {1}) ^ {2} -D-ZZ_ {1}}
Z Z 3 = Z 3 2 { displaystyle ZZ_ {3} = Z_ {3} ^ {2}}
F = 2 ( ( X 1 + D ) 2 − A − E ) { displaystyle F = 2 ((X_ {1} + D) ^ {2} -A-E)}
X 3 = C 2 − A 3 Z Z 3 − 2 F { displaystyle X_ {3} = C ^ {2} -a_ {3} ZZ_ {3} -2F}
Y 3 = C ( F − X 3 ) − 8 E { displaystyle Y_ {3} = C (F-X_ {3}) - 8E}
Příklad Nechat P 1 = ( 0 , 3 ) { displaystyle P_ {1} = (0, { sqrt {3}})} y 2 = X 3 + 3 ( X + 1 ) 2 { displaystyle y ^ {2} = x ^ {3} +3 (x + 1) ^ {2}}
Pak:
A = X 1 2 = 0 { displaystyle A = {X_ {1}} ^ {2} = 0}
B = A 2 Z Z 1 ( X 1 + Z Z 1 ) = 2 { displaystyle B = a_ {2} ZZ_ {1} (X_ {1} + ZZ_ {1}) = 2}
C = 3 ( A + B ) = 6 { displaystyle C = 3 (A + B) = 6}
D = Y 1 2 = 3 { displaystyle D = {Y_ {1}} ^ {2} = 3}
E = D 2 = 9 { displaystyle E = D ^ {2} = 9}
Z 3 = ( Y 1 + Z 1 ) 2 − D − Z Z 1 = 2 3 { displaystyle Z_ {3} = (Y_ {1} + Z_ {1}) ^ {2} -D-ZZ_ {1} = 2 { sqrt {3}}}
Z Z 3 = Z 3 2 = 12 { displaystyle ZZ_ {3} = Z_ {3} ^ {2} = 12}
F = 2 ( ( X 1 + D ) 2 − A − E ) = 0 { displaystyle F = 2 ((X_ {1} + D) ^ {2} -A-E) = 0}
X 3 = C 2 − A 3 Z Z 3 − 2 F = 0 { displaystyle X_ {3} = C ^ {2} -a_ {3} ZZ_ {3} -2F = 0}
Y 3 = C ( F − X 3 ) − 8 E = − 72 { displaystyle Y_ {3} = C (F-X_ {3}) - 8E = -72}
Všimněte si, že zde je bod v afinních souřadnicích, takže Z 1 = 1 { displaystyle Z_ {1} = 1} P 3 = ( 0 , − 72 , 2 3 , 12 ) { displaystyle P_ {3} = (0, -72,2 { sqrt {3}}, 12)} P 3 = ( 0 , − 3 ) { displaystyle P_ {3} = (0, - { sqrt {3}})}
Rovnocennost s formou Weierstrass Jakákoli eliptická křivka je birationally ekvivalent na jiný napsaný ve formě Weierstrass.
Následující zkroucený ztrojnásobená Doche-Icart-Kohelova křivka
T A , λ : y 2 = X 3 + 3 λ A ( X + λ ) 2 { displaystyle T_ {a, lambda}: quad y ^ {2} = x ^ {3} +3 lambda a (x + lambda) ^ {2}} lze transformovat do Weierstrassovy formy pomocí mapa :
( X , y ) ↦ ( X − λ A , y ) . { displaystyle (x, y) mapsto (x- lambda a, y).} Takto T A , λ { displaystyle T_ {a, lambda}}
y 2 = X 3 − 3 λ 2 A ( A − 2 ) X + λ 3 A ( 2 A 2 − 6 A + 3 ) { displaystyle y ^ {2} = x ^ {3} -3 { lambda} ^ {2} a (a-2) x + { lambda} ^ {3} a (2a ^ {2} -6a + 3 )} Naopak, vzhledem k eliptické křivce ve Weierstrassově formě:
E C , d : y 2 = X 3 + C X 2 + d { displaystyle E_ {c, d}: quad y ^ {2} = x ^ {3} + cx ^ {2} + d} je možné najít „odpovídající“ Triplingově orientovanou křivku Doche – Icart – Kohel pomocí následujícího vztahu:
λ = − 3 d ( A − 2 ) A ( 2 A 2 − 6 A + 3 ) { displaystyle lambda = { frac {-3d (a-2)} {a (2a ^ {2} -6a + 3)}}} kde A je vykořenit polynomu
6912 A ( A − 2 ) 3 − j ( 4 A − 9 ) , { displaystyle 6912a (a-2) ^ {3} -j (4a-9),} kde
j = 6912 C 3 4 C 3 + 27 d 2 { displaystyle j = { frac {6912c ^ {3}} {4c ^ {3} + 27d ^ {2}}}} je j-invariantní eliptické křivky E C , d { displaystyle E_ {c, d}}
Všimněte si, že v tomto případě není daná mapa pouze birakční ekvivalencí, ale také izomorfismus mezi křivkami.
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 ^ Christophe Doche, Thomas Icart a David R. Kohel, Efektivní skalární násobení isogenymi rozklady , str. 198-199 externí odkazy Reference Christophe Doche; Thomas Icart a David R. Kohel (2006). Efektivní skalární násobení isogenymi rozklady (PDF) . objevil se v PKC 2006, část svazku LNCS (Lecture Series in Computer Science) číslo 3958. Springer Verlag. str. 285–352. Daniel J. Bernstein Tanja Lange (2007). Analýza a optimalizace eliptické křivky s jedním skalárním násobením (PDF) . objevil se v G.L. Mullen, D. Panario, I.E. Shparlinski (eds.), Finite Fields and Applications (Proceedings 8. mezinárodní konference, Fq8, Melbourne, Austrálie, 9. – 13. Července 2007). Klasifikace matematických předmětů.DJ Bernstein , P.Birkner, T.Lange a C.Peters (2007). Optimalizace dvojité základny eliptické křivky s jedním skalárním násobením (PDF) . objevil se v K. Srinathan, C. Pandu Rangan , M. Yung (Eds.), Proceedings of the 8th International Conference on Cryptology in India: Progress in Cryptology (Indocrypt 2007) 9–13 December 2007, Chennai, India. Springer.CS1 maint: více jmen: seznam autorů (odkaz) http://hyperelliptic.org/EFD/g1p/auto-3dik-standard.html 
