A codificação com RSA


O que é 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. No entanto, ele ficou rapidamente obsoleto coo os trabalhos de Shamir, Zippel e de Herlestman, famosos criptoanalistas. Em 1978, o algoritmo com chave pública de Rivest, Shamir, e Adelman (daí o nome RSA) é lançado. Este algoritmo servia ainda, em 2002, para proteger os códigos nucleares do exército americano e russo.

Como funciona o RSA

O funcionamento do criptosistema RSA é baseado na dificuldade do sistema de fatores de grandes inteiros.


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

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

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

Suponhamos que M é a mensagem a enviar. A mensagem M dever ser criada com um primo com a chave n. Com efeito, a descodificação baseia-se 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, valendo no caso presente (p-1)*(q-1), exige 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 que o número 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.

Suponham que um usuário (chamado Bob) deseja enviar uma mensagem M a uma pessoa (chamada Alice), ele só tem que arranjar a chave pública (n,e) desta última, e depois calcular a mensagem codificada c:

c = Me mod(n)

Bob envia, em seguida, a mensagem codificada c à 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

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.