Skręcona krzywa Edwardsa

Skręcona krzywa Edwardsa równania ${\ Displaystyle 10x ^ {2} + y ^ {2} = 1 + 6x ^ {2} y ^ {2}}$

W geometrii algebraicznej skręcone krzywe Edwardsa to płaskie modele krzywych eliptycznych , uogólnienie krzywych Edwardsa wprowadzone przez Bernsteina , Birknera, Joye, Lange i Petersa w 2008 roku. Zestaw krzywych nosi imię matematyka Harolda M. Edwardsa . Krzywe eliptyczne są ważne w kryptografii klucza publicznego, a skręcone krzywe Edwardsa są sercem schematu podpisu elektronicznego o nazwie EdDSA który oferuje wysoką wydajność przy jednoczesnym uniknięciu problemów z bezpieczeństwem, które pojawiły się w innych schematach podpisu cyfrowego.

Definicja

Każda skręcona krzywa Edwardsa jest skrętem krzywej Edwardsa . Skręcona krzywa Edwardsa mi mi $a, d}}}$$} (\mathbb {K} )\neq 2}$ nad polem z $K$$operatorname {$ jest płaską krzywą afiniczną określoną równaniem:

${\ Displaystyle E_ {E_ {a, d}}: ax ^ {2} + y ^ {2} = 1 + dx ^ { 2}y^{2}}$

gdzie ${\ Displaystyle a, d}$ są odrębnymi niezerowymi elementami ${\ Displaystyle \ mathbb {K}}$ . Szczególny przypadek $, ponieważ$ nieskręcony się do zwykłej krzywej .

Każda skręcona krzywa Edwardsa jest dwuracjonalnie równoważna krzywej eliptycznej w postaci Montgomery'ego i odwrotnie.

Prawo grupowe

Jak dla wszystkich krzywych eliptycznych, także dla skręconej krzywej Edwardsa, pomiędzy jej punktami można wykonać pewne operacje, takie jak dodanie dwóch z nich lub podwojenie (lub potrojenie) jednego. Wynikiem tych operacji są zawsze punkty należące do samej krzywej. W kolejnych podrozdziałach podane są wzory pozwalające uzyskać współrzędne punktu powstałe w wyniku dodania dwóch innych punktów (dodania) lub współrzędne punktu wynikające z podwojenia pojedynczego punktu na krzywej.

Dodatek na skręconych krzywych Edwardsa

Niech ${\ Displaystyle \ mathbb {K}}$ będzie polem o charakterystyce różnej od 2. Niech K. ${\ Displaystyle (x_ {1}, y_ {1})}$ i $punktami$ na skręconej krzywej Edwardsa. Równanie skręconej krzywej Edwardsa jest zapisane jako;

mi mi _{, za , re :} za $\ Displaystyle ax ^ {2} + y ^ {2} = 1 + dx ^ {2} y ^ {2}}$ .

${\ Displaystyle (x_ {1}, y_ {1}), (x_ {2}, y_ {2}$ _{) , a , d} } na mi jest:

${\ Displaystyle (x_ {1}, y_ {1}) + (x_ {2}, y_ {2}) = \ lewo ({\ Frac {x_ {1} y_ {2} + y_{1}x_{2}}{1+dx_{1}x_{2}y_{1}y_{2}}},{\frac {y_{1}y_{2}-ax_{1}x_{ 2}}{1-dx_{1}x_{2}y_{1}y_{2}}}\prawo)}$

Element neutralny to (0,1), a ujemna z ${\ Displaystyle (x_ {1}, y_ {1})}$ to ${\ Displaystyle (-x_ {1},y_{1})}$

Formuły te działają również w przypadku podwojenia. Jeśli a jest kwadratem w i d nie jest kwadratem w , te formuły są kompletne : oznacza to, że można ich używać dla wszystkich par $K$$\ displaystyle \ mathbb {K}$ punktów bez wyjątków; więc działają również w przypadku podwojenia, a elementy neutralne i ujemne są akceptowane jako dane wejściowe.

Przykład dodawania

