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.