Fundamentos da criptografia assimétrica



Autor: Elgio Schlemer <elgio.schlemer at gmail.com>

Introdução

Usar técnicas matemáticas para esconder o significado de uma informação não é um artifício de uso recente, pois muito se usou em guerras ou mesmo incidentes governamentais. Histórias incríveis podem ser obtidas, por exemplo, no fantástico livro de Simon Singh, “O Livro dos Códigos”.
Basicamente um algoritmo de criptografia pode ser dividido em simétrico ou assimétrico. Os algoritmos simétricos são aqueles que simplesmente possuem uma chave e esta precisa ser compartilhada entre as partes envolvidas na comunicação secreta (Introdução a criptografia, uma leitura desejável antes de prosseguir a leitura deste).
Os simétricos ainda podem dividir-se em dois tipos, os chamados cifras de bloco e os de fluxo (veja Criptografia chave simétrica de bloco e de fluxo).
A ciência da criptografia pode ser descrita como a eterna e incansável guerra entre os criptógrafos, que querem esconder informações, e os criptoanalistas, que querem torná-las legíveis.
Durante a segunda guerra mundial, por exemplo, os alemães usaram a famosa máquina Enigma para cifrar suas mensagens. Aliados tentavam achar fraquezas neste equipamento a fim de quebrá-lo mas tinham certas dificuldades, seja pela falta de informações ou pela força do algoritmo em si. O desafio era ainda maior pois a chave usada pelos alemães trocava diariamente, sendo que cada mensagem ainda tinha três letras aleatórias em uma espécie de chave de sessão. Descobrir, com algum esforço, a chave do dia era uma vitória, pois todas as mensagens seriam decifradas, mas os aliados voltariam a estaca zero a meia noite, quando a chave usada pelos alemães seria substituída.
Contudo, se o uso da enigma desta forma era um desafio para os aliados, também o era para os alemães. Com navios, submarinos e exércitos espalhados em vários pontos e com uma chave descartável, usada somente durante um único dia, como dar a conhecer aos operadores de rádio a chave do próximo dia? Não se pode simplesmente transmití-la, mesmo que de forma cifrada. Não é nada seguro transmitir a chave da terça-feira para todos, cifrando-a com a chave da segunda, pois se os aliados conseguiram quebrar a chave da segunda podem simplesmente ler a nova chave sem esforço algum.
Os alemães resolveram isto com a publicação de livros de códigos. Cada livro tinha chaves para vários dias e era entregue em mãos ao operador de comunicações. Este tinha fortes recomendações para destruir o livro e o equipamento imediatamente quando estiver prestes e ser capturado. Jamais deveria o livro e tampouco a máquina, cair em mãos inimigas.
A primeira maneira que os aliados encontraram para quebrar a enigma foi subornar um oficial alemão descontente que lhes entregava uma cópia do livro. Hans-Thilo Schmidt sentia-se rejeitado pelo exército e tinha ciúmes do sucesso de seu irmão mais velho, do alto escalão alemão. Devido a influência deste seu irmão, acabou em um cargo burocrático e logo passou a vender informações para um agende secreto francês. E eis que um forte esquema de cifras, com chaves de uso diário, é posto por terra por causa de uma fraqueza humana e o compartilhamento de chaves.
A máquina enigma acabou sendo quebrada de forma definitiva por Alan Turing e suas “bombas” (a história de Turing é muito triste. Sem jamais receber reconhecimento em vida, um dos maiores gênios da criptoanálise acabou cometendo suicídio em 7 de Junho de 1954).
O mais interessante neste assunto de criptografia é todo o sigilo existente em torno dele. O mundo só tomou conhecimento de todos estes detalhes muitos anos depois, permanecendo um completo segredo até então e, talvez, com os alemães ainda achando que sua Enigma fora inquebrável.
Nos dias de hoje não é diferente. Já que não é possível confiar nos meios de comunicação, não se pode usá-lo para transmitir uma chave que será futuramente usada em uma conversa cifrada. A princípio a única maneira realmente segura de troca de um segredo é presencialmente, ou seja, as partes realizando um encontro pessoal e físico.
Mas existiria alguma forma realmente segura e confiável de realizar uma troca de chaves de forma sigilosa sem que um encontro físico ocorresse? Todos haviam desistido desta busca.

