Este artigo não pode ser considerado um artigo isolado. Ele faz parte de uma sequência de outros artigos sobre o tema. Se você não é versado no assunto da criptografia, talvez queira ler os artigos anteriores antes de prosseguir a leitura deste.

A primeira vez que escrevi sobre criptografia foi em fevereiro de 2009, com o artigo Introdução a criptografia. Neste eu defini algumas terminologias, explicando o que é chave, criptoanálise e força bruta, além de conceituar os tipos de algoritmos existentes.

Na sequência, em março de 2009, dei continuidade ao tema com o artigo Criptografia chave simétrica de bloco e de fluxo, que descrevia o primeiro tipo, os de cifras simétricas.

Por fim, em Julho de 2009, desejava completar a série falando sobre os algoritmos assimétricos. Porém ao perceber que o artigo estava ficando demasiadamente grande, optei em dividí-lo em duas partes, sendo que a primeira parte tratou dos fundamentos matemáticos que permitiram a construção do RSA, bem como situá-lo na história (Fundamentos da criptografia assimétrica).

Este artigo é, portanto, uma segunda parte sobre algoritmos assimétricos e traz, não apenas a descrição de um algoritmo assimétrico, como também um passo a passo de como ele realmente funciona, podendo qualquer um testar.

Para usar um algoritmo de criptografia é necessário que as partes envolvidas possuam um segredo em comum, uma chave. Ao transmitir uma mensagem o emissor pode cifrar ela com um algoritmo de criptografia usando esta chave. O receptor recupera a mensagem usando a mesma chave.

Porém existe um problema que é o compartilhamento desta chave, ou seja, de que forma o emissor e receptor chegaram a um consenso sobre seu valor. Se existe a possibilidade de um encontro pessoal e físico o compartilhamento desta informação pode ser realizado com segurança, mas se o único meio de transmissão existente entre eles é inseguro, tem-se um problema sério. Não se pode enviar a chave pela Internet, pois em caso de alguém estar escutando, este verá esta informação. Por isto que durante muitos anos pesquisadores procuraram um algoritmo que fosse assimétrico.

Um algoritmo assimétrico possui mais de uma chave, tipicamente duas. Uma delas é usada para cifrar e a outra serve apenas para decifrar. Caso tal algoritmo existisse, o emissor poderia enviar pela Internet apenas a chave que cifra, mantendo em segredo a chave que decifra, ou vice versa.

A comunidade científica desistiu desta busca, classificando o problema como sem solução, mas Whitfield Diffie e Martin Hellman insistiram na utopia de um algoritmo assimétrico. Suas buscas frustraram-se tentativa por tentativa até que finalmente fizeram uma importante descoberta ao explorar a matemática modular (detalhes em Fundamentos da criptografia assimétrica).

Infelizmente esta descoberta não resultou, de imediato, em um algoritmo assimétrico mas sim em um protocolo de troca de chaves que recebeu o nome de Diffie-Hellman, usado até hoje. Mesmo tendo continuado sua busca, foram os pesquisadores Ronald Rivest, Adir Shamir e Leonard Adlemann que chegaram ao primeiro algoritmo de cifra assimétrico, o popularmente conhecido algoritmo RSA (mais tarde tornou-se público que o governo britânico já possuía quatro anos antes um algoritmo assimétrico e que este seguia os mesmos princípios do RSA).

Talvez não seja do interesse de muitos entender como o RSA funciona. Afinal, nós, da área de TI, não os elaboramos, apenas os usamos. Muitos destes algoritmos são baseados em princípios matemáticos que nos são distantes e, não raro, nos resignamos a aceitar e acreditar nas informações que os matemáticos nos contam.

Por exemplo, se eles nos dizem que a operação exponencial de aritmética modular não pode ser revertida, que seja! Se nos dizem que a descoberta de dois divisores primos de um número só pode ser feita por tentativa e erro, que seja. Lemos, implementamos e usamos.

Contudo eu, particularmente, acredito que conhecer as coisas, as entranhas, o como é feito, ter o poder de fazer no braço, é um prazer indescritível.

Estejam com suas calculadores bc na mão.

Um algoritmo de criptografia assimétrico, mais popularmente conhecido como algoritmos de chave pública e privada, consiste no uso de duas chaves distintas. Uma delas é usada para cifrar dados e a outra para decifrar, ou seja, o que uma chave faz, a outra desfaz.

