Cálculo da potência modular de forma eficiente

Publicado por Elgio Schlemer em 17/08/2009

[ Hits: 25.112 ]

Blog: https://profelgio.duckdns.org/~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

Windows antes no Grub do Ubuntu 10.04

Enviar aspas em PHP de maneira menos suja

Usando rm para apagar arquivos esquisitos

DROP ou REJECT no iptables?

Em C, escrever em arquivo fácil

Leitura recomendada

Encontrando erros em C/C++ com Cppcheck

Encontrando erros em C/C++ com Valgrind

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

Biometria facial no login do GDM

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

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts