Cálculo da potência modular de forma eficiente

Publicado por Elgio Schlemer em 17/08/2009

[ Hits: 19.789 ]

Blog: http://gravatai.ulbra.tche.br/~elgio

 


Cálculo da potência modular de forma eficiente



Em 12/Agosto/2009 publiquei um desafio cuja premiação foi um livro (GANHE UM LIVRO aqui no VOL). Trata-se de um desafio de criptografia envolvendo o RSA. Para vencer é necessário fatorar o N, calcular o valor de D e decifrar a mensagem.

Particularmente a decifragem envolve uma operação matemática muito complexa que "fritaria" os processadores se feitas da forma original. Um exemplo modesto de uma cifragem RSA é a operação 30965537 mod 391, que levou 2 segundos para ser executada com a calculadora bc em um processador de 2.4 Ghz:

time echo "309 ^ 65537 % 391" | bc
122
real	0m1.918s
user	0m1.908s
sys	0m0.000s

Isto porque a calculadora primeiro calculou a parte 30965537, o que gera um número com 163.185 dígitos!

Contudo estas operações podem ter o esforço matemático drasticamente reduzido.

Basicamente consiste em explorar uma propriedade da aritmética modular.

Como exemplo, vamos pegar esta potência: 3119 mod 137

echo "31 ^ 19 % 137" | bc
117

Resposta é 117.

Mas a calculadora bc, para chegar ao resultado, computou primeiro a parte 3119, que resulta em um número grande:

echo "31 ^ 19 " | bc
21670662219970396194714277471

O atalho matemático pula esta fase, pois não queremos saber quanto é a potência, só nos interessa a resposta final e ela pode ser encontrada muito, mas muito mais rapidamente.

Qual a potência que nos parece pequena, gerenciável? Digamos, para este exemplo, que elevar um número ao cubo é algo rápido para nós e não resulta em um processamento muito elevado.

Qualquer expressão Xy mod N pode ter o y decomposto e partes menores. Decidimos que cada parte será 3.

Quantas vezes 3 está em 19? Resposta: 6 vezes.

3 * 6 = 18, havendo um resto 1.

Então, a expressão 3119 mod 137 pode ser reescrita como:

( (313 mod 137) * (313 mod 137) * (313 mod 137) * (313 mod 137) * (313 mod 137) * (313 mod 137) * (311 mod 137) ) mod 137

Observando que as somas das potências deve dar 19.

Seria estupidez computar o (313 mod 137) todas as vezes, pois pode ser computado uma única vez e armazenar:

313 mod 137 = 62
311 mod 137 = 31



echo "31 ^ 3" | bc
29791
echo "31 ^ 3 % 137" | bc
62
echo "31 ^ 1 % 137" | bc
31

Veja com os valores são mais amigáveis!

Então temos: ( 62 * 62 * 62 * 62 * 62 * 62 * 31) mod 137

Para números pequenos, podemos realmente executar isto:

echo "( 62 * 62 * 62 * 62 * 62 * 62 * 31) % 137" | bc
117

Mas veja que esta nova expressão ( 62 * 62 * 62 * 62 * 62 * 62 * 31) mod 137, devido as propriedades da aritmética modular, também pode ser reescrita como:

((626 mod 137) * (31 mod 137)) mod 137

O que permite, ainda, chamar a simplificação de forma recursiva para a expressão (626 mod 137):

Veja como dá certo:

echo "( ( (62 ^ 6) %137) * 31) % 137" | bc
117

Uma implementação em PHP que explora este atalho permitindo lidar com números de até 32 bits pode ser testada em Cálculo de X na potência Y modulo N (use VOL como número de matrícula).

Outras dicas deste autor

Melhore o desempenho do HISTORY

Uso das chaves na linha de comando

Windows antes no Grub do Ubuntu 10.04

Firewall SIMPLES e eficiente para DESKTOP em 5 linhas

Em C, escrever em arquivo fácil

Leitura recomendada

Encontrando erros em C/C++ com Cppcheck

Encontrando erros em C/C++ com Valgrind

Biometria facial no login do GDM

return main(); (fatal) - C++

Script que fecha portas

  

Comentários
[1] Comentário enviado por elgio em 21/08/2009 - 15:26h

André Matos, vencedor do desafio, publicou junto ao desafio uma implementação binária deste procedimento. Apesar de não parecer, trata-se do mesmo método, apenas que lá ele usou a potência 2 como divisor o que torna ainda mais rápido pois pode-se usar SHIFT para dividir por 2, já que no sistema binário, fazer um shift bit a bit para a esquerda equivale a dividir por dois.

[2] Comentário enviado por rob_som em 14/12/2009 - 00:58h

Muito interessante a dica.
Parabéns.



Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts