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 *í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 *roblema difícil*

Todos os clássicos (IFP, DLP, ECDLP) *uebram 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 *alph 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

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

Grupos padronizados (RFC 7919, 3526)

Ataques

• *aninthe-middle* DH não autentica. Sempre combine com assinatura ou autenticação prévia.
• *mall subgroup confinement* validar \(B^q \equiv 1 \mod p\) (ou usar safe primes).
• *ogjam*(2015): précomputação contra primos comuns DH1024; viável para state actor.
• *riple 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 *lifford 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).

*ublic key* \((N, e)\). *rivate key* \(d\) (ou \(p, q\)).

Encryption (textbook RSA — ❌ NUNCA use crua)

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

*or 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.
• *oppersmith attacks*com pequenas mensagens parcialmente conhecidas.

Padding seguro

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

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

*KCS#1 v1.5 padding*— antigo, vulnerável a *leichenbacher 1998*(padding oracle).

RSA-PSS para assinaturas

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

*tatus* PKCS#1 v1.5 signing *inda*é 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 *istintos* ambos primos, \(|p - q|\) não muito pequeno (Fermat factoring), entropia adequada.
• \(|N| \in \{2048, 3072, 4096\}\).
• *OCA*(CVE201715361, Infineon): geração defeituosa em milhões de chaves de smartcardsTPMsEstonian eID. Quebrável por algoritmo Coppersmith específico.
• *ining your Ps and Qs*(Heninger et al. 2012): chaves SSH/SSL com primos compartilhados por entropy starvation no boot.

Velocidade

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

Tamanhos equivalentes

*ecomendaçã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)

*aher 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 *SA*(Digital Signature Algorithm, FIPS 186, 1991).

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

5. DSA / ECDSA / EdDSA

DSA (FIPS 186, 1991)

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

*ssinatura*de mensagem \(m\) com chave privada \(x\):

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

*erify* \(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.

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

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

*itigação* *FC 6979*— deterministic nonces via HMAC. Padrão moderno.

EdDSA (Bernstein 2011, RFC 8032)

Schnorrstyle + Curve25519 (Ed25519) ou Curve448 (Ed448). *eterminístico*sem RFC 6979 (nonce derivado de hash de chave + msg). *onstanttime* *em pontos especiais* *em ambiguidade de codificação*

*d25519*

• 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).

*d448* 56-byte pubkey, ~224 bit security. Mais lento.

*tatus* 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. *atenteado até 2008* Bitcoin adotou via *aproot*(BIP340, ativado nov/2021) — assinaturas Schnorr + *uSig*(aggregation).

BLS signatures (BonehLynnShacham, 2001)

Pairingbased em curvas elípticas com pairing (BLS12381, BN curves). Assinaturas *gregá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 *eal Koblitz*(1985, Elliptic Curve Cryptosystems, Math. Comp.) e *ictor 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 *uito menor*que RSA.

Curvas padronizadas

NIST (FIPS 186, SEC 2)

*ontrovérsia* seed das curvas NIST gerado por hash de string nãopú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

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

*antagens*

• 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

*ecp256k1*— curva sem características aleatórias visíveis, mais rápida que P256 para algumas operações. NãoNIST. Adotada por Bitcoin, Ethereum.

Pairing-friendly

*LS12381* *N254* *N382* *LS12377*— 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)

*ybrid* 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 180332, SEC 1. Variantes: ECIES, ECIESKEM, ChaCha20Poly1305Curve25519 (libsodium crypto_box_seal).

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

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

8. Identity-Based Encryption (IBE)

Conceito proposto por *hamir 1984* primeira impl prática *oneh-Franklin 2001*com pairings.

Chave pública = string (email, telefone). Não precisa PKI tradicional. *ey 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.

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

Threshold signatures

• *hreshold RSA* Shoup 2000.
• *hreshold Schnorr* Stinson-Strobl 2001, *ROST*(Komlo + Goldberg 2020).
• *hreshold BLS* trivial pela linearidade.
• *hreshold 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

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

13. Bibliografia

• *ankerson, Menezes, Vanstone* Guide to Elliptic Curve Cryptography, Springer 2004.
• *ilverman* The Arithmetic of Elliptic Curves, Springer 1986 (math).
• *ernstein*papers sobre Curve25519, Ed25519, qhasm.
• *ernstein + Lange* SafeCurves (safecurves.cr.yp.to) — checklist para escolher curva.
• *FC 8032*EdDSA, *FC 7748*X25519, *FC 8446*TLS 1.3, *FC 9180*HPKE.
• *IPS 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 (MLKEM, MLDSA, SLH-DSA).
• Pessoas: 12-pessoas.md (Diffie, Hellman, Rivest, Shamir, Adleman, Merkle, Koblitz, Miller, Bernstein, Boneh).