Criptografia de Curva Elíptica

A criptografia de curva elíptica (ECC) implementa esquemas de chave pública sobre o grupo de pontos em uma curva elíptica, alcançando a mesma segurança que RSA ou Diffie-Hellman de campo finito com chaves muito menores.

Definition

A criptografia de curva elíptica é uma criptografia de chave pública cujo grupo subjacente é o conjunto de pontos em uma curva elíptica sobre um campo finito, com segurança baseada na dificuldade do problema do logaritmo discreto de curva elíptica.

Scope

Este tópico abrange a lei do grupo de curva elíptica sobre campos finitos, o problema do logaritmo discreto de curva elíptica e os esquemas construídos sobre eles: Diffie-Hellman de curva elíptica (ECDH), os esquemas de assinatura ECDSA e EdDSA, e curvas modernas como a Curve25519. Aborda por que os logs discretos de curva elíptica são mais difíceis do que os de campo finito (nenhum cálculo de índice subexponencial) e preocupações de implementação como a reutilização de nonce em ECDSA. Exclui RSA e esquemas de log discreto de campo finito abordados em tópicos relacionados.

Core questions

• Como a adição geométrica de pontos em uma curva elíptica forma um grupo criptográfico?
• Por que o logaritmo discreto de curva elíptica é mais difícil do que seu análogo de campo finito, permitindo chaves menores?
• Como Diffie-Hellman e assinaturas digitais são instanciados sobre curvas elípticas?
• O que torna as curvas modernas como a Curve25519 mais seguras de implementar do que as curvas NIST mais antigas?
• Por que a unicidade do nonce por assinatura é crítica no ECDSA?

Key concepts

• lei do grupo de curva elíptica
• multiplicação escalar
• problema do logaritmo discreto de curva elíptica
• ECDH
• ECDSA
• EdDSA e Ed25519
• Curve25519
• vulnerabilidade de reutilização de nonce
• tamanho da chave vs RSA

Key theories

Problema do logaritmo discreto de curva elíptica

Dados os pontos P e Q = kP em uma curva, recuperar o escalar k é considerado um esforço exponencial completo para curvas bem escolhidas, porque os ataques de cálculo de índice que enfraquecem os logs discretos de campo finito não se aplicam.

Chaves menores para segurança igual

Como os melhores ataques aos logs discretos de curva elíptica são algoritmos genéricos de raiz quadrada, uma curva elíptica de 256 bits oferece aproximadamente 128 bits de segurança — comparável a RSA de 3072 bits — resultando em operações mais rápidas e chaves e assinaturas menores.

Mechanisms

Pontos em uma curva elíptica sobre um campo finito formam um grupo abeliano sob uma lei de adição geométrica; adicionar repetidamente um ponto base P a si mesmo k vezes (multiplicação escalar, kP) é eficiente, mas recuperar k de kP é o problema difícil. O ECDH executa Diffie-Hellman trocando múltiplos escalares de um ponto base; ECDSA e EdDSA produzem assinaturas a partir de um escalar por mensagem (um nonce) — que, se repetido ou previsível, vaza a chave privada, como várias violações reais demonstraram.

Clinical relevance

ECC é a escolha padrão de chave pública para novos sistemas: ECDHE fornece troca de chaves com sigilo de encaminhamento em TLS 1.3, Ed25519 assina chaves SSH, atualizações de software e certificados, e Curve25519 protege Signal, WireGuard e mensagens modernas. Suas chaves pequenas e operações rápidas a tornam adequada para dispositivos móveis, cartões inteligentes e hardware IoT restrito.

Evidence & guidelines

ECDSA é padronizado em FIPS 186, ECDH em NIST SP 800-56A, e EdDSA/Ed25519 em RFC 8032; Curve25519/X25519 em RFC 7748. A prática moderna favorece as curvas de Edwards e X25519 por sua resistência a armadilhas de implementação. A falha do ECDSA quando os nonces são reutilizados (notavelmente a extração de chave do Sony PlayStation 3 em 2010) é um exemplo padrão de advertência.

History

Neal Koblitz e Victor Miller propuseram independentemente o uso de curvas elípticas para criptografia em 1985-1987. A adoção foi inicialmente lenta devido a preocupações com patentes e confiança e à complexidade das curvas NIST, mas a ECC tornou-se dominante na década de 2010 à medida que a eficiência do tamanho da chave se tornou mais importante e a Curve25519 (2006) de Bernstein e Ed25519 ofereceram designs rápidos e resistentes a uso indevido, agora amplamente implantados.

Key figures

• Neal Koblitz
• Victor Miller
• Daniel J. Bernstein
• Alfred Menezes
• Scott Vanstone

Seminal works

• koblitz1987
• hankerson2004
• katz2020

Frequently asked questions

Por que uma chave de curva elíptica de 256 bits corresponde a uma chave RSA de 3072 bits?

Os melhores ataques conhecidos ao logaritmo discreto de curva elíptica são genéricos e levam um tempo aproximadamente igual à raiz quadrada do tamanho do grupo, enquanto a fatoração e os logs discretos de campo finito possuem algoritmos subexponenciais mais rápidos. Assim, as curvas elípticas precisam de muito menos bits para o mesmo nível de segurança.

As curvas elípticas NIST são confiáveis?

As curvas P-NIST padrão são amplamente utilizadas e não se sabe que foram quebradas, mas suas escolhas constantes inexplicáveis e dificuldade de implementação levaram muitos a preferir Curve25519 e Ed25519, que têm justificativas de design transparentes e são mais fáceis de implementar com segurança em tempo constante.