Curva de Edwards

Na matemática, as curvas de Edwards são uma família de curvas elípticas estudadas por Harold Edwards em 2007. O conceito de curvas elípticas sobre corpos finitos é amplamente utilizado na criptografia de curva elíptica. As aplicações das curvas de Edwards à criptografia foram desenvolvidas por Daniel J. Bernstein e Tanja Lange: eles apontaram diversas vantagens da forma de Edwards em comparação com a mais conhecida forma de Weierstrass.

Definição

A equação de uma curva de Edwards sobre um corpo K que não possui característica 2 é:

x^{2}+y^{2}=1+d\ x^{2}y^{2}\,

para algum escalar $d\in K\setminus \{0,1\}$ . Também a seguinte forma com parâmetros c e d é chamada de curva de Edwards:

x^{2}+y^{2}=c^{2}(1+d\ x^{2}y^{2})\,

onde c, d ∈ K com cd(1 − c⁴·d) ≠ 0.

Cada curva de Edwards é birracionalmente equivalente a uma curva elíptica na forma de Montgomery e, portanto, admite uma lei de grupo algébrico uma vez que se escolha um ponto para servir como elemento neutro. Se K for finito, então uma fração considerável de todas as curvas elípticas sobre K pode ser escrita como curvas de Edwards. Frequentemente, as curvas elípticas na forma de Edwards são definidas tendo c=1, sem perda de generalidade. Nas seções seguintes, assume-se que c=1.

A lei de grupo

(Veja também lei de grupo da curva de Weierstrass)

Cada curva de Edwards $x^{2}+y^{2}=1+dx^{2}y^{2}$ sobre um corpo K com característica diferente de 2 com $d\neq 1$ é birracionalmente equivalente a uma curva elíptica sobre o mesmo corpo: $(1/e)v^{2}=u^{3}+(4/e-2)u^{2}+u$ , onde $e=1-d,u={\frac {1+y}{1-y}},v={\frac {2(1+y)}{x(1-y)}}$ e o ponto $P=(0,1)$ é mapeado para o infinito O. Este mapeamento birracional induz um grupo em qualquer curva de Edwards.

Lei de adição de Edwards

Em qualquer curva elíptica, a soma de dois pontos é dada por uma expressão racional das coordenadas dos pontos, embora, em geral, possa ser necessário usar várias fórmulas para cobrir todos os pares possíveis. Para a curva de Edwards, tomando o elemento neutro como sendo o ponto (0, 1), a soma dos pontos $(x_{1},y_{1})$ e $(x_{2},y_{2})$ é dada pela fórmula:

