Introdução: O «estado de pecado» de von Neumann e o paradoxo do acaso determinístico

Em 1951, John von Neumann proferiu uma frase imortal na ciência da computação: «Qualquer um que considere métodos aritméticos para produzir dígitos aleatórios está, claro, em estado de pecado (in a state of sin).» Um computador digital é uma máquina de estados finitos estritamente determinística: dado um estado inicial e uma instrução, cada bit produzido é 100% predeterminado. Ainda assim, desde simulações de Monte Carlo em física nuclear e geração procedural em jogos até chaves TLS, SSH e assinaturas ECDSA, nossa civilização consome trilhões de números aleatórios por segundo.

Como um algoritmo fixo pode criar imprevisibilidade? E por que um gerador estatisticamente brilhante como o Mersenne Twister (MT19937) torna-se catastroficamente inseguro ao gerar tokens de redefinição de senha, permitindo que um invasor que observe apenas 624 saídas consecutivas preveja 100% de todas as saídas futuras e passadas?

Capítulo 1: Anatomia matemática de um PRNG ── Semente (Seed), espaço de estados finito e princípio da casa dos pombos

Formalmente, um gerador de números pseudoaleatórios (PRNG) é um autômato determinístico $(\mathcal{S}, \mathcal{O}, f, g, s_0)$ com um espaço de estados interno finito $\mathcal{S}$ de tamanho $|\mathcal{S}| = 2^b$, uma semente inicial (Seed) $s_0 \in \mathcal{S}$, uma função de transição $f: \mathcal{S} \to \mathcal{S}$ e uma função de saída $g: \mathcal{S} \to \mathcal{O}$:

Fixada a semente $s_0$, toda a sequência $r_0, r_1, r_2, \dots$ está completamente determinada. Essa reprodutibilidade é essencial para depurar simulações científicas. Mas pelo princípio da casa dos pombos (Pigeonhole Principle), o autômato deve revisitar algum estado anterior $s_{k+P} = s_k$ em no máximo $2^b$ passos, entrando em um ciclo periódico de período $P \le 2^b$.

  flowchart LR
    S0["Semente inicial s0"] --> S1["Estado s1 = f(s0)"]
    S1 --> S2["Estado s2 = f(s1)"]
    S2 -. "Pré-período (Tail)" .-> Sk["Entrada do ciclo sk"]
    Sk --> Sk1["Estado s(k+1)"]
    Sk1 -. "Ciclo periódico P <= 2^b" .-> Skm1["Estado s(k+P-1)"]
    Skm1 -- "f(s(k+P-1)) = sk" --> Sk

O método do quadrado do meio (Middle-Square Method, 1949) de von Neumann (elevar ao quadrado um número de $2k$ dígitos e extrair os $2k$ dígitos centrais) colapsa rapidamente para 0000 ou em ciclos minúsculos de comprimento 4 por falta de estrutura algébrica.

Capítulo 2: Geradores congruenciais lineares (LCG) e o teorema de Marsaglia ── A tragédia dos 15 planos do IBM RANDU

Em 1949, D. H. Lehmer introduziu o gerador congruencial linear (LCG): $X_{n+1} = (a X_n + c) \bmod m$. Pelo teorema de Hull-Dobell (1962), um LCG atinge o período completo $P = m$ se e somente se: (1) $\gcd(c, m) = 1$, (2) todo fator primo $p$ de $m$ divide $a-1$, e (3) se $4 \mid m$, então $4 \mid (a-1)$.

Em 1968, o estatístico George Marsaglia publicou seu célebre artigo «Random numbers fall mainly in the planes», provando que os pontos $d$-dimensionais $(X_n, \dots, X_{n+d-1})$ de qualquer LCG caem sobre no máximo $(d! \cdot m)^{1/d}$ hiperplanos paralelos de uma rede cristalina!

O caso mais infame da história foi o RANDU da IBM ($m = 2^{31}, c = 0, a = 65539 = 2^{16} + 3$) nos mainframes System/360:

Devido à identidade $X_{n+2} \equiv 6 X_{n+1} - 9 X_n \pmod{2^{31}}$, todos os pontos 3D gerados pelo RANDU no cubo unitário ficam presos em apenas 15 planos paralelos com imensos vazios entre eles, comprometendo milhares de simulações de Monte Carlo por décadas!

Capítulo 3: Mersenne Twister (MT19937) e geradores estatísticos modernos (PCG64, Xoshiro256++)

Em 1997, os matemáticos japoneses Makoto Matsumoto e Takuji Nishimura criaram o Mersenne Twister (MT19937) sobre o corpo finito $\mathbb{F}_2 = \{0, 1\}$ (padrão em Python random, R, MATLAB, C++ std::mt19937):

1. Período colossal e equidistribuição em 623 dimensões: Um vetor de estado de $624$ palavras de 32 bits ($19.937$ bits ativos) garante um período igual ao primo de Mersenne $P = 2^{19937} - 1 \approx 4,315 \times 10^{6001}$ e equidistribuição exata em até 623 dimensões!
2. Transformação de têmpera (Tempering): Cada palavra de estado $x$ é multiplicada por uma matriz invertível sobre $\mathbb{F}_2^{32}$ em quatro etapas de deslocamento e XOR:

Para superar o tamanho de estado do MT19937 ($2,5\text{ KB}$) e sua falha em dois testes de linearidade $\mathbb{F}_2$ da suíte TestU01 (BigCrush), surgiram o PCG64 (Melissa O’Neill 2014: LCG de 128 bits com rotação aleatória dependente de dados; padrão no NumPy) e o Xoshiro256++ (Blackman & Vigna 2018: estado de 256 bits com embaralhador não linear; usado em Rust e Java), que passam em 100% do BigCrush em menos de um nanossegundo.

