Diffie-Hellman

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Ambox rewrite.svg
Esta página precisa ser reciclada de acordo com o livro de estilo (desde Fevereiro de 2008).
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.

A troca de chaves de Diffie-Hellman é um método de criptografia específico para troca de chaves desenvolvido por Whitfield Diffie e Martin Hellman e publicado em 1976. Foi um dos primeiros exemplos práticos de métodos de troca de chaves implementado dentro do campo da criptografia. O método da troca de chaves de Diffie-Hellman permite que duas partes que não possuem conhecimento a priori de cada uma compartilhar uma chave secreta sob um canal de comunicação inseguro. Tal chave pode ser usada para encriptar posteriores mensagens usando uma esquema de cifra de chave simétrica.

Tal conceito foi previamente 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úblico 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 incluia o conceito de assinatura digital.[1] Em 2002, Hellman sugeriu que o algoritmo fosse chamado de troca de chave de Diffie-Hellman-Merkle, em reconhecimento as contribuições de Ralph Merkle para a invenção da criptografia de chave pública. Martim Hellman escreveu:

O sistema é conhecido desde de 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 inveçã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[editar | editar código-fonte]

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 idéia geral de troca de chaves usando cores ao invés de um número muito grande. O passo chave do processo é que Alice e Bob trocam suas cores secretas apenas através de uma mistura. Isso gera uma chave idêntica que é praticamente impossível de ser revertida por qualquer outra parte que esteja escutando o canal. Alice e Bob usam sua chave comum encriptar e descriptar de modo secreto suas mensagens. Note que a cor amarela já foi previamente acordada por Alice e Bob.

Esquema de troca de chave 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 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
Bob
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 Bob 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 Bob A = ga mod p
    • A = 56 mod 23
    • A = 15,625 mod 23
    • A = 8
  3. Bob escolhe um inteiro secreto b=15, e então envia a Alice B = gb mod p
    • B = 515 mod 23
    • B = 30,517,578,125 mod 23
    • B = 19
  4. Alice calcula s = B a mod p
    • s = 196 mod 23
    • s = 47,045,881 mod 23
    • s = 2
  5. Bob computes s = A b mod p
    • s = 815 mod 23
    • s = 35,184,372,088,832 mod 23
    • s = 2
  6. Alice e Bob 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 = 56*15 mod 23
    • s = 515*6 mod 23
    • s = 590 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 Bob chegaram no mesmo valor pois (ga)b e (gb)a são iguais mod p. Note que apenas a, b e gab = gba mod p são mantidos em segredo. Todos os demais valores – p, g, ga mod p, and gb mod p – são enviados limpos no canal público. Uma vez que Alice e Bob 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 gab 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, gb mod p e ga 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 Bob 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 ga para Bob.
  3. Bob também escolhe um número natural aleatório b e envia gb para Alice.
  4. Alice calcula (gb)a.
  5. Bob calcula(ga)b.

Tanto Alice quanto Bob estão agora de posse de elemento de grupo gab, que pode servir como a chave secreta compartilhada. Os valores de (gb)a e (ga)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 mgab, Bob (ou Alice) deve primeiro calcular (gab)-1, da seguinte maneira:

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

Bob então calcula (ga)|G|-b = ga(|G|-b) = ga|G|-ab = ga|G|g-ab = (g|G|)ag-ab=1ag-ab=g-ab=(gab)-1.

Quando Alice envia a Bob a mensagem encriptada, mgab, Bob aplica (gab)-1 e recupera mgab(gab)-1 = m(1) = m.

Gráfico[editar | editar código-fonte]

Operação com mais de duas partes[editar | editar código-fonte]

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, executanto as interações do protocolo e trocando os dados intermediários entre si. Por exemplo, Alice, bob e Carol poderiam participar em um acordo do tipo Diffie-Hellman de acordo com o exeomplo 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 resutlado para Bob.
  4. Bob 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. Bob 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 Bob.
  11. Bob calcula (g^{ca})^b = g^{cab} = g^{abc} e utiliza o resultado como chave secreta compartilhadaand uses it as his secret.

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}.

Segurança[editar | editar código-fonte]

Demais usos[editar | editar código-fonte]

Acordo de chaves para autenticação de senhas[editar | editar código-fonte]

Chave pública[editar | editar código-fonte]

É utilizada em 128 bits.[editar | editar código-fonte]

Veja também[editar | editar código-fonte]

Notas[editar | editar código-fonte]

Referências[editar | editar código-fonte]

www.uniao.edu.br

Links Externos[editar | editar código-fonte]

Referências

  1. Public Key Cryptography (PKC), RSA, PKI www.livinginternet.com. Visitado em 8 de abril de 2010.

Ver também[editar | editar código-fonte]

Ícone de esboço Este artigo sobre Informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.