O RSA é brilhante, mas seu uso foi considerado como não prático durante muitos anos. Seu uso de forma segura requer a escolha de números p e q muito grandes, fazendo com que o d, principalmente, seja igualmente de muitos bits.

Considere o uso do e em um espaço de 17 bits, como o usado oficialmente pelo RSA: e = 65537. Ao usar este valor como e, a fórmula de euclides calculará d = 65, pois:


Agora, com esta pequena variação, cifrar algo, como por exemplo, a letra 'z', cujo valor decimal é 122, significa elevar na potência 65 e extrair o módulo 391:


Muito embora a parte 122⁶⁵ resulte em um número com 136 dígitos, o cálculo em um processador normal pode ser realizado em milisegundos.

Já a decifragem deve ser feita com o 65537 sendo que decifrar significa elevar a este número:

309⁶⁵⁵³⁷ mod 391

No meu processador foram necessários dois segundos para completar a operação, sendo que a operação de exponenciação gerou um número com mais de 160 mil dígitos!

E se está pegando muito leve, pois uma chave real, verdadeira, usada pelo RSA deve ser de, pelo menos, 1024 bits. Não tente fazer isto em sua calculadora bc, mas ai está um exemplo real de uma chave oficial do RSA gerada através do openssl. E pasmem: é apenas uma "chavesinha fraquinha" de 256 bits:


Alguém ai tem coragem de cifrar um simples caractere com esta chave? É só elevar a 65537. Moleza. E para decifrar, basta elevar ao simpático número 36109769233737818015273648021057724389187611534029825167304543901118715705601!

Este foi um dos impasses a que chegaram os pesquisadores do GCHQ e que os fizeram achar o algoritmo impraticável devido ao fato de que os cálculos exigiam muito processamento, muito além do hardware existente na época. Ainda hoje isto é uma completa utopia se não fosse possível simplificar a operação através de reduções matemáticas.

Não vou descrever como é possível reduzir drasticamente o esforço matemático desta operação, mas eu tenho uma implementação deste princípio em Cálculo de X na potência Y modulo N. Para usar este programa, digite VOL como matricula, já que o script PHP destina-se ao uso de alunos enquanto solucionando problemas de aula. Faça uma teste: veja quanto tempo o teu processador levará para calcular 12347⁶⁵⁵³¹ mod 107803 = 39618 (fazendo um echo "12347 ^ 65531 % 107803" | bc). Dependendo do seu processador, isto poderá demorar uns 10 segundos. Depois veja quanto tempo o script PHP, que usa a redução matemática, precisou.

Sem este atalho matemático o RSA seria inviável, pois os meros 256 bits anteriores ainda são insuficientes para garantir segurança. Com os atalhos matemáticos, o RSA pode ser usado, mas ainda assim ele é considerado um algoritmo que consome uma monstruosidade de processamento. Por isto seu emprego deve ser muito, mas muito restrito.

No protocolo SSL, por exemplo, ele é usado apenas o tempo necessário para que ambas as partes estabeleçam uma chave de sessão. Todo o tráfego de dados são cifrados usando um simétrico, mas rápido, e esta chave que ambos estabeleceram. Economia de processamento. Em assinaturas digitais, o mesmo princípio, pois se usa o RSA para assinar o hash da mensagem, que sempre tem o mesmo tamanho (128 bits no caso do MD5).