Na criptografia , a troca de chaves Diffie-Hellman , em homenagem a seus autores Whitfield Diffie e Martin Hellman , é um método, publicado em 1976, pelo qual dois agentes , convencionalmente chamados de Alice e Bob , podem concordar com um número (que podem usar como um chave para criptografar a próxima conversa) sem um terceiro agente chamado Eve sendo capaz de descobrir o número, mesmo depois de ter escutado a todas as suas trocas. Essa ideia rendeu aos dois autores o Prêmio Turing em 2015 .
Vamos primeiro dar uma explicação intuitiva fazendo uma analogia com as cores. O objetivo é que Alice e Bob concordem em uma cor secreta, sem que Eva seja capaz de saber. Esta explicação é pictórica e não faz sentido prático, mas ajuda a compreender a essência da troca de chaves Diffie-Hellman. Presumimos que os agentes podem misturar cores, mas é difícil (especialmente para Eva!) Extrair as cores usadas para fazer uma mistura. O princípio é o seguinte.
No final do protocolo, Alice e Bob têm a mesma cor marrom, que representa a cor secreta compartilhada. Supondo que seja difícil para Eva extrair as cores usadas para obter as cores públicas laranja e azul, Eva não conhece a cor marrom final.
No princípio original descrito abaixo, um número primo p é escolhido. As “cores” são números do módulo p. Misturar duas cores consiste em elevar um número a um determinado módulo de potência p. Encontrar as cores usadas em uma mistura corresponde a reverter a exponenciação, que é um problema algorítmico difícil.
Descrevemos o princípio original.
No final do protocolo, Alice e Bob sabem o número g ab [mod p ], mas não Eve. Uma vez que é difícil reverter a exponenciação em um corpo finito (ou em uma curva elíptica), ou seja, para calcular o logaritmo discreto , Eve não pode descobrir, portanto, não pode calcular g ab [mod p ].
Na descrição acima, Alice e Bob estão trabalhando no campo finito Z / p Z , eles trocarão os números do módulo p . De modo geral, a troca de chaves Diffie-Hellman generaliza para qualquer grupo cíclico finito (em vez de concordar com um número primo p, eles concordam com um grupo finito). Este grupo finito pode ser um corpo finito , do qual eles usam apenas a multiplicação, ou uma curva elíptica .
Na prática, podemos tomar um primo p de Sophie Germain (tal que q = 2p + 1 primo também) de tamanho grande e um gerador g em Z / pZ (g é, portanto, primo com p-1).
O método utiliza a noção de grupo , por exemplo o grupo multiplicativo de inteiros módulo p , onde p é um número primo: neste caso, as operações matemáticas (multiplicação, potência, divisão) são realizadas módulo p, ou seja - digamos por mantendo apenas o restante da divisão euclidiana por p. Como os grupos têm a propriedade de associatividade , a igualdade ( g b ) a = ( g a ) b é válida e ambas as partes realmente obtêm a mesma chave secreta.
A segurança desse protocolo reside na dificuldade do problema do logaritmo discreto: para Eva encontrar g ab de g a e g b , ela deve elevar um ou outro à potência b ou à potência a, respectivamente. Mas deduzir a (resp. B ) de g a (resp. G b ) é um problema que não sabemos como resolver eficientemente no caso geral. Eva é, portanto, incapaz (computacionalmente) para deduzir a partir das informações g um , g b , g e p , o valor de g ab .
No entanto, o grupo inicial deve ser bem escolhido e os números usados devem ser grandes o suficiente, por exemplo, para evitar um ataque de busca exaustivo . Atualmente, são geralmente usados números primos p de tamanho 2048 bits (da ordem de 600 dígitos na escrita decimal), para os quais a resolução do logaritmo discreto não é considerada viável. Se uma solução prática para resolver um logaritmo discreto surgisse, outros sistemas criptográficos poderiam cair, notadamente o sistema ElGamal , que se baseia no mesmo princípio.
Este protocolo é vulnerável ao " ataque man-in-the-middle ", que envolve um invasor capaz de ler e modificar todas as mensagens trocadas entre Alice e Bob.
Este ataque é baseado na interceptação de g a e g b , o que é fácil, pois eles são trocados a céu aberto; sendo o elemento g considerado conhecido por todos os atacantes. Para encontrar os números um e b e, assim, quebrar completamente a troca, seria necessário calcular o logaritmo discreto de g um e g b , o que é impossível na prática.
Mas um invasor pode se colocar entre Alice e Bob, interceptar a chave g a enviada por Alice e enviar a Bob outra chave g a ' , fingindo ser Alice. Da mesma forma, ele pode substituir a chave g b enviada por Bob a Alice por uma chave g b ' , fingindo ser Bob. O invasor, portanto, se comunica com Alice usando a chave compartilhada g ab ' e se comunica com Bob usando a chave compartilhada g a'b , Alice e Bob acreditam que estão se comunicando diretamente. Isso é chamado de “ataque man-in-the-middle”.
Alice e Bob acreditam que trocaram uma chave secreta quando, na realidade, cada um deles trocou uma chave secreta com o invasor, o homem do meio.
A solução clássica para esse ataque é assinar bolsas de valores usando um par de chaves assimétricas certificado por um terceiro confiável ou cujas metades públicas tenham sido trocadas anteriormente por ambos os participantes.
Alice pode ter certeza de que a chave que ela recebeu realmente vem de Bob e vice-versa para Bob.