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 309⁶⁵⁵³⁷ 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 309⁶⁵⁵³⁷, 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: 31¹⁹ mod 137

echo "31 ^ 19 % 137" | bc
117

Resposta é 117.

Mas a calculadora bc, para chegar ao resultado, computou primeiro a parte 31¹⁹, 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 X^y 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 31¹⁹ mod 137 pode ser reescrita como:

( (31³ mod 137) * (31³ mod 137) * (31³ mod 137) * (31³ mod 137) * (31³ mod 137) * (31³ mod 137) * (31¹ mod 137) ) mod 137

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

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

31³ mod 137 = 62
31¹ 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:

((62⁶ mod 137) * (31 mod 137)) mod 137

O que permite, ainda, chamar a simplificação de forma recursiva para a expressão (62⁶ 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).