(x_{1},y_{1})+(x_{2},y_{2})=\left({\frac {x_{1}y_{2}+x_{2}y_{1}}{1+dx_{1}x_{2}y_{1}y_{2}}},{\frac {y_{1}y_{2}-x_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}\right)\,

O oposto de qualquer ponto $(x,y)$ é $(-x,y)$ . O ponto $(0,-1)$ tem ordem 2, e os pontos $(\pm 1,0)$ têm ordem 4. Em particular, uma curva de Edwards sempre tem um ponto de ordem 4 com coordenadas em K.

Se d não for um quadrado em K e $\{(x_{1},y_{1}),(x_{2},y_{2})\}\in \{(x,y)|x^{2}+y^{2}=1+dx^{2}y^{2}\}^{2}$ , então não existem pontos excepcionais: os denominadores $1+dx_{1}x_{2}y_{1}y_{2}$ e $1-dx_{1}x_{2}y_{1}y_{2}$ são sempre diferentes de zero. Portanto, a lei de adição de Edwards é completa quando d não é um quadrado em K. Isso significa que as fórmulas funcionam para todos os pares de pontos de entrada na curva de Edwards sem exceções para duplicação, sem exceção para o elemento neutro, sem exceção para negativos, etc. Em outras palavras, ela é definida para todos os pares de pontos de entrada na curva de Edwards sobre K e o resultado fornece a soma dos pontos de entrada.

Se d for um quadrado em K, então a mesma operação pode ter pontos excepcionais, ou seja, pode haver pares de pontos $(x_{1},y_{1}),(x_{2},y_{2})\in \{(x,y)|x^{2}+y^{2}=1+dx^{2}y^{2}\}$ tais que um dos denominadores se torne zero: ou $1+dx_{1}x_{2}y_{1}y_{2}=0$ ou $1-dx_{1}x_{2}y_{1}y_{2}=0$ .

Uma das características atraentes da lei de adição de Edwards é que ela é fortemente unificada, ou seja, também pode ser usada para dobrar um ponto, simplificando a proteção contra ataque de canal lateral. A fórmula de adição acima é mais rápida do que outras fórmulas unificadas e possui a forte propriedade de completude.

Exemplo da lei de adição:

Considere a curva elíptica na forma de Edwards com d=2

{\displaystyle }x^{2}+y^{2}=1+2x^{2}y^{2}

e o ponto $P_{1}=(1,0)$ nela. É possível provar que a soma de P₁ com o elemento neutro (0,1) resulta novamente em P₁. De fato, usando a fórmula dada acima, as coordenadas do ponto dado por esta soma são:

x_{3}={\frac {x_{1}y_{2}+y_{1}x_{2}}{1+2x_{1}x_{2}y_{1}y_{2}}}=1

y_{3}={\frac {y_{1}y_{2}-x_{1}x_{2}}{1-2x_{1}x_{2}y_{1}y_{2}}}=0

Um análogo no círculo

Ficheiro:Edwards Curve,Clock group diagram.jpg

Grupo do relógio

Para entender melhor o conceito de "adição" de pontos em uma curva, um bom exemplo é dado pelo clássico grupo do círculo:

tome o círculo de raio 1

{\displaystyle }x^{2}+y^{2}=1

e considere dois pontos $P 1 =(x 1,y 1)$ , P₂=(x₂,y₂) sobre ele. Sejam α₁ e α₂ os ângulos tais que:

{\displaystyle }P_{1}=(x_{1},y_{1})=(\sin {\alpha _{1}},\cos {\alpha _{1}})

{\displaystyle }P_{2}=(x_{2},y_{2})=(\sin {\alpha _{2}},\cos {\alpha _{2}})

A soma de P₁ e P₂ é, portanto, dada pela soma de "seus ângulos". Ou seja, o ponto P₃=P₁+P₂ é um ponto no círculo com coordenadas ( $x 3,y 3$ ), onde:

{\displaystyle }x_{3}=\sin({\alpha }_{1}+{\alpha }_{2})=\sin {\alpha _{1}}\cos {\alpha _{2}}+\sin {\alpha _{2}}\cos {\alpha _{1}}=x_{1}y_{2}+x_{2}y_{1}

{\displaystyle }y_{3}=\cos({\alpha }_{1}+{\alpha }_{2})=\cos {\alpha _{1}}\cos {\alpha _{2}}-\sin {\alpha _{1}}\sin {\alpha _{2}}=y_{1}y_{2}-x_{1}x_{2}.

Desta forma, a fórmula de adição para pontos no círculo de raio 1 é:

{\displaystyle }(x_{1},y_{1})+(x_{2},y_{2})=(x_{1}y_{2}+x_{2}y_{1},y_{1}y_{2}-x_{1}x_{2})

.

Adição em curvas de Edwards

Os pontos em uma curva elíptica formam um grupo abeliano: pode-se adicionar pontos e obter múltiplos inteiros de um único ponto. Quando uma curva elíptica é descrita por uma equação cúbica não singular, então a soma de dois pontos P e Q, denotada como P + Q, está diretamente relacionada ao terceiro ponto de interseção entre a curva e a linha que passa por P e Q.

O mapeamento birracional entre uma curva de Edwards e a curva elíptica cúbica correspondente mapeia as linhas retas em seções cônicas $Axy+Bx+Cy+D=0$ . Em outras palavras, para as curvas de Edwards, os três pontos $P$ , $Q$ e $-(P+Q)$ estão sobre uma hipérbole.

Dados dois pontos distintos que não sejam a identidade $P_{1}=(x_{1},y_{1}),P_{2}=(x_{2},y_{2}),P_{1}\neq P_{2}$ , os coeficientes da forma quadrática são (até escalares):

$A=(x_{1}-x_{2})+(x_{1}y_{2}-x_{2}y_{1})$ ,

$B=(x_{2}y_{2}-x_{1}y_{1})+y_{1}y_{2}(x_{2}-x_{1})$ ,

$C=x_{1}x_{2}(y_{1}-y_{2}),D=C$

No caso de dobrar um ponto $P=(x,y)$ , o ponto inverso $-2P$ reside na cônica que toca a curva no ponto $P$ . Os coeficientes da forma quadrática que define a cônica são (até escalares^{[necessário esclarecer]}):

$A=dx^{2}y-1$ ,

$B=y-x^{2}$ ,

$C=x(1-y),D=C$

Coordenadas homogêneas projetivas

No contexto da criptografia, coordenadas homogêneas são usadas para evitar inversões de corpo que aparecem na fórmula afim. Para evitar inversões nas fórmulas originais de adição de Edwards, a equação da curva pode ser escrita em coordenadas projetivas como:

$(X^{2}+Y^{2})Z^{2}=Z^{4}+dX^{2}Y^{2}$ .

Um ponto projetivo $(X:Y:Z)$ corresponde ao ponto afim $(X/Z:Y/Z)$ na curva de Edwards.

O elemento de identidade é representado por $(0:1:1)$ . O inverso de $(X:Y:Z)$ é $(-X:Y:Z)$ .

A fórmula de adição em coordenadas homogêneas é dada por: $(X_{1}:Y_{1}:Z_{1})+(X_{2}:Y_{2}:Z_{2})=(X_{3}:Y_{3}:Z_{3})$

onde

$X_{3}=Z_{1}Z_{2}(X_{1}Y_{2}+X_{2}Y_{1})(Z_{1}^{2}Z_{2}^{2}-dX_{1}X_{2}Y_{1}Y_{2})$

$Y_{3}=Z_{1}Z_{2}(Y_{1}Y_{2}-X_{1}X_{2})(Z_{1}^{2}Z_{2}^{2}+dX_{1}X_{2}Y_{1}Y_{2})$

$Z_{3}=(Z_{1}^{2}Z_{2}^{2}-dX_{1}X_{2}Y_{1}Y_{2})(Z_{1}^{2}Z_{2}^{2}+dX_{1}X_{2}Y_{1}Y_{2})$

Algoritmo

A adição de dois pontos na curva de Edwards pode ser computada de forma mais eficiente na forma de Edwards estendida $(X:Y:Z:T)$ , onde $T=XY/Z$ :

$(X_{3}:Y_{3}:Z_{3}:T_{3})=(X_{1}:Y_{1}:Z_{1}:T_{1})+(X_{2}:Y_{2}:Z_{2}:T_{2})$

$A=X_{1}X_{2};B=Y_{1}Y_{2};C=dT_{1}T_{2};D=Z_{1}Z_{2};$

$E=(X_{1}+Y_{1})(X_{2}+Y_{2})-A-B;F=D-C;G=D+C;H=B-A;$

$X_{3}=E\cdot F;Y_{3}=G\cdot H;Z_{3}=F\cdot G;T_{3}=E\cdot H;$

Dobramento (Doubling)

O Dobramento pode ser realizado exatamente com a mesma fórmula da adição. O dobramento refere-se ao caso em que as entradas (x₁, y₁) e (x₂, y₂) são iguais.

Dobrando um ponto $P=(x,y)$ :

${\begin{aligned}(x,y)+(x,y)&=\left({\frac {2xy}{1+dx^{2}y^{2}}},{\frac {y^{2}-x^{2}}{1-dx^{2}y^{2}}}\right)\\[6pt]&=\left({\frac {2xy}{x^{2}+y^{2}}},{\frac {y^{2}-x^{2}}{2-x^{2}-y^{2}}}\right)\end{aligned}}$

Os denominadores foram simplificados com base na equação da curva $x^{2}+y^{2}=1+dx^{2}y^{2}$ . Uma aceleração adicional é alcançada computando $2xy$ como $(x+y)^{2}-x^{2}-y^{2}$ . Isso reduz o custo do dobramento em coordenadas homomórficas para 3M + 4S + 3C + 6a, enquanto a adição geral custa 10M + 1S + 1C + 1D + 7a. Aqui, M representa multiplicações de corpo, S quadrados de corpo, D o custo da multiplicação pelo parâmetro da curva d, e a a adição de corpo.

Exemplo de dobramento

Como no exemplo anterior para a lei de adição, considere a curva de Edwards com d=2:

$x^{2}+y^{2}=1+2x^{2}y^{2}$

e o ponto $P=(1,0)$ . As coordenadas do ponto $P_{2}=2P_{1}$ são:

$x_{2}={\frac {2xy}{x^{2}+y^{2}}}=0$

$y_{2}={\frac {y^{2}-x^{2}}{2-(x^{2}+y^{2})}}=-1$

O ponto obtido ao dobrar P é, portanto, $P_{2}=(0,-1)$ .

Adição mista

A adição mista é o caso em que Z₂ é conhecido como sendo 1. Nesse caso, A=Z₁^.Z₂ pode ser eliminado e o custo total reduz-se a 9M+1S+1C+1D+7a

Algoritmo

A= Z₁^.Z₂ // em outras palavras, A= Z₁

B= Z₁²

C=X₁.X₂

D=Y₁^.Y₂

E=d^.C^.D

F=B-E

G=B+E

X₃= A^.F((X_I+Y₁)^.(X₂+Y₂)-C-D)

Y₃= A^.G^.(D-C)

Z₃=C^.F^.G

Triplicação

A Triplicação pode ser feita primeiro dobrando o ponto e depois adicionando o resultado a si mesmo. Aplicando a equação da curva como no dobramento, obtemos

3(x_{1},y_{1})=\left({\frac {(x_{1}^{2}+y_{1}^{2})^{2}-(2y_{1})^{2}}{4(x_{1}^{2}-1)x_{1}^{2}-(x_{1}^{2}-y_{1}^{2})^{2}}}x_{1},{\frac {(x_{1}^{2}+y_{1}^{2})^{2}-(2x_{1})^{2}}{-4(y_{1}^{2}-1)y_{1}^{2}+(x_{1}^{2}-y_{1}^{2})^{2}}}y_{1}\right).\,

Existem dois conjuntos de fórmulas para esta operação em coordenadas Edwards padrão. O primeiro custa 9M + 4S, enquanto o segundo necessita de 7M + 7S. Se a razão S/M for muito pequena, especificamente abaixo de 2/3, então o segundo conjunto é melhor, enquanto para razões maiores o primeiro é preferível. Usando as fórmulas de adição e dobramento (como mencionado acima), o ponto (X₁ : Y₁ : Z₁) é computado simbolicamente como 3(X₁ : Y₁ : Z₁) e comparado com (X₃ : Y₃ : Z₃)

Exemplo de triplicação

Dada a curva de Edwards com d=2, e o ponto P₁=(1,0), o ponto 3P₁ tem coordenadas:

$x_{3}={\frac {(x_{1}^{2}+y_{1}^{2})^{2}-(2y_{1})^{2}}{4(x_{1}^{2}-1)x_{1}^{2}-(x_{1}^{2}-y_{1}^{2})^{2}}}x_{1}=-1$

$y_{3}={\frac {(x_{1}^{2}+y_{1}^{2})^{2}-2(x_{1})^{2}}{-4(y_{1}^{2}-1)y_{1}^{2}+(x_{1}^{2}-y_{1}^{2})^{2}}}y_{1}=0$

Assim, $3P 1 =(-1,0)=-P 1$ . Este resultado também pode ser encontrado considerando o exemplo de dobramento: 2P₁=(0,-1), logo 3P₁ = 2P₁ + P₁ = (0,-1) + (1,0) = (-1,0).

Algoritmo

A=X₁²

B=Y₁²

C=(2Z₁)²

D=A+B

E=D²

F=2D.(A-B)

G=E-B.C

H=E-A.C

I=F+H

J=F-G

X₃=G.J.X1

Y₃=H.I.Y1

Z₃=I.J.Z1

Esta fórmula custa 9M + 4S

Coordenadas de Edwards invertidas

Bernstein e Lange introduziram um sistema de coordenadas ainda mais rápido para curvas elípticas chamado coordenadas de Edwards invertidas no qual as coordenadas (X : Y : Z) satisfazem a curva (X² + Y²)Z² = (dZ⁴ + X²Y²) e correspondem ao ponto afim (Z/X, Z/Y) na curva de Edwards x² + y² = 1 + dx²y² com XYZ ≠ 0.

As coordenadas de Edwards invertidas, ao contrário das coordenadas de Edwards padrão, não possuem fórmulas de adição completas: alguns pontos, como o elemento neutro, devem ser tratados separadamente. Mas as fórmulas de adição ainda têm a vantagem de uma forte unificação: podem ser usadas sem alteração para dobrar um ponto.

Para mais informações sobre operações com estas coordenadas veja: http://hyperelliptic.org/EFD/g1p/auto-edwards-inverted.html

Coordenadas estendidas para curvas de Edwards

Existe outro sistema de coordenadas com o qual uma curva de Edwards pode ser representada. Estas novas coordenadas são chamadas de coordenadas estendidas e são ainda mais rápidas que as coordenadas invertidas. Para mais informações sobre o custo de tempo necessário nas operações com estas coordenadas, veja: http://hyperelliptic.org/EFD/g1p/auto-edwards.html

Ver também

Curva de Edwards torcida

Para mais informações sobre o tempo de execução necessário em um caso específico, veja Tabela de custos de operações em curvas elípticas.

Referências

↑ Bernstein, Daniel; Lange, Tanja (3 de março de 2014), How to design an elliptic-curve signature system
1 2 Daniel. J. Bernstein , Tanja Lange, pag. 3, Faster addition and doubling on elliptic curves
↑ Christophe Arene; Tanja Lange; Michael Naehrig; Christophe Ritzenthaler (2009). «Faster Computation of the Tate Pairing». Bibcode:2009arXiv0904.0854A. arXiv:0904.0854. Consultado em 28 de fevereiro de 2010
↑ Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson. Twisted Edwards curves revisited. In ASIACRYPT 2008, pages 326–343, 2008
↑ Bernstein et al., Optimizing Double-Base Elliptic curve single-scalar Multiplication
↑ Daniel J.Bernstein. Tanja Lange, pag.2, Inverted Edward coordinates
↑ H. Hisil, K. K. Wong, G. Carter, E. Dawson Faster group operations on elliptic curves

Bibliografia

Bernstein, Daniel; Lange, Tanja (2007), Faster Addition and Doubling on Elliptic curves (PDF)
Edwards, Harold M. (9 de abril de 2007), «A normal form for elliptic curves», Bulletin of the American Mathematical Society, ISSN 0002-9904, 44 (3): 393–422, doi:10.1090/s0273-0979-07-01153-6
Faster Group Operations on Elliptic curves, H. Hisil, K. K. Wong, G. Carter, E. Dawson
D.J.Bernstein, P.Birkner. T. Lange, C.Peters, Optimizing Double-Base Elliptic-Curve Single-Scalar Multiplication (PDF)
Washington, Lawrence C. (2008), Elliptic Curves: Number Theory and Cryptography, ISBN 978-1-4200-7146-7, Discrete Mathematics and its Applications 2nd ed. , Chapman & Hall/CRC
Bernstein, Daniel; Lange, Tanja, Inverted Edwards coordinates (PDF)

Ligações externas

[1] Bernstein, Daniel; Lange, Tanja (3 de março de 2014), How to design an elliptic-curve signature system

[BernsteinLange-2] 1 2 Daniel. J. Bernstein , Tanja Lange, pag. 3, Faster addition and doubling on elliptic curves

[3] Christophe Arene; Tanja Lange; Michael Naehrig; Christophe Ritzenthaler (2009). «Faster Computation of the Tate Pairing». Bibcode:2009arXiv0904.0854A. arXiv:0904.0854. Consultado em 28 de fevereiro de 2010

[Twisted_Edwards_curves_revisited-4] Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson. Twisted Edwards curves revisited. In ASIACRYPT 2008, pages 326–343, 2008

[5] Bernstein et al., Optimizing Double-Base Elliptic curve single-scalar Multiplication

[6] Daniel J.Bernstein. Tanja Lange, pag.2, Inverted Edward coordinates

[7] H. Hisil, K. K. Wong, G. Carter, E. Dawson Faster group operations on elliptic curves