RSA

O RSA foi o primeiro criptossistema prático de chave pública e continua amplamente usado em assinaturas e certificados. Ele é também o exemplo mais claro de matemática pura virando infraestrutura crítica.

Geração de chaves

1. Escolha dois primos grandes e distintos $p$ e $q$ (1024 bits cada, para $n$ de 2048).
2. Calcule $n = pq$ e $\varphi(n) = (p-1)(q-1)$.
3. Escolha $e$ com $\gcd(e,\varphi(n))=1$. Na prática, $e = 65537$.
4. Calcule $d = e^{-1} \bmod \varphi(n)$ pelo algoritmo de Euclides estendido.

Chave pública: $(n, e)$. Chave privada: $(n, d)$, mais $p$, $q$ e os expoentes reduzidos para a otimização por CRT.

Cifragem e decifragem

$$c = m^e \bmod n, \qquad m = c^d \bmod n$$

com $0 \le m < n$.

Por que funciona

Como $ed \equiv 1 \pmod{\varphi(n)}$, existe $k$ com $ed = 1 + k\varphi(n)$. Então:

$$c^d = (m^e)^d = m^{ed} = m^{1+k\varphi(n)} = m\cdot\left(m^{\varphi(n)}\right)^k$$

Pelo teorema de Euler, $m^{\varphi(n)} \equiv 1 \pmod n$ quando $\gcd(m,n)=1$, logo $c^d \equiv m$. $\blacksquare$

(O caso $\gcd(m,n)>1$ também funciona, por um argumento via CRT sobre $p$ e $q$ separadamente.)

Por que é seguro

Recuperar $d$ a partir de $(n,e)$ exige $\varphi(n)$, que exige conhecer $p$ e $q$ — ou seja, fatorar $n$. Com $n$ de 2048 bits, isso está fora do alcance computacional clássico.

Note a assimetria que torna tudo possível: multiplicar $p$ por $q$ é trivial; recuperar $p$ e $q$ de $n$ é inviável. Essa é uma função de mão única, e é toda a base do sistema.

Vale registrar que a equivalência entre "quebrar RSA" e "fatorar" não está provada — apenas que fatorar quebra o RSA.

RSA puro é inseguro

Esta é a parte que costuma faltar nas explicações introdutórias. O RSA "livro-texto", exatamente como descrito acima, tem falhas graves:

Determinismo. A mesma mensagem sempre produz o mesmo criptograma. Um adversário pode cifrar candidatos e comparar — devastador para espaços de mensagem pequenos, como "sim"/"não" ou um número de cartão.

Maleabilidade. $ (m_1m_2)^e = m_1^e m_2^e $. É possível manipular o criptograma de forma previsível sem conhecer a chave.

Mensagens pequenas. Se $m^e < n$, não há redução modular e basta extrair a raiz $e$-ésima inteira. Com $e=3$ e mensagem curta, a quebra é imediata.

Ataques de canal lateral. Tempo de execução e consumo de energia vazam bits da chave.

A resposta é o preenchimento: OAEP para cifragem e PSS para assinatura. Eles introduzem aleatoriedade e estrutura verificável. O esquema antigo PKCS#1 v1.5 é vulnerável ao ataque de Bleichenbacher e não deve ser usado em código novo.

# NUNCA implemente RSA você mesmo. Use biblioteca auditada:
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes

chave = rsa.generate_private_key(public_exponent=65537, key_size=2048)
cifrado = chave.public_key().encrypt(
    b'mensagem',
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

Escolha de parâmetros

Parâmetro	Recomendação
Tamanho de $n$	Mínimo 2048 bits; 3072 para longo prazo
$e$	65537 — primo, com poucos bits 1, rápido de calcular
$p$, $q$	Aleatórios, de tamanhos próximos mas não iguais
Preenchimento	OAEP para cifrar, PSS para assinar

Erros de geração já causaram incidentes reais: em 2012, um estudo encontrou milhares de chaves na internet que compartilhavam um fator primo, por entropia insuficiente na geração. Um simples MDC entre pares de módulos públicos revelava as chaves privadas.

RSA na prática: cifragem híbrida

RSA é lento e limitado a mensagens menores que $n$. Nenhum sistema real cifra dados diretamente com ele. O padrão é cifragem híbrida:

1. Gera-se uma chave simétrica aleatória (AES).
2. Cifra-se a mensagem com AES.
3. Cifra-se apenas a chave AES com RSA.

É assim que TLS, PGP e S/MIME funcionam. Hoje, aliás, TLS usa preferencialmente troca de chaves por curvas elípticas (ECDHE), com RSA apenas na assinatura do certificado.

Assinatura digital

Inverte os papéis: assina-se com a chave privada e verifica-se com a pública.

$$s = H(m)^d \bmod n, \qquad \text{verificação: } s^e \equiv H(m) \pmod n$$

Assina-se o resumo da mensagem, não a mensagem — por eficiência e porque a mensagem pode exceder $n$. Usa-se PSS, e não a construção ingênua.

Comparação com curvas elípticas

Segurança	RSA	Curva elíptica
112 bits	2048	224
128 bits	3072	256
192 bits	7680	384

Chaves muito menores para a mesma segurança, com operações mais rápidas. É por isso que sistemas novos preferem Ed25519 e ECDSA. RSA permanece por compatibilidade e pela verificação de assinatura, que é rápida com $e$ pequeno.

Exemplo trabalhado

Com $p=61$, $q=53$ (valores de brinquedo):

$n = 3233$, $\varphi(n) = 60 \cdot 52 = 3120$.

Tomando $e = 17$, o inverso é $d = 2753$, pois $17 \cdot 2753 = 46801 = 15\cdot3120 + 1$.

Cifrando $m = 65$: $c = 65^{17} \bmod 3233 = 2790$.

Decifrando: $2790^{2753} \bmod 3233 = 65$. ✓

Erros comuns

• Implementar RSA à mão em produção.
• Usar RSA sem preenchimento ou com PKCS#1 v1.5 em código novo.
• Cifrar dados grandes diretamente, em vez de usar cifragem híbrida.
• Chave de 1024 bits, já considerada insuficiente.
• Entropia fraca na geração dos primos.
• Reutilizar primos entre chaves.
• Assinar sem resumo ou com função de resumo obsoleta.

Leituras recomendadas

• Katz e Lindell, Introduction to Modern Cryptography — o tratamento moderno, com definições de segurança precisas.
• Menezes et al., capítulo 8 — RSA e variantes, gratuito online.
• Boneh, "Twenty Years of Attacks on the RSA Cryptosystem" — panorama dos ataques conhecidos; leitura curta e esclarecedora.
• Documentação da libsodium — a filosofia de expor apenas construções seguras por padrão.

Jonathan Katz and Yehuda Lindell (2014). Introduction to Modern Cryptography. CRC Press. DOI: 10.1201/b17668. Alfred J. Menezes and Paul C. van Oorschot and Scott A. Vanstone (1996). Handbook of Applied Cryptography. CRC Press. ISBN 9781439821916. Victor Shoup (2009). A Computational Introduction to Number Theory and Algebra. Cambridge University Press. DOI: 10.1017/cbo9780511814549.

Referências

1. Jonathan Katz; Yehuda Lindell (2014). Introduction to Modern Cryptography. CRC Press.
2. Alfred J. Menezes; Paul C. van Oorschot; Scott A. Vanstone (1996). Handbook of Applied Cryptography. CRC Press.
3. Victor Shoup (2009). A Computational Introduction to Number Theory and Algebra. Cambridge University Press.