RSA: Criptografia de Brinquedo

Escolha dois primos, digite uma mensagem e veja o RSA criptografá-la e depois decriptografá-la.

Exemplo resolvido — RSA: Criptografia de Brinquedo

Chave privada (n, d)	1783

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — RSA: Criptografia de Brinquedo

O RSA é uma só operação usada duas vezes. Cifrar é m^e mod n e decifrar é c^d mod n — a mesma exponenciação modular, com outro expoente. O truque está em escolher o par de modo que aplicá-lo duas vezes devolva a mensagem, enquanto conhecer um dos expoentes nada diz sobre o outro. Tudo o que o painel imprime é a procura desse par. Publicado por Rivest, Shamir e Adleman em 1978 — e, como só se soube quando o GCHQ o desclassificou em 1997, descoberto quatro anos antes por Clifford Cocks e deixado numa gaveta.

O que significa cada símbolo

n: o módulo, p·q. Público. O segredo são os seus fatores, não o número em si.
φ(n): a função φ de Euler, (p−1)(q−1). O painel consegue imprimi-la porque lhe deram p e q; um atacante com apenas n não consegue, e passar de n a φ é tão difícil como fatorizar.
e: o expoente público. Serve qualquer número coprimo com φ(n), e é por isso que muda quando mudas um primo.
d: o expoente privado, e⁻¹ mod φ(n). Um único inverso modular — imediato se souberes φ, e todo o jogo se não souberes.

De onde vem a fórmula

Multiplica os primos: n = p·q. Nos valores por omissão, 61 · 53 = 3233. Esse número é publicado. Recuperar 61 e 53 a partir de 3233 leva um instante à mão, e é essa a razão honesta para isto se chamar brinquedo.
Calcula φ(n) = (p−1)(q−1) = 60 · 52 = 3120. É o eixo de todo o esquema: n é público e φ(n) não é, e o único caminho conhecido de um para o outro passa pela fatorização.
Escolhe e coprimo com φ(n) e resolve e·d ≡ 1 (mod φ(n)) em ordem a d. O painel mostra 7⁻¹ mod 3120 = 1783. Repara no que esse passo não é: não é difícil. Sabendo φ, é um só inverso modular. O sigilo de d assenta inteiramente no sigilo de φ.
Porque é que a ida e volta resulta: por construção e·d = 1 + kφ(n), logo m^ed = m^1+kφ(n) ≡ m (mod n) — o teorema de Euler. Decifrar não é uma operação inversa inventada à parte; é a mesma exponenciação, com o expoente que desfaz a primeira.

Como ler o que vê

A linha que vale a pena vigiar é e, porque não é uma constante. Com os primos por omissão marca 7; muda p para 67 e passa a 5. A razão está na linha acima: e tem de ser coprimo com φ(n), e φ passou de 3120 para 3432. Compara depois os dois expoentes no ecrã — e = 7 contra d = 1783. O público é minúsculo e o privado não é, e nenhuma das duas coisas é acaso: e é escolhido pequeno de propósito para cifrar sair barato, e d é o que o inverso der. A última linha é a prova de que correu bem: m′ = 42, o número que escreveste.

Pressupõe: Que a mensagem é um número menor do que n. Com n = 3233 não há nada para cifrar acima de 3232 — por isso o RSA real nunca cifra uma mensagem diretamente: cifra uma chave simétrica preenchida de umas centenas de bits e deixa uma cifra mais rápida transportar o texto. Assume também p ≠ q, e que nunca reutilizas um primo num segundo módulo: dois módulos que partilham um fator ficam ambos quebrados por um único máximo divisor comum.
Falha quando: Podes quebrar esta página sem fatorizar nada. Põe p = 67, q = 53 e a mensagem a 3. O painel escolhe e = 5 e imprime como cifra 243 — que é apenas 3⁵. Como 3⁵ é menor do que n = 3551, a redução modular nunca aconteceu: a cifra é uma potência vulgar, e a raiz quinta de 243 é 3. Sem chave, sem fatorizar, mensagem recuperada. Experimenta m = 5 e obténs 3125, que é 5⁵; em m = 8 a potência ultrapassa finalmente n e a cifra torna-se um inútil 809. Isto não é um defeito desta página — é a razão por que ninguém cifra um número nu. O RSA real preenche primeiro a mensagem com aleatoriedade estruturada, que é o que a RFC 8017 especifica e o que faz de uma exponenciação um criptossistema.

A chave privada é derivada, não escolhida 🖖

