A codificação com RSA

Março 2017

O sistema RSA

O primeiro algoritmo de codificação com chave pública(codificação assimétrica) foi desenvolvido por R.Merckle e M.Hellman em 1977. Ficourapidamente obsoleto graças aos trabalhos de Shamir, Zippel e de Herlestman, famosos criptanalistas.

Em 1978, o algoritmo com chave pública de Rivest, Shamir, e Adelman (daí o nome RSA) aparece. Este algoritmo servia ainda em 2002 para proteger os códigos nucleares do exército americano e russo.

Funcionamento de RSA

O funcionamento do criptosistema RSA é baseado na dificuldade de factorização de grandes inteiros.

Tomemos dois números primos p e q, e d um inteiro de modo a que d seja primeiro com (p-1) * (q-1)). O trio (p, q, d) constitui assim a chave privada.

A chave pública é então o par (n,e) criado com a ajuda da chave privada pelas transformações seguintes:

n = p * q 
e = 1/d mod((p-1)(q-1))



Suponhamos que M é a mensagem a enviar. É necessário que a mensagem M seja primo com a chave n. Com efeito, descodificação assenta no teorema de Euler que estipula que se M e n forem primos entre eles, então:

Mphi(n) = 1 mod(n)

Phi(n) o indicador de euler, e valendo no caso presente (p-1)*(q-1).

É por conseguinte necessário que M não seja um múltiplo de p, de q, ou de n. Uma solução consiste em recortar a mensagem M em pedaços Mi de modo a que o número de números de cada Mi seja estritamente inferior ao de p e q. Isto supõe, então, que p e q sejam grandes, que é o caso na prática, dado que todo o princípio de RSA reside na dificuldade em encontrar num tempo razoável p e q que conhecem n., o que supõe p e q grandes.

Na prática…

Suponham que um utilizador (chamado Bob) deseja enviar uma mensagem M a uma pessoa (chamem-lhe Alice), ele só tem que arranjar e a chave pública (n,e) desta última e seguidamente calcular a mensagem codificada c:

c = Me mod(n)


Bob envia, seguidamente, a mensagem codificada c a Alice, que é capaz de decifrá-la com a ajuda da sua chave privada (p, q, d):

M =  Me*d mod(n) = cd mod(n)

Veja também


Encryption with RSA
Encryption with RSA
Cifrado por medio de RSA
Cifrado por medio de RSA
Algorithme de chiffrement RSA
Algorithme de chiffrement RSA
La codificazione con RSA
La codificazione con RSA
Este documento, intitulado 'A codificação com RSA', está disponível sob a licença Creative Commons. Você pode copiar e/ou modificar o conteúdo desta página com base nas condições estipuladas pela licença. Não se esqueça de creditar o CCM (br.ccm.net) ao utilizar este artigo.