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.

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. A implementação de referência é um software de domínio público.

Resumo

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.

Um esquema de assinatura EdDSA baseia-se na escolha:

• 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, de modo que ${\displaystyle \ell }$ deve ser grande o suficiente para que isso seja inviável, sendo tipicamente escolhido para exceder 2²⁰⁰. 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

Ed25519 é o esquema de assinatura EdDSA que usa a função hash SHA-512 e uma curva elíptica relacionada à Curve25519 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, e é birracionalmente equivalente à Curva de Montgomery conhecida como Curve25519. A equivalência é: $${\displaystyle x={\frac {u}{v}}{\sqrt {-486664}},\quad y={\frac {u-1}{u+1}}.}$$

Ed448

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.

Referências

Ligações externas

• Página inicial do Ed25519