A utopia da troca de chaves de forma segura

Resolver o problema da troca de chaves não foi nada fácil, sendo que a busca por tal mecanismo acabou virando uma espécie de Santo Graal dos criptógrafos. Depois de muito esforço, pesquisas sem sucesso, a comunidade científica havia decretado como insolúvel o problema da distribuição de chaves. Somente os tolos insistiriam em tal bobagem.
Mas “Deus Recompensa os Tolos” (sub-título de “O Livro dos Códigos”, página 277) e principalmente os teimosos como Whitfield Diffie. Mesmo desacreditado pelos criptógrafos mais brilhantes, ele ainda assim, “ingenuamente”, se interessou pelo problema da distribuição de chaves e trabalhou em uma solução. Quando começou a trabalhar junto com outro “lunático”, o Martin Hellman, as coisas começaram a fazer sentido.
Tiveram uma adesão e posterior desistência de Ralph Mekle, que não acreditou muito neste sonho impossível. O próprio Hellman tentou motivar Ralph escrevendo-lhe “…você tem a ideia número 1, fica empolgado e depois fracassa. Ai tem a ideia número 2, fica empolgado e também fracassa. Você tem a ideia número 99, fica empolgado e também fracassa. Só um tolo insistiria na ideia de número 100. Mas Deus recompensa os tolos.” (“O livro dos Códigos”, página 281, reproduzindo apenas alguns trechos).
Diffie e Hellman sempre citavam um experimento que servia como inspiração (que eu chego até a reproduzir em sala de aula). Apesar de ser considerado impossível a troca de informações de forma segura sem uma chave compartilhada, o mesmo podia incrivelmente ser realizado através dos correios.
Imagine que Cabelo e Fábio (eu não aguento mais a Alice e o Bob!) desejam trocar um documento sigiloso. Na verdade o Cabelo, que mora em Bebedouro deseja enviar ao Fábio detalhes secretos sobre o seu novo esquema de autenticação biométrica por cheiro (com tolerância a falhas em caso de falta de banho). Infelizmente Cabelo não pode algemar uma mala de documentos em seu pulso e viajar até um encontro pessoal com Fábio. Então ele decide enviar pelos correios.
Mas como? Como ele poderia enviar pelos correios de forma segura, sem que ninguém possa ler o conteúdo dos documentos?
Ele poderia colocar os documentos em uma caixa super forte, e fechá-la, enviando-a ao Fábio. Mas aí cai-se no problema original: Cabelo teria que enviar a chave da caixa ao Fábio, senão como Fábio a abriria? Esta novamente se falando de compartilhamento de chaves.
Porém existem uma solução extremamente criativa e funcional, descrita a seguir:

  1. Cabelo vai em qualquer ferragem e compra um cadeado e uma caixa, coloca os documentos dentro desta caixa e a fecha com seu cadeado;
  2. Cabelo envia pelo correio a caixa fechada ao Fábio, mas não envia a chave, sendo que no trajeto, ninguém pode abrir a caixa, pois ela está fechada com um cadeado que somente Cabelo tem a chave;
  3. A caixa chega às mãos de Fábio. Fábio também não pode abrir, pois não tem a chave;
  4. Fábio vai em uma ferragem e compra outro cadeado e o fecha na caixa que já tem o cadeado de Cabelo, deixando-a com dois cadeados, o cadeado F e o cadeado C;
  5. Fábio devolve a caixa para Cabelo com os dois cadeados;
  6. Cabelo recebe a caixa e agora nem mesmo ele pode abrir, pois lhe falta a chave do cadeado F;
  7. Cabelo abre seu cadeado C removendo-o da caixa e a devolve para Fábio, agora apenas com o cadeado F;
  8. Fábio recebe a caixa, agora apenas com o seu cadeado, e finalmente a abre com sua chave e lê os documentos.

