Detalhes

Categoria: Chave Pública

Atualização: Domingo, 14 Junho 2009 12:10

Autor: vovó Vicki

Acessos: 56080

3. Cálculo da chave privada

Aqui cabe mais uma explicação aritmética. O inverso de um número inteiro é 1 dividido por este número. Por exemplo, o inverso de 3 é 1/3 porque 3 x 1/3 = 1 e o inverso de 18 é 1/18 porque 18 x 1/18 = 1. Este conceito também pode ser aplicado à aritmética modular.

Considere 5 (mod 14). O resultado é 5 porque 5 ÷ 14 = 0 com resto 5. O inverso de 5 (mod 14) precisa ser um número que, multiplicando 5, resulte 1 no módulo 14 (assim como 3 x 1/3 = 1). Neste caso, o cálculo do inverso não é uma tarefa trivial. Como os números do exemplo são pequenos, podemos achar o inverso de 5 (mod 14) por tentativa:

     5 x 1 (mod 14) =  5 (mod 14) =  5
     5 x 2 (mod 14) = 10 (mod 14) = 10
     5 x 3 (mod 14) = 15 (mod 14) =  1 <----

Se chamarmos 5 de a, o módulo de n e a variável que multiplica 5 de y, podemos generalizar o problema do inverso de um módulo como a x y (mod n) = 1 onde precisamos encontrar o valor de y. O inverso de um módulo também é conhecido como redução modular. É importante saber que nem todas as reduções modulares têm soluções. Por exemplo, 2 não tem um inverso no módulo 14. De modo geral, quando a e n são primos entre si, existe uma solução única e, quando a e n não são primos entre si, não existe uma solução.

Para calcular a chave privada será preciso fazer uma redução modular. No exemplo que está sendo usado, é a redução modular 13 (mod 396). O cálculo de um inverso modular por tentativa pode ser um processo muito demorado e existem formas mais elegantes de resolver o problema. Uma delas é o algoritmo de Euclides estendido que será aplicado no nosso exemplo.

     (1)    13 ÷ 396 =  0 com resto 13   ...   divide-se o valor pelo módulo
     (2)   396 ÷  13 = 30 com resto  6   ...   divide-se o divisor anterior pelo resto
     (3)    13 ÷   6 =  2 com resto  1   ...   divide-se o divisor anterior pelo resto
             6 ÷   1 =  6 com resto  0   ...   divide-se o divisor anterior pelo resto

Na verdade, o cálculo acima nada mais é do que o cálculo do máximo divisor comum entre 13 e 396, comumente expresso como MDC(13,396). Como o último divisor com resto zero (divisão exata) é 1, sabemos que o MDC(13,396) = 1. Este é o algoritmo de Euclides que também serve para determinar se os números são primos entre si.

O algoritmo de Euclides estendido usa apenas os restos diferentes de zero das divisões mostradas acima. Estes podem ser expressos da seguinte maneira:

     (1)   13 = (1 x 13) - (0 x 396)
           13 = (1 x 13)

     (2)    6 = (1 x 396) - (30 x 13)       ...   e como (1) nos diz que 13 = (1 x 13)
            6 = (1 x 396) - (30 x (1 x 13))
            6 = (1 x 396) - (30 x 13)

     (3)    1 = (1 x 13) - (2 x 6)          ...   e como (2) nos diz que 6 = (1 x 396) - (30 x 13)
            1 = (1 x 13) - 2 x ((1 x 396) - (30 x 13))
            1 = (1 x 13) - (2 x 396) + (60 x 13)
            1 = (61 x 13) - (2 x 396)

O multiplicador de 13 é o inverso de 13 (mod 396). Neste caso, se chamarmos o inverso de d, então d = 61. Esta é a chave privada e que precisa ser mantida em sigilo.

Como os números primos que serviram de base para obter estes valores já cumpriram a sua função e precisam ser mantidos em segredo, eles podem ser simplesmente descartados. Resumindo os passos até este ponto temos:

     Chave pública: 437 e 13
     Chave privada: 437 e 61

4. Publicação da chave

Uma vez definida a chave pública N = 437 e e = 13, ela pode ser distribuída livremente para servir de chave para todos os remetentes que quiserem enviar mensagens cifradas para o dono do par de chaves. É importante esclarecer que se pode publicar e e manter d em segredo ou fazer o contrário, publicar d e manter e em segredo.

5. Cifrar uma mensagem

Digamos que um dos amigos do dono da chave queira lhe enviar uma mensagem confidencial e que o conteúdo desta mensagem seja (para variar) "numaboa". Esta mensagem precisa ser transformada num número (ou números) para que o algoritmo possa ser aplicado. Para isto, os valores ASCII dos caracteres da mensagem são perfeitos:

     n = 110
     u = 117
     m = 109
     a = 97
     b = 98
     o = 111
     a = 97

Neste caso, a mensagem será representada por m = 110117109979811197. Inicialmente m deve ser dividida em blocos. No presente exemplo, um bom tamanho serão blocos de três dígitos. Assim:

     m1 = 110
     m2 = 117
     m3 = 109
     m4 = 979
     m5 = 811
     m6 = 197

É preciso esclarecer que o último bloco não precisa necessariamente ter três dígitos. Cada um dos blocos será submetido à seguinte cifragem usando a chave pública, onde N é o módulo e e é o expoente:

     c = me (mod N)

     c1 = 11013 (mod 437)
     c2 = 11713 (mod 437)
     c3 = 10913 (mod 437)
     c4 = 97913 (mod 437)
     c5 = 81113 (mod 437)
     c6 = 19713 (mod 437)

Como as máquinas de calcular normalmente não mostram mais do que 10 a 12 dígitos, podemos facilitar os cálculos usando a propriedade distributiva da multiplicação modular. Como 13 = 5 + 5 + 3, então

     c1 = 11013 (mod 437)
        = [1105 (mod 437) x 1105 (mod 437) x 1103 (mod 437)] (mod 437)

     Como 1105 (mod 437) = 16.105.100.000 (mod 437) = 325
     e    1103 (mod 437) =      1.331.000 (mod 437) = 335
     
     c1 = [325 x 325 x 335] (mod 437)
        = 35.384.375 (mod 437)
        = 48

     c2 = 11713 (mod 437)
        = [1175 (mod 437) x 1175 (mod 437) x 1173 (mod 437)] (mod 437)

     Como 1175 (mod 437) = 21.924.480.357 (mod 437) = 262
     e    1173 (mod 437) =      1.601.613 (mod 437) =   8
     
     c2 = [262 x 262 x 8] (mod 437)
        = 549.152 (mod 437)
        = 280

Completando os cálculos, a mensagem cifrada será 048 280 401 146 243 330