RSA: criptografia de chave pública

RSA: criptografia de chave pública

Imagine que você precisa receber uma mensagem secreta de alguém com quem nunca falou. Se os dois precisam combinar uma senha antes, alguém pode interceptá-la. A criptografia de chave pública resolve isso com um par de chaves: uma pública, que pode ser divulgada, e uma privada, que fica só com o dono.

O RSA, criado em 1977 por Ron Rivest, Adi Shamir e Leonard Adleman, é o exemplo mais conhecido. Esta aula usa números pequenos para você ver a matemática por dentro. Na prática, os primos têm centenas de dígitos.

A receita

1. Escolha dois primos distintos, p e q, e calcule n = p · q.
2. Calcule φ(n) = (p − 1)(q − 1), o número de inteiros de 1 a n que são primos com n.
3. Escolha um expoente público e, com 1 < e < φ(n) e mdc(e, φ(n)) = 1.
4. Calcule a chave privada d, o inverso de e módulo φ(n): e · d ≡ 1 (mod φ(n)).
5. Cifre a mensagem m com c = mᵉ mod n. Decifre com m = cᵈ mod n.

A chave pública é o par (e, n), e a privada é (d, n). Para o exemplo clássico, p = 61 e q = 53 dão n = 3233 e φ(n) = 3120. Com e = 17, a chave privada é d = 2753. A mensagem 65 vira 2790 e volta a 65.

Por que funciona?

O ponto central é o teorema de Euler: se mdc(m, n) = 1, então m^φ(n) ≡ 1 (mod n). Como e · d = 1 + k · φ(n) para algum k, temos:

(mᵉ)ᵈ = m^(ed) = m^(1 + kφ(n)) = m · (m^φ(n))ᵏ ≡ m · 1ᵏ = m (mod n)

Assim, decifrar desfaz a cifragem. O mesmo resultado vale para todo m de 0 a n − 1, inclusive quando m tem fator comum com n (o caso é tratado separadamente na teoria, mas não atrapalha a conta).

Por que é seguro?

Quem conhece (e, n) pode calcular d se souber φ(n). E φ(n) = (p − 1)(q − 1) só é fácil de calcular se você já conhece p e q. Portanto, o problema central é fatorar n. Para n = 3233, basta tentar divisores até 53: são poucas tentativas. Para n com 600 dígitos, nenhum método conhecido fatora em tempo razoável. Esse é o motivo de o RSA usar primos grandes.

A aula mostra a quantidade de tentativas por divisão de tentativa, que cresce com o menor primo de n. É um cálculo pequeno, para dar a noção da escala.

Aplicações

• HTTPS: quando seu navegador abre um banco, o servidor apresenta um certificado com sua chave pública, que serve para verificar a identidade dele. A conversa é cifrada com chaves temporárias combinadas durante o acesso; em versões modernas do protocolo, essa combinação usa outra técnica, não o RSA.
• Assinaturas digitais: quem tem a chave privada assina, e qualquer um confere com a pública.
• Verificação de software: atualizações assinadas garantem que o programa veio de quem diz ser o autor.

Na prática, o RSA costuma cifrar uma chave simétrica, e não a mensagem inteira, porque é mais lento.

Curiosidades

• A mesma ideia foi descoberta antes, de forma secreta, no GCHQ britânico: Clifford Cocks chegou ao método em 1973, mas o trabalho ficou classificado até 1997.
• Diffie e Hellman publicaram em 1976 o conceito de troca de chaves pública, e o RSA foi um dos primeiros métodos práticos de cifragem com chave pública.
• Em 1977, Martin Gardner publicou um desafio de decifragem com um número de 129 dígitos. A fatoração só foi concluída em 1994, após anos de trabalho distribuído.