Criptografia Assimétrica - Principais Algoritmos

Depois de entender o conceito e o funcionamento da criptografia assimétrica, é hora de conhecer os algoritmos que a implementam na prática. Cada um deles se baseia em um problema matemático diferente, apresenta tamanhos de chave distintos e tem seus próprios casos de uso preferenciais.

Neste post percorreremos os algoritmos mais relevantes do universo assimétrico: suas origens, fundamentos matemáticos, variantes e status atual. Essa visão panorâmica permitirá, no post seguinte, entender onde cada um é aplicado no mundo real.

Como os algoritmos assimétricos são classificados

Antes de entrar nos algoritmos específicos, vale situar as três grandes famílias que agrupam a maioria deles.

Baseados em fatoração

Dependem da dificuldade de fatorar números inteiros muito grandes. O principal representante é o RSA.

Baseados em logaritmo discreto

Dependem da dificuldade de calcular logaritmos em grupos finitos. Incluem DSA, ElGamal e o próprio Diffie-Hellman.

Baseados em curvas elípticas (ECC)

Dependem da dificuldade do logaritmo discreto sobre curvas elípticas, um problema ainda mais difícil para o mesmo tamanho de chave. Incluem ECDSA, ECDH, Ed25519 e X25519.

Família	Problema matemático base	Exemplos
Fatoração	Fatorar n = p × q	RSA
Logaritmo discreto	log em grupo multiplicativo	DSA, ElGamal, Diffie-Hellman clássico
Curvas elípticas	log discreto sobre curva elíptica	ECDSA, ECDH, Ed25519, X25519

RSA, o algoritmo pioneiro

O RSA (iniciais de Rivest, Shamir e Adleman, seus criadores) foi publicado em 1977 e é o algoritmo assimétrico mais tradicional e amplamente conhecido. Está presente em protocolos antigos e novos, embora venha sendo progressivamente substituído pela ECC em novos projetos.

Fundamento matemático

A segurança do RSA depende da dificuldade de fatorar o produto de dois números primos grandes. O par de chaves é derivado dessa estrutura:

1. Escolhem-se dois primos grandes p e q
2. Calcula-se n = p × q (o módulo)
3. Calcula-se φ(n) = (p − 1)(q − 1) (função totiente de Euler)
4. Escolhe-se um expoente público e (geralmente 65537)
5. Calcula-se o expoente privado d tal que d × e ≡ 1 (mod φ(n))

A chave pública é o par (n, e). A chave privada é d (ou mais detalhadamente p, q, d e valores derivados).

Tamanhos de chave usuais

Tamanho	Status
1024	Obsoleto, considerado inseguro desde 2013
2048	Mínimo aceito atualmente, usado em muitos sistemas
3072	Equivalente a 128 bits simétricos, recomendado
4096	Nível conservador, usado em certificados raiz
7680+	Equivalente a 192 bits simétricos ou mais

Características

• Suporta cifragem e assinatura (poucos algoritmos fazem os dois)
• Chaves grandes: 3072 bits é o mínimo recomendado para novos projetos
• Lento, especialmente para gerar chaves e cifrar grandes volumes
• Vulnerável a implementações mal feitas: ataques como Bleichenbacher e padding oracle demonstram que o uso do RSA exige padding correto (OAEP para cifragem, PSS para assinatura)

Gerando uma chave RSA

openssl genpkey -algorithm RSA \
  -pkeyopt rsa_keygen_bits:3072 \
  -out chave_rsa.pem

Significado de cada opção:

• genpkey: subcomando genérico para geração de chaves privadas
• -algorithm RSA: define o algoritmo como RSA
• -pkeyopt rsa_keygen_bits:3072: tamanho da chave em bits
• -out chave_rsa.pem: arquivo de saída da chave privada

ECC: criptografia de curvas elípticas

A ECC (Elliptic Curve Cryptography) utiliza propriedades de curvas elípticas sobre corpos finitos para oferecer o mesmo nível de segurança do RSA com chaves muito menores. Isso traz vantagens práticas enormes: menos processamento, menos uso de memória, assinaturas e trocas de chave mais rápidas.

Fundamento matemático

A ECC se baseia no problema do logaritmo discreto sobre curvas elípticas (ECDLP), que é significativamente mais difícil que o logaritmo discreto comum. Isso permite chaves de 256 bits oferecerem segurança equivalente a RSA de 3072 bits.

Curvas mais comuns

Curva	Tamanho	Padronização	Observações
P-256	256	NIST (FIPS 186)	Amplamente adotada em TLS e certificados
P-384	384	NIST	Nível de segurança mais alto
P-521	521	NIST	Nível máximo em curvas NIST
Curve25519	256	IETF	Projetada por Daniel J. Bernstein
Curve448	448	IETF	Alternativa de maior segurança

Variantes do ECC

