As chaves
Como se encontra d: o algoritmo de Euclides estendido
Cada linha divide as duas linhas acima dela. Na linha com resto 1, a última coluna é d (some φ(n) se for negativo).
| Quociente | Resto | Coeficiente de e |
|---|
A mensagem
Enviado pela rede
| Bit | Quadrado | Multiplicar por m |
|---|
Quebrar a chave
Demonstração da cifragem RSA
O RSA permite que qualquer pessoa tranque uma mensagem com a sua chave pública, enquanto só você a pode abrir com a sua chave privada. Por trás estão umas poucas linhas de aritmética escolar: dois números primos, uma multiplicação, um resto e um inverso engenhoso. Construa um par de chaves a partir de primos à sua escolha, cifre e decifre uma mensagem carácter a carácter, assine-a para que qualquer pessoa possa verificar que veio de si e depois faça de atacante e fatorize n para ver porque é que as chaves reais precisam de centenas de algarismos. Escolha dois números primos p e q, ou prima Novos primos. A aplicação constrói a chave pública (e, n) e a chave privada d, e mostra como o algoritmo de Euclides estendido encontra d. Escreva uma mensagem: cada carácter é cifrado com a chave pública e decifrado com a chave privada. Clique numa linha para ver a potência calculada por quadrados sucessivos. Mude para Assinar para, em vez disso, assinar com a chave privada, e prima Fatorizar n para ver com que rapidez as chaves pequenas são quebradas.
Como funciona
- Introduza dois primos p e q, ou escolha um tamanho e prima Novos primos; a aplicação calcula n, φ(n), e e d, e mostra como se encontra d.
- Escreva uma mensagem e escolha Cifrar ou Assinar. Cada carácter é transformado num número e elevado a uma potência mod n; clique numa linha para ver os quadrados sucessivos.
- Prima Fatorizar n para deixar Eve decompor n nos seus dois primos e recuperar a chave privada.
Como funcionam as chaves
Multiplique dois primos: n = p × q. Com p = 61 e q = 53, n = 3233. O número φ(n) = (p − 1)(q − 1) = 3120 conta os números menores do que n que não têm nenhum fator em comum com ele, e só pode ser calculado por quem conhece p e q. Escolha e = 17, que não tem nenhum fator em comum com 3120, e encontre d tal que e × d seja 1 mais do que um múltiplo de φ(n): aqui d = 2753, porque 17 × 2753 = 46801 = 15 × 3120 + 1. Publique (e, n) e guarde d. Uma mensagem m passa a c = mᵉ mod n, e o teorema de Euler garante que cᵈ mod n devolve m.
Porque é difícil de quebrar
Tudo aquilo de que um atacante precisa está escondido nos fatores de n. Com n = 3233, isso não protege nada: testar divisores ímpares encontra o 53 ao fim de umas duas dúzias de tentativas. Mas o esforço cresce com a raiz quadrada de n. Um módulo de 2048 bits tem cerca de 617 algarismos, e nenhum método conhecido, em nenhum computador existente hoje, consegue fatorizá-lo num tempo útil. Assinar é usar o RSA ao contrário: s = mᵈ mod n só pode ser produzido com a chave privada, e qualquer pessoa pode verificar que sᵉ mod n devolve m.
Perguntas frequentes
Porque é que ninguém consegue calcular d a partir da chave pública?
Para encontrar d é preciso φ(n) = (p − 1)(q − 1), e para obter φ(n) é preciso p e q. Recuperá-los a partir de n significa fatorizá-lo, e para números com centenas de algarismos não se conhece nenhum método rápido. A demonstração permite fatorizar chaves de brinquedo numa fração de segundo, o que mostra exatamente porque é que as chaves reais são tão grandes.
Porque é que a mensagem é cifrada um carácter de cada vez?
Porque as chaves de brinquedo são pequenas: o RSA só consegue cifrar um número menor do que n. Com n = 3233, o código de qualquer carácter cabe, mas uma frase inteira não. O RSA real usa um módulo de 2048 bits ou mais, preenche a mensagem com bytes aleatórios para que a mesma mensagem nunca seja cifrada duas vezes da mesma forma e, na prática, cifra apenas uma chave curta para uma cifra mais rápida como o AES.
O que fazem os quadrados sucessivos?
Calculam potências enormes como m²⁷⁵³ mod n sem nunca escrever o número enorme. Escreva o expoente em binário e percorra os seus bits: eleve ao quadrado o resultado acumulado em cada bit e multiplique por m em cada 1, tirando sempre o resto mod n. Um expoente de 2048 bits precisa apenas de cerca de 2048 elevações ao quadrado.
Qual é a diferença entre cifrar e assinar?
Cifrar usa a chave pública do destinatário, para que só a chave privada do destinatário consiga desfazer a cifragem. Assinar usa a chave privada do remetente, para que qualquer pessoa possa verificar a assinatura com a chave pública do remetente e saber que a mensagem veio do titular dessa chave e não foi alterada.
A minha mensagem é enviada para algum lado?
Não. Tudo é calculado no seu navegador, e os seus primos e a sua mensagem ficam no armazenamento local deste navegador.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor