Detalhes

Categoria: Chave Pública

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

Autor: vovó Vicki

Acessos: 56085

6. Decifrar a mensagem

Decifrar a mensagem significa realizar a mesma exponenciação, porém usando a chave de decifração ou chave privada:

     m = cd (mod N)

     m1 =  4861 (mod 437)
     m2 = 28061 (mod 437)
     m3 = 40161 (mod 437)
     m4 = 14661 (mod 437)
     m5 = 24361 (mod 437)
     m6 = 33061 (mod 437)

Se com o expoente 13 já é aconselhável usar a propriedade distributiva da multiplicação modular, com o expoente 61 esta necessidade fica ainda mais evidente. Como normalmente usamos o computador para fazer os cálculos e a máquina usa o sistema binário, segue um exemplo de como usar a base 2. O valor decimal 61 é expresso em binário como 0011 1101, ou seja, é o mesmo que 2⁵ + 2⁴ + 2³ + 2² + 2⁰ = 32 + 16 + 8 + 4 + 1 = 61. Tomando o bloco m₁ como exemplo, podemos calcular:

     4861 (mod 437) = 4832 x 4816 x 488 x 484 x 48 (mod 437)
     
     Como
     484 (mod 437) = (482 (mod 437))2 (mod 437)
                   = (2.304 (mod 437))2 (mod 437)
                   = 1192 (mod 437)
                   = 14.161 (mod 437)
                   = 177

     Como
     488 (mod 437) = ((482 (mod 437))2 (mod(437))2 (mod 437)
     e                (482 (mod 437))2 (mod 437) = 177
     então         = 1772 (mod 437)
                   = 31.329 (mod 437)
                   = 302

     Pelo mesmo raciocínio
     4816 (mod 437) = (488 (mod 437))2 mod (437)
                    = 3022 mod (437)
                    = 91.204 (mod 437)
                    = 308
     
     E novamente pelo mesmo raciocínio
     4832 (mod 437) = (4816 (mod 437))2 mod (437)
                    = 3082 mod (437)
                    = 94.864 (mod 437)
                    = 35

De posse destes valores intermediários, fica fácil calcular

     4861 (mod 437) = 4832 x 4816 x 488 x 484 x 48 (mod 437)
                    = 35 x 308 x 302 x 177 x 48 (mod 437)
                    = 27.659.237.760 (mod 437)
                    = 110 <-- o valor original

Esta forma "binária" de calcular a exponenciação é um bom exemplo de como montar uma sub-rotina em qualquer linguagem de programação para calcular tanto a cifragem quanto a decifração, por que é iterativa.

Segurança e Velocidade

Com frequência se afirma que a segurança do RSA depende exclusivamente da dificuldade de fatorar números grandes. Mas não é bem assim. Até agora não foi provado matematicamente que seja necessário fazer a fatoração de N para calcular a mensagem clara a partir do texto cifrado e da chave pública. Portanto, não é possível descartar a possibilidade de algum "maluco beleza" descobrir uma forma de encontrar a chave privada usando a chave pública. Enquanto isto não acontecer, a forma mais óbvia de atacar o RSA vai continuar sendo descobrir um método de fatoração rápido que consiga abrir N nos seus fatores primos. Também, enquanto isto, a segurança do RSA vai depender essencialmente dos números primos que escolhermos para criar as chaves. Primos pequenos, como os usados no exemplo, são um desastre e primos grandes demais (usados pelos paranóicos por segurança) acabam tornando os cálculos extremamente lentos.

Já que falamos de cálculos lentos, não custa frisar que um software que implementa o algoritmo RSA é cerca de 100 vezes mais lento do que um que implementa o DES. Por mais otimizado que seja, nada supera uma cifra de bloco em termos de velocidade. Se o algoritmo for implementado através de hardware, o cenário não melhora. Muito pelo contrário. Pelo que se sabe, chips especiais para RSA são cerca de 1000 vezes mais lentos do que chips para o DES, ou seja, em termos de velocidade, a coisa fica 10 vezes pior! Mas, apesar de tudo isto, o que eu tenho a dizer é "vida longa para os algoritmos assimétricos!".

Brinque um pouco on line para sentir o gosto. Acho que vale a pena por que me diverti um bocado escrevendo o JavaScript