Detalhes

Categoria: Chave Pública

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

Autor: vovó Vicki

Acessos: 35177

Conferindo a raiz primitiva calculada no início

No exemplo 3 (mod 5), de acordo com aquela afirmação de Burton que deu nó na minha cabeça, se a ordem multiplicativa 3 (mod 5) e a função totiente phi(5) forem iguais, então 3 é uma raiz primitiva do módulo 5. Por outro lado, se os resultados forem diferentes, 3 não é uma raiz primitiva do módulo 5. Como já fizemos os cálculos e determinamos que 3 é uma raiz primitiva do módulo 5, então a ordem multiplicativa de 3 (mod 5) e phi(5) precisam ser iguais. Burton parece ter razão, elas são mesmo iguais: ordem multiplicativa de 3 (mod 5) = 4 e phi(5) = 4.

Raiz primitiva de um módulo grande

As ferramentas citadas neste texto ajudam a provar com rapidez se determinado número é ou não uma raiz primitiva de determinado módulo, mesmo quando este módulo tiver um valor muito grande. Veja mais um exemplo: 143 é uma raiz primitiva do módulo 1142? Para responder esta pergunta, a primeira providência é verificar se 143 e 1142 são primos entre si:

     143 | 11
      13 | 13     --> Os divisores de 143 são 11, 13 e 1
       1 |

     1142 | 2
      571 | 571   --> Os divisores de 1142 são 2, 571 e 1
        1 |

     O único e o máximo divisor que estes números têm em comum é 1, ou seja

     MDC(143, 1142) = 1 mostra que 143 e 1142 são primos entre si.

A seguir, calculamos o phi(1142). Como 1142 é um número composto pelos fatores 571 e 2, o phi(1142) pode ser calculado de acordo com a fórmula

     phi(n) = (p - 1) x (q - 1)

     phi(1142) = (571 - 1) x (2 - 1) = 570

Agora é só confirmar se a ordem multiplicativa de 143 (mod 1142) também é igual a 570, ou seja, se 143⁵⁷⁰ (mod 1142) = 1. Como o módulo 1142 não é um número primo, não vamos poder usar o Pequeno Teorema de Fermat, mas, em compensação, como o MDC(143, 1142) = 1, eles são primos entre si e podemos apelar para a generalização que Euler fez deste teorema, o qual nos diz que:

     gφ(n) (mod n) = 1

     ou seja, de acordo com Euler,

     143φ(1142) (mod 1142) = 1
     143570 (mod 1142) = 1

     e, se ainda houver dúvidas, é só calcular para verificar que

     3,4796964099440242706248097324932e+1228 (mod 1142) = 1

Conferindo os valores de João e Maria

Será que nossos amigos cuidaram para que os valores usados com o algoritmo Diffie-Hellman realmente oferecessem o máximo de segurança possível? Descontando o fato de que propositalmente foram escolhidos valores pequenos para a base e para o módulo afim de facilitar o acompanhamento do exemplo, ainda falta avaliar alguns itens da checklist:

• O módulo n deve ser um número primo: o módulo escolhido foi 11, que é primo --> OK
• (n-1)/2 também precisa ser primo: (11 - 1) / 2 = 10 / 2 = 5, que é primo --> OK
• A base g precisa ser uma raiz primitiva no módulo n: OK (veja abaixo)

     Os escolhidos foram g = 7 e n = 11.

     MDC(7, 11) = 1              (são primos entre si)

     phi(11) = (11 - 1) = 10     (phi de número primo)

     Como n é primo e g não é um múltiplo de n,
     o Pequeno Teorema de Fermat é aplicável:

     710 (mod 11) =
     282.475.249 (mod 11) = 1    (a ordem multiplicativa de 7 (mod 11) é 10)

              phi(11) = 10 |
                           | --> 7 é uma raiz primitiva no módulo 11
     ordem 7 (mod 11) = 10 |

Diffie-Hellman estendido

V. S. Miller e Kevin McCurley estenderam este algoritmo para curvas elípticas e Taher ElGamal usou a idéia básica para desenvolver um algoritmo de encriptação e de assinatura digital. Além disso, o protocolo de troca de chaves pode ser facilmente estendido para atender três ou mais pessoas. Se João, Maria e Onofre quiserem gerar uma chave secreta, o procedimento é o seguinte:

     1. Maria escolhe um inteiro grande qualquer x e calcula
                         X = gx (mod n)
     2. João escolhe um inteiro grande qualquer y e calcula
                         Y = gy (mod n)
     3. Onofre escolhe um inteiro grande qualquer z e calcula
                         Z = gz (mod n)
     4. Maria envia X para João, João envia Y para Onofre e Onofre envia Z para Maria.
     5. Maria calcula Z' = Zx (mod n)
     6. João calcula X' = Xy (mod n)
     7. Onofre calcula Y' = Yz (mod n)
     8. Maria envia Z' para João, João envia X' para Onofre e Onofre envia Y' para Maria.
     9. Maria calcula k = Y'x (mod n)
     10. João calcula k = Z'y (mod n)
     11. Onofre calcula k = X'z (mod n)

A chave secreta k é igual a g^xyz (mod n) e este protocolo pode ser facilmente estendido para quatro ou mais pessoas.

Sugestões

Se você precisar de mais algumas ferramentas on line, procure-as na Escolinha da Aldeia na Caixa de Ferramentas. Sugestões: MDC - Máximo Divisor Comum, Este número é primo?, Aritmética Modular, Logaritmos e Potenciação. Divirtam-se com o Diffie-Hellman e um grande abraço da

vovó Vicki

Fontes

• Bruce Schneier, "Applied Cryptography"
• Simon Singh, "O Livro dos Códigos"
• Number Theory - Congruences
• David Morgan, Primitive roots and Diffie-Hellman key exchange>/li>