05 — Criptografia Assimétrica (Chave Pública)

Par de chaves (pública, privada). Base de quase todo protocolo moderno: TLS, SSH, S/MIME, PGP, Signal, criptomoedas. Mais lento que simétrica — por isso TLS faz híbrido: assimétrica troca chave, simétrica cifra dados.

1. Problemas matemáticos subjacentes

Toda criptografia de chave pública clássica é baseada em um problema difícil:

Todos os clássicos (IFP, DLP, ECDLP) quebram com Shor (computador quântico).

2. Diffie-Hellman Key Exchange (1976)

Whitfield Diffie + Martin Hellman, New Directions in Cryptography (IEEE Trans. Info Theory, 1976). Crédito também a Ralph Merkle (Merkle's Puzzles, 1974) e CocksWilliamsonEllis no GCHQ (1969–1974, classificado).

Protocolo

Setup público: grupo \(\mathbb{Z}_p^*\) de ordem prima \(q\), gerador \(g\).

1. Alice: \(a \stackrel{\\)}{leftarrow} {1, ..., q-1}\(, envia \)A = g^a$.
2. Bob: \(b \stackrel{\\)}{leftarrow} {1, ..., q-1}\(, envia \)B = g^b$.
3. Alice computa \(K = B^a = g^{ab}\).
4. Bob computa \(K = A^b = g^{ab}\).

Eavesdropper vê \(g^a, g^b\); precisa resolver CDH.

Variantes

• Static DH: chaves de longo prazo. Sem forward secrecy.
• Ephemeral DH (DHE): chaves usadas uma vez. Forward secrecy.
• Static-Ephemeral: um lado estático (server cert), outro ephemeral.

Grupos padronizados (RFC 7919, 3526)

Ataques

• Man-in-the-middle: DH não autentica. Sempre combine com assinatura ou autenticação prévia.
• Small subgroup confinement: validar \(B^q \equiv 1 \mod p\) (ou usar safe primes).
• Logjam (2015): pré-computação contra primos comuns DH-1024; viável para state actor.
• Triple Handshake (TLS): cross-protocol attack — mitigado em TLS 1.3.

ECDH

Mesma estrutura em curva elíptica: \(A = aG\), \(B = bG\), shared \(= aB = bA = abG\).

3. RSA (1977)

Ron Rivest + Adi Shamir + Leonard Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (CACM 1978, MIT/LCS Tech Memo 82, 1977).

Anteriormente descoberto por Clifford Cocks no GCHQ (1973, classificado até 1997).

Setup

1. Escolha \(p, q\) primos grandes secretos.
2. \(N = pq\) (modulus público).
3. \(\varphi(N) = (p-1)(q-1)\) (Euler totient).
4. Escolha \(e\) tal que \(\gcd(e, \varphi(N)) = 1\) (típico \(e = 65537 = 2^{16} + 1\)).
5. \(d = e^{-1} \mod \varphi(N)\) (chave privada).

Public key: \((N, e)\). Private key: \(d\) (ou \(p, q\)).

Encryption (textbook RSA — ❌ NUNCA use crua)

\(C = M^e \mod N\), \(M = C^d \mod N\).

Por que insegura:

• Determinística (mesmo \(M\) → mesmo \(C\)): vaza padrões.
• Maleável: \(C_1 \cdot C_2 \mod N = (M_1 M_2)^e\).
• \(M\) pequeno + \(e\) pequeno: \(C = M^e\) sem mod (se \(M^e < N\)) — raiz \(e\)-ésima.
• Coppersmith attacks com pequenas mensagens parcialmente conhecidas.

Padding seguro

OAEP (Optimal Asymmetric Encryption Padding) — Bellare + Rogaway 1994.

$\(C = (m \\\| r \\\| \text{hash padding})^e \mod N\)$

PKCS#1 v1.5 padding — antigo, vulnerável a Bleichenbacher 1998 (padding oracle).

RSA-PSS para assinaturas

PSS (Probabilistic Signature Scheme) — Bellare + Rogaway 1996. Substituto seguro do PKCS#1 v1.5 signing.

Status: PKCS#1 v1.5 signing ainda é amplamente usado (X.509 certs!). Suscetível a Bleichenbacher-style mas com mitigation; PSS é mais seguro mas adoção lenta.

Geração de chave

• \(p, q\) devem ser distintos, ambos primos, \(|p - q|\) não muito pequeno (Fermat factoring), entropia adequada.
• \(|N| \in \{2048, 3072, 4096\}\).
• ROCA (CVE-2017-15361, Infineon): geração defeituosa em milhões de chaves de smartcardsTPMsEstonian eID. Quebrável por algoritmo Coppersmith específico.
• Mining your Ps and Qs (Heninger et al. 2012): chaves SSH/SSL com primos compartilhados por entropy starvation no boot.

Velocidade

RSA é lento: signing 2048 bit ~1ms; encryption ~50µs (e pequeno). Mais ainda em 4096. Mais lento que ECC com mesmo nível de segurança.

Tamanhos equivalentes

Recomendação 2026: 3072 mínimo; 4096 em sistemas legacy onde ECC não disponível. Migração para PQC em 2025–2030.

4. ElGamal (1984)

Taher ElGamal, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (IEEE Trans. Info Theory 1985).

Encryption

Setup: \(\mathbb{Z}_p^*\), \(g\), chave privada \(x\), pública \(y = g^x\).

1. Sender escolhe \(k\) random, envia \((c_1, c_2) = (g^k, m \cdot y^k)\).
2. Receiver: \(m = c_2 / c_1^x\).

IND-CPA seguro sob DDH.

Signing

Variante padronizada como DSA (Digital Signature Algorithm, FIPS 186, 1991).

ElGamal cripto raramente usado direto; ElGamal signature evoluiu para DSA → ECDSA → EdDSA.

5. DSA / ECDSA / EdDSA

DSA (FIPS 186, 1991)

Modular, baseado em DLP em \(\mathbb{Z}_p^*\).

Assinatura de mensagem \(m\) com chave privada \(x\):

1. \(k \stackrel{\\)}{leftarrow} {1, ..., q-1}$ (nonce ephemeral).
2. \(r = (g^k \mod p) \mod q\).
3. \(s = k^{-1}(H(m) + xr) \mod q\).
4. Signature: \((r, s)\).

Verify: \(w = s^{-1}\), \(u_1 = H(m) w\), \(u_2 = rw\), verificar \((g^{u_1} y^{u_2} \mod p) \mod q = r\).

ECDSA (1992 Vanstone, padrão FIPS 186-3 em 2009)

Versão em curva elíptica. Padrão no Bitcoin (secp256k1), TLS (P-256384521), SSH.

Nonce \(k\) é crítico: se \(k\) repetido ou previsível, chave privada extraível em 2 assinaturas (resolve sistema linear). Famosos incidentes:

• PS3 (Sony, 2010): nonce constante → chave master leakada pelo group fail0verflow.
• Bitcoin wallets com RNG quebrado: drained.

Mitigação: RFC 6979 — deterministic nonces via HMAC. Padrão moderno.

EdDSA (Bernstein 2011, RFC 8032)

Schnorr-style + Curve25519 (Ed25519) ou Curve448 (Ed448). Determinístico sem RFC 6979 (nonce derivado de hash de chave + msg). Constant-time. Sem pontos especiais. Sem ambiguidade de codificação.

Ed25519:

• 32-byte public key.
• 64-byte signature.
• ~128 bit security.
• ~70k signs/sec por core moderno.
• ~25k verifies/sec.
• Batch verification disponível (10× speedup).

Ed448: 56-byte pubkey, ~224 bit security. Mais lento.

Status: Ed25519 é o padrão recomendado para qualquer signing novo. OpenSSH default desde 2020. RFC 8032.

Schnorr signatures

Claus Schnorr, 1989. Mais simples que ECDSA, com prova de segurança em ROM mais limpa. Patenteado até 2008. Bitcoin adotou via Taproot (BIP340, ativado nov/2021) — assinaturas Schnorr + MuSig (aggregation).

BLS signatures (Boneh-Lynn-Shacham, 2001)

Pairing-based em curvas elípticas com pairing (BLS12-381, BN curves). Assinaturas agregáveis — 1000 assinaturas → 1 assinatura curta. Usado em Ethereum 2.0 consensus, dfinity, Filecoin, threshold signing.

• Assinatura: 48 bytes (BLS12-381 G1).
• Public key: 96 bytes (G2).
• Aggregation: \(\sigma = \prod \sigma_i\).
• Verificação aggregada: 1 pairing por signer.

6. ECC (Elliptic Curve Cryptography)

Proposto independentemente por Neal Koblitz (1985, Elliptic Curve Cryptosystems, Math. Comp.) e Victor Miller (1985, CRYPTO).

Curva elíptica curta de Weierstrass

$\(E: y^2 = x^3 + ax + b \mod p\)$

com \(4a^3 + 27b^2 \not\equiv 0 \mod p\) (não-singular).

Pontos formam grupo abeliano sob adição geométrica (com \(O\) = ponto no infinito). Ordem \(\#E(\mathbb{F}_p) = p + 1 - t\) onde \(|t| \leq 2\sqrt{p}\) (Hasse).

ECDLP

Dado \(P, Q = kP\), recuperar \(k\). Sem subexponential algorithm como GNFS para IFP — daí ECC com chave muito menor que RSA.

Curvas padronizadas

NIST (FIPS 186, SEC 2)

Controvérsia: seed das curvas NIST gerado por hash de string não-pública (Jerry Solinas). Suspeita de backdoor — sem evidência mas reduz confiança. Curvas P-* têm peculiaridades implementacionais (não-Edwards, branches, special points).

Bernstein curves

• Curve25519 (\(y^2 = x^3 + 486662 x^2 + x\) mod \(2^{255} - 19\), Montgomery form) — X25519 ECDH (RFC 7748). ~128 bit. Rápida, simples, constant-time fácil.
• Curve448 (\(2^{448} - 2^{224} - 1\)) — X448 ECDH. ~224 bit.
• Ed25519 — Edwards form da mesma curva pra signing.
• Ed448 — idem para Curve448.

Vantagens:

• Constants públicos, deterministic, transparent generation.
• Twist-secure: pontos do twist têm ordem segura (não vaza).
• Constant-time scalar multiplication trivialmente implementável.
• Cofactor pequeno (8) — sem chaves "weak".

Brainpool (Alemanha, RFC 5639)

brainpoolP256r1, P384r1, P512r1 — alternativa NIST-paranoid europeia. Seeds derivados de \(\pi, e\).

Bitcoin

secp256k1 — curva sem características aleatórias visíveis, mais rápida que P-256 para algumas operações. Não-NIST. Adotada por Bitcoin, Ethereum.

Pairing-friendly

BLS12-381, BN254, BN382, BLS12-377 — curvas com pairing eficiente para BLS, zk-SNARKs (Groth16, PLONK, Halo). Adoção em Ethereum, Zcash, Filecoin.

SM2 (China GM/T 0003)

Curva sm2p256v1 (256 bit), parâmetros próprios. Obrigatória em sistemas chineses.

7. Esquemas de encryption baseados em chave pública

RSA-OAEP

Padrão moderno para RSA encryption. Bellare-Rogaway 1994. RFC 8017.

ECIES (Elliptic Curve Integrated Encryption Scheme)

Hybrid: gera shared secret ECDH com chave pública do destinatário, deriva chave simétrica, cifra com AEAD.

ephemeral_priv = random
ephemeral_pub = ephemeral_priv * G
shared = ECDH(ephemeral_priv, recipient_pub)
key = KDF(shared)
ciphertext, tag = AEAD(key, plaintext)
send (ephemeral_pub, ciphertext, tag)

ISO/IEC 18033-2, SEC 1. Variantes: ECIES, ECIES-KEM, ChaCha20-Poly1305-Curve25519 (libsodium crypto_box_seal).

HPKE — Hybrid Public Key Encryption (RFC 9180, 2022)

Padronização moderna IETF de ECIES-style. Suporta múltiplos modos (base, PSK, auth, auth-PSK). Usado em ECH (Encrypted Client Hello TLS), MLS.

8. Identity-Based Encryption (IBE)

Conceito proposto por Shamir 1984; primeira impl prática Boneh-Franklin 2001 com pairings.

Chave pública = string (email, telefone). Não precisa PKI tradicional. Key escrow: TA (Trust Authority) gera private keys — deve ser confiável.

Usos: cifragem por email, EHR healthcare. Pouco adoção mainstream; alternativas baseadas em DID (decentralized identifiers) crescendo.

9. Threshold cryptography

Chave \(sk\) dividida entre \(n\) partes; \(t\) partes podem assinar/decriptar; \(< t\) não conseguem.

Shamir Secret Sharing (1979)

Polinômio \(f(x)\) de grau \(t-1\) com \(f(0) = sk\). Cada parte recebe \((i, f(i))\). Lagrange interpolation reconstrói.

Information-theoretic seguro (cada parte sozinha = zero info).

Threshold signatures

• Threshold RSA: Shoup 2000.
• Threshold Schnorr: Stinson-Strobl 2001, FROST (Komlo + Goldberg 2020).
• Threshold BLS: trivial pela linearidade.
• Threshold ECDSA: muito mais difícil (Gennaro-Goldfeder, Lindell — usado em wallets MPC enterprise).

Aplicações

• HSMs distribuídos.
• Custodial wallets cripto (BitGo, Fireblocks, Coinbase Prime usam threshold ECDSA).
• DKG (Distributed Key Generation) sem trusted dealer.

10. Comparação prática — qual usar em 2026?

11. Performance comparativa (cycles, CPU moderna 2026)

ECC é ~10–100× mais rápido que RSA com segurança equivalente. PQC competitivo em performance moderna (não trivial — Kyber é mais rápido que ECDH em CPUs sem ECC accel).

12. Side-channel concerns

• Constant-time scalar mult: implementar como Montgomery ladder; nunca branch sobre bit de chave.
• Table lookup leaks: precomputed tables vazam via cache.
• Branchless conditional swap: mask = -bit; a ^= mask & (a ^ b).
• Validate untrusted points: ECDH com ponto inválido pode revelar chave (invalid curve attack).
• Power analysis on smartcards: well-known, mitigado por blinding/dummy operations.

13. Bibliografia

• Hankerson, Menezes, Vanstone, Guide to Elliptic Curve Cryptography, Springer 2004.
• Silverman, The Arithmetic of Elliptic Curves, Springer 1986 (math).
• Bernstein papers sobre Curve25519, Ed25519, qhasm.
• Bernstein + Lange, SafeCurves (safecurves.cr.yp.to) — checklist para escolher curva.
• RFC 8032 EdDSA, RFC 7748 X25519, RFC 8446 TLS 1.3, RFC 9180 HPKE.
• FIPS 186-5 Digital Signature Standard.

14. Referência cruzada

• Ataques: 11-ataques.md (Bleichenbacher, ROCA, invalid curve, twist, Coppersmith).
• Protocolos que usam: 07-protocolos.md (TLS, SSH, Signal, IKE, OPAQUE).
• PQC sucessores: 08-pos-quantica.md (ML-KEM, ML-DSA, SLH-DSA).
• Pessoas: 12-pessoas.md (Diffie, Hellman, Rivest, Shamir, Adleman, Merkle, Koblitz, Miller, Bernstein, Boneh).