• ECDSA (Elliptic Curve Digital Signature Algorithm): usado para assinatura digital em certificados TLS, Git, Bitcoin
• ECDH (Elliptic Curve Diffie-Hellman): usado para acordo de chaves em TLS 1.3 e SSH
• Ed25519: variante de EdDSA sobre Curve25519, otimizada para assinaturas rápidas e seguras
• X25519: variante de ECDH sobre Curve25519, padrão em WireGuard, Signal e TLS 1.3

Gerando chaves ECC

# Com uma curva NIST
openssl genpkey -algorithm EC \
  -pkeyopt ec_paramgen_curve:P-256 \
  -out chave_ecc.pem

# Com Ed25519 (parâmetros fixos)
openssl genpkey -algorithm ED25519 \
  -out chave_ed25519.pem

# Com X25519 (para ECDH)
openssl genpkey -algorithm X25519 \
  -out chave_x25519.pem

Significado de cada opção:

• -algorithm EC: algoritmo de curvas elípticas genérico (com parâmetros)
• -pkeyopt ec_paramgen_curve:P-256: curva específica a ser usada
• -algorithm ED25519: algoritmo Ed25519 (parâmetros fixos por projeto, não precisa de -pkeyopt)
• -algorithm X25519: algoritmo X25519 para ECDH, também com parâmetros fixos

Prefira Ed25519 e X25519

Para novos projetos, Ed25519 (assinatura) e X25519 (acordo de chaves) são as melhores escolhas: simples de usar, rápidas, seguras, com chaves pequenas e sem armadilhas de parâmetros. Elas são hoje o padrão em SSH, WireGuard e TLS 1.3.

Diffie-Hellman

Embora frequentemente classificado junto com algoritmos assimétricos, o Diffie-Hellman (DH) não é um algoritmo de cifragem nem de assinatura, mas sim um protocolo de acordo de chaves. Ele permite que duas partes cheguem a uma chave simétrica compartilhada em comum, sem jamais transmiti-la pela rede.

Variantes

• DH clássico: baseado em aritmética modular, exige chaves de 2048 a 3072 bits para segurança adequada
• ECDH: variante sobre curvas elípticas, muito mais eficiente
• DHE / ECDHE: variantes efêmeras, usadas para implementar forward secrecy
• X25519: ECDH sobre Curve25519, padrão atual

O DH foi abordado em profundidade no post sobre limitações da criptografia simétrica, incluindo o exemplo didático com p=23 e g=5.

DSA e ECDSA

O DSA (Digital Signature Algorithm) é um algoritmo de assinatura padronizado pelo NIST em 1991. Baseia-se no logaritmo discreto em grupos multiplicativos. Era muito usado em certificados antigos, mas foi progressivamente substituído pelo RSA (por versatilidade) e pelo ECDSA (por eficiência).

• DSA clássico: considerado legado, obsoleto desde 2023 pelo NIST
• ECDSA: variante sobre curvas elípticas, amplamente usada em TLS, SSH, Bitcoin e certificados digitais

Cuidado com ECDSA e nonces

O ECDSA é extremamente sensível à qualidade do número aleatório (nonce k) usado em cada assinatura. Se o mesmo nonce for usado em duas assinaturas diferentes, ou se o nonce for previsível, a chave privada pode ser recuperada completamente. Esse foi o problema que permitiu a extração da chave de assinatura do PlayStation 3 em 2010. O Ed25519 evita essa classe de erros por utilizar nonces determinísticos derivados da chave e da mensagem.

Ed25519 e EdDSA

O EdDSA (Edwards-curve Digital Signature Algorithm) é uma família moderna de algoritmos de assinatura projetada em 2011. Suas variantes principais são:

• Ed25519: sobre a curva Edwards25519, com 128 bits de segurança efetiva
• Ed448: sobre a curva Edwards448, com 224 bits de segurança efetiva

Vantagens

• Determinístico: elimina a dependência de aleatoriedade por assinatura (evita o erro do ECDSA)
• Rápido: assinatura e verificação muito eficientes em software
• Chaves pequenas: 32 bytes para a chave pública, 64 bytes para a assinatura
• Simplicidade de implementação: menos armadilhas de uso

Onde é usado

• OpenSSH (preferido em versões modernas): ssh-keygen -t ed25519
• GPG (versões recentes suportam Ed25519)
• Certificados TLS modernos (ainda em adoção crescente)
• Signal, WireGuard e muitos mensageiros ponta a ponta

ElGamal

O ElGamal é um algoritmo histórico, publicado em 1985 por Taher ElGamal. Baseia-se no logaritmo discreto e permite tanto cifragem quanto assinatura, embora com usos distintos para cada operação.

• Foi muito utilizado em versões antigas do PGP e do GnuPG
• Hoje é considerado legado, substituído por RSA e ECC na maioria dos usos
• Sua estrutura influenciou o design do DSA e de outros algoritmos

