O Algoritmo RSA

Em 1977 os criptógrafos Rivest, Shamir e Adleman do Massassuchets Institute of Technology (MIT) definiram a primeira técnica de criptografia assimétrica divulgada na literatura aberta, o algoritmo RSA. Este é o principal algoritmo assimétrico em uso (ANSI X9.31) na atualidade. Para operar, cada pessoa que for trocar correspondência deve fabricar uma chave pública e uma chave privada. A chave pública será utilizada para cifrar as mensagens para um certo destinatário enquanto a chave privada será utilizada pelo destinatário para decifrar a mensagem recebida. A relação entre as chaves pública e privada é a proteção do destinatário. Um indivíduo prepara suas chaves do seguinte modo:
Escolhe adequadamente dois números primos p e q
Calcula n = p*q
Escolhe aleatoriamente um número x e calcula y tal que:

mdc(x, fi(n))=1, onde fi(n)=(p-1)(q-1), tal que x esteja entre 1 e fi(n)

y=(x mod fi(n))^(-1)

No fim do cálculo é obtida a chave pública (n, x) e a chave privada (n, y). A chave pública é divulgada abertamente para que qualquer interessado possa trocar mensagens com o criador das chaves.
A partir de uma mensagem de entrada M, gera-se sua representação numérica m substituindo os caracteres por números. As chaves criptográficas são então utilizadas para cifrar e decifrar a mensagem m conforme as seguintes fórmulas:

Cifrar: c=m^x mod n

Decifrar: m=c^y mod n


A segurança do RSA está na dificuldade de obter p e q a partir da fatoração de n, esse problema torna-se complexo quando n é muito grande. O teorema dos números primos afirma que existem 4,3 X 1097 números primos de 100 dígitos. É maior que o total de partículas do universo.
Na prática, devido ao tempo de processamento do RSA, utiliza-se uma combinação de criptografia simétrica com assimétrica. Desta forma, uma chave simétrica de sessão aleatória é gerada para cifrar o texto utilizando-se um algoritmo simétrico, por exemplo: AES. Com a chave pública disponível a chave simétrica é cifrada e em seguida enviada ao destinatário juntamente com a mensagem cifrada. Para decifrar, o destinatário decifra a chave privada de sessão com a sua chave privada para depois decifrar a mensagem com a chave simétrica obtida.