EdDSA
Geral
Projetistas	Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, Bo-Yin Yang, et al.
Primeira publicação	26 de setembro de 2011
Detalhe
Estrutura	Criptografia de curva elíptica

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}}.}$$

A equipa original otimizou o Ed25519 para a família de processadores x86-64 Nehalem/Westmere. A verificação pode ser executada em lotes (batches) de 64 assinaturas para um rendimento ainda maior. O Ed25519 destina-se a fornecer uma resistência a ataques comparável a cifras simétricas de qualidade de 128 bits.^[9]

As chaves públicas têm 256 bits de comprimento e as assinaturas têm 512 bits de comprimento.^[10]

O Ed25519 foi projetado para evitar implementações que usem condições de ramificação (branch) ou índices de arrays que dependam de dados secretos,^[2][1] a fim de mitigar ataques de canal lateral.

Assim como ocorre em outros esquemas de assinatura baseados em logaritmo discreto, o EdDSA utiliza um valor secreto chamado nonce, que é único para cada assinatura. Nos esquemas de assinatura DSA e ECDSA, este nonce é tradicionalmente gerado de forma aleatória para cada assinatura — e se o gerador de números aleatórios for quebrado ou se tornar previsível ao fazer uma assinatura, a assinatura pode vazar a chave privada, como aconteceu com a chave de assinatura da atualização de firmware do Sony PlayStation 3.^{[11][12][13][14]}

Em contrapartida, o EdDSA escolhe o nonce de forma determinística como o hash de uma parte da chave privada e da mensagem. Assim, uma vez gerada uma chave privada, o EdDSA não necessita mais de um gerador de números aleatórios para criar assinaturas, e não existe o perigo de que um gerador de números aleatórios corrompido revele a chave privada.^[2]

De notar que existem dois esforços de padronização para o EdDSA: um da IETF, a RFC 8032 (informativa), e um do NIST como parte do FIPS 186-5.^[15] As diferenças entre os padrões foram analisadas,^[16][17] e encontram-se disponíveis vetores de teste.^[18]

Usos notáveis do Ed25519 incluem o OpenSSH,^[19] o GnuPG^[20] e várias alternativas, além da ferramenta signify do OpenBSD.^[21] O uso do Ed25519 (e Ed448) no protocolo SSH foi padronizado.^[22] Em 2023, a versão final do padrão FIPS 186-5 incluiu o Ed25519 determinístico como um esquema de assinatura aprovado.^[15]

• Apple Watch e iPhone usam chaves Ed25519 para autenticação mútua IKEv2^[23]
• Botan
• Crypto++
• Protocolo da criptomoeda CryptoNote
• Dropbear SSH^[24]
• Implementação do EdDSA pelo I2Pd^[25]
• Java Development Kit 15
• Libgcrypt
• Minisign^[26] e Minisign Miscellanea para o macOS
• NaCl / libsodium^[27]
• OpenSSL 1.1.1^[28]
• Python - Uma implementação alternativa lenta porém concisa,^[29] não inclui proteção contra ataques de canal lateral^[30]
• Implementação de referência Supercop^[31] (Linguagem C com código assembly em linha)
• Virgil PKI utiliza chaves Ed25519 por padrão^[32]
• wolfSSL^[33]

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