Como exemplo, considere que duas pessoas desejam enviar dados sigilosos pelos correios. Usarão uma caixa fechada com um cadeado para isto. O problema é como enviar a chave, já que uma pessoa poderia capturá-la e realizar uma cópia. Diffie e Hellman pensaram na ideia de dois cadeados, com duas chaves, conforme descrito no artigo Fundamentos da criptografia assimétrica. Porém tem uma maneira ainda mais fácil de realizar esta comunicação.

Caso um emissor C queira enviar dados para um receptor F usando os correios, o procedimento poderia ser o seguinte:

• C requisita a F um cadeado;
• F vai em uma ferragem, compra um cadeado qualquer e o envia aberto para C, mantendo consigo a chave;
• C recebe pelos correios o cadeado aberto de F;
• C usa o cadeado para fechar a caixa e a envia para F.

Usando a analogia do cadeado, pode-se considerar que o cadeado aberto é uma das chaves de cifragem, justamente aquela que só serve para cifrar (bater o cadeado). A chave do cadeado é que serve para abrir.

F poderia pedir a um grande fabricante de cadeados que confeccionasse milhares deles, todos iguais e abertos por uma única chave. Estes cadeados poderiam ser espalhados em supermercados, ferragens, lojas de conveniência. Todo mundo teria acesso fácil a um destes cadeados abertos. Quando alguém desejar enviar algo para F, basta pegar um cadeado aberto em algum posto de gasolina e usar ele para fechar uma caixa, enviado-a para F. Assim o cadeado aberto seria, analogicamente, a chave pública de F.

Para que isto funcione, algumas propriedades são muito importantes sob o risco de comprometer o sigilo:

1. o cadeado é muito forte e uma vez fechado, só a chave pode abrí-lo;
2. mesmo aberto, o cadeado não possui informações suficientes para que um chaveiro, mesmo habilidoso, consiga confeccionar uma nova chave para ele;
3. o número de chaves possíveis inviabiliza que um chaveiro, mesmo com muito tempo, pudesse tentar cada uma delas.

Trazendo a analogia para os termos criptográficos, a propriedade 2 significa que o algoritmo deve resistir a criptoanálise enquanto que a propriedade 3 significa que deve resistir a força bruta.

A propriedade de número dois é a mais complicada. Facilmente se percebe que para cadeados normais ela não é atendida, pois qualquer chaveiro, mesmo nem tão habilidoso assim, consegue em minutos confeccionar uma nova chave para um cadeado, se puder analisá-lo. Eles conseguem até mesmo abrir um cadeado já fechado ou se existe muita pressa em abrir a caixa, nada que um alicate não resolva (propriedade 1).

Diffie e Hellman foram os primeiros acadêmicos a descobrir uma função matemática de mão única e a usaram como base ao protocolo de troca de chaves. Tentaram, sem sucesso, chegar ao assimétrico. Para que o assimétrico fosse possível, esta função de mão única precisa ser desfeita, mas apenas por quem conhece algum segredo em especial. Precisavam, desta forma, tornar a função de mão única reversível.

E foi isto que Ronald Rivest, Adir Shamir e Leonard Adlemann conseguiram.

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

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

A quebra do algoritmo RSA consiste simplesmente em se descobrir o valor de d da chave privada Kd. O d pode ser calculado pelo teorema de euclides, desde que se conheçam os valores do e e de qq (quociente de euclides).

Ora, o valor de e é publicamente conhecido, pois está exposto na chave pública Ke. Logo, quebrar o algoritmo RSA consiste em se descobrir o valor de qq, o quociente de euclides.

Como qq é calculado? Pela multiplicação de (P-1) por (Q -1), então, quebrar o RSA consiste simplesmente em encontrar os valores de P e Q.

Pensar em uma forma de encontrar os valores de P e Q é muito fácil, afinal sabe-se que o valor de N resultou da multiplicação destes dois números. Como o valor de N também é conhecido, pois está exposto na chave pública, quebrar o RSA é simplesmente respondera a pergunta

Quais os dois números que multiplicados um pelo outro resulta em N?

Se lhe é dito que o N é 299, a busca pelo P e pelo Q teria sucesso ao se achar P=13 e Q=23. Pronto. Fácil fácil. Um simples laço em qualquer linguagem de programação resolve isto rapidamente. Que tal uma versão do laço em bash:

