Detalhes

Categoria: Chave Pública

Atualização: Terça, 14 Abril 2009 14:44

Autor: vovó Vicki

Acessos: 35243

O algoritmo Diffie-Hellman foi o primeiro algoritmo de chave pública a ser inventado. Isto signidica que seus autores também são os donos da idéia. O algoritmo pode ser usado para a distribuição de chaves, mas não para cifrar ou decifrar mensagens. Sua segurança reside na dificuldade de calcular logaritmos discretos num campo finito comparada com a facilidade de realizar exponenciações no mesmo campo. Se você ficou confuso com tudo isto, não se preocupe. Leia o restante do texto e aprenda a mágica de Diffie-Hellman

Um pouco da história

Whitfield
Diffie

Whitfield Diffie nasceu em Nova Iorque, EUA, em 1944. Desde criança tinha fascínio pela matemática e foi por isto que acabou estudando no MIT - Massachusetts Institute of Technology, formando-se em 1965. Depois disto trabalhou com segurança de computadores até que, em 1970, estava pronto para uma carreira solo - transformou-se num dos poucos especialistas em segurança realmente independente, sem vínculos com o governo ou com grandes corporações. Seus cabelos longos e seu jeito de ser fazem de Diffie uma espécie de hippie da alta tecnologia e, sem dúvida alguma, pode ser considerado o primeiro cypherpunk da história.

Um dos problemas que mais chamava a atenção de Diffie era o problema da distribuição de chaves. Acompanhando a evolução da organização de pesquisa ARPA (Advanced Research Projects Agency), fundada pelo Departamento de Defesa dos EUA, a qual, em 1969, criou o sistema de comunicação em rede chamado de ARPANet, Diffie sentia que uma revolução estava prestes a acontecer e que o projeto abria as portas para o desenvolvimento de uma supervia de comunicação. O tempo mostrou que seu prognóstico estava certo (em 1982 nascia a Internet) e que sua preocupação com o sigilo e a privacidade dos usuários de uma grande rede era mais do que justificado. Neste contexto, sabia que a criptografia se transformaria numa ferramenta essencial e que o problema da distribuição de chaves se tornaria especialmente agudo.

Martin
Hellman

Em 1974 Diffie foi convidado para dar uma palestra na IBM e o tema, como não poderia deixar de ser, foi sobre as várias estratégias de ataque à distribuição de chaves e propostas para algumas soluções. A reação dos ouvintes não foi das mais calorosas. Os monstros sagrados da IBM, assim como todo mundo, tinham a idéia preconcebida de que este era um problema insolúvel (e não seria um cabeludo que iria mudar as coisas). A única resposta positiva foi a de Alan Konheim, um dos especialistas em criptografia da IBM. Comentou que Martin Hellman, professor da Universidade de Stanford, Califórnia, também havia proferido uma palestra destacando o problema da distribuição de chaves. Foi o que bastou para Diffie atravessar os EUA à procura da pessoa que, aparentemente, era a única que compartilhava suas opiniões.

Martin Hellman nasceu no Bronx, Nova Iorque, EUA, em 1945. Judeu numa vizinhança católica, teve problemas de autoafirmação desde a infância. Ele conta que este foi um dos motivos pelos quais começou a se interessar pela criptografia - já que era diferente, queria ser diferente de vez. Até a inesperada visita de Diffie em 1974, o famoso livro de David Kahn, The Codebreakers, tinha sido o livro de cabeceira e a única fonte de informação de Hellman. Depois de uma meia hora de conversa, um estava impressionado com o conhecimento do outro e perceberam que não estavam mais sozinhos na busca de uma solução "impossível". Apesar das evidentes diferenças de personalidade, este foi o começo de uma grande amizade e companheirismo. Imediatamente começaram a arquitetar um plano para poderem trabalhar juntos. Como Diffie não tinha condições de contratar o novo amigo como pesquisador, Hellman resolveu registrar Diffie como estudante graduado de Stanford. E a peregrinação começou...

Ralph Merkle

Após algum tempo de trabalho conjunto, Ralph Merkle se juntou aos dois. Merkle era um refugiado intelectual de um outro grupo de pesquisa cujo professor não simpatizava nem um pouquinho com as idéias mirabolantes de distribuição de chaves de Merkle. Era o "maluco beleza" ideal e sua ajuda era mais do que bem vinda. Estava formado o trio, os três mosqueteiros desta história.

O problema da distribuição de chaves

O problema da distribuição de chaves é o mesmo que o do ovo e da galinha. Se duas pessoas quiserem trocar mensagens secretas, elas precisam cifrar as mensagens. Para cifrá-las e decifrá-las, precisam de uma chave secreta. Como esta chave também precisa ser transmitida, teria que ser cifrada com outra chave, e assim indefinidamente.