Veja o painel construir d. Com os primos padrão ele mostra φ(n) = 60 · 52 = 3120, depois recorre a e = 7 — seu 65537 preferido é aqui maior que a própria φ — e por fim calcula d ≡ 7⁻¹ mod 3120 = 1783. Esse último passo é um único inverso modular, instantâneo em qualquer máquina. Nada em d é secreto por si só: ele sai direto de φ(n), e φ(n) sai direto de p e q. Portanto o RSA não esconde o expoente privado, ele esconde a fatoração. Aqui n = 3233, que um laptop quebra antes de você terminar esta frase; um módulo RSA-2048 tem 617 dígitos decimais, e todos os passos na tela são no mais idênticos.

O cadeado que só você abre 🖖

O RSA dá a todos um cadeado aberto (sua chave pública) que qualquer um pode fechar em torno de uma mensagem, mas só sua chave privada consegue reabri-lo. Como fechar e abrir usam chaves diferentes, você pode publicar a chave pública à vista de todos sem revelar como descriptografar. Esta ferramenta deixa você percorrer o ciclo inteiro com primos minúsculos; sistemas reais usam os mesmos passos com números de centenas de dígitos.

Cifrar ao contrário é assinar 🖖

A mesma operação do RSA, executada no sentido inverso, prova quem enviou uma mensagem em vez de escondê-la. Se você "descriptografa" uma mensagem com sua chave privada, qualquer um pode "criptografá-la" de volta com sua chave pública para conferir que ela veio mesmo de você - isso é uma assinatura digital. Assim, uma única conta matemática sustenta tanto a confidencialidade quanto a autenticação, só trocando qual chave vem primeiro.

Problemas resolvidos na íntegra

Um par de chaves RSA para p = 61 e q = 53 5 passos
Gere o par de chaves RSA para p = 61 e q = 53 e cifre m = 42. Todos os números abaixo decorrem desses três, incluindo o expoente público.
1. O módulo é publicado e a função totiente é destruída, contudo ambos estão à distância de uma multiplicação dos números primos. φ(n) conta os inteiros inferiores a n que não partilham nenhum fator com ele, o que para um produto de dois primos distintos é (p − 1)(q − 1).
  
  $n = 61 \cdot 53 = 3233, ϕ (n) = (61 - 1) (53 - 1) = 60 \cdot 52 = 3120$
2. O expoente público tem de ser invertível módulo φ, o que significa coprimo em relação a ele. Fatorize-se φ e os candidatos pequenos eliminam-se a si mesmos, deixando 7 como o menor expoente ímpar disponível. As chaves reais usam 65537, mas isso é maior do que este φ, pelo que a ferramenta recorre ao menor coprimo.
  
  $3120 = 2^{4} \cdot 3 \cdot 5 \cdot 13 ⟹ g cd (3, ϕ) = 3, g cd (5, ϕ) = 5, g cd (7, ϕ) = 1 ⟹ e = 7$
3. Inverter 7 módulo 3120 é o algoritmo de Euclides estendido e nada mais. Três divisões chegam a um resto de 1, e inverter o percurso dessas mesmas três linhas escreve esse 1 como uma combinação de 3120 e 7.
  
  $3120 = 445 \cdot 7 + 5, 7 = 1 \cdot 5 + 2, 5 = 2 \cdot 2 + 1 ⟹ 1 = 3 \cdot 3120 - 1337 \cdot 7$
4. O coeficiente de 7 nessa combinação é negativo, e um inverso negativo torna-se positivo somando o módulo uma vez. A cifragem é então uma única exponenciação modular, efetuada elevando ao quadrado duas vezes em vez de multiplicar 42 por si mesmo sete vezes.
  
  $d \equiv - 1337 \equiv 1783 (mod 3120), c = 4 2^{4} \cdot 4 2^{2} \cdot 42 = 1550 \cdot 1764 \cdot 42 \equiv 240 (mod 3233)$
5. A decifragem nunca precisa de ser verificada por força bruta e, para tamanhos de chave realistas, nem seria possível. Os dois expoentes foram construídos de modo a que o seu produto seja uma unidade superior a um múltiplo de φ, e o teorema de Euler conclui a prova para qualquer m coprimo com n — o que 42 é.
  
  $e d = 7 \cdot 1783 = 12481 = 4 \cdot 3120 + 1 ⟹ c^{d} \equiv m^{e d} = m (m^{ϕ})^{4} \equiv m = 42$
Resposta

