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)

É 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 M_i de modo a que o número de números de cada M_i 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)