A troca de chaves Diffie-Hellman explicada

Durante milhares de anos, enviar uma mensagem secreta implicava primeiro partilhar uma chave secreta pessoalmente ou por mensageiro. Em 1976, dois investigadores de Stanford mostraram que duas partes podiam criar uma chave partilhada a partir do nada, trocando mensagens à vista de todos. A ideia abriu a era da criptografia de chave pública e continua em ação sempre que um navegador mostra um cadeado.

Alice e Bob de cada lado de um canal público, cada um a misturar uma tinta amarela comum com uma cor secreta, ambos a terminar com a mesma mistura enquanto Eve observa
Alice e Bob de cada lado de um canal público, cada um a misturar uma tinta amarela comum com uma cor secreta, ambos a terminar com a mesma mistura enquanto Eve observa

O problema da distribuição de chaves

Uma cifra como o AES só é tão segura quanto a sua chave, e ambos os lados precisam da mesma chave. Antes de 1976, a chave tinha de ser entregue em segredo: por mala diplomática, por mensageiros de confiança ou com livros de códigos impressos antecipadamente. Para dois desconhecidos que querem comunicar com segurança já, por exemplo uma loja e um cliente na internet, isso é impossível. O artigo de Whitfield Diffie e Martin Hellman «New Directions in Cryptography» resolveu o problema com um método que não precisa de nenhum segredo prévio.

Aritmética num relógio

A troca usa aritmética modular: cálculos num relógio com p horas, em que p é um primo grande. Neste relógio as potências comportam-se de forma notável. Se g for uma raiz primitiva, os números g, g², g³, … mod p saltam de um lado para o outro e passam por todas as horas de 1 a p − 1 antes de se repetirem, numa ordem que parece aleatória. Calcular gᵃ mod p é rápido, com aproximadamente tantas multiplicações quantos os algarismos binários de a. Desfazê-lo não é.

A troca passo a passo

Alice e Bob combinam abertamente p e g. Alice escolhe um segredo a e envia A = gᵃ mod p; Bob escolhe um segredo b e envia B = gᵇ mod p. Alice calcula Bᵃ = (gᵇ)ᵃ e Bob calcula Aᵇ = (gᵃ)ᵇ, ambos mod p. Como a ordem dos expoentes não importa, ambos obtêm g^(ab) mod p. No pequeno exemplo clássico com p = 23, g = 5, a = 6 e b = 15, Alice envia 8, Bob envia 19, e ambos chegam ao segredo partilhado 2.

O problema do logaritmo discreto

Eve vê p, g, A e B. Se conseguisse encontrar a a partir de A = gᵃ mod p, poderia calcular o segredo tal como Alice. Este é o problema do logaritmo discreto. Os melhores algoritmos clássicos conhecidos, como o crivo do corpo de números, são muito mais rápidos do que testar todos os expoentes, mas continuam a precisar de um tempo que cresce mais depressa do que qualquer potência do número de algarismos. Com primos de 2048 bits, o problema está fora do alcance de qualquer computador existente. Não se sabe se é possível algo mais rápido, e a segurança da troca assenta nessa convicção.

Man-in-the-middle

O Diffie-Hellman protege contra quem escuta, mas não contra um impostor. Mallory, colocado entre Alice e Bob, pode fazer uma troca com cada um deles e passar as mensagens, lendo tudo. A defesa é a autenticação: no HTTPS, o servidor assina a sua parte da troca com uma chave certificada por uma autoridade de confiança, para que o navegador saiba que está mesmo a falar com o site certo. A troca de chaves e as assinaturas andam sempre juntas.

Quem a inventou?

Diffie e Hellman publicaram em 1976, baseando-se em ideias de Ralph Merkle; mais tarde, Hellman pediu que também ele fosse reconhecido. Em 1997, a agência de informações britânica GCHQ revelou que os seus matemáticos tinham lá chegado primeiro: James Ellis teve a ideia da criptografia de chave pública em 1970, Clifford Cocks encontrou um sistema semelhante ao RSA em 1973 e Malcolm Williamson descobriu a mesma troca de chaves em 1974, tudo mantido em segredo durante mais de vinte anos.

Martin Hellman (à esquerda) e Whitfield Diffie (à direita), 1977
Martin Hellman (à esquerda) e Whitfield Diffie (à direita), 1977
Ralph Merkle na Singularity Summit de 2007.
Ralph Merkle na Singularity Summit de 2007.

O Diffie-Hellman hoje

As ligações modernas usam sobretudo Diffie-Hellman de curvas elípticas, que dá a mesma segurança com números muito mais curtos, por exemplo a curva X25519 no TLS 1.3, no Signal e no WhatsApp. Usar um novo par de segredos em cada ligação garante sigilo futuro (forward secrecy): mesmo que a chave de longo prazo de um servidor seja roubada mais tarde, as conversas passadas continuam seguras. Os parâmetros fracos continuam a ser um perigo, como o ataque Logjam de 2015 mostrou para antigos primos de 512 bits, e um grande computador quântico a executar o algoritmo de Shor quebraria tanto o Diffie-Hellman clássico como o de curvas elípticas, razão pela qual estão agora a ser implementadas, a par deles, trocas de chaves pós-quânticas.

Explore

Abra o visualizador Diffie-Hellman para acompanhar os cinco passos num quadro com o que Alice, o canal público e Bob sabem, como tinta e como números. Escolha primos de 23 até 2.147.483.647, defina os segredos e deixe Eve atacar testando todos os expoentes: veja-a ter êxito instantaneamente com primos pequenos e observe como o tempo de pesquisa estimado cresce à medida que o primo fica mais longo.

Perguntas frequentes

O Diffie-Hellman é o mesmo que o RSA?

Não, embora ambos sejam métodos de chave pública dos anos 1970. O RSA, publicado em 1977, consegue cifrar e assinar com uma chave pública e uma privada e assenta na dificuldade de fatorizar números grandes. O Diffie-Hellman apenas combina um segredo partilhado e assenta no problema do logaritmo discreto.

Qual é o tamanho dos números na prática?

O Diffie-Hellman clássico usa primos de pelo menos 2048 bits, cerca de 617 algarismos decimais, e muitas vezes de 3072 ou 4096 bits. As versões de curvas elípticas usam chaves de cerca de 256 bits para uma segurança comparável.

Porque é que cada bit adicional duplica o trabalho de Eve?

Um primo com mais um bit tem cerca do dobro do tamanho, por isso há cerca do dobro dos expoentes para testar. Os ataques reais são mais engenhosos do que testar todos os expoentes, mas o seu custo continua a crescer muito depressa com o tamanho do primo.

Porque precisam Alice e Bob de um primo?

Com um módulo primo, todos os números de 1 a p − 1 têm inverso e existem raízes primitivas, pelo que as potências de g cobrem todas as possibilidades. Escolhem-se muitas vezes primos seguros, em que (p − 1)/2 também é primo, para excluir atalhos que usam fatores pequenos de p − 1.

Pronto para experimentar?

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

Abrir o visualizador Diffie-Hellman