A ferramenta apresenta n = 3233, φ = 3120, d = 1783 e c = 240, e confirma que 240 é decifrado de volta para 42. A parte que vale a pena reter é o que φ realmente é. Não é um segundo segredo ao lado de p e q — é o mesmo segredo escrito de forma diferente. Dados n e φ, obtém-se p + q = n − φ + 1 = 114 e pq = 3233, uma equação do segundo grau cujo discriminante é um quadrado perfeito, a qual devolve 61 e 53 numa única linha. Portanto, um gerador de chaves que revele φ revelou a fatorização tão completamente como se tivesse impresso os primos, razão pela qual φ é calculado uma vez, usado para encontrar d e depois descartado.

$p + q = n - ϕ + 1 = 114, pq = 3233 ⟹ x^{2} - 114 x + 3233 = 0 ⟹ x = 61, 53$
Fatorizar 3233 em 61 × 53 para derrotar a segurança RSA 6 passos
O painel fatoriza 3233 em 61 × 53 antes de acabar de ler a página. Essa fatorização é toda a segurança do RSA, aparentemente quebrada num instante. Calcule o que torna o mesmo problema impossível um tamanho de chave acima.
1. Os dois números de que o painel parte: o módulo, e a função de Euler que decorre dos dois primos.
  
  $n = 61 \times 53 = 3233, ϕ (n) = 60 \times 52 = 3120$
2. Um atacante precisa de um único facto: o primo menor não pode exceder a raiz quadrada do módulo. Qualquer coisa maior precisaria de um parceiro mais pequeno do que ele próprio.
  
  $p \leq n ⟹ 3233 = 56.86, π (56) = 16$
3. A busca percorre então os primos até 56, e há dezasseis. O décimo sexto é 53. Dezasseis divisões não são segurança, são um erro de arredondamento.
  
  $53 < 56.86 \in {2, 3, 5, \dots, 53} ⟹ k \leq 16$
4. Meta agora um módulo que alguém use a sério. 2048 bits significa n perto de 2²⁰⁴⁸, e a sua raiz quadrada é 2¹⁰²⁴, cerca de 10³⁰⁸.
  
  $n \approx 2^{2048} ⟹ n = 2^{1024} \approx 1 0^{308}$
5. Ponha-lhe um preço. A mil milhões de divisões por segundo, são 10²⁹⁹ segundos — contra um universo com cerca de 4 × 10¹⁷ segundos.
  
  $\frac{1 0 ^{308}}{1 0 ^{9} s ^{- 1}} = 1 0^{299} s \approx 1 0^{291} yr$
6. O tempo é a unidade errada para um número destes; compare-o antes com algo físico.
  
  $1 0^{308} ⋙ 1 0^{80}$
Resposta

Dezesseis divisões contra 10³⁰⁸. Como 10³⁰⁸ equivale a 10²²⁸ vezes o número de átomos no universo observável, seria impossível sequer armazenar o contador. A parte útil é a forma, e não o tamanho: o trabalho do atacante cresce como √n, enquanto a chave cresce como log n. Assim, cada dois bits adicionais de chave duplicam o custo de quebrá-la e custam dois bits ao defensor. Essa assimetria é o sistema em si. A resposta instantânea da ferramenta não é uma falha na demonstração — ela é a própria demonstração, porque 3233 é o aspecto de um módulo quando a assimetria não ganha espaço para atuar.

$16 ⟷ 1 0^{308}; O (n), n = 2^{2048}$

Referências (4)

The idea RSA is an instance of — public keys, two years earlier: W. Diffie & M. Hellman, "New directions in cryptography." IEEE Transactions on Information Theory 22(6), 644–654, 1976.
What real RSA wraps round the message, and why the bare exponentiation on this page is not a cryptosystem: K. Moriarty (Ed.), B. Kaliski, J. Jonsson & A. Rusch, "PKCS #1: RSA Cryptography Specifications Version 2.2." RFC 8017, November 2016 — RSAES-OAEP in §7.1.
The scheme the tool walks through, including e·d ≡ 1 mod φ(n): R. L. Rivest, A. Shamir and L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems." Communications of the ACM 21(2), 120–126, 1978.
Why the security rests on factoring rather than on hiding d: A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, §8.2. CRC Press, 1996. ISBN 978-0-8493-8523-0.

Pela equipa 42Math · Atualizado 2026-08-17

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Computação →

Problemas de exemplo

p=61, q=53 - p=61, q=53: RSA clássico de livro-texto
Primos minúsculos - p=7, q=11: primos minúsculos, fáceis de acompanhar
Primos maiores - p=101, q=103: espaço de chaves maior
Exemplo de livro didático - p=17, q=19: exercício de livro-texto