EdDSA

 Nota: Não confundir com ECDSA.

Na criptografia de chave pública, o Edwards-curve Digital Signature Algorithm (EdDSA - Algoritmo de Assinatura Digital de Curva de Edwards) é um esquema de assinatura digital que utiliza uma variante da assinatura de Schnorr baseada em curvas de Edwards torcidas.^[1]

Foi projetado para ser mais rápido do que os esquemas de assinatura digital existentes sem sacrificar a segurança. Foi desenvolvido por uma equipa que inclui Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe e Bo-Yin Yang.^[2] A implementação de referência é um software de domínio público.^[3]

A seguir apresenta-se uma descrição simplificada do EdDSA, ignorando os detalhes da codificação de inteiros e pontos da curva como cadeias de bits; todos os detalhes completos encontram-se nos artigos originais e no RFC.^[4][2][1]

Um esquema de assinatura EdDSA baseia-se na escolha:^[4][2][1]

• do corpo finito ${\displaystyle \mathbb {F} _{q}}$ sobre a potência de um número primo ímpar ${\displaystyle q}$;
• da curva elíptica ${\displaystyle E}$ sobre ${\displaystyle \mathbb {F} _{q}}$ cujo grupo ${\displaystyle E(\mathbb {F} _{q})}$ de pontos racionais sobre ${\displaystyle \mathbb {F} _{q}}$ tem ordem ${\displaystyle \#E(\mathbb {F} _{q})=2^{c}\ell }$, onde ${\displaystyle \ell }$ é um número primo grande e ${\displaystyle 2^{c}}$ é chamado de cofator;
• do ponto base ${\displaystyle B\in E(\mathbb {F} _{q})}$ com ordem ${\displaystyle \ell }$; e
• da função hash criptográfica ${\displaystyle H}$ com saídas de ${\displaystyle 2b}$ bits, onde ${\displaystyle 2^{b-1}>q}$ de modo que os elementos de ${\displaystyle \mathbb {F} _{q}}$ e os pontos da curva em ${\displaystyle E(\mathbb {F} _{q})}$ possam ser representados por cadeias de ${\displaystyle b}$ bits.

Estes parâmetros são comuns a todos os utilizadores do esquema de assinatura EdDSA. A segurança do esquema de assinatura EdDSA depende criticamente da escolha dos parâmetros, exceto pela escolha arbitrária do ponto base — por exemplo, espera-se que o algoritmo rho de Pollard para logaritmos exija aproximadamente ${\displaystyle {\sqrt {\ell \pi /4}}}$ adições de curva antes de conseguir calcular um logaritmo discreto,^[5] de modo que ${\displaystyle \ell }$ deve ser grande o suficiente para que isso seja inviável, sendo tipicamente escolhido para exceder 2²⁰⁰.^[6] A escolha de ${\displaystyle \ell }$ é limitada pela escolha de ${\displaystyle q}$, uma vez que, pelo teorema de Hasse, ${\displaystyle \#E(\mathbb {F} _{q})=2^{c}\ell }$ não pode diferir de ${\displaystyle q+1}$ por mais de ${\displaystyle 2{\sqrt {q}}}$. A função hash ${\displaystyle H}$ é normalmente modelada como um oráculo aleatório nas análises formais de segurança do EdDSA.

Dentro de um esquema de assinatura EdDSA:

Chave pública

Uma chave pública EdDSA é um ponto da curva ${\displaystyle A\in E(\mathbb {F} _{q})}$, codificado em ${\displaystyle b}$ bits.

Verificação da assinatura

Uma assinatura EdDSA para uma mensagem ${\displaystyle M}$ usando a chave pública ${\displaystyle A}$ é o par ${\displaystyle (R,S)}$, codificado em ${\displaystyle 2b}$ bits, de um ponto da curva ${\displaystyle R\in E(\mathbb {F} _{q})}$ e um número inteiro ${\displaystyle 0<S<\ell }$ que satisfaz a seguinte equação de verificação, onde ${\displaystyle \parallel }$ denota a concatenação:

$${\displaystyle 2^{c}SB=2^{c}R+2^{c}H(R\parallel A\parallel M)A.}$$

Chave privada

Uma chave privada EdDSA é uma cadeia de ${\displaystyle b}$ bits ${\displaystyle k}$ que deve ser escolhida uniformemente de forma aleatória. A chave pública correspondente é ${\displaystyle A=sB}$, onde ${\displaystyle s=H_{0,\dots ,b-1}(k)}$ corresponde aos ${\displaystyle b}$ bits menos significativos de ${\displaystyle H(k)}$ interpretados como um número inteiro em formato little-endian.

Assinatura

A assinatura de uma mensagem ${\displaystyle M}$ é computada deterministicamente como ${\displaystyle (R,S),}$ onde ${\displaystyle R=rB}$ para ${\displaystyle r=H(H_{b,\dots ,2b-1}(k)\parallel M)}$, e

$${\displaystyle S\equiv r+H(R\parallel A\parallel M)s{\pmod {\ell }}.}$$ Isto satisfaz a equação de verificação: $${\displaystyle {\begin{aligned}2^{c}SB&=2^{c}(r+H(R\parallel A\parallel M)s)B\\&=2^{c}rB+2^{c}H(R\parallel A\parallel M)sB\\&=2^{c}R+2^{c}H(R\parallel A\parallel M)A.\end{aligned}}}$$

Ed25519 é o esquema de assinatura EdDSA que usa a função hash SHA-512 e uma curva elíptica relacionada à Curve25519^[2] onde:

• ${\displaystyle q=2^{255}-19,}$
• ${\displaystyle E/\mathbb {F} _{q}}$ é a curva de Edwards torcida

$${\displaystyle -x^{2}+y^{2}=1-{\frac {121665}{121666}}x^{2}y^{2},}$$

• ${\displaystyle \ell =2^{252}+27742317777372353535851937790883648493}$ e ${\displaystyle c=3}$
• ${\displaystyle B}$ é o ponto único em ${\displaystyle E(\mathbb {F} _{q})}$ cuja coordenada ${\displaystyle y}$ é ${\displaystyle 4/5}$ e cuja coordenada ${\displaystyle x}$ é positiva. "Positivo" é definido em termos de codificação de bits:
  • coordenadas "positivas" são coordenadas pares (o bit menos significativo está zerado)
  • coordenadas "negativas" são coordenadas ímpares (o bit menos significativo está ativado)
• ${\displaystyle H}$ é o SHA-512, com ${\displaystyle b=256}$.

A curva de Edwards torcida ${\displaystyle E/\mathbb {F} _{q}}$ é conhecida como edwards25519,^[7][1] e é birracionalmente equivalente à Curva de Montgomery conhecida como Curve25519. A equivalência é:^[2][7][8] $${\displaystyle x={\frac {u}{v}}{\sqrt {-486664}},\quad y={\frac {u-1}{u+1}}.}$$

Ed448 é o esquema de assinatura EdDSA definido na RFC 8032 usando a função hash SHAKE256 e a curva elíptica edwards448, uma curva de Edwards (não torcida) relacionada à Curve448 definida na RFC 7748. O Ed448 também foi aprovado na versão final do padrão FIPS 186-5.^[15]

• Página inicial do Ed25519