Uma forma bastante simples de resolver o problema das chaves seria usar cadeados. Digamos que Maria queira enviar uma mensagem para João. Ela coloca a mensagem numa caixa de metal, fecha a caixa com um cadeado (só ela tem a chave deste cadeado) e a envia para João. João também coloca um cadeado na caixa (só ele tem a chave deste segundo cadeado) e devolve a caixa para Maria. Ao receber a caixa, Maria abre e retira o seu cadeado e, novamente, envia a caixa para João. Agora, João pode tirar o seu cadeado, abrir a caixa e ler a mensagem. Esquema perfeito? Quase...

Funções matemáticas

Se as funções matemáticas necessárias para cifrar uma mensagem tivessem um comportamento igual ao dos cadeados, a solução encontrada por João e Maria seria perfeita. Infelizmente, este não é o caso As funções matemáticas precisam ser "retiradas" na ordem inversa em que foram "colocadas", o que não é necessário quando se trata de cadeados. Apesar disto, este foi o ponto de partida usado por Diffie e Hellman.

A maioria das funções matemáticas são facilmente reversíveis e, por este motivo, podem ser chamadas de funções bidirecionais (eu costumo chamá-las de funções gangorra ). Uma função multiplicativa é reversível, fácil de resolver e um ótimo exemplo. Digamos que f(x) = 2x. Neste caso, se x = 3, então f(x) = 2 x 3 = 6. Conhecendo a função pode-se calcular x com rapidez, independentemente do tamanho do resultado da função. Por exemplo, se f(x) = 1000, podemos fazer a conta de cabeça e chegar em x = 500. Até aí, nada de muito especial. Acontece que Diffie e Hellman estavam concentrando esforços na procura de uma função unidirecional ou de mão única.

Podemos definir uma função unidirecional como sendo uma função que não tem volta (esta seria a verdadeira função unidirecional) ou cuja volta é tão complicada ou demorada que, na prática, a volta se torna inviável.

A aritmética modular

Uma excelente fonte de funções unidirecionais é a aritmética modular. A aritmética modular é uma área da matemática onde se lida com uma quantidade finita de números arranjados como num mostrador de relógio. Por isto a aritmética modular também é conhecida como aritmética circular. Usando o mostrador do relógio como exemplo, é fácil entender como funciona. A primeira coisa é saber que o mostrador possui apenas 12 números, portanto, o relógio mostra as horas em módulo 12 (este é o campo finito citado na introdução). Apesar desta limitação, costumamos dizer, por exemplo, 15 horas. Como estamos acostumados a raciocinar neste módulo, imediatamente sabemos que o ponteiro das horas está no 3. Na verdade fizemos um pequeno cálculo mental (15 - 12 = 3) que infelizmente não é tão eficiente quando falamos, por exemplo, 43 horas. Onde estará o mostrador do relógio quando são 43 horas? Estará no 7 porque o ponteiro deu 3 voltas completas (3 x 12 = 36) e depois avançou mais 7 posições (43 - 36 = 7). Resumindo, para achar o módulo de um número (ou de uma operação), divide-se este número (ou o resultado) pelo módulo e se considera apenas o resto.

     43 (mod 12) = 43 ÷ 12 =  3 com resto 7 --> 43 (mod 12) = 7
     59 (mod  5) = 59 ÷  5 = 11 com resto 4 --> 59 (mod  5) = 4
     
     da mesma forma
     
     2 + 3 (mod 7) = 5 porque  5 ÷ 7 = 0 com resto 5
     2 + 9 (mod 7) = 4 porque 11 ÷ 7 = 1 com resto 4
     3 x 3 (mod 7) = 2 porque  9 ÷ 7 = 1 com resto 2

O comportamento errático dos resultados modulares faz com que a reversão de uma operação modular seja bem mais trabalhosa do que a reversão de uma operação normal. Se considerarmos a função 4^x, por exemplo, à medida que o valor de x aumentar, o valor do resultado também aumenta. A mesma função em qualquer módulo, no entanto, não mostra a mesma linearidade. Observe a seguir:

     41 =    4          41 (mod 11) = 4
     42 =   16          42 (mod 11) = 5
     43 =   64          43 (mod 11) = 9
     44 =  256          44 (mod 11) = 3
     45 = 1024          45 (mod 11) = 1

Quando os valores são pequenos, como os mostrados no exemplo, montar uma tabela para encontrar o valor de x procurado não é nenhum bicho de sete cabeças. Mas imagine encontrar pela frente alguma coisa como 1793^x (mod 32748) ou outros números bem maiores. Em primeiro lugar já haveria um problema com as calculadoras (e, dependendo do tamanho dos números, até com o computador) e, em segundo lugar, o processo pode ser tão demorado que você levaria a vida inteira para achar o resultado correto. É por isto que este é um exemplo clássico de função unidirecional.

Como pesquisadores tarimbados, Diffie e Hellman sabiam que nada podia ser desprezado, mesmo aquilo que parecesse ser coisa que as crianças aprendem no primeiro grau. Depois de dois anos de trabalho com as funções unidirecionais oferecidas pela aritmética modular, Hellman finalmente conseguiu provar o que até então era considerado impossível: remetente e destinatário poderiam usar uma estratégia que punha o problema da distribuição de chaves a nocaute!