Capítulo 4: Por que perfeição estatística $\neq$ segurança criptográfica ── Clonagem do MT19937 e CSPRNG

4.1 Inversão do Tempering: clonando o MT19937 com 624 saídas

Usar MT19937 para tokens de sessão ou senhas é um erro fatal: cada etapa do Tempering é uma bijeção linear invertível em tempo $O(1)$:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def untemper(z: int) -> int:
    # Invert MT19937 32-bit output z back to internal state word x in O(1)
    y3 = z ^ (z >> 18)
    y2 = y3 ^ ((y3 << 15) & 0xEFC60000)
    y1 = y2
    for _ in range(4):
        y1 = y2 ^ ((y1 << 7) & 0x9D2C5680)
    x = y1
    for _ in range(2):
        x = y1 ^ (x >> 11)
    return x & 0xFFFFFFFF

Um invasor que observe apenas 624 saídas consecutivas de 32 bits ($2.496\text{ bytes}$) de um servidor usando MT19937 aplica untemper(z) a cada uma para clonar 100% das 624 palavras do estado interno do servidor! A partir daí, ele prevê 100% dos números futuros e reconstrói todos os passados.

4.2 Teorema de Andrew Yao (1982) e geradores criptograficamente seguros (CSPRNG)

A criptografia exige um CSPRNG (Cryptographically Secure PRNG) baseado em três axiomas:

1. Imprevisibilidade do próximo bit $\iff$ Indistinguibilidade computacional (Teorema de Yao, 1982 / Blum-Micali): Nenhum adversário de tempo polinomial $\mathcal{A}$ que conheça os primeiros $k$ bits pode prever o bit $r_{k+1}$ com vantagem não desprezível sobre $1/2$:

2. Sigilo direto (Forward Secrecy / Resistência ao retrocesso): Após cada saída, a chave interna é sobrescrita por uma função unidirecional (Fast-Key-Erasure), impedindo recuperar chaves passadas mesmo se o estado atual vazar.
3. Sigilo reverso (Backward Secrecy / Resistência à previsão): A injeção contínua de entropia física fresca (Reseeding) restaura a segurança após um vazamento.

  flowchart TD
    subgraph Insecure ["PRNG estatístico (LCG / MT19937 / Xoshiro)"]
        StateM["Estado interno s_i (624 palavras)"] -- "Tempering F2 linear invertível" --> OutM["Saída r_i"]
        OutM -- "untemper() clona o estado com 624 saídas!" --> StateM
    end
    subgraph Secure ["CSPRNG criptográfico (ChaCha20 / AES-CTR_DRBG)"]
        Entropy["Fontes de entropia física<br/>(Ruído térmico / RDSEED)"] -- "Reseeding periódico (Backward Secrecy)" --> StateC["Chave secreta 256 bits e Contador"]
        StateC -- "Primitiva unidirecional (ChaCha20 / AES)<br/>[Inverter custa 2^256 operações!]" --> OutC["Fluxo aleatório criptográfico r_i"]
        StateC -- "Fast-Key-Erasure Key' = PRF(Key)<br/>[Forward Secrecy!]" --> StateC_Next["Estado renovado Key'"]
    end

Os CSPRNGs modernos utilizam cifras como ChaCha20-RNG (kernel Linux, OpenBSD, Rust) e AES-CTR_DRBG (NIST SP 800-90A), ou problemas teóricos como Blum-Blum-Shub ($x_{n+1} = x_n^2 \bmod M$). Em contrapartida, o gerador de curvas elípticas Dual_EC_DRBG padronizado pelo NIST em 2006 continha um backdoor kleptográfico da NSA (confirmado pelos documentos de Snowden em 2013: quem conhecesse o logaritmo discreto secreto $d$ tal que $P = d \cdot Q$ podia deduzir o estado interno com apenas 32 bytes de saída e descriptografar o tráfego TLS).

Capítulo 5: Geradores físicos (TRNG), min-entropia ($H_\infty$) e pools de entropia do sistema operacional

A semente de um CSPRNG vem de um gerador de números aleatórios por hardware (TRNG / HRNG) que coleta caos físico: ruído térmico de Johnson-Nyquist em resistores, ruído quântico de disparo por ruptura em avalanche de diodos Zener e jitter de fase em osciladores em anel (instruções RDSEED/RDRAND em CPUs Intel/AMD). Na criptografia (NIST SP 800-90B), a imprevisibilidade no pior caso é medida pela min-entropia ($H_\infty$) em vez da entropia média de Shannon $H_1$:

O ruído físico bruto passa por «branqueamento» (Whitening) via algoritmo de von Neumann ou extratores hash criptográficos (BLAKE2s no kernel Linux, apoiado pelo Leftover Hash Lemma) antes de alimentar o CSPRNG.

No Linux moderno (5.6+), /dev/random e /dev/urandom usam exatamente o mesmo CSPRNG ChaCha20; desenvolvedores devem usar sempre getrandom(2) (ou Python secrets, JS crypto.getRandomValues(), Rust OsRng/ThreadRng, Go crypto/rand). O desastre do Debian OpenSSL de 2008 (CVE-2008-0166) — onde comentar uma linha por causa de um aviso do Valgrind reduziu a entropia de todas as chaves RSA/SSH ao ID de processo PID de 15 bits ($32.768$ chaves possíveis) por dois anos — e a falha do nonce estático ECDSA no PlayStation 3 da Sony (2010) provam uma regra de ouro: a segurança de qualquer sistema criptográfico jamais pode superar a entropia de seu gerador de números aleatórios.