E quase que o algoritmo recebeu o nome de ARS!

Ronald Rivest teve um momento de brilhantismo após uma grande quantidade de vinho e passou a noite de páscoa escrevendo um artigo científico sobre sua descoberta. Após terminar, como só chegara a este algoritmo após anos de trabalho junto com seus colegas, enumerou os autores em ordem alfabética: Adleman, Rivest, Shamir.

Adleman não concordou em ser citado como autor do artigo pois julgara que o trabalho maior fora de Rivest e, conforme confidenciou mais tarde, não considerava aquilo realmente algo brilhante. Após longa discussão e negociação, Adleman aceitou seu nome no trabalho, desde que fosse o último autor citado, nascendo assim o algoritmo mais conhecido da criptografia, batizado pelas iniciais de seus criadores Rivest, Shamir e Adleman, o RSA (O livros dos códigos, páginas 297 a 299).

O coração do RSA consiste na mesma função de mão única descoberta por Whitfield Diffie e Martin Hellman, a função modular. Novamente, assim como no algoritmo Diffie-Hellman, a segurança está no emprego de números realmente gigantes, hoje da ordem de 512 bits. Zelando pela compreensão, serão usados valores numéricos pequenos nesta demonstração, assim todos os leitores podem reproduzir facilmente em suas calculadoras de linha de comando, bc ou dc.

A primeira etapa do algoritmo RSA é a criação do par de chaves, a pública e a privada. Deixando Alice e Bob de lado, pois ninguém mais os aguenta, Luiza quer criar seu par de chaves.

Luiza cria seu par de chaves

Luiza começa escolhendo dois números primos, chamados de p e q, que mantém em segredo. Um número primo é aquele que não possui nenhum divisor, exceto 1 e ele mesmo. Luiza escolheu os números p=17, q=23.

Após Luiza calcula o produto destes dois números, chamado de n. No caso, n = p*q, sendo que n=17*23.

Agora Luiza computa o quociente de Euler, que nada mais é do que (p-1)*(q-1). Neste exemplo este valor será representado por qq.

Neste momento Luiza tem os seguintes números:


Luiza agora precisa encontrar um número e que seja primo relativo a qq. Um primo relativo é apenas aquele que não possui divisor em comum, ou seja, sendo qq=352 e possuindo vários divisores (352 possui 10 divisores: 2, 4, 8, 11, 16, 22, 32, 44, 88 e 176 ) qualquer número que não tenha nenhum destes divisores serve. Na prática se e for também um número primo, ou seja, não possuir divisor algum, ele será com certeza um primo relativo a qq. Assim qualquer número primo serve como e (de fato, o RSA atual fixa este número para todas as chaves, normalmente 65537).

Luiza decidiu ficar com o número 7 para e.

Agora vem a parte mais interessante do algoritmo. Luiza precisa encontrar um número d, que satisfaça a expressão (d*e) mod qq = 1, ou seja, um número d que ao se multiplicar por e, realizando o módulo com o quociente de Euler (qq), resulte em 1. Pode-se, para números pequenos, simplesmente escolher um d que sirva, mas isto não é uma boa ideia para números grandes. Contudo o número d pode ser calculado através de uma variação do teorema de Euclides, chamada de euclides estendido, para cálculo do máximo divisor comum. Uma implementação em C deste algoritmo pode ser encontrada em Algoritmo de euclides estendido (calcula o D RSA)

Luiza calculou o valor d=151, pois (151*7) mod 352 é realmente igual a 1, conforme você mesmo pode verificar com o seu bc:

echo "(151 * 7) % 352" | bc
1

Desta forma, Luiza possui os seguintes números:


Luiza agora precisa apagar e remover quaisquer vestígios de p, q e qq, mantendo apenas o e, d e o n (e aconselha-se escrever na memória várias vezes lixo nas variáveis que tem p, q e qq, a fim de que não fiquem vestígios dela nem mesmo na área de troca do sistema, o swap).

Luiza agora já tem o seu par de chaves, a saber:

• Ke = (n, e), ou seja, Ke é a chave usada para cifrar (e de "encriptar") e deve ser tornada pública. Assim o "cadeado aberto" de Luiza será Ke = (391, 7).
• Kd = (n, d), ou seja, Kd é a chave usada para decifrar (d de "decifrar") e deve manter-se em sigilo. Assim, a "chave" que abre o cadeado é Kd = (391, 151).

Chaves públicas de Luiza:

        Kd = (391, 151)             Ke = (391, 7)

Usar o RSA significa cifrar algo com a chave Ke e que somente quem tiver a chave Kd possa abrir. Quando me deparei com isto pela primeira vez, minha reação foi de ceticismo. Não é por menos, pois Clifford Cocks, matemático do serviço secreto GCHQ ficou igualmente cético e dedicou boa parte do seu precioso tempo para tentar provar que não funciona. Ele fracassou (GCHQ era o Quartel General de comunicações do Governo Britânico. Hoje se sabe que lá nasceu o RSA quatro anos antes de Diffie-Hellman terem descoberto a função de mão única).

Para cifrar uma mensagem para Luiza basta realizar a seguinte operação matemática:

C = M^e mod N

O único cuidado que é necessário ter é que M, mensagem a ser cifrada, não pode ser maior do que o valor de N. Neste exemplo, considerando que N é 391, pegando-se apenas 8 bits da mensagem o valor numérico máximo que se pode ter é 255, ficando sempre menor do que N. Desta forma o algoritmo RSA pode ser considerado como um algoritmo de cifra de bloco e, neste caso, com um tamanho de bloco igual a oito bits (veja Criptografia chave simétrica de bloco e de fluxo).

Ainda está com a sua calculadora bc a postos?

Cifrando com o RSA

Fulano deseja enviar de forma cifrada a string "Amanha" para Luiza (sem acento no ã, para não entrar em detalhes sobre UTF-8 ou ISO8859-1). Fulano obteve a chave pública de Luiza, pois ela não é segredo:

Ke_(Luiza) = (391, 7)

Então ele simplesmente divide a mensagem em blocos, cada bloco não maior do que 391, e cifra usando a expressão C = M^e mod n, ou no caso, C = M⁷ mod 391:


Assim Fulano pode cifrar a mensagem para Luiza aplicando a expressão matemática em cada byte. Convido-o a reproduzir este cálculo em sua calculadora bc:


Desta forma Fulano cifrou a palavra "Amanha" e chegou ao resultado 176, 250, 109, 236, 315 e 109. Estes valores cifrados serão transmitidos para Luiza que deverá ter condições de recuperar a mensagem.

Decifrando com o RSA

Luiza, ao receber a mensagem, usa a sua chave privada Kd, nunca divulgada, para recuperar a mensagem original.

Kd_(Luiza) = (391, 151)

Para recuperar a mensagem, Luiza precisa executar a expressão M = C^d mod n, ou seja, M = C¹⁵¹ mod 391

Sinta-se novamente a vontade para reproduzir em seu Linux:


Luiza recuperou com sucesso os valores 65, 109, 97, 110, 104 e 97 que quando lidos como letras resultam na frase "Amanha".