ECDSA

Em criptografia, o Elliptic Curve Digital Signature Algorithm (ECDSA, em português Algoritmo de Assinatura Digital de Curvas Elípticas) oferece uma variante do Digital Signature Algorithm (DSA), que usa criptografia de curva elíptica.

Comparação do tamanho de chave e assinatura com o DSA

Tal como ocorre com a criptografia de curva elíptica em geral, o tamanho em bits da chave pública que se acredita ser necessário para o ECDSA é cerca de duas vezes o tamanho do nível de segurança, em bits. Por exemplo, em um nível de segurança de 80 bits (o que significa que um invasor precisaria de no máximo cerca de $2^{80}$ operações para encontrar a chave privada) o tamanho da chave pública de um algoritmo ECDSA deverá ser de 160 bits, enquanto que o tamanho de uma chave pública para o DSA é de pelo menos 1024 bits. Por outro lado, o tamanho da assinatura é o mesmo para o DSA e o ECDSA: aproximadamente $4t$ bits, onde $t$ é o nível de segurança medido em bits, isto é, cerca de 320 bits para um nível de segurança de 80 bits.

Algoritmo de geração de assinaturas

Suponha que Alice deseje enviar uma mensagem assinada para o Bob. Inicialmente, eles devem concordar com os parâmetros $({\textrm {CURVE}},G,n)$ da curva. Além do corpo e da equação da curva, é preciso $G$, um ponto de base de primeira ordem sobre a curva; $n$ é a ordem multiplicativa do ponto $G$.

Parâmetro
CURVA	o corpo e a equação usados na curva elíptica
G	ponto base da curva elíptica, tal como um ponto $(x_{0},y_{0})$ sobre $y^{2}=x^{3}+7$, um gerador da curva elíptica com grande ordem prima n
n	ordem inteira de G, significa que $n\times G=O$, em que $O$ é o elemento identidade.

A ordem $n$ do ponto base $G$ deve ser prima. De fato, supõe-se que cada elemento diferente de zero do anel $\mathbb {Z} /n\mathbb {Z}$ são invertíveis, de modo que $\mathbb {Z} /n\mathbb {Z}$ deve ser um corpo. Isso implica que $n$ deve ser primo (ver identidade de Bézout).

Alice cria um par de chaves, consistindo de uma chave privada $d_{A}$, que é um inteiro selecionado aleatoriamente no intervalo $[1,n-1]$; e uma chave pública, um ponto da curva $Q_{A}=d_{A}\times G$. Utiliza-se $\times$ para denotar a multiplicação de um ponto da curva elíptica por um escalar.

Para Alice assinar uma mensagem $m$, ela deve seguir os seguintes passos:

1. Calcular $e={\textrm {HASH}}(m)$. (Aqui HASH é uma função de hash criptográfica, como SHA-2, com a saída convertida para um inteiro.)
2. Considerar $z$ como sendo os $L_{n}$ bits mais à esquerda de $e$, em que $L_{n}$ é o comprimento de bit da ordem do grupo $n$. (Note que $z$ pode ser maior do que $n$ mas não mais longo.)
3. Escolher um inteiro aleatório criptograficamente seguro $k$em $[1,n-1]$.
4. Calcular o ponto da curva $(x_{1},y_{1})=k\times G$.
5. Calcular $r=x_{1}\,{\bmod {\,}}n$. Se $r=0$, voltar para o passo 3.
6. Calcular $s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n$. Se $s=0$, voltar para o passo 3.
7. A assinatura é o par $(r,s)$. (E $(r,-s\,{\bmod {\,}}n)$ também é uma assinatura válida.)

