Troca de chaves de Diffie–Hellman

A troca de chaves de Diffie-Hellman é um método de criptografia para trocas de chaves de maneira segura em canal público. Desenvolvido por Whitfield Diffie e Martin Hellman, foi um dos primeiros exemplos práticos de métodos de troca de chaves implementado dentro do campo da criptografia, tendo sido publicado em 1976.

Tradicionalmente, uma comunicação criptografada segura entre duas partes exigia que trocassem as chaves a priori por algum meio físico seguro, como uma lista de chaves em papel transportada por um mensageiro confiável. O método da troca de chaves de Diffie-Hellman permite que duas partes que não possuem conhecimento prévio uma da outra, compartilhem uma chave secreta sob um canal de comunicação inseguro. Tal chave pode ser usada para encriptar mensagens posteriores usando um esquema de cifra de chave simétrica.

Tal conceito foi originalmente inventado por Malcolm Williamson, um funcionário do Government Communications Headquarters (GCHQ) no Reino Unido, alguns anos antes de Whitfield Diffie e Martin Hellman, porém o GCHQ decidiu não tornar pública a descoberta pois tratava-se de assunto de segurança nacional. Somente em 1997 foi revelado o trabalho mas não teve muita repercussão na pesquisa em universidades. O trabalho de Malcolm Williamson não incluía o conceito de assinatura digital. Em 2002, Hellman sugeriu que o algoritmo fosse chamado de troca de chave de Diffie-Hellman-Merkle, em reconhecimento às contribuições de Ralph Merkle para a invenção da criptografia de chave pública. Martin Hellman escreveu:

O sistema é conhecido desde então como troca de chave de Diffie-Hellman. Enquanto tal sistema foi descrito em um artigo por mim e Diffie, ele é um sistema de distribuição de chave pública, um conceito desenvolvido por Merkle, e desta forma deveria ser chamado de "troca de chave de Diffie-Hellman-Merkle". Eu espero que esta pequena contribuição ajude na jornada para reconhecer as contribuições de Merkle na invenção da criptografia de chave pública.

O método foi seguido pelo RSA, uma outra implementação de criptografia de chave pública usando algoritmos assimétricos.

Descrição

Antes de 1975 se alguém falasse que seria possível a troca de informações criptografadas entre duas partes sem que houvesse uma troca de chaves secretas entre ambas as partes, provavelmente muitos matemáticos diriam ser impossível. Mas em 1976 o algoritmo Diffie-Hellman foi inventado. O maior problema para que isso acontecesse foi a dificuldade de cálculos de logaritmos discretos em um campo infinito.

Diffie-Hellman estabelece um compartilhamento de chaves secreto que pode ser usado para troca de mensagens secretas dentro de um canal de comunicação público. O diagrama a seguir ilustra a ideia geral de troca de chaves usando cores ao invés de um número muito grande.

1. Inicialmente, uma cor em comum é compartilhada entre Alice e João, cor esta que pode ser observada por um terceiro interessado na comunicação entre os dois.
2. O passo seguinte é a escolha de Alice e João, cada um, de uma cor secreta própria, que não é compartilhada com ninguém.
3. Cada um faz uma mistura primária com a cor comum e com suas cores secretas.
4. O passo chave do processo é que Alice e João trocam apenas suas misturas primárias. Estas misturas primárias, resultado das combinações da cor comum e das cores secretas, muito dificilmente conseguem reverter e determinar quais as cores secretas Alice e João utilizaram, caso um terceiro esteja escutando a comunicação.
5. Alice e João então usam suas cores secretas sobre as misturas primárias que receberam, gerando misturas secundárias (chave comum) que serão iguais tanto para Alice quanto para João, sem que um terceiro que esteja observando a comunicação consiga produzir esta mistura secundária.

Alice e João usam sua chave comum encriptar e desencriptar de modo secreto suas mensagens. Note que a cor amarela já foi previamente acordada por Alice e João.

Esquema de troca de chaves de Diffie-Hellman

A mais simples e original implementação do protocolo utiliza grupos multiplicativos de inteiros módulo "p", onde "p" é um número primo e "g" é uma raiz primitiva de módulo "p". Aqui está um exemplo do protocolo, onde os valores públicos estão em azul e os valores secretos estão em vermelho e destacados :

Alice				João
Secreto	Público	Calcula	Envia	Calcula	Público	Secreto
a	p, g		p,g$\rightarrow$			b
a	p, g, A	ga mod p = A	A$\rightarrow$		p, g	b
a	p, g, A		$\leftarrow$ B	gb mod p = B	p, g, A, B	b
a, s	p, g, A, B	Ba mod p = s		Ab mod p = s	p, g, A, B	b, s

1. Alice e João entram em acordo para usar um número primo p=23 e como base g=5.
2. Alice escolhe um inteiro secreto a=6, e então envia a João A = g^a mod p
   • A = 5⁶ mod 23
   • A = 15.625 mod 23
   • A = 8
3. João escolhe um inteiro secreto b=15, e então envia a Alice B = g^b mod p
   • B = 5¹⁵ mod 23
   • B = 30.517.578.125 mod 23
   • B = 19
4. Alice calcula s = B ^a mod p
   • s = 19⁶ mod 23
   • s = 47.045.881 mod 23
   • s = 2
