Entendendo a criptografia RSA-Parte I

Olá pessoal. Este vai ser o primeiro de uma série de posts em que vamos falar sobre criptografia RSA. O RSA é o método de criptografia mais utilizado no mundo e o objetivo desta série é mostrar a teoria matemática e a implementação dela em forma de algoritmo computacional. Atenção: ao acompanhar a série você vai descobrir que não existe mágica no processo e isto, às vezes, pode ser um pouco decepcionante.

E como o RSA funciona?

Esta é a parte legal. Com o RSA eu tenho duas chaves: uma pública e uma privada. A chave pública, como nome diz, eu posso distribuir livremente; qualquer pessoa pode usar a minha chave publica para criptografar uma mensagem para mim. Entretanto, só é possível descriptografar a mensagem usando a minha chave privada, que eu mantenho em segredo.

O RSA foi construído sobre uma das áreas mais clássicas da matemática, a Teoria dos números. Ele se baseia na dificuldade em fatorar um número em seus componentes primos. Primeiro vamos lembrar que um número primo é um número que só pode ser dividido por ele mesmo e por 1 (numa divisão exata, sem números quebrados); segundo, temos que lembrar como descobrir os fatores primos de um número.

Segundo o Teorema Fundamental da Aritmética todo número inteiro positivo maior que 1 pode ser decomposto de forma única em um produto de números primos, por exemplo:

26 = 2 * 13
44 = 2 * 2 * 11

Fatorar números pequenos é algo simples, mas fatorar números grandes é bem difícil e demorado, pois este é um problema que não pode ser resolvido em um tempo polinomial determinístico, ou falando de forma bem simplificada, não há uma fórmula para isto.

E como o RSA usa isto tudo? As chaves pública e privada são geradas com base na multiplicação de dois números primos. O resultado desta multiplicação será público mas, se o número for grande o suficiente, fatorar este número para descobrir os primos que multiplicamos para formá-lo pode demorar anos.

É desta particularidade que vem segurança do RSA. Na verdade não é impossível quebrar a criptografia RSA, mas como para fazer isto seriam necessários alguns bons anos ou décadas, a ideia se torna inviável.

Preparem papel, caneta e calculadora, pois no próximo post vamos executar o passo-a-passo do método e criptografar/descriptografar algumas mensagens. Até mais!

Clique aqui para ler a Parte II