Den trippelorienterade Doche–Icart–Kohel-kurvan är en form av en elliptisk kurva som har använts på sistone inom kryptografi [ när? ; det är en speciell typ av Weierstrass-kurva . Under vissa förhållanden är vissa operationer , som att lägga till, dubbla eller tredubbla punkter, snabbare att beräkna med detta formulär. Den triplingorienterade Doche–Icart–Kohel-kurvan, ofta kallad med förkortningen 3DIK har introducerats av Christophe Doche, Thomas Icart och David R. Kohel i
Definition
En trippelorienterad Doche–Icart–Kohel-kurva med ekvation
y
2
=
x
3
− 3
x
2
− 6 x − 3
{\displaystyle y^{2}=x^{3}-3x^{2}-6x-3 }
Låt
K
{\displaystyle K}
fält med karaktäristiska olika former 2 och 3.
En elliptisk kurva i trefaldig orienterad Doche–Icart–Kohel-form definieras av ekvationen :
T
a
:
y
2
=
x
3
+ 3 a ( x + 1
)
2
{\displaystyle T_{a}\ :\ y^{2}=x^{3}+3a(x+1)^{2}}
med
en ∈ K
{\displaystyle a\in K}
En allmän punkt P på
T
a
{\displaystyle T_{a}}
affina koordinater
( x , y )
{\displaystyle (x,y)}
neutrala elementet för grupplagen och den skrivs i projektiva koordinater som O = (0:1:0). Negationen av en punkt P = ( x , y ) med avseende på detta neutrala element är − P = ( x , − y ).
Grupplagen
Betrakta en elliptisk kurva i den Tripling-orienterade Doche-Icart-Kohel-formen i affina koordinater :
0
Ta
+
:
y2
1
=
x
3
+ 3 a ( x
)
2
, a ≠ ,
9 4
. _ _
{\displaystyle T_{a}:\quad y^{2}=x^{3}+3a(x+1)^{2},\qquad a\neq 0,{\tfrac {9}{4}} .}
Liksom i andra former av elliptiska kurvor är det möjligt att definiera vissa "operationer" mellan punkter, som att lägga till punkter eller dubbla (Se även Grupplagen ) . I följande avsnitt ges formler för att lägga till, negera och dubbla poäng. Adderings- och dubbleringsformlerna används ofta för andra operationer: givet en punkt P på en elliptisk kurva är det möjligt att beräkna [n]P , där n är ett heltal , med hjälp av addition och dubblering; att beräkna multipler av punkter är viktigt i elliptisk kurvkryptografi och i Lenstra elliptisk kurvfaktorisering .
Tillägg
Givet
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}\right.\\&\qquad \qquad \qquad \qquad \left.+(y_{1}^{3}-3y_{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{aligned}}}
Fördubbling
Givet en punkt
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}}}+\left({\frac {9}{y_{1}^{2}a^{2}}}+{\frac {9}{y_{ 1}^{2}a}}\höger)x_{1}^{2}+\vänster({\frac {18}{y_{1}^{2}a^{2}}}-2\höger )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}}\right)x_{1}^{4}+\left (-{\frac {27}{y_{1}^{3}a^{3}}}-{\frac {81}{y_{1}^{3}a^{2}}}+{\ frac {9}{2y_{1}}}\right)x_{1}^{3}+\left(-{\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}}\right)x_{1}+\left(-{\frac {27}{y_{1}^{3}a^{ 3}}}+{\frac {9}{y_{1}a^{2}}}-y_{1}\right)\end{aligned}}}
Negation
Givet en punkt
P
1
= (
x
1
,
y
1
)
{\displaystyle P_{1}=(x_{1},y_{1})}
T
a
{\displaystyle T_{a}}
negation med avseende på det neutrala elementet
0
0
( : 1 : )
{\displaystyle (0:1:0)}
−
P
1
= (
x
1
, −
y
1
)
{\displaystyle -P_{1}=(x_{1},-y_{ 1})}
Det finns även andra formler som anges för Tripling-orienterade Doche–Icart–Kohel-kurvor för snabb tripling och blandad addition.
Nya jakobianska koordinater
För beräkning på dessa kurvor representeras punkter vanligtvis i nya jakobianska koordinater ( Jn ) :
en punkt i de nya jakobiska koordinaterna är av formen
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}),}
för alla
λ ∈ K
{\displaystyle \lambda \in K}
Detta betyder till exempel att punkten
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}
Så, en affinpunkt
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}} :
Ta
_
:
Y2
+
=
X3
_
+ 3 a
Z2
)
( X
Z2
_
2
.
_ _
{\displaystyle T_{a}\ :\ Y^{2}=X^{3}+3aZ^{2}(X+Z^{2})^{2}.}
Termen
Z
2
{\displaystyle Z^{2}}
additionen (det vill säga additionen mellan två punkter i olika koordinatsystem) mer effektiv.
Det neutrala elementet i nya jakobianska koordinater är
0
0
( 1 : 1 : : )
{\displaystyle (1:1:0:0)}
Algoritmer och exempel
Tillägg
Följande algoritm representerar summan av två punkter
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}
antalet additioner nödvändig.
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}
Exempel
Låt
P
1
= ( 1 ,
13
)
{\displaystyle P_{1}=(1,{\sqrt {13}})}
0
P
2
= ( ,
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}}
Sedan:
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}
Lägg märke till att i det här fallet
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}})}
Fördubbling
Följande algoritm representerar dubbleringen av en punkt
P
1
{\displaystyle P_{1}}
a
3
= 3 a
{\displaystyle a_{3}=3a}
a
2
= 2 a
{\displaystyle a_{2}=2a}
2 respektive a 3 , och add anger additionerna.
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}-AE)}
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}
Exempel
Låt
0
P
1
= ( ,
3
)
{\displaystyle P_{1}=(0,{\sqrt {3}})}
y
2
=
x
3
+ 3 ( x + 1
)
2
{\displaystyle y^ {2}=x^{3}+3(x+1)^{2}}
Sedan:
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}-AE)=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}
Lägg märke till att här är punkten i affina koordinater, så
Z
1
= 1
{\displaystyle Z_{1}=1}
0
P
3
= ( , − 72 , 2
3
, 12 )
{\displaystyle P_{3}=(0,-72,2{\sqrt {3}},12)} ,
0
P
3
= ( , −
3
)
{\displaystyle P_{3}=(0,-{\sqrt {3}})}
Ekvivalens med Weierstrass-formen
Varje elliptisk kurva är birationellt ekvivalent med en annan skriven i Weierstrass-formen.
Följande vridna trippelorienterade Doche-Icart-Kohel-kurva
Ta
(
, λ
:
y
2
=
x
3
+ 3 λ a ( x + λ
)
2
{\displaystyle T_{a,\lambda }:\quad y^{2}=x^{3}+3\lambda a x+\lambda )^{2}}
kan omvandlas till Weierstrass-formen av kartan :
( x , y ) ↦ ( x − λ a , y ) .
{\displaystyle (x,y)\mapsto (x-\lambda a,y).}
På detta sätt blir
Ta
:
, λ
{\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)}
Omvänt, givet en elliptisk kurva i Weierstrass-formen:
E
c , d
:
y
2
=
x
3
+ c
x
2
+ d
{\displaystyle E_{c,d}:\quad y^{2}=x^{3}+cx^{2}+d}
det är möjligt att hitta den "motsvarande" Tripling-orienterade Doche–Icart–Kohel-kurvan, med hjälp av följande relation:
λ =
− 3 d ( a − 2 )
a ( 2
a
2
− 6 a + 3 )
{\displaystyle \lambda ={\frac {-3d(a-2)}{a(2a^{2}-6a+ 3)}}}
där a är en rot av polynomet
6912 a ( a − 2
)
3
− j ( 4 a − 9 ) ,
{\displaystyle 6912a(a-2)^{3}-j(4a-9),}
var
j =
6912
c
3
4
c
3
+ 27
d
2
{\displaystyle j={\frac {6912c^{3}}{4c^{3}+27d^{2}}}}
är j-invarianten för den elliptiska kurvan
E
c , d
{\displaystyle E_{c,d}}
Lägg märke till att i det här fallet är den givna kartan inte bara en birational ekvivalens, utan en isomorfism mellan kurvor.
Intern länk
För mer information om den löptid som krävs i ett specifikt fall, se Tabell över kostnader för operationer i elliptiska kurvor
Anteckningar
externa länkar
Christophe Doche; Thomas Icart & David R. Kohel (2006). Effektiv skalär multiplikation genom isogena nedbrytningar (PDF) . medverkade på PKC 2006, en del av LNCS (Lecture Series in Computer Science) volym nummer 3958. Springer Verlag. s. 285–352.
Daniel J. Bernstein , Tanja Lange (2007). Analys och optimering av elliptisk kurva enkel-skalär multiplikation ( PDF) . medverkat i GL Mullen, D. Panario, IE Shparlinski (red.), Finite Fields and Applications (Proceedings 8th International Conference, Fq8, Melbourne, Australien, 9–13 juli 2007). Ämnesklassificering i matematik.
DJBernstein , P. Birkner, T. Lange och C. Peters (2007). Optimera dubbelbas elliptisk kurva enkelskalär multiplikation (PDF) . medverkade i 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, Indien. Springer. {{ citera bok }} : CS1 underhåll: flera namn: lista över författare ( länk )
http://hyperelliptic.org/EFD/g1p/auto-3dik-standard.html
