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.
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 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.
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)