Esta é a história do RSA, um dos primeiros algoritmos de criptografia assimétricos ou de chave pública.
O que é criptografia RSA?
RSA é o nome de um sistema criptográfico de chave pública inventado e nomeado por Ron Rivest, Adi Shamir e Leonard Adleman . Eles são os heróis desta história.
Espere. Não dissemos que havia quatro heróis? Sim nós fizemos. Aqui está a parte intrigante.
Os inventores do RSA trabalharam no Massachusetts Institute of Technology (MIT), onde, em 1977, resolveram um problema crucial de criptografia. Como se viu 20 anos depois, outra pessoa os havia vencido.
A história da criptografia RSA
Para entender o que aconteceu, devemos deixar os Estados Unidos e atravessar o oceano até o Sudoeste da Inglaterra. Aqui, em 1969, o professor James H. Ellis teve uma ideia.
Na época, a única maneira de proteger os arquivos era por meio de criptografia simétrica. Em outras palavras, a chave é compartilhada entre diferentes partes. A situação se torna muito mais problemática quando você precisa enviar uma mensagem criptografada para alguém que não conhece antes.
A ideia de Ellis era o que hoje é conhecido como chave pública. Ele imaginou que as partes poderiam ter uma chave pública que, em combinação com uma chave secreta, poderia ser usada para criptografar e descriptografar mensagens. Embora o professor não tenha encontrado uma maneira de implementar sua ideia, ele compartilhou seu processo de pensamento com colegas da Sede de Comunicações do Governo (GCHQ). Felizmente, nosso quarto herói veio em socorro.
Conheça Clifford Cocks. Ele se juntou ao GCHQ em 1973. Depois de aprender sobre a ideia de Ellis, Cocks percebeu que a fatoração em primos poderia ser a resposta.
Caso sua matemática da 6ª série esteja um pouco enferrujada, um número primo é qualquer número que tenha apenas dois divisores (1 e ele mesmo). Portanto, 2, 3, 5, 7, 11 e 13 são todos números primos. Em breve, mostraremos por que a fatoração de primos foi a solução certa para RSA. Primeiro, vamos terminar a história.
Segundo Cocks, ele deu a solução, foi para casa, fez os cálculos de cabeça e nem anotou nada. Logo depois, Cocks apresentou suas descobertas ao GCHQ.
O problema era a relação secreta entre o GCHQ (a agência de inteligência britânica) e a NSA (a agência de inteligência dos EUA). Duas agências compartilhavam segredos e não queriam que seu relacionamento se tornasse público. Portanto, foi tomada a decisão de manter o algoritmo de criptografia de Cocks classificado. Demorou 20 anos para o GCHQ divulgar o trabalho do professor Cocks.
Então, o que Cocks descobriu? Explicaremos isso a seguir.
Como funciona a criptografia RSA?
Já sabemos que o RSA usa números primos. A razão pela qual a fatoração de primos é tão eficaz é que é fácil calcular de uma maneira e incrivelmente difícil de fazer no sentido inverso. Em criptografia, é conhecido como alçapão. Mostraremos o que queremos dizer.
Vamos multiplicar dois números primos: 23 e 29. Você pode precisar de uma calculadora, mas provavelmente concordará que a tarefa é fácil. Mas e se fizéssemos isso ao contrário? Você poderia encontrar os números primos de 3.139? É muito mais difícil, não é? Mesmo uma calculadora não é tão útil.
Essa é a chave para a criptografia RSA. Se você expandir os números o suficiente, nem mesmo um computador poderá encontrar a solução. Considere que o RSA lida com números primos com centenas de dígitos. E a única maneira de resolver esse problema é por tentativa e erro. Mesmo o supercomputador de hoje levaria séculos para encontrar a resposta. Simples mas fascinante.
Em sua essência, o RSA é uma combinação de outro algoritmo de criptografia de chave pública que foi criado em um momento semelhante e uma função de alçapão com números primos sobrecarregados. Ah, e havia outro componente crucial que transformou a RSA em uma fortaleza.
Criptografia de chave pública
Na época em que a criptografia RSA foi inventada, outro algoritmo de criptografia de chave pública nasceu. Com o nome de seus criadores Whitfield Diffie e Martin Hellman, é simplesmente chamado de troca de chaves Diffie-Hellman. Usando aritmética modular, Diffie-Hellman permitiu que duas ou mais partes trocassem mensagens secretas sem compartilhar uma chave secreta antecipadamente.
Ilustraremos a troca de chaves Diffie-Hellman com um exemplo usando dois caracteres, Alice e Bob.
Curiosidade: Alice e Bob foram inventados pelos criadores do RSA em uma de suas publicações. Esses caracteres foram então adotados pela comunidade de criptografia para uso na maioria das situações hipotéticas de criptografia.
De volta a Diffie-Hellman. Aqui está como funciona. Digamos que Bob e Alice querem compartilhar uma mensagem. Primeiro, eles trocam sua chave pública. Então, Alice usa a chave pública de Bob com sua chave secreta para calcular um resultado público para compartilhar com Bob. Bob faz o mesmo com os números de Alice. Devido às especificidades da aritmética modular, Alice pode usar sua chave secreta em combinação com o resultado público de Bob para calcular a mensagem secreta e vice-versa. As chaves públicas por si só não permitem que uma parte externa faça os cálculos necessários. Em outras palavras, assim como a torta de maçã da vovó, você deve ter o ingrediente secreto para obter o mesmo resultado. Caso contrário, simplesmente não funciona.
Mas houve dois problemas com a troca de chaves Diffie-Hellman. Primeiro, não tinha uma função de alçapão — algo que a criptografia RSA resolve com números primos.
Outra fraqueza do Diffie-Hellman era a autenticação. Teoricamente, mesmo que você estabeleça um canal seguro, você não pode confirmar que está falando com a parte pretendida. Já que estamos falando de festas, vamos convidar Alice e Bob para outro exemplo. Mas desta vez vamos adicionar um hacker chamado Eve.
Digamos que Alice pretende entrar em contato com sua companhia de seguros, onde Bob trabalha. Primeiro, Alice precisa enviar sua chave pública para a seguradora. Mas e se Eve não for uma ouvinte ociosa, mas uma hacker competente? Eve poderia entrar na rede antes que Alice e Bob trocassem as chaves e tentassem interceptar o sinal. Se Eve conseguisse, ela fingiria ser Bob para extrair o máximo possível de informações pessoais sobre Alice. E Alice não suspeitaria de nada.
Foi aí que a criptografia RSA foi superior. Sua chave pública também incluía uma assinatura digital.
Naturalmente, tanto a Diffie-Hellman quanto a RSA tiveram muitas melhorias desde sua invenção, bem como diferentes usos. Hoje, a troca de chaves Diffie-Hellman é comumente usada no protocolo TLS (Transport Layer Security) para criptografar o tráfego do site.
Onde a criptografia RSA é usada?
A RSA ajuda as pessoas on-line a se manterem seguras de várias maneiras, sem que elas percebam. SSL (Secure Sockets Layer), ou TLS (Transport Layer Security), é o mais comum. SSL/TLS é usado para proteger todos os tipos de informações privadas, como nomes de usuário ou senhas. No entanto, você pode conhecer melhor o HTTPS, uma maneira de tornar os dados do site mais seguros.
O RSA é amplamente utilizado porque pode ajudar a proteger assinaturas e certificados digitais. Em outras palavras, a criptografia RSA confirma que alguém com quem você está falando é quem diz ser. Esse tipo de criptografia pode ser usado por provedores de e-mail, serviços de armazenamento em nuvem , VPNs (redes privadas virtuais) e aplicativos de comunicação.
A única ressalva é que os algoritmos de chave pública, incluindo RSA, não são tão eficientes quanto as chaves simétricas que são comumente usadas para armazenamento de dados. É por isso que mensagens e arquivos geralmente são criptografados com uma chave simétrica primeiro, enquanto uma chave pública, como RSA, é usada quando esses dados são transferidos.
Quão seguro é o algoritmo RSA?
A criptografia RSA não é inquebrável. De fato, pelo menos quatro métodos para quebrar o algoritmo RSA ao longo dos anos foram identificados. Um deles ignora completamente a criptografia ao encontrar o máximo divisor comum das duas chaves públicas. Sempre que o divisor não for 1, significa que o resultado é um número primo que pode quebrar ambas as chaves públicas. Um computador pode calcular o máximo divisor comum entre dois números em momentos, mas usando o algoritmo euclidiano, você pode até fazê-lo manualmente.
Isso não significa que há algo para se preocupar. Após várias modificações, o RSA é um dos métodos de criptografia mais seguros e comuns do mundo. No entanto, os criptologistas concordam que um pequeno problema com o RSA permanece. Em sua essência, RSA é uma simples equação de multiplicação. Embora um ataque de força bruta contra o RSA levaria séculos, um avanço repentino na fatoração de números primos poderia tornar toda a tecnologia inútil praticamente da noite para o dia. Não importa o quão improvável isso possa ser.