Biorąc pod uwagę następującą skręconą krzywą Edwardsa z a = 3 i d = 2:

${\ Displaystyle 3x ^ {2} + y ^ {2} = 1 + 2x ^ {2} y ^ {2}}$

możliwe jest dodanie punktów ${\ Displaystyle P_ {1} = (1, {\ sqrt {2}})}$ i ${\ Displaystyle P_ { 2}=(1,-{\sqrt {2}})}$ korzystając ze wzoru podanego powyżej. Wynikiem jest punkt P ₃ , który ma współrzędne:

${\ Displaystyle x_ {3} = {\ Frac {x_ {1} y_ {2} + y_ {1} x_{2}}{1+dx_{1}x_{2}y_{1}y_{2}}}=0,}$

${\ Displaystyle y_ {3} = {\ Frac {y_ {1} y_ {2} -ax_ {1} x_ {2}} {1-dx_ {1} x_ {2} y_ { 1}y_{2}}}=-1.}$

Podwojenie na skręconych krzywych Edwardsa

Podwojenie można wykonać za pomocą dokładnie tego samego wzoru co dodawanie. Podwojenie punktu na krzywej E _{a, d} wynosi: ${\ Displaystyle (x_ {1}, y_ {1})}$

${\ Displaystyle 2 (x_ {1}, y_ {1}) = (x_ {3}, y_ {3})}$

Gdzie

${\ Displaystyle {\ rozpocząć {wyrównane} x_ {3} i = {\ Frac {x_ {1} y_ {1} + y_ {1} x_ {1}} {1 + dx_ {1} x_ {1} y_ { 1}y_{1}}}={\frac {2x_{1}y_{1}}{ax_{1}^{2}+y_{1}^{2}}}\\[6pt]y_{3 }&={\frac {y_{1}y_{1}-ax_{1}x_{1}}{1-dx_{1}x_{1}y_{1}y_{1}}}={\frac {y_{1}^{2}-ax_{1}^{2}}{2-ax_{1}^{2}-y_{1}^{2}}}.\end{aligned}}}$

re $Displaystyle dx ^ {2} y ^ {2} = ax ^ {2} + przez ^ {2} - 1}$ . Zmniejsza to moc z 4 do 2 i pozwala na bardziej wydajne obliczenia.

Przykład podwojenia

Biorąc pod uwagę tę samą skręconą krzywą Edwardsa podaną w poprzednim przykładzie, przy a = 3 i d = 2, możliwe jest podwojenie punktu ${\ Displaystyle P_ {1} = (1, {\ sqrt {2}})}$ . Punkt 2P ₁ otrzymany za pomocą powyższego wzoru ma następujące współrzędne:

${\ Displaystyle x_ {3} = {\ Frac {2x_ {1} y_ {1}} {ax_ {1} ^ {2 }+y_{1}^{2}}}={\frac {2{\sqrt {2}}}{5}},}$

${\ Displaystyle y_ {3} = {\ Frac {y_ {1} ^ {2} -ax_ {1} ^ {2}} {2-ax_ {1} ^ {2} -y_ {1} ^ {2} }}={\frac {1}{3}}.}$

Łatwo zauważyć, przy pewnych małych obliczeniach, że punkt ${\ Displaystyle P_ {3} = \ lewo ({\ Frac {2 {\ sqrt {2}}} 5}}, {\ Frac {1}{3}} \ prawej)}$ należy do krzywej ${\ Displaystyle 3x ^ {2} + y ^ {2} =1+2x^{2}y^{2}}$ .

Rozszerzone współrzędne

Istnieje inny rodzaj układu współrzędnych, za pomocą którego można przedstawić punkt na skręconych krzywych Edwardsa. punkt ${\ Displaystyle (x, y, z)}$ na ${\ Displaystyle ax ^ {2} + y ^ {2} = 1+dx^{2}y^{2}}$ jest reprezentowane jako X , Y , Z , T spełniające następujące równania x = X / Z , y = Y / Z , xy = T / Z .

