Criptografia de chave pública

Misturar é fácil; separar é impossível

Alice e Bob querem uma cor secreta em comum, mas só podem trocar potes de tinta na frente de todo mundo. Começam com uma tinta amarela pública. Cada um mistura, em segredo, uma cor própria e envia o resultado. Ao receber o pote do outro, cada um mistura de novo a sua cor secreta — e os dois chegam à mesma mistura final.

Quem interceptou os potes tem amarelo, a mistura de Alice e a de Bob. Para chegar ao segredo, teria que separar as tintas — e separar é incomparavelmente mais difícil que misturar. Essa assimetria, que na tinta é física, na matemática é a exponenciação modular: calcular g^a mod p é instantâneo, e desfazê-lo é o problema do logaritmo discreto.

Diffie-Hellman e RSA com números que cabem na tela

Mexa nos segredos de Alice e de Bob e confirme que os dois chegam sempre ao mesmo número — sem nunca o transmitirem. Depois veja a espiã resolver o logaritmo discreto por força bruta em 22 tentativas, e imagine isso com um número de 617 dígitos. Na segunda aba, o RSA completo com p = 11 e q = 13.

Diffie-Hellman

# Diffie-Hellman (1976): combinar um segredo em público.
# Públicos, à vista de todos: um primo p e uma base g.

p = 23; g = 5

# Cada lado sorteia um segredo que NUNCA sai da máquina
a = 6                      # só Alice sabe
b = 15                     # só Bob sabe

# Cada um envia g^segredo mod p — isto viaja pela rede
A = pow(g, a, p)           # 5^6  mod 23 = 8   → vai para Bob
B = pow(g, b, p)           # 5^15 mod 23 = 19  → vai para Alice

# Cada um eleva o que recebeu ao próprio segredo
s_alice = pow(B, a, p)     # 19^6 mod 23 = 2
s_bob   = pow(A, b, p)     # 8^15 mod 23 = 2
# Iguais! Porque (g^b)^a = g^(ab) = (g^a)^b — só isso.

# A espiã tem p, g, A e B. Para achar o segredo ela precisa
# resolver o LOGARITMO DISCRETO: dado 5^a mod 23 = 8, quanto vale a?
# Com p = 23 ela testa 22 valores. Com p de 2048 bits, não existe
# algoritmo conhecido que termine antes do fim do universo —
# enquanto calcular pow(g, a, p) leva microssegundos.

# É uma função de mão única com PORTA DOS FUNDOS: fácil de calcular,
# inviável de inverter, MAS trivial para quem conhece o segredo.

RSA

# RSA (1977): a outra assimetria — multiplicar é fácil, fatorar não.

# 1. Dois primos grandes e SECRETOS
p, q = 11, 13                # na prática, ~1024 bits cada
n = p * q                     # 143 — este é público
phi = (p-1) * (q-1)          # 120 — secreto (depende de p e q)

# 2. Um expoente público e, coprimo com phi
e = 7                         # na prática quase sempre 65537

# 3. O expoente privado é o inverso de e módulo phi
d = pow(e, -1, phi)            # 103, pois 7 × 103 = 721 = 6×120 + 1

# CHAVE PÚBLICA:  (n=143, e=7)    → pode ir para o mundo inteiro
# CHAVE PRIVADA:  (d=103)         → e p, q, que devem ser destruídos

# Cifrar (qualquer um pode) e decifrar (só quem tem d)
c = pow(m, e, n)              # 42^7   mod 143 = 81
m = pow(c, d, n)              # 81^103 mod 143 = 42

# Funciona porque m^(e·d) ≡ m (mod n) — consequência do
# pequeno teorema de Fermat, já que e·d ≡ 1 (mod phi).

# A segurança: para achar d é preciso conhecer phi, e para conhecer
# phi é preciso FATORAR n de volta em p e q. Fatorar 143 você faz
# de cabeça; fatorar um n de 617 dígitos, ninguém sabe fazer.

# ⚠ Este é o "RSA de livro" e é INSEGURO: determinístico (cifrar a
# mesma mensagem dá sempre o mesmo resultado) e maleável. O RSA real
# usa preenchimento aleatório OAEP. Nunca implemente isto à mão.

O sistema híbrido, e as curvas elípticas

