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

editar

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   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   bits, onde   é 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

editar

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

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   sobre  , um gerador da curva elíptica com grande ordem prima n
n ordem inteira de G, significa que  , em que   é o elemento identidade.

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

Alice cria um par de chaves, consistindo de uma chave privada  , que é um inteiro selecionado aleatoriamente no intervalo  ; e uma chave pública, um ponto da curva  . Utiliza-se   para denotar a multiplicação de um ponto da curva elíptica por um escalar.

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

  1. Calcular  . (Aqui HASH é uma função de hash criptográfica, como SHA-2, com a saída convertida para um inteiro.)
  2. Considerar   como sendo os   bits mais à esquerda de  , em que   é o comprimento de bit da ordem do grupo  . (Note que   pode ser maior do que   mas não mais longo.[1])
  3. Escolher um inteiro aleatório criptograficamente seguro  em  .
  4. Calcular o ponto da curva  .
  5. Calcular  . Se  , voltar para o passo 3.
  6. Calcular  . Se  , voltar para o passo 3.
  7. A assinatura é o par  . (E   também é uma assinatura válida.)

Como é observado no padrão, é preciso não apenas que   seja secreto, mas também que sejam escolhidos valores de  diferentes para assinaturas diferentes, caso contrário, a equação da etapa 6 pode ser resolvido para  , a chave privada: Dadas duas assinaturas   e  empregando a mesmo mesmo   desconhecido para diferentes mensagens conhecidas   e  , um invasor pode calcular   e  , e como   (todas as operações neste parágrafo são feitas módulo  ) o atacante pode encontrar  . Como  , o invasor pode agora calcular a chave privada  . Esta falha na implementação foi utilizada, por exemplo, para extrair a chave de assinatura utilizada para o console de jogos PlayStation 3.[2] Outra forma como a assinatura ECDSA pode vazar as chaves privadas é quando   é 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.[3] Para garantir que   é único para cada mensagem, pode-se ignorar completamente a geração de números aleatórios e gerar assinaturas deterministicas derivando   tanto da mensagem quanto da chave privada.[4]

Algoritmo de verificação de assinatura

editar

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

  1. Verificar que   não é igual ao elemento identidade  , e suas coordenadas são, de outra forma válida
  2. Verificar que   está sobre a curva
  3. Verificar que  

Depois, Bob segue estes passos:

  1. Verificar que   e   são números inteiros em  . Se não, a assinatura é inválida.
  2. Calcular  , em que HASH é a mesma função utilizada na geração da assinatura.
  3. Considerar   como os   bits mais à esquerda de  .
  4. Calcular  .
  5. Calcular   e  .
  6. Calcular o ponto da curva  . Se   então, a assinatura é inválida.
  7. A assinatura é válida se  , e inválida caso contrário.

Note que utilizando o truque de Shamir, uma soma de duas multiplicações escalares   pode ser calculada mais rapidamente do que duas multiplicações escalares feitas de forma independente.[5]

Corretude do algoritmo

editar

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

 

A partir da definição da chave pública como  ,

 

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

 

Expandindo as definições de   e   a partir da etapa de verificação 5,

 

Colocando o termo comum  em evidência,

 

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

 

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

 

A partir da definição de  , 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

editar

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   era estático em vez de aleatório. Como apontado anteriormente, na seção sobre o algoritmo de geração de assinatura, isso torna   solucionável, e o algoritmo completamente inútil.[6]

Em 29 de Março de 2011, dois pesquisadores publicaram um artigo IACR,[7] 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.[8] A vulnerabilidade foi corrigida no OpenSSL 1.0.0e.[9]

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  . 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.[10]

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

Preocupações

editar

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[11] expressaram[12][13] dúvidas sobre como as curvas do NIST foram concebidas, e o estrago voluntário já foi provado no passado.[14][15]
  2. Preocupações de ordem técnica: a dificuldade de implementar corretamente o padrão,[16] 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 .[17]

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

Implementações

editar

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

Referências

Leitura complementar

editar
  • 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

editar