Com este método jamais alguma chave foi enviada. Fábio manteve sob sua custódia a chave do cadeado F e Cabelo manteve a chave do cadeado C. Não houve compartilhamento de chaves. Tem-se um método seguro de troca de informações (na verdade este protocolo pode ser derrubado pelo ataque do Homem do meio, mas isto é assunto para depois).
Este procedimento torna-se possível se existirem três propriedades importantes no cadeado e na caixa:

  1. Força: a caixa e o cadeado são fortes, a prova de qualquer alicate que se tenha conhecimento;
  2. Segurança: não é possível construir uma chave apenas analisando o cadeado fechado (criptoanálise) e também não é possível tentar-se todos os possíveis padrões de chaves até abrir (força bruta);
  3. Comutatividade: a ordem de fechamento dos cadeados não precisa ser a mesma de sua abertura. Pode-se colocar na caixa 10 cadeados, de 1 a 10, todos “em paralelo” mas pode-se removê-los em qualquer outra ordem. Não daria certo, se, por exemplo, se Fábio pegasse a caixa fechada de Cabelo e colocasse tudo dentro de uma caixa maior, fechando esta com seu cadeado.

Diffie e Hellman precisavam apenas encontrar um princípio matemático com estas três propriedades. Quando encontraram, não apenas criaram o famoso algoritmo Diffie-Hellman como abriram as portas para uma nova era no ramo da criptografia.

Os “tolos” venceram

Um princípio matemático que respeitasse a característica três (comutatividade) é extremamente fácil e não era mistério. Soma ou multiplicação são exemplos bem simples disto.
Como o real princípio matemático (que irei descrever e demonstrar) é um tanto complexo, vou antes explicar a ideia do algoritmo usando o princípio da multiplicação, apenas para finalidades didáticas:

Linux: Fundamentos da criptografia assimétrica

Da forma como ilustrado, nenhuma das informações que está em vermelho (1357, 35, 89) foi transmitida, no entanto o Receptor foi capaz de recuperar com sucesso a informação correta.
Considerando que um atacante, observando o tráfego, tenha cópias de todas as mensagens, ele tem os valores da mensagem a (47.495), da mensagem b (4.227.055) e da mensagem c (120.773), mas não tem a chave.
O que torna a multiplicação inviável é justamente porque o atacante tem como descobrir estes valores apenas com as mensagens que obteve. Se o atacante dividir b por a, terá o cadeado do receptor (4227055/47495=89). Óbvio! Se ele dividir b por c terá o cadeado do Emissor. Pronto. Não serve. Era necessário não apenas um princípio matemático que tivesse as propriedades citadas, mas que também fosse irreversível. Multiplicação não serve, pois a divisão o reverte.
Finalmente Diffie e Hellman descobriram isto na operação de módulo. Qual é a expressão matemática que desfaz uma operação de módulo?
Módulo, lembra? O resto de uma divisão. Se eu pergunto quanto é 135 MOD 12, facilmente alguém calcula 3 (qual o resto da divisão de 135 por 12?).
Mas e se eu disser que 1239 MOD X = 21, como vocês fariam para descobrir o valor de X? Qual o número (X) que quando se divide 1239 por ele resulta em resto 21? Vocês provavelmente irão fazer por tentativa e erro, ou seja, ir tentando valores de X até achar um que dê 21. Ao tentar o 29, verão que 1239 MOD 29 resulta em 21.
Mas apenas a operação de módulo em si ainda não serve, pois existem vários candidatos a X (29, 42, 58, 87, 174, 203, 406, 609, 1218, …) e ao menos um deles pode ser facilmente calculado. E ainda tem sim uma forma matemática para reverter esta expressão (deixo como desafio).
Mas que tal esta expressão então:
23X mod 1311 = 1127
Qual é o valor de x?
Agora sim, você terá mesmo que ir testando valores de x na expressão até encontrar um que resulte em 1127. Ao tentar o valor 7 você terá sucesso. Não existe uma fórmula matemática que calcule o x de forma direta.
Finalmente os tolos descobriram o Santo Graal!

Algoritmo Diffie-Hellman

