O RSA foi desenvolvido em 1978 por Ron Rivest, Adi Shamir e Leonard Adleman. É considerado o primeiro algoritmo de criptografia assimétrica fácil de entender e implementar, portanto é largamente utilizado em codificações de mensagens e assinaturas digitais. O RSA tem resistido a anos de extensivas análises criptográficas, o que sugere um nível de segurança do algoritmo.

A segurança do RSA consiste na dificuldade de fatorar números grandes. As chaves públicas e privadas são funções de um par de grandes números primos (mais de 128 bits). Dado o texto codificado, a recuperação do plain text com a chave pública é equivalente a fatorar o produto de dois primos.

Para gerar as duas chaves, escolha dois números primos grandes aleatoriamente, p e q. Para segurança máxima, escolha p e q de tamanhos iguais. Compute o produto:

Então aleatoriamente escolha a chave de codificação, e de forma que não tenha nenhum fator de (p-1)(q-1).

Finalmente, use o algoritmo extendido de Euclides para computar a chave de decodificação, d, de modo que:

Em outras palavras:

Observe que d e n são também relativamente primos.

Os números e e n são a chave pública, o número d é a chave privada. Os dois primos p e q não são mais necessários. Eles devem ser descartados, mas numca revelados.

Para codificar uma mensagem m, primeiro divida a em blocos numéricos menores que n (com dados binários escolha a maior potência de dois menor que n). Isto é, se ambos p e q são primos de tamanho de 100 digitos, então n terá menos de 200 digitos e cada bloco de mensagem m[i] deve ser menor que 200 digitos.(Se vc necessita codificar um número fixo de blocos, você pode preenche-los com zeros a esquerda para ter certeza que eles sempre serão menores que n). A mensagem codificada c, será composta de blocos de mensagem de tamanho similares c[i]. A formula de codificação é simplismente:

Para decodificar a mensagem, use a formula nos blocos codificados:

Então:

é a formula que recupera a mensagem.

A mensagem poderia apenas ter sido codificada com d e decodificada com e, a escolha é arbitrária.

Um pequeno exemplo provavelmente tornará isso mais claro:

Dado:

	p =47 e q =71

Então:

	n= pq = 3337

A chave de codificação e, não deve ter fatores em comum com:

	(p-1)(q-1) = 46*70= 3220

Escolha e (aleatoriamente) para ser 79. Neste caso:

	d = 79^-1 mod 3220 = 1019

Este número foi calculado utilizando o algoritmo extendido de Euclides. Publique e e mantenha d em segredo. Descarte p e q.

Para codificar a mensagem:

	m = 6882326879666683

Primeiro divida em pequenos blocos. Blocos de três digitos funcionaram bem neste caso. A mensagem é colocada em seis blocos m[i]:

	m[1] = 688
	m[2] = 232
	m[3] = 687
	m[4] = 966
	m[5] = 668
	m[6] = 003

O primeiro bloco é codificado como:

 
	c[1] = 688^79 mod 3337 = 1570 
	c[2] = 232^79 mod 3337 = 2756 
	c[3] = 687^79 mod 3337 = 2091
	c[4] = 966^79 mod 3337 = 2276 
	c[5] = 668^79 mod 3337 = 2423 
	c[6] = 003^79 mod 3337 = 158 

Repetindo a mesma operação nos blocos subsequentes, geramos uma mensagem codificada:

	c = 1570 2756 2091 2276 2423 158

Decodificar a mensagem requer a repetição da mesma exponenciação usando a chave de decodificação de 1019, então:

	m[1] = 1570 ^1019 mod 3337 = 688 
	m[2] = 2756 ^1019 mod 3337 = 232
	m[3] = 2091 ^1019 mod 3337 = 687
	m[4] = 2276 ^1019 mod 3337 = 966
	m[5] = 2423 ^1019 mod 3337 = 668
	m[6] = 158  ^1019 mod 3337 = 003