EdDSA

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 F q {\displaystyle \mathbb {F} _{q}} sobre a potência de um número primo ímpar q {\displaystyle q} ;
• da curva elíptica E {\displaystyle E} sobre F q {\displaystyle \mathbb {F} _{q}} cujo grupo E ( F q ) {\displaystyle E(\mathbb {F} _{q})} de pontos racionais sobre F q {\displaystyle \mathbb {F} _{q}} tem ordem # E ( F q ) = 2 c ℓ {\displaystyle \#E(\mathbb {F} _{q})=2^{c}\ell } , onde ℓ {\displaystyle \ell } é um número primo grande e 2 c {\displaystyle 2^{c}} é chamado de cofator;
• do ponto base B ∈ E ( F q ) {\displaystyle B\in E(\mathbb {F} _{q})} com ordem ℓ {\displaystyle \ell } ; e
• da função hash criptográfica H {\displaystyle H} com saídas de 2 b {\displaystyle 2b} bits, onde 2 b − 1 > q {\displaystyle 2^{b-1}>q} de modo que os elementos de F q {\displaystyle \mathbb {F} _{q}} e os pontos da curva em E ( F q ) {\displaystyle E(\mathbb {F} _{q})} possam ser representados por cadeias de b {\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 ℓ π / 4 {\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 q {\displaystyle q} , uma vez que, pelo teorema de Hasse, # E ( F q ) = 2 c ℓ {\displaystyle \#E(\mathbb {F} _{q})=2^{c}\ell } não pode diferir de q + 1 {\displaystyle q+1} por mais de 2 q {\displaystyle 2{\sqrt {q}}} . A função hash H {\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 A ∈ E ( F q ) {\displaystyle A\in E(\mathbb {F} _{q})} , codificado em b {\displaystyle b} bits.

Verificação da assinatura

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

2 c S B = 2 c R + 2 c H ( R ∥ A ∥ M ) A . {\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 b {\displaystyle b} bits k {\displaystyle k} que deve ser escolhida uniformemente de forma aleatória. A chave pública correspondente é A = s B {\displaystyle A=sB} , onde s = H 0 , … , b − 1 ( k ) {\displaystyle s=H_{0,\dots ,b-1}(k)} corresponde aos b {\displaystyle b} bits menos significativos de H ( k ) {\displaystyle H(k)} interpretados como um número inteiro em formato little-endian.

Assinatura

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

S ≡ r + H ( R ∥ A ∥ M ) s ( mod ℓ ) . {\displaystyle S\equiv r+H(R\parallel A\parallel M)s{\pmod {\ell }}.} Isto satisfaz a equação de verificação: 2 c S B = 2 c ( r + H ( R ∥ A ∥ M ) s ) B = 2 c r B + 2 c H ( R ∥ A ∥ M ) s B = 2 c R + 2 c H ( R ∥ A ∥ M ) A . {\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:

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

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

• ℓ = 2 252 + 27742317777372353535851937790883648493 {\displaystyle \ell =2^{252}+27742317777372353535851937790883648493} e c = 3 {\displaystyle c=3}
• B {\displaystyle B} é o ponto único em E ( F q ) {\displaystyle E(\mathbb {F} _{q})} cuja coordenada y {\displaystyle y} é 4 / 5 {\displaystyle 4/5} e cuja coordenada x {\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)
• H {\displaystyle H} é o SHA-512, com b = 256 {\displaystyle b=256} .

A curva de Edwards torcida E / F q {\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] x = u v − 486664 , y = u − 1 u + 1 . {\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