Com a descoberta do princípio matemático, todas as propriedades foram satisfeitas. A força, evidentemente, deve ser obtida através da escolha de números realmente muito grandes, que inviabilize o esforço da tentativa e erro.
Porém, como números grandes demandam operações aritméticas gigantescas, irei demonstrar o funcionamento do algoritmo usando números pequenos, para que todos possam reproduzir em suas calculadoras de linha de comando bc!
O algoritmo de troca de chaves Diffie-Hellman constitui em uma série de operações matemáticas feitas por ambas as partes, sendo que ambos chegarão a um mesmo valor, a um mesmo número. Este número pode ser usado, então, como chave para algum algoritmo simétrico. Ele permite compartilhar uma única chave entre duas partes mas sem jamais enviá-la pela rede e sem possibilidade de alguém a descobrir.
Consiste nas seguintes etapas, feitas por ambas as partes:

  1. Ambos, em conjunto, escolhem dois números que não serão segredos, o número P e E. P deve ser um número primo e E deve ser menor que o P.
  2. Cada um escolhe para si um número X, mantendo-o em segredo
  3. Cada um usa o seu valor de X na operação modular, envolvendo P e E. Obtém com isto um número que chamaremos de Y
  4. Cada um envia para o outro o seu valor de Y
  5. Cada um realiza novamente a operação de módulo, porém usando o Y que recebeu do outro. Magicamente ambos obterão o mesmo resultado.

Confuso? Acredito que um exemplo completo, com operações e valores reais ajude na compreensão.

Linux: Fundamentos da criptografia assimétrica

Com números pequenos ainda se é vulnerável ao ataque por força bruta, pois o atacante, não tendo nenhum dos valores de X, poderá tentar usar alguns possíveis valores até acertar. Porém se usar números realmente grandes, da ordem de 512 bits, o número de tentativas torna inviável este ataque.

Conclusão

Com esta descoberta se abriram as portas para uma nova era de algoritmos de criptografia. De Diffie-Hellman para um algoritmo assimétrico de verdade é apenas um pequeno passo.
O algoritmo por si só é vulnerável ao ataque do homem do meio, ataque este que também derruba o forte protocolo SSL. Justamente por causa dele é que torna-se necessário as certificadoras digitais.
Antigamente, no SSL, o cliente ficava responsável por escolher uma chave de sessão completamente aleatória. Clientes mal implementados o faziam com displicência, escolhendo chaves previsíveis, como o caso de uma das versões do Netscape. Usando o Diffie-Hellman, a chave de sessão não é escolhida, mas sim calculada por valores aleatórios que ambas as partes escolheram. Mesmo que um cliente seja irresponsável, escolhendo um X previsível, o protocolo está salvo se o servidor escolher o seu X de uma forma mais decente.
Deve-se mencionar também que todo o esforço de Diffie em ser o primeiro a chegar em uma algoritmo desta natureza foi em vão. Cientistas ligados a governos haviam achado um algoritmo semelhante anos anteriores, mas esta notícia só se tornou pública muitos anos depois. Coisas da criptografia.
Se hoje acredita-se em alguns princípios matemáticos cruciais para a criptografia, como a fatoração de números primos ou a não reversão da operação de módulo, esta crença se dá unicamente ao fato de que ninguém ainda descobriu como vencê-los. Ou, se descobriu, não nos pode contar por força de seus cargos. Daqui a dezenas de anos talvez nos surpreendamos com o fato de que o RSA de 1024 bits já é, hoje, café da manhã na mesa dos cientistas da NSA.
Por fim, quando comecei a escrever este artigo o mesmo era para entrar no conceito dos algoritmos assimétricos, estudando o RSA e finalizando com seu emprego no protocolo SSL e em assinaturas digitais. Quanto vi que esta ideia viraria um “livro”, decidi fragmentar a informação. Portanto, fico-vos devendo para um futuro próximo outros artigos para completar a série.


Fonte: http://www.vivaolinux.com.br/artigo/Fundamentos-da-criptografia-assimetrica

Anúncios

Publicado em 7 de janeiro de 2012, em Vivaolinux e marcado como . Adicione o link aos favoritos. 3 Comentários.

  1. José Ricardo da Rocha Catuta

    Descupe o atraso mas como se chama o livro?

    Curtir

Um comentário começa grandes debates!

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: