Detalhes

Categoria: Chave Pública

Atualização: Terça, 14 Abril 2009 14:44

Autor: vovó Vicki

Acessos: 35177

O algoritmo Diffie-Hellman

No início de 1976, Hellman estava analisando um axioma que já existe há algumas centenas de anos. A idéia era usar a função na forma de

          gx (mod n)

Para que a mágica funcionasse, havia algumas restrições:

          g (a base) precisa ser menor do que n (o módulo)
                                  e
          g precisa ser maior do que 1

Para obter as chaves, João e Maria podem trocar informações abertamente, sem a mínima preocupação com alguém que esteja presente ou que eventualmente esteja interceptando estas informações. Em apenas 4 etapas, os dois terão uma chave secreta.

1. A escolha da base e do módulo

Inicialmente João e Maria escolhem dois números grandes, um para a base g e um para o módulo n, obedecendo as restrições citadas acima. Esta escolha não necessariamente envolve apenas os dois, mais pessoas podem participar do grupo de usuários. Para facilitar, será usado um exemplo com números pequenos e apenas com João e Maria. Digamos que eles, durante o intervalo das aulas, tenham concordado com

          g = 7
            e
          n = 11

2. A escolha dos expoentes

Depois, na privacidade da sua casa, João escolhe um expoente x bem grande. Este número João mantém cuidadosamente em segredo. Maria faz a mesma coisa e também mantém sua escolha em segredo. De posse dos seus expoentes, os dois calculam o resultado da função:

                   MARIA                         JOÃO
          --------------------------     --------------------------
          x = 6                          y = 3

          M = 76 (mod 11)                J = 73 (mod 11)
          M = 117649 (mod 11)            J = 343 (mod 11)
          M = 4                          J = 2

3. A troca de resultados

No dia seguinte, os dois se encontram novamente no intervalo das aulas. Maria entrega o resultado obtido (M=4) para João e este entrega o resultado que obteve (J=2) para Maria. Mais uma vez, nenhum dos dois está preocupado que alguém tome conhecimento destes números.

4. O cálculo da chave secreta

Com o resultado obtido pelo outro, João e Maria voltam a fazer cálculos em particular. Usam a mesma função só que, desta vez, a base usada por Maria é o resultado obtido por João e a base usada por João é o resultado obtido por Maria. Os expoentes continuam sendo os previamente escolhidos:

                   MARIA                          JOÃO
          --------------------------      --------------------------
          x = 6                           y = 3

          J' = 26 (mod 11)                M' = 43 (mod 11)
          J' = 64 (mod 11)                M' = 64 (mod 11)
          J' = 9                          M' = 9

Como num passe de mágica, ambos chegaram ao mesmo resultado e agora possuem uma chave secreta em comum

Algumas considerações

A chave secreta nada mais é do que g^xy (mod n). Para confirmar, basta fazer os cálculos:

          gxy (mod n) = 76 x 3 (mod 11)
                      = 718 (mod 11)
                      = 1.628.413.597.910.449 (mod 11)
                      = 9

Mesmo que se conheça os valores de g, n, M e J não é possível calcular o valor da chave secreta. Se usarmos o método das tentativas (ou seja, a força bruta) poderemos encontrar inúmeros valores que fecham as primeiras equações. Por exemplo, no caso de Maria, os valores possíveis de x são 6, 16, 26, ..., 6 + 10n e, no caso de João, os valores possíveis de y são 3, 13, 23, ..., 3 + 10n. Tanto x quanto y podem ter infinitos valores de acordo com as progressões aritméticas citadas e estes valores precisariam ser agrupados em todos os pares possíveis para tentar encontrar a chave - uma tarefa impossível de ser realizada se os valores escolhidos forem grandes o suficiente.

Mas não são apenas os valores suficientemente grandes dos expoentes que conferem segurança a este sistema. A escolha de g e n também tem uma influência acentuada. O módulo n deve ser um número primo e, mais importante do que isto, (n-1)/2 também deve ser um número primo. A base g, por sua vez, deve ser uma raiz primitiva no módulo n (mais sobre o assunto logo a seguir). Agora, o mais importante de tudo é que n deve ser grande, ter no mínimo 512 bits (ou seja, ter 64 bytes, o que é o mesmo que 64 algarismos). Usar 1028 bits seria mais seguro.