Um smart card, um token de autenticação, um chip de secure boot — qualquer dispositivo que alguém consiga colocar as mãos fisicamente em cima é candidato a um ataque de canal lateral. Não é ficção: já apareceu documentado em produto comercial real. O atacante nem precisa quebrar a matemática do RSA; basta medir tempo de execução ou consumo de energia enquanto o dispositivo faz a conta, e reconstruir bit a bit o expoente secreto.
O motivo é conhecido: no algoritmo clássico de square-and-multiply, a multiplicação só acontece quando o bit do expoente é 1. Essa diferença de trabalho vaza. Se você já leu sobre essa vulnerabilidade em “Exponenciação Modular Rápida e Segura: Square-and-Multiply na Prática”, este artigo é sobre uma das respostas mais elegantes ao problema: randomizar a própria conta, sem mudar o resultado final.
A ideia central
Exponenciação modular randomizada não muda o algoritmo de multiplicação em si — muda os parâmetros que entram nele. Em vez de operar diretamente sobre x, d e N (base, expoente secreto e módulo), o algoritmo gera três números aleatórios e transforma os parâmetros antes de fazer a conta. O padrão de bits que um atacante observaria durante a execução deixa de corresponder ao expoente real, porque o expoente real nunca é usado diretamente.
O algoritmo, passo a passo
1. Escolha de números aleatórios
Três valores aleatórios são sorteados: r₁, r₂ e r₃. Eles servem para modificar os parâmetros originais da computação.
2. Transformação dos parâmetros
Usando esses números, os valores originais x, d e N são transformados em novos parâmetros:
- x′ = x + r₁ · N
- d′ = d + r₂ · φ(N)
- N′ = r₃ · N
Aqui, φ(N) é a função totiente de Euler — quantos números até N são relativamente primos a N.
3. Cálculo da exponenciação
Em vez de calcular xd mod N diretamente, o algoritmo calcula x′d′ mod N′. Depois disso, o resultado é reduzido módulo N para recuperar o valor final.
4. Resultado final
O valor obtido, mesmo depois das modificações e do uso de números aleatórios, é igual a xd mod N. O processo intermediário, no entanto, impede que o expoente secreto d seja revelado pela análise das operações — porque o expoente que efetivamente “aparece” na execução é d′, diferente a cada rodada.
Por que isso funciona: Euler entra em cena
A segurança do método randomizado depende diretamente de dois conceitos de teoria dos números.
Função totiente de Euler (φ)
φ(N) é o número de inteiros positivos até N que são relativamente primos a N. Alguns exemplos:
- φ(2) = 1
- φ(3) = 2
- φ(5) = 4
- φ(10) = 4 (só 1, 3, 7 e 9 são relativamente primos a 10)
Além disso, para dois números m e n relativamente primos entre si, vale φ(m·n) = φ(m)·φ(n) — propriedade que simplifica bastante os cálculos envolvidos.
Teorema de Euler
O Teorema de Euler diz que, para qualquer inteiro a relativamente primo a n:
aφ(n) mod n = 1
Essa relação é o que garante que, depois de toda a transformação dos parâmetros com números aleatórios, a redução final módulo N devolve exatamente o valor correto — sem essa garantia matemática, a randomização quebraria o resultado em vez de só disfarçar o processo.
O que você ganha — e o que isso custa
Ganhos:
- Obscurecimento do expoente secreto: a aleatoriedade incorporada ao processo impede que o padrão de multiplicações e quadrados revele bits de d, neutralizando o vetor de ataque por canal lateral.
- Correção computacional preservada: apesar das modificações, o Teorema de Euler garante que o resultado final continua equivalente ao cálculo original xd mod N.
- Camada extra de segurança: a técnica reforça a robustez do sistema contra técnicas de ataque cada vez mais sofisticadas.
O que isso custa, e ninguém deveria fingir que não custa: gerar três números aleatórios de qualidade criptográfica a cada operação não é grátis, e os parâmetros transformados (x′, d′, N′) são maiores que os originais — o que significa mais bits para processar em cada multiplicação. Randomização é uma troca deliberada de performance por resistência a canal lateral, não um upgrade “de graça”. Se seu dispositivo já está no limite de processamento (um microcontrolador simples, por exemplo), vale medir esse overhead antes de assumir que a técnica cabe no orçamento do projeto.
Vale notar também que essa técnica resolve um problema diferente do que a Redução de Montgomery resolve — Montgomery ataca o custo da multiplicação modular em si (ver “Redução de Montgomery: Otimizando a Multiplicação Modular em Hardware”), enquanto randomização ataca especificamente o vazamento de informação através do padrão observável de execução. Na prática, é comum ver as duas combinadas na mesma implementação, cada uma resolvendo a sua parte do problema.
Fechando
Exponenciação modular randomizada é a evolução natural do square-and-multiply clássico quando você para de tratar side-channel como “problema de outro departamento”. Integrando aleatoriedade a fundamentos matemáticos sólidos — o Teorema de Euler não é coadjuvante aqui, é o que garante que a técnica não quebre o resultado — ela neutraliza justamente a vulnerabilidade que a versão otimizada e “rápida” do algoritmo introduziu.
Se você trabalha com hardware que processa chaves privadas fisicamente acessíveis a terceiros — cartão, token, qualquer secure element — essa é uma das primeiras defesas que vale avaliar, ao lado de Montgomery Ladder e blinding de base. Comenta aqui se você já mediu o overhead de uma implementação randomizada em produção: quanto isso pesou no seu caso?