# Por que ninguém cifra dados com RSA.
#
# RSA é ~1000x mais lento que AES e só cifra mensagens menores que n.
# A solução universal é o SISTEMA HÍBRIDO:
#
#   1. sorteie uma chave AES aleatória para esta sessão
#   2. cifre os DADOS com AES          ← rápido, sem limite de tamanho
#   3. cifre a CHAVE AES com RSA       ← 32 bytes, custo irrelevante
#   4. envie os dois
#
# A criptografia assimétrica resolve a DISTRIBUIÇÃO da chave.
# A simétrica faz o trabalho pesado. É assim em TLS, PGP, Signal,
# SSH — em tudo. As duas famílias não competem: elas se completam.

# CURVAS ELÍPTICAS: o padrão moderno
#   Mesma ideia de mão única, com outra estrutura matemática.
#   Segurança equivalente com chaves MUITO menores:
#
#     RSA 2048 bits  ≈  ECC 224 bits
#     RSA 3072 bits  ≈  ECC 256 bits
#     RSA 15360 bits ≈  ECC 512 bits
#
#   Menos bytes na rede, menos CPU, chaves que cabem num QR code.
#   X25519 para troca de chaves, Ed25519 para assinaturas — são o
#   padrão de fato hoje em SSH, Signal, WireGuard e TLS 1.3.

A ameaça quântica

# A ameaça no horizonte.
#
# O algoritmo de SHOR (1994) fatora inteiros e resolve logaritmos
# discretos em tempo POLINOMIAL — num computador quântico grande
# o bastante. Isso quebraria, de uma só vez:
#   . RSA          (fatoração)
#   . Diffie-Hellman e curvas elípticas (logaritmo discreto)
#
# Ou seja: TODA a criptografia assimétrica em uso hoje.
#
# A simétrica sofre bem menos. O algoritmo de GROVER acelera a
# busca por raiz quadrada: 2^256 vira 2^128 — ainda inviável.
# Por isso a recomendação é simplesmente dobrar as chaves:
# AES-256 e SHA-512 seguem seguros.

# "COLHER AGORA, DECIFRAR DEPOIS" — por que isso já importa hoje.
# Um adversário pode gravar tráfego cifrado HOJE e guardá-lo até
# ter a máquina que o decifre. Para um segredo que precisa durar
# 20 anos, a ameaça quântica é um problema do PRESENTE.

# A resposta: criptografia PÓS-QUÂNTICA — problemas matemáticos
# diferentes (reticulados, códigos corretores, hashes), que rodam
# em computadores comuns e resistem a Shor. O NIST padronizou em
# 2024: ML-KEM (troca de chaves) e ML-DSA (assinaturas).
# A migração já começou: navegadores e o Signal já usam modos
# HÍBRIDOS, combinando X25519 com ML-KEM — se um dos dois cair,
# o outro ainda protege.

Experimentando

Mini projeto: implemente Diffie-Hellman com números pequenos e escreva a espiã. Dado p, g e A, ache a por força bruta e cronometre. Depois aumente p progressivamente — 2¹⁶, 2²⁴, 2³² — e plote o tempo do ataque contra o tempo de calcular pow(g, a, p). Uma curva sobe exponencialmente e a outra fica praticamente plana: é o gráfico da criptografia moderna inteira.

Projeto principal: construa um sistema híbrido completo, usando a biblioteca cryptography do Python. Gere um par RSA (ou X25519), e implemente enviar(mensagem, chave_publica) que sorteia uma chave AES, cifra os dados com AES-GCM, cifra a chave AES com a chave pública e devolve o pacote. Do outro lado, receber() desfaz tudo. Depois meça: cifre 100 MB e compare o tempo da parte assimétrica com o da simétrica. A proporção explica sozinha por que ninguém cifra dados com RSA.

Desafio extra: implemente o ataque man-in-the-middle contra Diffie-Hellman sem autenticação. Escreva três processos — Alice, Bob e Mallory no meio — em que Mallory negocia uma chave com cada lado e retransmite as mensagens, lendo e alterando o conteúdo. Alice e Bob não devem perceber nada. Depois adicione assinaturas às mensagens do handshake e mostre o ataque falhar. Essa é a demonstração mais clara de por que "está cifrado" e "está seguro" não são a mesma coisa.

Teste sua intuição

Onde você encontra isso