Programadores em C, Java, PHP, Perl e até Basic não terão dificuldades em construir seus códigos para quebrar o RSA.

Se considerou isto uma tarefa fácil, topas um desafio?

Desafio 1 (VENCIDO)

Como incentivo será dado 500 pontos no Viva o Linux para o primeiro que responder corretamente os valores de P e de Q para os N propostos. Junto com a simples resposta deve vir um relato sobre o programa ou técnica usada e o tempo de processamento. Alunos e ex-alunos meus não podem participar, pois estudaram em sala de aula técnicas que os colocariam em vantagem em relação aos demais. Vamos lá, tente, já que não estou realmente enviando valores impossíveis.

Para o gerenciamento deste desafio foi criado o tópico Desafio RSA número 1 . Lá estarão todas as regras do desafio e os valores a serem quebrados. Todos estes detalhes serão colocados dois dias após a publicação deste artigo. Assim, caso o desafio ainda não tenha sido publicado, você tem um tempinho para ajustar sua ferramenta.

Desafio 2 (VALE LIVRO)

Após o desafio 1 ter sido vencido, criei outro valendo um livro. A definição e os resultados podem ser vistos em Ganhe um LIVRO aqui no Vol (Desafio 2 RSA)

Devo deixar claro que só serão aceitas respostas se você mesmo implementou sua própria ferramenta e disponibilizou o código fonte, conforme instruções do fórum. Outro aviso de extrema importância é que este desafio será realizado com a concordância do administrador do Viva o Linux, já que envolvem pontos.

Toda a segurança do RSA está focada em um problema matemático ainda sem solução, que é o cálculo de divisores de um número. Ainda hoje a única forma conhecida para se calcular quais números dividem exatamente, sem resto, um outro número é através da tentativa e erro, ou seja, a força bruta. Muitos avanços se tem feito e muitas técnicas usadas para acelerar em muito esta tarefa, mas ela ainda é um problema que demanda muito tempo.

Contudo, basta que algum matemático descubra como calcular os divisores de um número de forma eficiente e pronto, fim do RSA. Se é que algum pesquisador secreto já não o tenha descoberto.

Faz alguns anos o RSA foi posto em cheque devido a uma descoberta envolvendo números primos. O desafio de determinar se um número é ou não primo também demanda tempo. Como tu poderias dizer que o número 65537 é ou não primo? A princípio tentando dividir ele por todos os números primos anteriores a ele. Tenta-se dividir por 2, por 3, por 5 (não teria sentido tentar por 4, pois se fosse divisível por 4, já o teria sido por 2), por 7, 11, 13… Se não se encontrar um divisor até o valor da raiz quadrada de 65537, pode-se com segurança eleger este número como sendo primo.

Esta parte foi um desafio para o RSA. Como o algoritmo, que precisa escolher P e Q primos, pode ter certeza de que são primos? O número P=339837669899793087932310819184919452667 gerado pela biblioteca openssl é primo? Como o RSA tem certeza? O fato é que não tem! Quando da escolha de P e Q não se tem certeza de que eles realmente são primos. O impacto caso não sejam é que o algoritmo ficará mais fraco, mas funcionará tranquilamente.

Chegar a conclusão de que P é realmente primo demandaria o mesmo esforço que um atacante teria para quebrar o N. Por isto o RSA limita-se a aplicar os 3 testes da primaridade. Se ele reprovar em um dos testes, não é primo e será descartado. Se passar em todos os testes, tem uma chance de X% de ser primo. Ao executar os testes várias vezes refina-se a precisão tendo-se, hoje, quase certeza de que são primos.

Pois bem, a descoberta recente (e nem tão recente assim) foi de um algoritmo que dá 100% de certeza de que um número é primo. Isto, por si só, não compromete o RSA pois o que se precisa é de um algoritmo que descubra o P e o Q a partir do N. Contudo aquela “luzinha vermelha” acabou se acendendo e uma névoa de suspeita paira sobre o RSA.

Pretendia tornar este artigo ainda mais extenso, com muitos anexos descrevendo o teorema de Euclides e os atalhos matemáticos para cálculo de módulo. Porém, estes conceitos são necessários para alunos meus resolverem alguns desafios e não pretendo publicar algo que lhes tire o prazer da descoberta!