Já vi código em produção fazendo a ** e antes de aplicar o módulo, com e de várias centenas de bits. O processo travava, a memória disparava, e a primeira reação de quem escreveu foi “deve ser bug na lib”. Não era. Era matemática básica: número elevado a expoente grande antes de reduzir cresce exponencialmente, e nenhuma biblioteca aguenta isso de graça.
Se você vai implementar RSA, Diffie-Hellman ou qualquer coisa que dependa de ae mod n com expoentes grandes, esse artigo é sobre como fazer essa conta rápido — e sobre um detalhe que a maioria só descobre depois de apanhar: a própria otimização de performance pode abrir uma porta para ataque.
Por que a implementação ingênua não sobrevive
Método 1 — potência primeiro, módulo depois:
result = a ** e
result %= n
Simples de ler, inviável na prática — o valor intermediário a ** e explode antes de você conseguir reduzi-lo.
Método 2 — multiplicação iterativa:
result = 1
for _ in range(e):
result = (result * a) % n
Melhor, porque mantém os números sempre dentro de uma faixa controlada — mas ainda exige uma multiplicação por unidade do expoente. Para um expoente de 2048 bits, isso é proibitivo.
Square-and-Multiply: de O(e) para O(log e)
A virada acontece quando você para de tratar o expoente como uma contagem e passa a tratá-lo como uma sequência de bits. Convertendo e para binário, dá para reduzir o número de multiplicações de O(e) para O(log e) — uma diferença gigantesca quando e tem centenas de bits.
Existem duas formas equivalentes de implementar isso.
Esquerda para direita
- Converta o expoente para binário (s+1 bits).
- Inicialize
result = 1. - Para cada bit, do mais significativo ao menos significativo:
- Eleve ao quadrado:
result = (result * result) % n - Se o bit for 1, multiplique:
result = (result * a) % n
Direita para esquerda
- Converta o expoente para binário.
- Inicialize
result = ase o bit menos significativo for 1, senãoresult = 1. Definabase = a. - Para cada bit restante, do menos significativo ao mais significativo:
- Eleve ao quadrado a base:
base = (base * base) % n - Se o bit for 1, multiplique:
result = (result * base) % n
As duas chegam no mesmo resultado — a diferença é só a ordem de varredura dos bits e qual variável carrega o acumulador. Na prática, a escolha entre uma e outra costuma depender de qual encaixa melhor na arquitetura onde o código vai rodar.
Rodando o exemplo: a²³
23 em binário é 10111. Usando esquerda-para-direita:
| Iteração | Bit | Operação | Valor (pré-módulo) | Resultado parcial |
|---|---|---|---|---|
| Init | — | inicializa | — | 1 |
| 1 | 1 | quadrado + multiplica | a | a |
| 2 | 0 | quadrado | a² | a² |
| 3 | 1 | quadrado + multiplica | a⁴ × a = a⁵ | a⁵ |
| 4 | 1 | quadrado + multiplica | a¹⁰ × a = a¹¹ | a¹¹ |
| 5 | 1 | quadrado + multiplica | a²² × a = a²³ | a²³ |
Economia real: 7 multiplicações contra 22 do método ingênuo — mais de 70% de operações a menos. Multiplica isso por um expoente de 2048 bits e a diferença deixa de ser acadêmica: é a diferença entre um handshake TLS instantâneo e um que trava o usuário na tela de carregamento.
O problema que a otimização introduz
Aqui está o ponto que costuma pegar quem implementou isso pensando só em performance: a etapa condicional — “multiplica só se o bit for 1” — cria uma diferença observável de comportamento dependendo do valor do bit. Essa diferença aparece em:
- Tempo de execução (um branch a mais quando o bit é 1)
- Consumo de energia (mais operações = mais corrente consumida)
Um atacante monitorando essas variáveis — timing attack ou power analysis — pode, com repetições suficientes, inferir os bits do expoente secreto. Ou seja: o mesmo algoritmo que você otimizou para ser rápido é, por construção, mais fácil de espionar do que uma versão “lenta” que sempre faz o mesmo trabalho independente do bit.
Isso não é motivo para descartar square-and-multiply — é motivo para não parar na primeira versão que funciona e passa nos testes de correção.
Como mitigar sem abrir mão da performance
- Algoritmos de tempo constante: eliminar desvios condicionais que dependem do valor dos bits do expoente.
- Montgomery Ladder: garante uma sequência fixa de quadrado-e-multiplica para todo bit, independente do valor — elimina a assimetria que o atacante exploraria. Vale um artigo à parte para detalhar a mecânica de redução por trás dela: “Redução de Montgomery: Otimizando a Multiplicação Modular em Hardware”.
- Exponent blinding: randomizar o expoente antes da computação, de forma que o resultado final continue correto mas o padrão de bits observado não corresponda ao expoente real. O fundamento matemático dessa técnica — apoiado no Teorema de Euler — está detalhado em “Exponenciação Modular Randomizada: Como Blindar RSA Contra Ataques de Canal Lateral”.
- Base blinding: adicionar máscaras aleatórias às entradas, removendo-as depois do cálculo.
Fechando
Exponenciação modular eficiente é o que viabiliza criptografia rápida e de baixo consumo de energia — mas “eficiente” e “seguro” não vêm de graça juntos. Square-and-multiply reduz drasticamente o custo computacional, só que, sem cuidado adicional, também abre uma janela de vazamento por canal lateral. Combinar técnicas de tempo constante com algoritmos como Montgomery Ladder é o que entrega as duas coisas ao mesmo tempo — velocidade e robustez.
Se você mantém código de criptografia em produção, vale parar agora e checar: sua implementação de exponenciação modular tem algum branch condicional dependente de bit secreto? Se a resposta for sim, os dois artigos linkados acima (Montgomery e randomização) são o próximo passo lógico. Comenta se você já teve que revisar código assim depois de um pentest — quero saber que tipo de vazamento apareceu na prática.
