No Sync Encrypt: Criptografia em RSA - O Algoritmo mais usado atualmente

Nessa postagem falaremos do RSA, o mais usado algoritmo de criptografia assimétrica atualmente, mostrando um pouco como ele funciona e dando exemplos bem simples.

O RSA foi inventado em 1977 pelos professores do MIT: Ronald L. Rivest, Adi Shamir, e Leonard Adleman que controlavam a empresa RSA Security. Essa empresa é a detentora da patente do algoritmo RSA nos EUA. Mas se restringe a esse país, não se aplicando a outros que desenvolvam programas que usem o RSA, o que permite que o usemos livremente.

O RSA é usado para envio de informação de forma segura usando uma chave pública e uma privada (criptografia assimétrica). Um exemplo seria eu mandar uma mensagem criptografada por mim para um amigo. Se eu usasse uma criptografia de uma chave única privada para isso, teria de enviar para meu amigo a chave que usei na criptografia de forma segura, o que é um grande problema nesse tipo de comunicação. A criptografia simétrica não resolveria esse caso e o RSA é um dos algoritmos de chave assimétrica que resolveriam esse problema como mostra a imagem abaixo.

Desta forma eu não precisaria enviar minha chave para meu amigo, o que é uma vantagem, porém seriam necessárias 3 viagens e eu não estaria criptografando a mensagem diretamente, mas sim o "recipiente que a envolveu", nesse caso do exemplo a "caixa com os cadeados".

RSA e seu funcionamento

RSA é um algoritmo de criptografia assimétrica, então usa duas chaves: uma pública e uma privada, onde a pública pode ser distribuida livremente para que qualquer remetente possa usa-la para me enviar uma mensagem criptografada, mas só sendo possivel descriptografá-las com minha chave privada que é guardada comigo em segredo.

Seguindo com essa idéia, para eu enviar uma mensagem para meu amigo, como no exemplo anterior, eu só precisaria enviá-la usando a chave pública dele e somente ele poderia abrí-la usando sua chave privada guardada com ele em segredo.

Esse algoritmo se baseia na teoria dos números, uma clássica área matemática, e se fundamenta na dificuldade em fatorar um número em seus componentes primos (números divisíveis por eles mesmos e pelo número 1 numa divisão exata e sem restos).

"Apesar dessa função ser inversível, se multiplicarmos números primos muito grandes, a quantidade de números que precisaremos testar para descobrir a entrada vai ser tão grande, que torna esse trabalho impraticável. Por isso, para que essa função seja segura, devemos estar certos de que os dois números escolhidos são realmente primos e que sejam números muito grandes. Por exemplo, quando dizemos que estamos trabalhando com uma chave de 1024 bits no RSA, isso quer dizer, que a chave pública tem 1024 bits, ou seja, precisamos de 1024 bits para representar o número que foi gerado pela multiplicação dos dois primos, portanto cada número primo deveria ter 512 bits.
Para se ter uma ideia, um número de 1024 bits é da ordem de 1 x 10^308 na representação decimal, imagine quantos números antes desse devemos testar para encontrar os dois números primos que o geraram!!! Com o computador que está na sua frente agora, você levaria mais tempo do que a idade do universo para conseguir fatorar esse número, heheheh que exagero..."

Para isso temos de nos lembrar como descobrir fatores primos de um número e para facilitar abaixo segue um vídeo, do Youtube postado por Vinicius Silva, que nos ajudará a entender como funciona a matemática por trás do RSA, e que não há magia nenhuma nisso.

O vídeo é bem prático e explicativo mostrando o passo-a-passo da matemática que fundamenta o RSA e me ajudou bastante a compreender esse algoritmo criptográfico, espero que ajude a todos da mesma forma e como diz no fim do vídeo por enquanto "that's all folks" (isso é tudo pessoal).