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.

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 ${\displaystyle 2^{80}}$ operações para encontrar a chave privada) o tamanho da chave pública de um algoritmo ECDSA deverá ser de 160 bits. Por outro lado, o tamanho da assinatura é o mesmo para o DSA e o ECDSA: aproximadamente ${\displaystyle 4t}$ bits, onde ${\displaystyle 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, que é equivalente a ${\displaystyle 2^{80}}$

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 ${\displaystyle ({\textrm {CURVE}},G,n)}$ da curva. Além do corpo e da equação da curva, é preciso ${\displaystyle G}$, um ponto de base de primeira ordem sobre a curva; ${\displaystyle n}$ é a ordem multiplicativa do ponto ${\displaystyle 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 de curva que gera um subgrupo de grande ordem prima n
n	ordem inteira de G, significa que ${\displaystyle n\times G=O}$, em que ${\displaystyle O}$ é o elemento identidade.
${\displaystyle d_{A}}$	a chavem privada (escolhida aleatóriamente)
${\displaystyle Q_{A}}$	a chave pública ${\displaystyle d_{A}\times G}$ (calculado pela curva elíptica)
m	a mensagem a ser enviada

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

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

Para Alice assinar uma mensagem ${\displaystyle m}$, ela deve seguir os seguintes passos:

1. Calcular ${\displaystyle 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 ${\displaystyle z}$ como sendo os ${\displaystyle L_{n}}$ bits mais à esquerda de ${\displaystyle e}$, em que ${\displaystyle L_{n}}$ é o comprimento de bit da ordem do grupo ${\displaystyle n}$. (Note que ${\displaystyle z}$ pode ser maior do que ${\displaystyle n}$ mas não mais longo.)
3. Escolher um inteiro aleatório criptograficamente seguro ${\displaystyle k}$ em ${\displaystyle [1,n-1]}$.
4. Calcular o ponto da curva ${\displaystyle (x_{1},y_{1})=k\times G}$.
5. Calcular ${\displaystyle r=x_{1}\,{\bmod {\,}}n}$. Se ${\displaystyle r=0}$, voltar para o passo 3.
6. Calcular ${\displaystyle s=k^{-1}(z+rd_{A})\,{\bmod {\,}}n}$. Se ${\displaystyle s=0}$, voltar para o passo 3.
7. A assinatura é o par ${\displaystyle (r,s)}$. E ${\displaystyle (r,-s\,{\bmod {\,}}n)}$ também é uma assinatura válida.)

Como é observado no padrão, é preciso não apenas que ${\displaystyle k}$ seja secreto, mas também que sejam escolhidos valores de ${\displaystyle k}$ diferentes para assinaturas diferentes, caso contrário, a equação da etapa 6 pode ser resolvido para ${\displaystyle d_{A}}$, a chave privada: Dadas duas assinaturas ${\displaystyle (r,s)}$ e ${\displaystyle (r,s')}$ empregando a mesmo mesmo ${\displaystyle k}$ desconhecido para diferentes mensagens conhecidas ${\displaystyle m}$ e ${\displaystyle m'}$, um invasor pode calcular ${\displaystyle z}$ e ${\displaystyle z'}$, e como ${\displaystyle s-s'=k^{-1}(z-z')}$ (todas as operações neste parágrafo são feitas módulo ${\displaystyle n}$) o atacante pode encontrar ${\displaystyle k={\frac {z-z'}{s-s'}}}$. Como ${\displaystyle s=k^{-1}(z+rd_{A})}$, o invasor pode agora calcular a chave privada ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle k}$ é único para cada mensagem, pode-se ignorar completamente a geração de números aleatórios e gerar assinaturas deterministicas derivando ${\displaystyle k}$ tanto da mensagem quanto da chave privada.

Algoritmo de verificação de assinatura

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

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

Depois, Bob segue estes passos:

1. Verificar que ${\displaystyle r}$ e ${\displaystyle s}$ são números inteiros em ${\displaystyle [1,n-1]}$. Se não, a assinatura é inválida.
2. Calcular ${\displaystyle e={\textrm {HASH}}(m)}$, em que HASH é a mesma função utilizada na geração da assinatura.
3. Considerar ${\displaystyle z}$ como os ${\displaystyle L_{n}}$ bits mais à esquerda de ${\displaystyle e}$.
4. Calcular ${\displaystyle u_{1}=zs^{-1}\,{\bmod {\,}}n}$ e ${\displaystyle u_{2}=rs\,{\bmod {\,}}n}$.
5. Calcular o ponto da curva ${\displaystyle (x_{1},y_{1})=u_{1}\times G+u_{2}\times Q_{A}}$. Se ${\displaystyle (x_{1},y_{1})=O}$ então, a assinatura é válida.
6. A assinatura é válida se ${\displaystyle 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 ${\displaystyle u_{1}\times G+u_{2}\times Q_{A}}$ pode ser calculada mais rapidamente do que duas multiplicações escalares feitas de forma independente.

Recuperação da chave pública

Dado uma mensagem ${\displaystyle m}$ e a assinatura de Alice ${\displaystyle r}$, Bob pode recuperar a chave pública de Alice da seguinte forma:

1. Verificar que r e s são inteiros em ${\displaystyle [1,n-1]}$. Caso contrário, a assinatura é inválida.
2. Calcular o ponto de curva ${\displaystyle R=(x_{1},y_{1})}$ onde ${\displaystyle x_{1}}$ é um dos ${\displaystyle r,r+n,r+2n}$ etc. (${\displaystyle x_{1}}$ não é um valor grande de campo da curva) e ${\displaystyle y_{1}}$ é um valor tal que a equação da curva é satisfeita. Vale ressaltar que existem inúmeros pontos de curva que satisfazem essas condições, e cada valor ${\displaystyle R}$ vai resultar em uma chave diferente.
3. Calcule ${\displaystyle e=HASH(m)}$, onde HASH é a mesma função usada na geração da assinatura.
4. Seja ${\displaystyle z}$ os ${\displaystyle L_{n}}$ bits mais à esquerda de ${\displaystyle e}$.
5. Calcule ${\displaystyle u_{1}=zr^{-1}{\bmod {n}}}$ e ${\displaystyle u_{2}=sr^{-1}{\bmod {n}}}$.
6. Calcule o ponto de curva ${\displaystyle Q_{A}=(x_{A},y_{A})=u_{1}\times G+u_{2}\times R}$.
7. A assinatura é válida se ${\displaystyle Q_{A}}$, combina com a chave pública de Alice.
8. Se todos os pontos R foram tentados e nenhum deles combinam com a chave pública de Alice, então a assinatura é inválida.

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 ${\displaystyle k}$ era estático em vez de aleatório. Como apontado anteriormente, na seção sobre o algoritmo de geração de assinaturas, isso torna ${\displaystyle d_{A}}$ solucionável, e o algoritmo completamente inútil.

Em 29 de Março de 2011, dois pesquisadores publicaram um artigo da IACR (Associação Internacional para pesquisa criptológica), demonstrando que é possível obter uma chave privada TLS de um servidor utilizando OpenSSL que autentica com curvas elípticas DSA 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, algumas vezes gerava colisões em valores 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 do ECDSA para autenticar transações.

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

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

Referências

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

• Portal da ciência