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
- Prima Passo seguinte para acompanhar a troca: o acordo público, os segredos, as mensagens e o resultado partilhado.
- Observe cada valor como tinta e como número, e veja quais ficam privados e quais Eve consegue ler.
- 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