5. João calcula s = A ^b mod p
   • s = 8¹⁵ mod 23
   • s = 35.184.372.088.832 mod 23
   • s = 2
6. Alice e João compartilham agora uma chave secreta: s = 2. Isto é possível porque 6*15 é o mesmo que 15*6. Alguém que tenha descoberto estes dois inteiros privados também será capaz de calcular s da seguinte maneira:
   • s = 5^6*15 mod 23
   • s = 5^15*6 mod 23
   • s = 5⁹⁰ mod 23
   • s = 807.793.566.946.316.088.741.610.050.849.573.099.185.363.389.551.639.556.884.765.625 mod 23
   • s = 2

Tanto Alice quanto João chegaram no mesmo valor pois (g^a)^b e (g^b)^a são iguais mod p. Note que apenas a, b e g^ab = g^ba mod p são mantidos em segredo. Todos os demais valores – p, g, g^a mod p, e g^b mod p – são enviados limpos no canal público. Uma vez que Alice e João calculam a chave secreta, eles podem então usá-la como chave de encriptação, conhecida apenas por eles, para enviar e receber mensagens ao longo do mesmo canal de comunicação. É claro que valores bem maiores de a, b, e p seriam necessários para tornar este exemplo seguro, uma vez que é fácil tentar todos os possíveis valores de g^ab mod 23. Existem apenas 23 possíveis inteiros que possuem os resultados observados para mod 23. Por outro lado, se p for um primo de ao menos 300 dígitos e a e b tenham ao menos 100 dígitos, então até os melhores algoritmos conhecidos atualmente não poderiam encontrar a dado apenas g, p, g^b mod p e g^a mod p, mesmo usando todo o poder computacional existente na humanidade. Tal problema é conhecido como problema do logaritmo discreto. Note que g não precisa ser necessariamente grande, e na prática seus valores são usualmente 2 ou 5.

Exemplo matemático do esquema de Diffie-Hellman

Aqui está uma descrição mais genérica do protocolo:

1. Alice e João acordam em um grupo cíclico finito G e um elemento gerador g em G.( Isto é usualmente feito muito antes do resto do protocolo; assume que g é conhecido por todos os atacantes.) Nós vamos escrever o grupo G de modo multiplicativo.
2. Alice escolhe um número natural aleatório a e envia g^a para João.
3. João também escolhe um número natural aleatório b e envia g^b para Alice.
4. Alice calcula (g^b)^a.
5. João calcula(g^a)^b.

Tanto Alice quanto João estão agora de posse de elemento de grupo g^ab, que pode servir como a chave secreta compartilhada. Os valores de (g^b)^a e (g^a)^b são os mesmos porque os grupos são associativos a potência. (Veja também exponenciação.)

Com o objetivo de decifrar uma mensagem m, enviada como mg^ab, João (ou Alice) deve primeiro calcular (g^ab)^-1, da seguinte maneira:

João sabe |G|, b, e g^a. Um resultado da teoria de grupos estabelece que a partir da construção de G, x^|G| = 1 para todo x em G.

João então calcula (g^a)^|G|-b = g^a(|G|-b) = g^a|G|-ab = g^a|G|g^-ab = (g^|G|)^ag^-ab=1^ag^-ab=g^-ab=(g^ab)^-1.

Quando Alice envia a João a mensagem encriptada, mg^ab, João aplica (g^ab)^-1 e recupera mg^ab(g^ab)^-1 = m(1) = m.

Operação com mais de duas partes

O esquema de acordo de chaves Diffie-Helman não está limitado à interação entre apenas dois participantes. Qualquer número de usuários pode participar no acordo, executando as interações do protocolo e trocando os dados intermediários entre si. Por exemplo, Alice, João e Carol poderiam participar em um acordo do tipo Diffie-Hellman de acordo com o exemplo a seguir, onde todas as operações tomadas com módulo $p$:

1. Os participantes selecionam os parâmetros iniciais do algoritmo $p$ e $g$;
2. Os participantes geram suas respectivas chaves privadas, que chamaremos $a$, $b$ e $c$.
3. Alice calcula $g^{a}$ e envia o resultado para João.
4. João calcula $(g^{a})^{b}=g^{ab}$ e envia o resultado para Carol.
5. Carol calcula $(g^{ab})^{c}=g^{abc}$ e utiliza esse valor como sua chave secreta compartilhada.
6. João calcula $g^{b}$ e envia para Carol
7. Carol calcula $(g^{b})^{c}=g^{bc}$ e envia o resultado para Alice.
8. Alice calcula $(g^{bc})^{a}=g^{bca}=g^{abc}$ e utiliza o resultado como chave secreta compartilhada.
9. Carol calcula $g^{c}$ e envia para Alice.
10. Alice calcula $(g^{c})^{a}=g^{ca}$ e envia o resultado para João.
11. João calcula $(g^{ca})^{b}=g^{cab}=g^{abc}$ e utiliza o resultado como chave secreta compartilhada.

Um intruso com acesso ao canal onde essas mensagens foram trocadas foi capaz de observar os valores $g^{a}$, $g^{b}$, $g^{c}$, $g^{ab}$, $g^{ac}$, e $g^{bc}$, mas não pode usar qualquer combinação desses valores para reproduzir $g^{abc}$.

Ver também

• Criptografia de chave pública
• Assinatura digital