Tempo de leitura: 4 minutos

O Algoritmo RSA (Rivest-Shamir-Adleman – criadores deste modelo) é um dos primeiros algoritmos de criptografia assimétrica, portanto funciona com duas chaves distintas – uma pública e uma privada. É também um dos sistemas de criptografia mais usado e seguro do mundo.

Funcionamento do modelo RSA

O modelo RSA utiliza chaves baseadas em números primos. Quanto maior o número, mais segura a chave é.

Para calcular duas chaves, são seguidos estes passos:

1. Se escolhe dois números primos.

Para exemplificar, escolherei os números:

p=3; q=11;

Porém na implementação real, estes números devem ser muito grandes. O menor número que foi usado na criptografia RSA tinha 100 dígitos (RSA-100 – 330 bits). O último número RSA quebrado foi o RSA-230 (762 bits). Foi fatorado em 15 de agosto de 2018. O maior número RSA usado hoje tem 617 dígitos (RSA-2048).

2. Calcula o produto dos dois números do passo anterior.

Este número será usado depois na cifragem e na decifragem.

n = 3*11 = 33

3. Calcular a função totiente de Euler

Euler foi um matemático suíço que descobriu uma fórmula para calcular o número de coprimos à um número. Coprimo é um número que o máximo divisor comum entre ele e outro número é 1.

Por exemplo, o número totiente (ou seja, o número de coprimos) de 8 é 4. Por que?

MDC(8,1) = 1
MDC(8,2) = 2
MDC(8,3) = 1
MDC(8,4) = 4
MDC(8,5) = 1
MDC(8,6) = 2
MDC(8,7) = 1

Portanto existem 4 números que são coprimos ao 8: 1,3,5,7. Então o número totiente de 8 é 4.

Calcular o número totiente de um valor é bastante difícil. Mas Euler descobriu que quando se conhece os dois números primos que dão origem a um número, é facil saber seu número totiente. A fórmula é:

totiente(n) = (p - 1) * (q - 1)

Vamos pegar o número 15 para um exemplo da eficácia dessa fórmula. Os números coprimos de 15 são: 1, 2, 4, 7, 8, 11, 13, 14. Portanto o número totiente de 15 é 8.

Sabemos que 15 é o resultado da multiplicação de dois primos: 3 e 5. Aplicando a fórmula de Euler:

totiente(15) = (3 – 1) * (5 – 1) = 2 * 4 = 8

Voltando ao nosso exemplo, quanto é o totiente do nosso n?

totiente(33) = (3 – 1) * (11 – 1) = 2 * 10 = 20

Quer tirar a prova real? Vamos lá. Os números coprimos de 33 são: 1,2,4,5,7,8,10,13,14,16,17,19,20,23,25,26,28,29,31,32! 20 números! Exatamente como a fórmula de Euler nos disse.

4. Escolha um número “e” que seja um dos coprimos de n

No passo anterior já vimos todos os coprimos de n (que no nosso exemplo é 33). Dos coprimos, escolherei o 17. Portanto nosso “e” vale 17. Este número comporá a chave pública.

5. Calculando o “d” da chave privada

O “e” e o “d” devem ser tais que a seguinte fórmula seja verdadeira:

e * d mod totiente(n) = 1

Portanto sabemos que 17 * d mod 20 precisa ser 1.

Para calcular isso, eu fiz um pequeno código em javascript que calcula para mim.

function achad(e, totiente){
    var i = 1;
    var x;
    while (true){
        if (e * i % totiente == 1){
            console.log("d vale: "+i);
            break;
        }
        i++;
    }
}

Menos de um segundo depois aparece na minha tela que “d vale 13”.

Temos tudo que precisamos

Agora temos tudo que precisamos para criptografar usando algoritmo RSA:

p = 3;
q = 11;
n = 33
totiente(n) = 20
e = 17
d = 13

A chave pública é: e=17, n=33
A chave privada é: d = 13, n = 33

Criptografando

Apenas para exemplificar selecionarei uma “mensagem” (m) qualquer. O “m” valerá 9. Portanto nossa “mensagem” secreta será “9”. Para criptografar, usaremos a seguinte fórmula:

c = m ^ e mod n

No nosso exemplo, c = 9 ^ 17 mod 33 = 16677181699666569 mod 33 = 15

Então nosso texto criptografado será 15

Decriptografando

Uma vez que o texto for criptografado com a chave pública, apenas a chave privada conseguirá decriptografar! Será usada a seguinte fórmula para reverter o processo:

decrypt = c ^ d mod n

Substituindo no nosso exemplo, decrypt = 15 ^ 13 mod 33 = 1946195068359375 mod 33 = 9

E assim recuperamos a mensagem original!

Segurança do algoritmo RSA

A RSA mantem um desafio aberto em que a empresa dá o “n”. A pessoa (ou grupo) que encontrar os dois primos que multiplicados dá o “n” ganha um prêmio em dinheiro. Por isso ao longo dos anos vários grupos vem tentando quebrar este modelo um por um tem fracassado, demonstrando a extraordinária segurança deste algoritmo.

O maior “n” que foi quebrado, como já falei, foi o RSA-768 que tinha como “n” o número 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413. O grupo de matemáticos Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen K. Lenstra, Emmanuel Thomé, Pierrick Gaudry, Alexander Kruppa, Peter Montgomery, Joppe W. Bos, Dag Arne Osvik, Herman te Riele, Andrey Timofeev e Paul Zimmermann, após dois anos, descobriram que este “n” era o produto da multiplicação dos seguintes números primos: 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 × 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

Assim, toda segurança do algoritmo RSA está em proteger os números primos “p” e “q”.

Com toda a tecnologia que chegamos, o máximo que conseguimos quebrar foi o RSA-768. Lembre-se que a DigiCert (Entidade Certificadora americana) suporta RSA-2048 (porém chaves de 3072 e 4096 bits também estão disponíveis). Então agora você entende por que é computacionalmente impossível quebrar o HTTPS hoje?

Conclusão

A ideia deste artigo apareceu porque não existem materiais bons e simples para entender este algoritmo em português. Por isso quis fazer algo que qualquer um com conhecimentos básicos de matemática consiga acompanhar.

Ficou alguma dúvida? Ficou claro? Deixa seu comentário aqui embaixo!

Abraços e até a próxima.