Introducción: El «estado de pecado» de von Neumann y la paradoja del azar determinista

En 1951, John von Neumann pronunció una sentencia célebre en la historia de la computación: «Cualquiera que considere métodos aritméticos para producir dígitos aleatorios está, por supuesto, en estado de pecado (in a state of sin).» Una computadora digital es una máquina de estados finitos estrictamente determinista: dado un estado inicial y una instrucción, cada bit resultante está predeterminado al 100%. Sin embargo, desde las simulaciones de Monte Carlo en física nuclear y la generación procedural de videojuegos hasta las claves TLS, SSH y firmas ECDSA, nuestra civilización consume billones de números aleatorios cada segundo.

¿Cómo puede un algoritmo fijo producir imprevisibilidad? ¿Y por qué un generador estadísticamente sobresaliente como Mersenne Twister (MT19937) resulta catastróficamente inseguro al generar tokens de contraseñas, permitiendo que un atacante que observe apenas 624 salidas consecutivas prediga el 100% de todas sus salidas futuras y pasadas?

Capítulo 1: Anatomía matemática de un PRNG ── Semilla (Seed), espacio de estados finito y principio del palomar

Formalmente, un generador de números pseudoaleatorios (PRNG) es un autómata determinista $(\mathcal{S}, \mathcal{O}, f, g, s_0)$ con un espacio de estados interno finito $\mathcal{S}$ de tamaño $|\mathcal{S}| = 2^b$, una semilla inicial (Seed) $s_0 \in \mathcal{S}$, una función de transición $f: \mathcal{S} \to \mathcal{S}$ y una función de salida $g: \mathcal{S} \to \mathcal{O}$:

Fijada la semilla $s_0$, toda la sucesión $r_0, r_1, r_2, \dots$ queda completamente determinada. Esta reproducibilidad es vital para depurar simulaciones científicas. Pero por el principio del palomar (Pigeonhole Principle), el autómata debe repetir algún estado previo $s_{k+P} = s_k$ en a lo sumo $2^b$ pasos, quedando atrapado en un ciclo periódico de período $P \le 2^b$.

  flowchart LR
    S0["Semilla inicial s0"] --> S1["Estado s1 = f(s0)"]
    S1 --> S2["Estado s2 = f(s1)"]
    S2 -. "Pre-período (Tail)" .-> Sk["Entrada al 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

El método del cuadrado medio (Middle-Square Method, 1949) de von Neumann (elevar al cuadrado un número de $2k$ dígitos y extraer los $2k$ dígitos centrales) colapsa rápidamente hacia 0000 o en ciclos minúsculos de longitud 4 por carecer de estructura algebraica.

Capítulo 2: Generadores congruenciales lineales (LCG) y el teorema de Marsaglia ── La tragedia de los 15 planos de IBM RANDU

En 1949, D. H. Lehmer introdujo el generador congruencial lineal (LCG): $X_{n+1} = (a X_n + c) \bmod m$. Por el teorema de Hull-Dobell (1962), un LCG alcanza el período completo $P = m$ si y solo si: (1) $\gcd(c, m) = 1$, (2) todo factor primo $p$ de $m$ divide a $a-1$, y (3) si $4 \mid m$, entonces $4 \mid (a-1)$.

En 1968, el estadístico George Marsaglia publicó su famoso artículo «Random numbers fall mainly in the planes», demostrando que los puntos $d$-dimensionales $(X_n, \dots, X_{n+d-1})$ de cualquier LCG caen sobre a lo sumo $(d! \cdot m)^{1/d}$ hiperplanos paralelos formando una red cristalina.

El caso más infame de la historia fue RANDU de IBM ($m = 2^{31}, c = 0, a = 65539 = 2^{16} + 3$) en los mainframes System/360:

Debido a la identidad $X_{n+2} \equiv 6 X_{n+1} - 9 X_n \pmod{2^{31}}$, ¡todos los puntos 3D generados por RANDU en el cubo unitario están atrapados en tan solo 15 planos paralelos con enormes vacíos entre ellos, invalidando miles de simulaciones de Monte Carlo durante décadas!

Capítulo 3: Mersenne Twister (MT19937) y generadores estadísticos modernos (PCG64, Xoshiro256++)

En 1997, los matemáticos japoneses Makoto Matsumoto y Takuji Nishimura crearon el Mersenne Twister (MT19937) sobre el cuerpo finito $\mathbb{F}_2 = \{0, 1\}$ (adoptado por defecto en Python random, R, MATLAB, C++ std::mt19937):

1. Período astronómico y equidistribución en 623 dimensiones: Una matriz de estado de $624$ palabras de 32 bits ($19.937$ bits activos) logra un período igual al primo de Mersenne $P = 2^{19937} - 1 \approx 4,315 \times 10^{6001}$ y equidistribución exacta en hasta 623 dimensiones.
2. Transformación de templado (Tempering): Cada palabra de estado $x$ se multiplica por una matriz invertible sobre $\mathbb{F}_2^{32}$ mediante cuatro desplazamientos y XOR:

Para superar el tamaño de estado de MT19937 ($2,5\text{ KB}$) y su fallo en dos pruebas de linealidad $\mathbb{F}_2$ de la suite TestU01 (BigCrush), surgieron PCG64 (Melissa O’Neill 2014: LCG de 128 bits con rotación aleatoria dependiente de datos; estándar en NumPy) y Xoshiro256++ (Blackman & Vigna 2018: estado de 256 bits con mezclador no lineal; usado en Rust y Java), que superan el 100% de BigCrush a velocidades sub-nanosegundo.

Capítulo 4: Por qué perfección estadística $\neq$ seguridad criptográfica ── Clonación de MT19937 y CSPRNG

4.1 Inversión del Tempering: clonar MT19937 observando 624 salidas

Usar MT19937 para tokens de sesión o restablecimiento de contraseñas es un error letal: cada paso del Tempering es una biyección lineal invertible en tiempo $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

¡Un atacante que observe solo 624 salidas consecutivas de 32 bits ($2.496\text{ bytes}$) de un servidor que use MT19937 aplica untemper(z) a cada una para clonar al 100% las 624 palabras del estado interno del servidor! A partir de ese instante, puede predecir el 100% de los números futuros y reconstruir todos los pasados.

4.2 Teorema de Andrew Yao (1982) y generadores criptográficamente seguros (CSPRNG)

La criptografía exige un CSPRNG (Cryptographically Secure PRNG) basado en tres axiomas:

1. Imprevisibilidad del siguiente bit $\iff$ Indistinguibilidad computacional (Teorema de Yao, 1982 / Blum-Micali): Ningún adversario de tiempo polinómico $\mathcal{A}$ que conozca los primeros $k$ bits puede predecir el bit $r_{k+1}$ con ventaja no despreciable sobre $1/2$:

2. Secreto hacia adelante (Forward Secrecy / Resistencia al retroceso): Tras cada salida, la clave interna se sobrescribe mediante una función unidireccional (Fast-Key-Erasure), impidiendo recuperar claves pasadas incluso si se filtra el estado actual.
3. Secreto hacia atrás (Backward Secrecy / Resistencia a la predicción): La inyección periódica de entropía física fresca (Reseeding) permite recuperar la seguridad tras una filtración.

  flowchart TD
    subgraph Insecure ["PRNG estadístico (LCG / MT19937 / Xoshiro)"]
        StateM["Estado interno s_i (624 palabras)"] -- "Tempering F2 lineal invertible" --> OutM["Salida r_i"]
        OutM -- "¡untemper() clona el estado con 624 salidas!" --> StateM
    end
    subgraph Secure ["CSPRNG criptográfico (ChaCha20 / AES-CTR_DRBG)"]
        Entropy["Fuentes de entropía física<br/>(Ruido térmico / RDSEED)"] -- "Reseeding periódico (Backward Secrecy)" --> StateC["Clave secreta 256 bits y Contador"]
        StateC -- "Primitiva unidireccional (ChaCha20 / AES)<br/>[¡Invertir cuesta 2^256 operaciones!]" --> OutC["Flujo aleatorio criptográfico r_i"]
        StateC -- "Fast-Key-Erasure Key' = PRF(Key)<br/>[¡Forward Secrecy!]" --> StateC_Next["Estado renovado Key'"]
    end

Los CSPRNG modernos emplean cifradores como ChaCha20-RNG (kernel Linux, OpenBSD, Rust) y AES-CTR_DRBG (NIST SP 800-90A), o problemas numéricos como Blum-Blum-Shub ($x_{n+1} = x_n^2 \bmod M$). Por el contrario, el generador de curvas elípticas Dual_EC_DRBG estandarizado por el NIST en 2006 contenía una puerta trasera kleptográfica de la NSA (confirmada por los documentos de Snowden en 2013: quien conociera el logaritmo discreto secreto $d$ tal que $P = d \cdot Q$ podía deducir el estado interno con solo 32 bytes de salida y descifrar TLS).

Capítulo 5: Generadores físicos (TRNG), min-entropía ($H_\infty$) y piscinas de entropía del sistema operativo

La semilla de un CSPRNG proviene de un generador de números aleatorios por hardware (TRNG / HRNG) que captura el caos físico: ruido térmico de Johnson-Nyquist en resistencias, ruido de disparo cuántico por ruptura en avalancha de diodos Zener y jitter de fase en osciladores en anillo (instrucciones RDSEED/RDRAND en CPUs Intel/AMD). En criptografía (NIST SP 800-90B), la imprevisibilidad en el peor caso se mide con la min-entropía ($H_\infty$) en lugar de la entropía media de Shannon $H_1$:

El ruido físico bruto se somete a «blanqueo» (Whitening) mediante el algoritmo de von Neumann o extractores hash criptográficos (BLAKE2s en el kernel Linux, respaldado por el Leftover Hash Lemma) antes de alimentar al CSPRNG.

En Linux moderno (5.6+), /dev/random y /dev/urandom usan exactamente el mismo CSPRNG ChaCha20; los desarrolladores deben usar siempre getrandom(2) (o Python secrets, JS crypto.getRandomValues(), Rust OsRng/ThreadRng, Go crypto/rand). El desastre de Debian OpenSSL de 2008 (CVE-2008-0166) —donde comentar una línea por una advertencia de Valgrind redujo la entropía de todas las claves RSA/SSH al ID de proceso PID de 15 bits ($32.768$ claves posibles) durante dos años— y el fallo del nonce estático ECDSA en la PlayStation 3 de Sony (2010) demuestran una ley inquebrantable: la fortaleza de cualquier sistema criptográfico jamás puede superar la entropía de su generador de números aleatorios.