O problema, que parece impossível

Até 1976, todo mundo que pensava em mensagens secretas concordava numa coisa: antes de duas pessoas trocarem segredos, elas precisam primeiro compartilhar uma chave, e compartilhar a chave é a parte difícil. Exércitos usavam mensageiros com maletas trancadas. Bancos mandavam funcionários de avião. Embaixadas usavam malas diplomáticas. A mensagem podia viajar por qualquer meio; a chave tinha de viajar por um meio confiável.

Isso funciona quando as duas partes podem se planejar. Não funciona de jeito nenhum para o que fazemos o tempo todo hoje: seu navegador nunca viu o servidor da loja, não há mensageiro disponível, e você quer comprar algo nos próximos quatro segundos.

Então eis o problema na forma pura. Você e um estranho estão numa sala cheia de gente. Todos ouvem tudo o que qualquer um de vocês diz. Quando pararem de falar, você e o estranho precisam saber o mesmo número, e ninguém mais na sala pode sabê-lo. Vocês nunca se viram e não compartilham nada de antemão.

A primeira reação da maioria é que isso é obviamente impossível. Não é, e a razão vale uma tarde do tempo de qualquer pessoa.

Tinta

A ilustração padrão é misturar tinta, e ela é boa o bastante para carregar a ideia inteira.

Suponha que misturar duas cores seja fácil, mas desmisturar seja impossível - dado um balde de verde barrento, ninguém consegue dizer quais duas cores entraram nem em que proporção. Essa única assimetria é tudo de que precisamos.

  1. Você e o estranho combinam, em voz alta na frente de todos, uma cor inicial. Digamos amarelo. Todos na sala agora sabem: amarelo.
  2. Você escolhe em segredo uma cor - vermelho - e não conta a ninguém. Mistura seu vermelho num pote do amarelo público, produzindo laranja, e entrega o pote laranja ao estranho. Todos veem o laranja.
  3. O estranho escolhe em segredo a cor dele - azul - mistura no próprio pote de amarelo, produzindo verde, e lhe entrega o verde. Todos veem o verde.
  4. Você acrescenta o seu vermelho secreto ao verde que recebeu. O estranho acrescenta o azul dele ao laranja que recebeu.

Os dois terminaram com amarelo mais vermelho mais azul. A mesma cor. E a sala viu amarelo, laranja e verde - e, para chegar à cor compartilhada a partir dessas, teria de desmisturar uma delas, o que dissemos ser impossível.

Isso é o . Todo o resto é aritmética que se comporta como tinta.

A aritmética que se comporta como tinta

O truque é achar números que se misturem fácil e se desmisturem impossivelmente. A operação usada é a exponenciação com resto, e se a expressão não lhe diz nada, pense num relógio.

Num relógio de doze horas, nove horas mais seis horas dá três horas. O número passou do doze e deu a volta, e aqui está o ponto: uma vez que deu a volta, você não consegue olhar a resposta e dizer quantas voltas foram. Três horas pode significar três, ou quinze, ou vinte e sete. Informação foi destruída, de forma barata e irreversível.

Agora faça isso com multiplicação em vez de soma, num relógio com um número primo enorme de horas em vez de doze. Pegue um número público, multiplique-o por ele mesmo um número secreto de vezes, e fique só com o resto. Multiplicar é rápido. Trabalhar de trás para frente, do resto até quantas vezes você multiplicou - o logaritmo discreto - é, até onde alguém publicou em cinquenta anos, inviável para números do tamanho que usamos.

É tudo. Eis a única equação deste artigo, e você pode lê-la como uma frase:

segredo compartilhado = (valor público do outro) ^ (meu segredo) mod p

Os dois lados calculam isso, cada um usando o próprio segredo e o valor público do outro, e os dois chegam à mesma resposta - pela mesma razão que amarelo mais vermelho mais azul é igual a amarelo mais azul mais vermelho. A ordem da mistura não importa. Quem escuta tem os dois valores públicos e o número inicial, e precisa de um segredo para combiná-los, e não consegue nenhum sem resolver o problema que ninguém sabe resolver.

