Algoritmo de assinatura digital de curva elíptica - Elliptic Curve Digital Signature Algorithm
Na criptografia , o Algoritmo de Assinatura Digital de Curva Elíptica ( ECDSA ) oferece uma variante do Algoritmo de Assinatura Digital (DSA) que usa criptografia de curva elíptica .
Tamanho da chave e assinatura
Tal como acontece com a criptografia de curva elíptica em geral, o tamanho do bit da chave pública que se acredita ser necessária para 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 requer no máximo cerca de operações para encontrar a chave privada - o tamanho de uma chave privada ECDSA seria de 160 bits, enquanto o tamanho de uma chave privada DSA é de pelo menos 1024 bits. Por outro lado, o tamanho da assinatura é o mesmo para DSA e ECDSA: aproximadamente bits, onde é o nível de segurança medido em bits, ou seja, cerca de 320 bits para um nível de segurança de 80 bits.
Algoritmo de geração de assinatura
Suponha que Alice queira enviar uma mensagem assinada para Bob . Inicialmente, eles devem concordar com os parâmetros da curva . Além do campo e da equação da curva, precisamos de um ponto base de ordem primária na curva; é a ordem multiplicativa do ponto .
Parâmetro | |
---|---|
CURVA | o campo da curva elíptica e a equação usada |
G | ponto de base da curva elíptica, um ponto na curva que gera um subgrupo de grande ordem principal n |
n | ordem inteira de G , significa que , onde está o elemento de identidade. |
a chave privada (selecionada aleatoriamente) | |
a chave pública (calculada pela curva elíptica) | |
m | a mensagem para enviar |
A ordem do ponto base deve ser primo . Na verdade, assumimos que todo elemento diferente de zero do anel é invertível, de modo que deve ser um campo. Isso implica que deve ser primo (cf. a identidade de Bézout ).
Alice cria um par de chaves, consistindo em um inteiro de chave privada , selecionado aleatoriamente no intervalo ; e um ponto de curva de chave pública . Usamos para denotar a multiplicação do ponto da curva elíptica por um escalar .
Para que Alice assine uma mensagem , ela segue estas etapas:
- Calcule . (Aqui, HASH é uma função hash criptográfica , como SHA-2 , com a saída convertida em um número inteiro.)
- Let Ser os bits mais à esquerda de , onde é o comprimento do bit da ordem do grupo . (Note-se que pode ser maior do que , mas não mais .)
- Selecione um inteiro aleatório criptograficamente seguro de .
- Calcule o ponto da curva .
- Calcule . Se , volte para a etapa 3.
- Calcule . Se , volte para a etapa 3.
- A assinatura é o par . (E também é uma assinatura válida.)
Como observa o padrão, não só é necessário ser secreto, mas também é crucial selecionar diferentes para assinaturas diferentes, caso contrário, a equação na etapa 6 pode ser resolvida para a chave privada: dadas duas assinaturas e , empregando a mesma desconhecido para diferentes mensagens conhecidas e , um invasor pode calcular e , e desde (todas as operações neste parágrafo são feitas módulo ) o invasor pode encontrar . Desde então , o invasor agora pode calcular a chave privada .
Essa falha de implementação foi usada, por exemplo, para extrair a chave de assinatura usada para o console de jogos PlayStation 3 .
Outra maneira pela qual a assinatura ECDSA pode vazar chaves privadas é quando é gerada por um gerador de números aleatórios com defeito . Essa falha na geração de números aleatórios fez com que os usuários do Android Bitcoin Wallet perdessem seus fundos em agosto de 2013.
Para garantir que seja único para cada mensagem, pode-se ignorar a geração de números aleatórios completamente e gerar assinaturas determinísticas derivando da mensagem e da chave privada.
Algoritmo de verificação de assinatura
Para que Bob autentique a assinatura de Alice, ele deve ter uma cópia de seu ponto de curva de chave pública . Bob pode verificar se é um ponto de curva válido da seguinte maneira:
- Verifique se não é igual ao elemento de identidade O , e se suas coordenadas são válidas
- Verifique se está na curva
- Verifique isso
Depois disso, Bob segue estas etapas:
- Verifique se r e s são inteiros em . Caso contrário, a assinatura é inválida.
- Calcule , onde HASH é a mesma função usada na geração da assinatura.
- Sejam z os bits mais à esquerda de e .
- Calcule e .
- Calcule o ponto da curva . Nesse caso , a assinatura é inválida.
- A assinatura é válida se , inválida caso contrário.
Observe que uma implementação eficiente calcularia o inverso apenas uma vez. Além disso, usando o truque de Shamir, uma soma de duas multiplicações escalares pode ser calculada mais rápido do que duas multiplicações escalares feitas independentemente.
Exatidão do algoritmo
Não é imediatamente óbvio por que a verificação funciona corretamente. Para ver o porquê, denote como C o ponto da curva calculado na etapa 5 de verificação,
A partir da definição da chave pública como ,
Como a multiplicação escalar da curva elíptica distribui sobre a adição,
Expandindo a definição de e da etapa de verificação 4,
Coletando o termo comum ,
Expandindo a definição de s da etapa 6 de assinatura,
Uma vez que o inverso de um inverso é o elemento original, e o produto do inverso de um elemento e o elemento é a identidade, ficamos com
A partir da definição de r , esta é a etapa de verificação 6.
Isso mostra apenas que uma mensagem assinada corretamente será verificada corretamente; muitas outras propriedades são necessárias para um algoritmo de assinatura seguro.
Recuperação de chave pública
Dada uma mensagem m e assinatura de Alice sobre essa mensagem, Bob pode (potencialmente) recuperar a chave pública de Alice:
- Verifique se r e s são inteiros em . Caso contrário, a assinatura é inválida.
- Calcular um ponto da curva em que é um dos , , , etc (fornecida não é demasiado grande para um elemento de campo) e é um valor de tal modo que a equação da curva é satisfeita. Observe que pode haver vários pontos de curva que satisfaçam essas condições, e cada valor de R diferente resulta em uma chave recuperada distinta.
- Calcule , onde HASH é a mesma função usada na geração da assinatura.
- Sejam z os bits mais à esquerda de e .
- Calcule e .
- Calcule o ponto da curva .
- A assinatura é válida se , corresponder à chave pública de Alice.
- A assinatura é inválida se todos os pontos R possíveis tiverem sido tentados e nenhum corresponder à chave pública de Alice.
Observe que uma assinatura inválida ou uma assinatura de uma mensagem diferente resultará na recuperação de uma chave pública incorreta. O algoritmo de recuperação só pode ser usado para verificar a validade de uma assinatura se a chave pública do assinante (ou seu hash) for conhecida de antemão.
Exatidão do algoritmo de recuperação
Comece com a definição da etapa de recuperação 6,
Pela definição da etapa de assinatura 4,
Como a multiplicação escalar da curva elíptica distribui sobre a adição,
Expandindo a definição de e da etapa de recuperação 5,
Expandindo a definição de s da etapa 6 de assinatura,
Uma vez que o produto do inverso de um elemento e o elemento é a identidade, ficamos com
O primeiro e o segundo termos se cancelam,
Pela definição de , esta é a chave pública de Alice.
Isso mostra que uma mensagem assinada corretamente recuperará a chave pública correta, desde que informações adicionais tenham sido compartilhadas para calcular exclusivamente o ponto da curva a partir do valor da assinatura r .
Segurança
Em dezembro de 2010, um grupo que se autodenomina fail0verflow anunciou a recuperação da chave privada ECDSA usada pela Sony para assinar o 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. Conforme apontado na seção Algoritmo de geração de assinatura acima, isso torna solucionável, tornando todo o algoritmo inútil.
Em 29 de março de 2011, dois pesquisadores publicaram um artigo IACR demonstrando que é possível recuperar uma chave privada TLS de um servidor usando OpenSSL que autentica com Elliptic Curves DSA em um campo binário por meio de um ataque de temporização . A vulnerabilidade foi corrigida no OpenSSL 1.0.0e.
Em agosto de 2013, foi revelado que bugs em algumas implementações da classe Java SecureRandom às vezes geravam colisões no valor. Isso permitiu que os hackers recuperassem as chaves privadas, dando-lhes o mesmo controle sobre as transações de bitcoin que os proprietários das chaves legítimas tinham, usando o mesmo exploit usado para revelar a chave de assinatura do PS3 em algumas implementações de aplicativos Android , que usam Java e contam com ECDSA para autenticar transações.
Esse problema pode ser evitado por uma geração imprevisível de , por exemplo, um procedimento determinístico conforme descrito pela RFC 6979.
Preocupações
Algumas preocupações expressas sobre ECDSA:
- Preocupações políticas : a confiabilidade das curvas produzidas pelo NIST sendo questionada após revelações de que a NSA insere voluntariamente backdoors em software, componentes de hardware e padrões publicados foram feitos; Criptógrafos bem conhecidos expressaram dúvidas sobre como as curvas NIST foram projetadas, e a contaminação voluntária já foi comprovada no passado. (Veja também a introdução da curva libssh25519 .) No entanto, uma prova de que as curvas NIST nomeadas exploram uma rara fraqueza ainda está faltando.
- Preocupações técnicas : a dificuldade de implementação adequada do padrão, sua lentidão e falhas de projeto que reduzem a segurança em implementações insuficientemente defensivas.
Implementações
Abaixo está uma lista de bibliotecas criptográficas que fornecem suporte para ECDSA:
- Botan
- Castelo inflável
- cryptlib
- Crypto ++
- libgcrypt
- GnuTLS
- OpenSSL
- wolfCrypt
- LibreSSL
- mbed TLS
- Microsoft CryptoAPI
- Crypto API (Linux)
Exemplo de uso
Wikipedia.org usa ECDSA em um ciphersuite TLS para se autenticar em navegadores da web, o que mostra a seguinte transcrição abreviada.
$ date
Wed Mar 4 10:24:52 EST 2020
$ openssl s_client -connect wikipedia.org:443 # output below has DELETIONS for brevity
CONNECTED(00000003)
depth=2 O = Digital Signature Trust Co., CN = DST Root CA X3
verify return:1
depth=1 C = US, O = Let's Encrypt, CN = Let's Encrypt Authority X3
verify return:1
depth=0 CN = *.wikipedia.org
verify return:1
---
Certificate chain
0 s:/CN=*.wikipedia.org
i:/C=US/O=Let's Encrypt/CN=Let's Encrypt Authority X3
1 s:/C=US/O=Let's Encrypt/CN=Let's Encrypt Authority X3
i:/O=Digital Signature Trust Co./CN=DST Root CA X3
---
Server certificate
-----BEGIN CERTIFICATE-----
MIIHOTCCBiGgAwIBAgISA4srJU6bpT7xpINN6bbGO2/mMA0GCSqGSIb3DQEBCwUA
... many lines DELETED ....
kTOXMoKzBkJCU8sCdeziusJtNvWXW6p8Z3UpuTw=
-----END CERTIFICATE-----
subject=/CN=*.wikipedia.org
issuer=/C=US/O=Let's Encrypt/CN=Let's Encrypt Authority X3
---
No client certificate CA names sent
Peer signing digest: SHA256
Server Temp Key: ECDH, P-256, 256 bits
---
SSL handshake has read 3353 bytes and written 431 bytes
---
New, TLSv1/SSLv3, Cipher is ECDHE-ECDSA-AES256-GCM-SHA384
Server public key is 256 bit
Secure Renegotiation IS supported
Compression: NONE
Expansion: NONE
No ALPN negotiated
SSL-Session:
Protocol : TLSv1.2
Cipher : ECDHE-ECDSA-AES256-GCM-SHA384
Session-ID: ... DELETED ...
Session-ID-ctx:
Master-Key: ... DELETED ...
Key-Arg : None
PSK identity: None
PSK identity hint: None
SRP username: None
Start Time: 1583335210
Timeout : 300 (sec)
Verify return code: 0 (ok)
---
DONE
Veja também
Referências
Leitura adicional
- Comitê de Padrões Credenciado X9 , ASC X9 Emite Novo Padrão para Criptografia de Chave Pública / ECDSA , 6 de outubro de 2020. Fonte
- Comitê de Padrões Credenciado X9 , Padrão Nacional Americano X9.62-2005, Criptografia de Chave Pública para a Indústria de Serviços Financeiros, Algoritmo de Assinatura Digital da Curva Elíptica (ECDSA) , 16 de novembro de 2005.
- Certicom Research, Standards forfficient cryptography, SEC 1: Elliptic Curve Cryptography , Versão 2.0, 21 de maio de 2009.
- López, J. e Dahab, R. Uma Visão Geral da Criptografia da Curva Elíptica , Relatório Técnico IC-00-10, Universidade Estadual de Campinas, 2000.
- Daniel J. Bernstein , algoritmo de exponenciação de Pippenger , 2002.
- Daniel RL Brown, Generic Groups, Collision Resistance, and ECDSA , Designs, Codes and Cryptography, 35 , 119–152, 2005. Versão ePrint
- Ian F. Blake, Gadiel Seroussi e Nigel Smart , editores, Advances in Elliptic Curve Cryptography , London Mathematical Society Lecture Note Series 317, Cambridge University Press, 2005.
- Hankerson, D .; Vanstone, S .; Menezes, A. (2004). Guia para criptografia de curva elíptica . Springer Professional Computing. Nova York: Springer . doi : 10.1007 / b97644 . ISBN 0-387-95273-X. S2CID 720546 .