O RSA explicado

Sempre que um navegador mostra um cadeado, uma mensagem é assinada ou um programa verifica uma atualização, a criptografia de chave pública está em ação, e o RSA é a sua forma mais conhecida. A ideia é que a chave que tranca uma mensagem pode ser publicada, enquanto a chave que a abre continua privada. Notavelmente, todo o sistema assenta em aritmética ensinada na escola: números primos, multiplicação e restos.

Os primos secretos 61 e 53 dão o módulo público 3233. As letras de HELLO passam a 3000, 28, 2726, 2726 e 1307 com o expoente público 17, e o expoente privado 2753 devolve 3000 a 72
Os primos secretos 61 e 53 dão o módulo público 3233. As letras de HELLO passam a 3000, 28, 2726, 2726 e 1307 com o expoente público 17, e o expoente privado 2753 devolve 3000 a 72

O problema que o RSA resolve

As cifras tradicionais, desde a cifra de César até ao moderno AES, usam a mesma chave para trancar e destrancar, por isso os dois lados têm primeiro de partilhar em privado uma chave secreta. A criptografia de chave pública elimina esse passo. Cada pessoa tem duas chaves: uma chave pública que qualquer pessoa pode usar para lhe cifrar uma mensagem e uma chave privada que só ela possui e que é a única capaz de a decifrar. Whitfield Diffie e Martin Hellman descreveram a ideia em 1976, e um ano depois Ron Rivest, Adi Shamir e Leonard Adleman, do MIT, encontraram uma forma de a pôr em prática, a que chamaram RSA a partir das suas iniciais.

Martin Hellman (à esquerda) e Whitfield Diffie (à direita), 1977
Martin Hellman (à esquerda) e Whitfield Diffie (à direita), 1977

Criar as chaves

Escolha dois primos grandes, p e q, e multiplique-os: n = p × q. Calcule φ(n) = (p − 1)(q − 1), a função totiente de Euler, que conta os números menores do que n que não têm nenhum fator em comum com ele. Escolha um expoente público e sem nenhum fator em comum com φ(n); 65537 é a escolha habitual. Depois encontre o expoente privado d tal que e × d deixe resto 1 na divisão por φ(n). O algoritmo de Euclides estendido faz isto rapidamente. A chave pública é o par (e, n); a chave privada é d. Com p = 61 e q = 53, obtém-se n = 3233, φ(n) = 3120, e = 17 e d = 2753.

Cifrar e decifrar

Primeiro, a mensagem é transformada num número m menor do que n. Para a cifrar, calcula-se c = mᵉ mod n, o resto da divisão de mᵉ por n. Para decifrar, calcula-se cᵈ mod n. O teorema de Euler garante que isto devolve m, porque e × d é 1 mais do que um múltiplo de φ(n). Com as chaves acima, a letra A, de código 65, passa a 65¹⁷ mod 3233 = 2790, e 2790²⁷⁵³ mod 3233 volta a dar 65. Potências tão grandes nunca são escritas por extenso: os quadrados sucessivos calculam-nas com uma elevação ao quadrado por cada bit do expoente, tirando o resto em cada passo.

Assinaturas digitais

O RSA também funciona ao contrário. Elevar uma mensagem ao expoente privado, s = mᵈ mod n, produz uma assinatura que só o dono da chave consegue criar. Qualquer pessoa a pode verificar com a chave pública: se sᵉ mod n devolver m, a mensagem veio do titular de d e não foi alterada pelo caminho. Na prática, o que se assina é um hash curto da mensagem e não a própria mensagem. Assinaturas como esta protegem atualizações de software, sites seguros e documentos eletrónicos.

Porque é seguro

Toda a gente vê n e e. Para encontrar d, um atacante precisa de φ(n), e para encontrar φ(n) precisa de p e q, por isso quebrar o RSA resume-se a fatorizar n. Multiplicar dois primos demora a um computador uma fração de microssegundo; decompor o produto de novo nesses primos é considerado extremamente difícil. O maior número do desafio RSA fatorizado até hoje, o RSA-250, em 2020, tem 829 bits e exigiu cerca de 2700 anos de tempo de computação. As chaves usadas hoje têm pelo menos 2048 bits, cerca de 617 algarismos.

Um segredo descoberto duas vezes

Em 1973, quatro anos antes do RSA, o matemático britânico Clifford Cocks encontrou o mesmo esquema enquanto trabalhava na agência de informações GCHQ, partindo de uma ideia do seu colega James Ellis. O trabalho era confidencial e só foi tornado público em 1997. O próprio RSA foi patenteado nos Estados Unidos em 1983; a patente expirou em setembro de 2000, duas semanas depois de o algoritmo ter sido colocado no domínio público.

Ron Rivest, Adi Shamir e Len Adleman (da esquerda para a direita)
Ron Rivest, Adi Shamir e Len Adleman (da esquerda para a direita)

O RSA na prática

O RSA real nunca cifra texto diretamente. A mensagem é preenchida com bytes aleatórios, com um esquema como o OAEP, para que a mesma mensagem seja cifrada de forma diferente de cada vez e não possam escapar padrões. Como o RSA é lento, é usado sobretudo para trocar ou proteger uma chave curta para uma cifra simétrica rápida como o AES, ou para assinar. Computadores quânticos suficientemente grandes poderiam fatorizar n rapidamente com o algoritmo de Shor, de 1994, e é por isso que estão a ser introduzidos novos métodos pós-quânticos a par do RSA.

Explore-o

Abra a demonstração da cifragem RSA para construir chaves a partir dos seus próprios primos ou de primos aleatórios de 2 a 8 algarismos, ver o algoritmo de Euclides estendido encontrar d linha a linha, cifrar ou assinar uma mensagem carácter a carácter e acompanhar os quadrados sucessivos de qualquer carácter. Depois deixe Eve fatorizar n e veja como o tempo de que ela precisa cresce com o tamanho dos primos.

Perguntas frequentes

Porque é que o RSA precisa de números primos?

Porque φ(n) só é fácil de calcular quando se sabe como n se decompõe em primos. Para n = p × q com p e q primos, φ(n) = (p − 1)(q − 1). Os primos também tornam n o mais difícil possível de fatorizar para o seu tamanho, já que não tem nenhum fator pequeno.

Porque é que e é muitas vezes 65537?

65537 = 2¹⁶ + 1 é primo e tem apenas dois uns em binário, por isso cifrar com ele exige apenas 16 elevações ao quadrado e uma multiplicação. Também é suficientemente grande para evitar as fraquezas de expoentes muito pequenos como 3.

Qual é a diferença entre o RSA e o Diffie–Hellman?

O Diffie–Hellman permite a duas pessoas combinar uma chave secreta partilhada através de um canal aberto; por si só, não cifra nem assina nada. O RSA cifra e assina diretamente com um par de chaves. Ambos assentam em problemas que são fáceis num sentido e difíceis no outro: a fatorização, no caso do RSA, e o logaritmo discreto, no caso do Diffie–Hellman.

As chaves da demonstração podem ser usadas para cifrar a sério?

Não. Os seus primos têm no máximo uma dúzia de algarismos, por isso qualquer chave que gere pode ser fatorizada em segundos ou menos, e cifra cada carácter isoladamente, sem preenchimento. Serve para ver como o RSA funciona, não para proteger seja o que for.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Abrir a demonstração da cifragem RSA