A parte que quase toda explicação deixa de fora

Tudo acima é verdade e é também, sozinho, insuficiente - e esta é a parte de que um profissional precisa e que um leitor comum merece.

No fim da troca você compartilha um segredo com alguém. O Diffie-Hellman não lhe dá jeito nenhum de saber com quem. Se um terceiro se põe entre você e o estranho e roda o procedimento inteiro duas vezes - uma com você, fingindo ser o estranho, outra com o estranho, fingindo ser você - então ele fica com dois segredos compartilhados, decifra tudo de um lado, lê, e recifra para o outro. Os dois veem uma conexão segura funcionando perfeitamente. Este é o problema do intermediário, e não é um defeito do Diffie-Hellman; é uma pergunta que o Diffie-Hellman não responde.

A resposta vem de outro lugar: os certificados, que têm artigo próprio e que existem para permitir que um lado prove ser quem afirma. Todo cadeado de navegador é a soma das duas metades - o Diffie-Hellman para acordar um segredo que mais ninguém sabe, e um certificado para estabelecer que o alguém do outro lado é a loja e não um estranho no meio.

Por que isso também faz o tráfego antigo continuar secreto

Há uma segunda consequência que vale ter, porque explica uma expressão que aparece em toda discussão de segurança.

Como os segredos da troca podem ser jogados fora no momento em que a conversa termina, um atacante que grave seu tráfego cifrado hoje e roube a chave de longo prazo da loja daqui a cinco anos ainda assim não consegue lê-lo: a chave que cifrou aquela conversa nunca foi guardada em lugar nenhum e não existe mais. Essa propriedade se chama sigilo futuro, e é por isso que o protocolo moderno usa esta troca a cada conexão, em vez de cifrar uma chave com a permanente do servidor.

De onde veio

e publicaram New Directions in Cryptography em novembro de 1976, e a primeira linha não é o pigarro acadêmico de sempre: estamos hoje à beira de uma revolução na criptografia. Estavam certos. vinha trabalhando numa ideia relacionada de forma independente em Berkeley, e o relato do próprio Hellman sobre a colaboração é generoso e vale repetir - cada um tinha uma parte-chave do quebra-cabeça, e foi o vaivém entre eles que produziu a descoberta. Hellman defendeu depois que o esquema deveria levar também o nome de Merkle. Os três estão na patente de 1977.

Duas notas de rodapé pertencem a isso, e são a razão de este artigo estar num catálogo de segurança e não de matemática.

Eles não foram os primeiros, mas foram os primeiros a contar a alguém. No GCHQ, a agência britânica de inteligência de sinais, conceituara a possibilidade por volta de 1969-70 e produzira um algoritmo para ela em 1973. Um ex-diretor da agência americana disse depois que a criptografia de duas chaves fora achada lá cerca de uma década antes de 1976, sem dar detalhes. Nada disso chegou ao público, e portanto nada disso protegeu ninguém. A comparação é o argumento a favor da pesquisa aberta num único dado: o trabalho classificado existiu e não mudou nada; o trabalho publicado mudou tudo.

E publicá-lo foi uma briga. Diffie e Hellman também publicaram um artigo sustentando que a agência americana pressionara a IBM a enfraquecer o padrão DES limitando sua chave a 56 bits - os mesmos 56 bits que a Electronic Frontier Foundation depois demonstrou poderem ser quebrados por um quarto de milhão de dólares. A resposta foi um esforço concertado para restringir a distribuição da pesquisa deles, que é o capítulo de abertura das crypto wars e uma das razões de este site ter um artigo sobre elas.

Receberam o Turing Award pelo trabalho em 2015, trinta e nove anos depois.

A única coisa a lembrar

Se não levar mais nada: duas pessoas que nunca se viram podem combinar um segredo em público, porque algumas operações são fáceis de fazer e impossíveis de desfazer. Todo o resto da segurança moderna está construído em cima dessa frase, e as pessoas que a disseram primeiro em voz alta quase foram impedidas de fazê-lo.

Fontes