RSA: a matemática que protege a internet

Toda vez que você acessa um site com HTTPS, o cadeado no browser tá dizendo: "a conexão é segura". Por trás disso, em algum momento, RSA (ou algo baseado nele) rodou. Duas chaves: uma pública, que qualquer um pode ver, e uma privada, que só o servidor conhece. Uma tranca, a outra destranca.

Esse post abre a matemática por trás disso.

O problema

Você quer mandar uma mensagem secreta pra alguém que nunca viu na vida. Sem se encontrar antes, sem combinar uma senha.

Com criptografia simétrica, as duas pontas usam a mesma chave. Funciona, mas tem um problema: como combinar essa chave sem que alguém no meio intercepte?

A sacada da criptografia assimétrica: são duas chaves diferentes. Uma tranca, a outra destranca. Você publica a chave de trancar pro mundo inteiro. Qualquer pessoa pode trancar uma mensagem pra você. Mas só você tem a chave que destranca.

É como um cadeado aberto que você manda pelo correio. Qualquer um pode fechar, mas só você tem a chave pra abrir.

Números primos

RSA começa com dois números primos grandes. Primos são números que só dividem por 1 e por eles mesmos: 2, 3, 5, 7, 11, 13...

Por que primos? Porque multiplicar dois primos é fácil:

61 × 53 = 3233

Qualquer calculadora faz isso. Mas dado 3233, descubra quais dois primos foram multiplicados. Com número pequeno, você testa na mão. Com um número de 600 dígitos, todos os computadores do mundo juntos não conseguem.

Fácil pra um lado, impossível pro outro. É nisso que o RSA se apoia.

Aritmética modular

Antes de montar as chaves, precisa entender uma operação: $\bmod$ . É o resto da divisão.

17 mod 5 = 2    (17 ÷ 5 = 3, sobra 2)
23 mod 7 = 2    (23 ÷ 7 = 3, sobra 2)

Pensa num relógio. Se são 10h e passam 5 horas, é 15h? No relógio de 12h, volta pro 3. Isso é $15 \bmod 12 = 3$ .

Aritmética modular é o que faz o RSA funcionar. Ela cria uma espécie de "caixa de sentido único": dado $c = m^e \bmod n$ , saber $c$ , $e$ e $n$ não te dá $m$ de volta. A não ser que você tenha uma informação extra (a chave privada).

Totiente de Euler — $\varphi(n)$

Dado um número $n$ , $\varphi(n)$ conta quantos números menores que $n$ são coprimos com $n$ (ou seja, não compartilham nenhum fator além de 1).

Pra um primo $p$ , $\varphi(p) = p - 1$ . Todos os números menores que um primo são coprimos com ele.

Pra o produto de dois primos, $n = p \times q$ :

$\varphi(n) = (p - 1)(q - 1)$

Essa fórmula só funciona se você souber $p$ e $q$ . Se só tiver $n$ , precisa fatorar — e esse é exatamente o problema difícil.

Gerando as chaves

Passo a passo com números pequenos (na prática usam-se primos de centenas de dígitos):

1. Escolha dois primos:

$p = 61, \quad q = 53$

2. Calcule n:

$n = p \times q = 61 \times 53 = 3233$

3. Calcule $\varphi(n)$ :

$\varphi(n) = (p - 1)(q - 1) = 60 \times 52 = 3120$

4. Escolha e (expoente público):

$e$ precisa ser coprimo com $\varphi(n)$ . Um valor comum é $e = 17$ .

$\gcd(17, 3120) = 1 \quad \checkmark$

5. Calcule d (expoente privado):

$d$ é o inverso modular de $e \bmod \varphi(n)$ . Ou seja, o número tal que:

$e \times d \equiv 1 \pmod{\varphi(n)}$

$17 \times d \equiv 1 \pmod{3120}$

$d = 2753$

Verificação: $17 \times 2753 = 46801 = 15 \times 3120 + 1$ . Bate.

Chave pública: $(e=17, n=3233)$ — essa você publica. Chave privada: $(d=2753, n=3233)$ — essa fica com você.

Encriptando e decriptando

Com as chaves prontas:

Encriptar (qualquer um pode fazer, usando a chave pública):

$c = m^e \bmod n$

Decriptar (só quem tem a chave privada):

$m = c^d \bmod n$

Exemplo com $m = 42$ :

$c = 42^{17} \bmod 3233 = 2557$

$m = 2557^{2753} \bmod 3233 = 42$

O número volta. Sempre.

message (2-3232):

1/5

Por que funciona? Por causa do Pequeno Teorema de Fermat e sua generalização por Euler: $m^{\varphi(n)} \equiv 1 \pmod{n}$ quando $m$ e $n$ são coprimos. Como $e \times d \equiv 1 \pmod{\varphi(n)}$ , a exponenciação "dá a volta" e recupera o valor original.

Por que é seguro

Com nosso exemplo, $n = 3233$ . Você fatorar isso na mão é trivial. Mas na prática, RSA usa chaves de 2048 ou 4096 bits. O $n$ tem mais de 600 dígitos decimais.

Fatorar um número desse tamanho é o gargalo. O melhor algoritmo que existe (General Number Field Sieve) é sub-exponencial, mas ainda absurdamente lento pra números grandes.

Pra ter noção de escala:

RSA-768 (232 dígitos) foi fatorado em 2009. Levou 2 anos com centenas de máquinas.
RSA-2048 (617 dígitos) nunca foi fatorado. Estimativas conservadoras falam em milhões de anos com a tecnologia atual.

Computadores quânticos mudam esse cenário. O algoritmo de Shor fatora em tempo polinomial. Por isso já existem padrões pós-quânticos (como CRYSTALS-Kyber). Mas RSA clássico ainda é seguro contra computadores convencionais.

RSA na prática

Ninguém encripta dados grandes com RSA. É lento demais, ordens de magnitude mais lento que AES.

O que acontece de verdade numa conexão TLS (simplificado):

Seu browser e o servidor fazem o handshake
RSA (ou variante) encripta uma chave simétrica temporária
O resto da comunicação usa essa chave simétrica (AES)

RSA só protege a troca de chaves. Os dados em si são encriptados com criptografia simétrica, que é muito mais rápida.

Outra aplicação: assinaturas digitais. Em vez de encriptar a mensagem, você encripta o hash dela com sua chave privada. Qualquer um pode verificar com sua chave pública. Se o hash bate, a mensagem não foi alterada e veio de você.

Multiplicar dois primos é fácil. Descobrir quais primos foram multiplicados é difícil. Toda conexão HTTPS depende disso.