Współrzędne punktu ( X : Y : Z : T ) nazywane są rozszerzonymi skręconymi współrzędnymi Edwardsa . Element tożsamości jest reprezentowany przez (0:1:1:0). Minusem punktu jest (− X : Y : Z :− T ).

Odwrócone skręcone współrzędne Edwardsa

Współrzędne $_$ współrzędnymi krzywej ${\ textstyle (X ^ {2} + aY ^ {2}) Z ^ {2} = X ^ {2} Y ^ {2} + dZ ^ { 4}}$ _ z ${\ textstyle X_ {1} Y_ {1} Z_ {1} \ neq 0}$ ; ten punkt do afinicznego jeden ${\ Displaystyle (Z_ {1} / X_ {1}, Z_ {1} / Y_ {1})}$ na mi _{mi , za , re} . Bernstein i Lange wprowadzili te odwrócone współrzędne dla przypadku a=1 i zauważyli, że współrzędne te dodatkowo oszczędzają czas.

Rzutowe skręcone współrzędne Edwardsa

Równanie rzutowej skręconej krzywej Edwardsa jest podane jako: $^ {2}) Z ^ { 2}=Z^{4}+dX^{2}Y^{2}}$ Dla Z ₁ ≠ 0 punkt (X ₁ :Y ₁ :Z ₁ ) reprezentuje punkt afiniczny ( x ₁ = X ₁ / Z ₁ , y ₁ = Y ₁ / Z ₁ ) na mi _{mi , za , re} .

Wyrażanie krzywej eliptycznej w skręconej postaci Edwardsa oszczędza czas w arytmetyce, nawet jeśli tę samą krzywą można wyrazić w postaci Edwardsa.

Dodatek w rzutowych krzywych skręconych

Dodatek na rzutowej skręconej krzywej Edwardsa jest określony przez

(X ₃ : Y ₃ : Z ₃ ) = ( X ₁ : Y ₁ : Z ₁ ) + (X ₂ : Y ₂ : Z ₂ )

i kosztuje 10 mnożeń + 1 podniesienie do kwadratu + 2 D + 7 dodat ków, gdzie 2 D to jedno pomnożenie przez a i jedno przez d .

Algorytm

A = Z ₁ · Z ₂ ,

B = A ²

C = X ₁ · X ₂

D = Y ₁ · Y ₂

E = dC · D

F = B - mi

G = B + mi

X ₃ = A · F((( X ₁ + Y ₁ ) · (X ₂ + Y ₂ ) - do - re)

Y ₃ = ZA · G · (D - aC)

Z ₃ = fa · G

Podwojenie na projekcyjnych skręconych krzywych

Podwojenie rzutowej krzywej skręconej jest podane przez

(X3 _: Y3 _: Z3 ₎ = 2(X1 _: Y1 _: Z1 ₎ .

Kosztuje to 3 mnożenia + 4 kwadraty + 1 D + 7 dodat ków, gdzie 1 D to mnożenie przez a .

Algorytm

B = (X ₁ + Y ₁ ) ²

do = X ₁ ²

re = Y ₁ ²

mi = aC

fa = mi + re

H = Z ₁ ²

jot = fa - 2H

x ₃ = (b - do - re). jot

Y ₃ = fa · (mi - re)

Z ₃ = fa · jot

Zobacz też

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

Notatki

• Daniela J. Bernsteina; Marca Joye'a; Tanja Lange; Petera Birknera; Christiane Peters, Twisted Edwards Curves (PDF)

• Huseyin Hisil, Kenneth Wong, Gary Carter, Ed Dawson. (2008), „Twisted Edwards Curves revisited” , Cryptology ePrint Archive {{ cytat }} : CS1 maint: wiele nazwisk: lista autorów ( link )

• Daniel J. Bernstein; Tanja Lange; Petera Birknera; Christiane Peters, ECM przy użyciu krzywych Edwardsa (PDF)

Linki zewnętrzne

• http://hyperelliptic.org/EFD/g1p/index.html
• http://hyperelliptic.org/EFD/g1p/auto-twisted.html
• Algorytm Ed25519: http://ed25519.cr.yp.to/