Algoritmos pós-quânticos

Com a ameaça crescente da computação quântica, o NIST padronizou em 2024 um conjunto de algoritmos pós-quânticos, resistentes a ataques por computadores quânticos. Os principais:

• ML-KEM (anteriormente CRYSTALS-Kyber): mecanismo de encapsulamento de chaves
• ML-DSA (anteriormente CRYSTALS-Dilithium): assinatura digital
• SLH-DSA (anteriormente SPHINCS+): assinatura baseada em hash
• FN-DSA (anteriormente Falcon): assinatura compacta baseada em reticulados

Todos se baseiam em problemas matemáticos para os quais não se conhecem algoritmos quânticos eficientes, como problemas em reticulados (lattice-based cryptography) e hashes criptográficos.

Adoção prática

Esses algoritmos já aparecem em versões recentes do OpenSSH (que suporta sntrup761x25519-sha512@openssh.com como KEM híbrido), em branches experimentais do OpenSSL e em alguns navegadores. A transição completa deve se consolidar ao longo dos próximos anos.

Comparativo geral

Algoritmo	Família	Uso principal	Tamanho de chave	Status
RSA	Fatoração	Cifragem + assinatura	2048 a 4096 bits	Legado, ainda muito usado
DSA	Log discreto	Assinatura	2048 a 3072 bits	Obsoleto desde 2023
ECDSA	Curva elíptica	Assinatura	256 a 521 bits	Moderno, cuidado com nonces
Ed25519	Curva Edwards	Assinatura	256 bits	Recomendado
DH	Log discreto	Acordo de chaves	2048 a 3072 bits	Legado
ECDH	Curva elíptica	Acordo de chaves	256 a 521 bits	Moderno
X25519	Curva Montgomery	Acordo de chaves	256 bits	Recomendado
ElGamal	Log discreto	Cifragem + assinatura	2048+ bits	Legado, substituído
ML-KEM	Reticulados	Troca de chaves PQ	~800 a 1600 bytes	Pós-quântico, em adoção
ML-DSA	Reticulados	Assinatura PQ	~1300 a 2600 bytes	Pós-quântico, em adoção

O que escolher hoje?

Para novos projetos, as recomendações mais consolidadas são:

Cenário	Recomendação
Chaves SSH para servidores	Ed25519
Certificados TLS para site HTTPS	ECDSA (P-256) ou RSA 3072
Acordo de chaves em TLS 1.3	X25519 (preferido) ou P-256
Assinatura de código ou de pacotes	Ed25519 ou ECDSA
Compatibilidade com sistemas legados	RSA 2048 ou 3072
Longa validade (acima de 10 anos)	Avaliar modo híbrido pós-quântico

Evite algoritmos obsoletos

Em novos projetos, evite:

• RSA com chaves menores que 2048 bits
• DSA clássico (obsoleto desde 2023)
• MD5 e SHA-1 como funções hash em assinatura
• Diffie-Hellman clássico sem forward secrecy
• Curvas elípticas com parâmetros customizados sem padronização

Verificando algoritmos disponíveis

No OpenSSL

openssl list -public-key-algorithms

Significado do comando:

• list: lista itens suportados pela instalação
• -public-key-algorithms: filtra apenas algoritmos de chave pública

No OpenSSH

ssh -Q key
ssh -Q sig

Significado de cada opção:

• -Q key: lista algoritmos de chaves aceitos pelo SSH (RSA, ECDSA, Ed25519, etc.)
• -Q sig: lista algoritmos de assinatura aceitos

Benchmark de desempenho

openssl speed rsa2048 rsa3072 rsa4096
openssl speed ecdsap256 ed25519

Significado do comando:

• speed: subcomando que executa benchmarks de desempenho
• rsa2048 rsa3072 rsa4096: variantes do RSA a serem testadas
• ecdsap256 ed25519: algoritmos elípticos a serem testados

A saída permite comparar quantas assinaturas e verificações cada algoritmo consegue fazer por segundo, mostrando concretamente a superioridade do Ed25519 em desempenho.

Considerações Finais

A escolha de um algoritmo assimétrico depende de três fatores principais: o tipo de operação (cifragem, assinatura ou acordo de chaves), o nível de segurança desejado e a compatibilidade com sistemas que irão interagir. Felizmente, para a maioria dos cenários atuais, as respostas convergem: Ed25519 para assinaturas, X25519 para acordo de chaves e RSA 3072 ou ECDSA P-256 quando a compatibilidade com infraestrutura legada é necessária.

No próximo post exploraremos os casos de uso da criptografia assimétrica, mapeando como esses algoritmos aparecem concretamente em HTTPS, SSH, PGP, certificados, assinatura de código, autenticação e outras aplicações do mundo real.