ECDSA

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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

Ver também[editar | editar código-fonte]

  • EdDSA

Referências[editar | editar código-fonte]

  1. NIST FIPS 186-4, de julho de 2013, pp. 19 e 26
  2. Console de Hacking 2010 - PS3 Epic Fail, página 123-128
  3. «Android Security Vulnerability» 
  4. «RFC 6979 - Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)» 
  5. «The Double-Base Number System in Elliptic Curve Cryptography» (PDF) 
  6. «Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access» 
  7. «Cryptology ePrint Archive: Report 2011/232» 
  8. «Vulnerability Note VU#536044 - OpenSSL leaks ECDSA private key through a remote timing attack». www.kb.cert.org 
  9. «ChangeLog» 
  10. «Android bug batters Bitcoin wallets» 
  11. «The NSA Is Breaking Most Encryption on the Internet». Schneier on Security 
  12. «SafeCurves: choosing safe curves for elliptic-curve cryptography» 
  13. «Security dangers of the NIST curves» (PDF) 
  14. «The Strange Story of Dual_EC_DRBG». Schneier on Security 
  15. «NSA Efforts to Evade Encryption Technology Damaged U.S. Cryptography Standard» 
  16. «How to design an elliptic-curve signature system». The cr.yp.to blog 
  17. «New key type (ed25519) and private key format» 
  18. «curve25519-sha256@libssh.org.txt\doc - projects/libssh.git». libssh shared repository 

Leitura complementar[editar | editar código-fonte]

  • 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 | editar código-fonte]