Como é observado no padrão, é preciso não apenas que $k$ seja secreto, mas também que sejam escolhidos valores de $k$diferentes para assinaturas diferentes, caso contrário, a equação da etapa 6 pode ser resolvido para $d_{A}$, a chave privada: Dadas duas assinaturas $(r,s)$ e $(r,s')$empregando a mesmo mesmo $k$ desconhecido para diferentes mensagens conhecidas $m$ e $m'$, um invasor pode calcular $z$ e $z'$, e como $s-s'=k^{-1}(z-z')$ (todas as operações neste parágrafo são feitas módulo $n$) o atacante pode encontrar $k={\frac {z-z'}{s-s'}}$. Como $s=k^{-1}(z+rd_{A})$, o invasor pode agora calcular a chave privada $d_{A}={\frac {sk-z}{r}}$. Esta falha na implementação foi utilizada, por exemplo, para extrair a chave de assinatura utilizada para o console de jogos PlayStation 3. Outra forma como a assinatura ECDSA pode vazar as chaves privadas é quando $k$ é gerado por um gerador de números aleatórios defeituoso. Uma falha como esta na geração de um número aleatório fez com que usuários de carteiras de Bitcoin para Android perdessem seus fundos em agosto de 2013. Para garantir que $k$ é único para cada mensagem, pode-se ignorar completamente a geração de números aleatórios e gerar assinaturas deterministicas derivando $k$ tanto da mensagem quanto da chave privada.

Algoritmo de verificação de assinatura

Para Bob autenticar a assinatura de Alice, ele deve ter uma cópia de sua chave pública de ponto da curva $Q_{A}$. Bob pode verificar que $Q_{A}$ é um ponto válido da curva da seguinte forma:

1. Verificar que $Q_{A}$ não é igual ao elemento identidade $O$, e suas coordenadas são, de outra forma válida
2. Verificar que $Q_{A}$ está sobre a curva
3. Verificar que $n\times Q_{A}=O$

Depois, Bob segue estes passos:

1. Verificar que $r$ e $s$ são números inteiros em $[1,n-1]$. Se não, a assinatura é inválida.
2. Calcular $e={\textrm {HASH}}(m)$, em que HASH é a mesma função utilizada na geração da assinatura.
3. Considerar $z$ como os $L_{n}$ bits mais à esquerda de $e$.
4. Calcular $w=s^{-1}\,{\bmod {\,}}n$.
5. Calcular $u_{1}=zw\,{\bmod {\,}}n$ e $u_{2}=rw\,{\bmod {\,}}n$.
6. Calcular o ponto da curva $(x_{1},y_{1})=u_{1}\times G+u_{2}\times Q_{A}$. Se $(x_{1},y_{1})=O$ então, a assinatura é inválida.
7. A assinatura é válida se $r\equiv x_{1}{\pmod {n}}$, e inválida caso contrário.

Note que utilizando o truque de Shamir, uma soma de duas multiplicações escalares $u_{1}\times G+u_{2}\times Q_{A}$ pode ser calculada mais rapidamente do que duas multiplicações escalares feitas de forma independente.

Corretude do algoritmo

Não é imediatamente óbvio o porquê de a verificação sequer funcionar corretamente. Para ver porquê, indique por $C$ o ponto da curva calculado no passo 6 da verificação,

$C=u_{1}\times G+u_{2}\times Q_{A}$

A partir da definição da chave pública como $Q_{A}=d_{A}\times G$,

$C=u_{1}\times G+u_{2}d_{A}\times G$

Como a multiplicação por escalar em curva elíptica é distributiva em relação à adição,

$C=(u_{1}+u_{2}d_{A})\times G$

Expandindo as definições de $u_{1}$ e $u_{2}$ a partir da etapa de verificação 5,

$C=(zs^{-1}+rd_{A}s^{-1})\times G$

Colocando o termo comum $s^{-1}$em evidência,

$C=(z+rd_{A})s^{-1}\times G$

Expandindo a definição de $s$ a partir do passo 6 da assinatura,

$C=(z+rd_{A})(z+rd_{A})^{-1}(k^{-1})^{-1}\times G$

Como o inverso de um inverso é o elemento original e o produto de um elemento inverso e o elemento é a identidade, resulta que

$C=k\times G$

A partir da definição de $r$, este é o passo de verificação 7.

Isso só mostra que uma mensagem assinada corretamente será verificad corretamente; muitas outras propriedades [quais?] são necessárias para um algoritmo de assinatura seguro.

Segurança

Em dezembro de 2010, um grupo autodenominado fail0verflow anunciou a recuperação da chave privada do ECDSA usada pela Sony para assinar software para o console de jogos PlayStation 3. No entanto, esse ataque só funcionou porque a Sony não implementou corretamente o algoritmo, porque $k$ era estático em vez de aleatório. Como apontado anteriormente, na seção sobre o algoritmo de geração de assinatura, isso torna $d_{A}$ solucionável, e o algoritmo completamente inútil.

Em 29 de Março de 2011, dois pesquisadores publicaram um artigo IACR, demonstrando que é possível obter uma chave privada TLS de um servidor utilizando OpenSSL que autentica com DSA de Curvas Elípticas sobre um corpo binário através de um ataque de temporização. A vulnerabilidade foi corrigida no OpenSSL 1.0.0e.

Em agosto de 2013, foi revelado que os erros em algumas implementações da classe Java SecureRandom, por vezes, gerava colisões entre os valores de $k$. Isso permitiu que hackers recuperassem chaves privadas, dando-lhes o mesmo controle sobre transações de bitcoin que os proprietários legítimos das chaves tinham, usando a mesma falha que foi usada para revelar a chave de assinatura do PS3 em algumas implementações em aplicativos para Android, que usam Java e dependem de ECDSA para autenticar transações.

Este problema pode ser evitado por meio da geração determinística de $k$, como descrito pela RFC 6979.

Preocupações

Existem dois tipos de preocupações com ECDSA:

1. Preocupações políticas: a confiabilidade das curvas produzidas pelo NIST sendo questionada após serem feitas revelações de que a NSA voluntariamente insere backdoors em software, componentes de hardware e padrões publicados; criptógrafos bem conhecidos expressaram dúvidas sobre como as curvas do NIST foram concebidas, e o estrago voluntário já foi provado no passado.
2. Preocupações de ordem técnica: a dificuldade de implementar corretamente o padrão, sua lentidão e falhas de projeto reduzem a segurança em implementações insuficientemente defensivas do gerador de número aleatório Dual EC DRBG .

Ambas as preocupações são resumidas na introdução do libssh curve25519.

Implementações

Abaixo, está uma lista de bibliotecas de criptografia que fornecem suporte para o algoritmo ECDSA:

• Botan
• Bouncy Castle
• cryptlib
• Crypto++
• libgcrypt
• OpenSSL
• wolfCrypt
• mbed TLS

Leitura complementar

• Accredited Standards Committee X9, American National Standard X9.62-2005, Criptografia de Chave Pública para a Indústria de Serviços Financeiros, O Elliptic Curve Digital Signature Algorithm (algoritmo ECDSA), 16 de novembro de 2005.
• Certicom de Pesquisa, Padrões eficientes de criptografia, SEC 1: Criptografia de Curva Elíptica, Versão 2.0, de 21 de Maio de 2009.
• López, J. e Dahab, R. Uma Visão geral da Criptografia de Curva Elíptica, Relatório Técnico IC-00-10 Universidade Estadual de Campinas, Campinas, 2000.
• Daniel J. Bernstein, Pippenger do algoritmo de exponenciação, 2002.
• Daniel R. L. Brown, Grupos Genéricos, Colisão de Resistência, e ECDSA, Designs, Códigos e Criptografia, 35, 119-152, 2005. ePrint versão
• Ian F. Blake, Gadiel Seroussi, e Nigel Inteligente, os editores, os Avanços na Criptografia de Curva Elíptica, London Mathematical Society Palestra de Série Nota 317, Cambridge University Press, 2005.
• Hankerson, D.; Vanstone, S.; Menezes, A. Guide to Elliptic Curve Cryptography. Col: Springer Professional Computing. [S.l.: s.n.] ISBN 0-387-95273-X. doi:10.1007/b97644 

Ligações externas

• Padrão de Assinatura Digital; inclui informações sobre ECDSA
• Elliptic Curve Digital Signature Algorithm (algoritmo ECDSA); fornece um guia detalhado no algoritmo ECDSA. Wayback link