Primo p
Segredo partilhado
Tentativas de Eve
Para testar todos os expoentes
Alice
Em público (Eve vê isto)
Bob

Mostrar

Mais sobre a troca de chaves Diffie-Hellman

Troca de chaves Diffie-Hellman

Como podem duas pessoas que nunca se encontraram combinar uma chave secreta enquanto alguém escuta cada palavra que dizem? Em 1976, Whitfield Diffie e Martin Hellman encontraram a resposta que hoje protege quase todas as ligações seguras na internet. Acompanhe Alice e Bob ao longo dos cinco passos, uma vez como mistura de tintas e outra com números reais, e depois deixe a espia Eve atacar: com números pequenos ganha num piscar de olhos; com os tamanhos usados na prática precisaria de mais tempo do que a idade do universo. Prima Passo seguinte para acompanhar Alice e Bob enquanto combinam um segredo e Eve lê tudo o que enviam; Voltar recua um passo. Cada valor é mostrado como tinta e como número. Os valores com cadeado nunca saem do seu dono. Escolha à direita um primo maior ou outros segredos, ou prima Novos segredos. No último passo, Deixar Eve atacar faz com que ela teste todos os expoentes até um servir: fácil com primos pequenos, sem esperança com os verdadeiros.

Como funciona

  1. Prima Passo seguinte para acompanhar a troca: o acordo público, os segredos, as mensagens e o resultado partilhado.
  2. Observe cada valor como tinta e como número, e veja quais ficam privados e quais Eve consegue ler.
  3. No último passo prima Deixar Eve atacar, depois escolha um primo maior e veja com que rapidez as hipóteses dela desaparecem.

Como funciona a troca

Alice e Bob combinam primeiro em público um primo p e um número g. Depois, cada um escolhe um número secreto, a para Alice e b para Bob, e guarda-o para si. Alice envia a Bob A = gᵃ mod p, e Bob envia a Alice B = gᵇ mod p. Por fim, Alice calcula Bᵃ mod p e Bob calcula Aᵇ mod p. Ambos os resultados são iguais a g elevado a a·b mod p, por isso passam a partilhar um número que nunca atravessou a linha. Eve, que viu p, g, A e B, não tem nenhum atalho desses.

Porque é que Eve fica bloqueada

Calcular gᵃ mod p é rápido, mesmo para números com centenas de algarismos, graças a quadrados sucessivos. Fazer o caminho inverso, ou seja, encontrar o expoente a a partir do resultado, é o problema do logaritmo discreto, e não se conhece nenhum método rápido para primos bem escolhidos. Com os primos pequenos desta demonstração, Eve pode simplesmente testar todos os expoentes; a aplicação conta as tentativas dela e estima quanto tempo demoraria uma pesquisa completa. Cada bit adicional do primo duplica o trabalho, pelo que os primos de 2048 bits usados na internet põem uma pesquisa por força bruta muito fora de alcance. A versão com tintas capta a mesma ideia: misturar cores é fácil, mas separar uma mistura nas suas cores é praticamente impossível.

Perguntas frequentes

Porque é que a analogia das tintas funciona?

Misturar tinta é fácil e não se pode desfazer, tal como elevar g a uma potência mod p é fácil de fazer e difícil de desfazer. Alice e Bob juntam cada um a sua cor secreta a uma cor comum e trocam as misturas; depois cada um junta a sua própria cor secreta à mistura que recebeu. Ambos ficam com a cor comum mais os dois segredos, enquanto Eve só vê as duas misturas de duas cores e não as consegue separar. Aqui as tintas são misturadas em partes iguais, por isso a ordem não importa, tal como (gᵃ)ᵇ = (gᵇ)ᵃ.

O que é g e porque tem de ser uma raiz primitiva?

g é um gerador: as suas potências g¹, g², …, g^(p−1) mod p percorrem todos os números de 1 a p − 1. Assim, os valores públicos distribuem-se por todas as possibilidades e Eve aprende com eles o mínimo possível. A aplicação escolhe para cada primo o menor desses números, por exemplo g = 5 para p = 23.

O Diffie-Hellman cifra as minhas mensagens?

Não. Serve apenas para combinar um segredo partilhado. Esse segredo é depois usado como chave de uma cifra simétrica rápida como o AES, que cifra os dados propriamente ditos. Todas as ligações HTTPS funcionam assim: uma troca de chaves, normalmente com curvas elípticas, seguida de cifragem simétrica.

Eve pode fazer-se passar por Bob?

Se a troca for usada sozinha, sim. Um intermediário poderia fazer uma troca com Alice e outra com Bob e retransmitir tudo. Os protocolos reais impedem isto obrigando o servidor a provar a sua identidade com uma assinatura digital e um certificado, para que a troca seja autenticada.

É enviado algo para um servidor?

Não. Todos os números, a mistura das tintas e o ataque de Eve são calculados no navegador, e as definições ficam no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor