Generador de números aleatorios

Una breve historia de la aleatoriedad en computadoras

Las computadoras son máquinas deterministas, lo que vuelve «aleatorio» algo extraño que tengan que producir. La historia de los generadores de números pseudoaleatorios (PRNG) en computadoras empieza con el método del cuadrado medio de John von Neumann en 1946, elevar al cuadrado el número anterior, tomar las cifras del medio como nuevo valor, repetir. El propio von Neumann lo llamó «un estado pecaminoso» usar generadores de números aleatorios sin entenderlos por completo, porque el cuadrado medio tiene modos de fallo evidentes (cae a cero, períodos cortos). El generador congruencial lineal de Lehmer (LCG, 1951), x_(n+1) = (a × x_n + c) mod m, fue la primera familia de PRNG con propiedades estadísticas razonables; la rand() de la biblioteca estándar de C todavía suele usar una variante LCG. El Mersenne Twister (Matsumoto y Nishimura, 1997-1998) nos dio un generador con un período de 2¹⁹⁹³⁷−1 (sí, un número de 6.000 dígitos) y excelentes propiedades estadísticas; pasó a ser el predeterminado en Python, R, MATLAB, PHP y muchos otros lenguajes. La familia xorshift de Marsaglia (2003) es bastante más rápida y suficientemente pequeña para caber en un registro de hardware; el V8 moderno (el motor JavaScript de Chrome) usa una variante xorshift128+ para Math.random(). PCG (Permuted Congruential Generator) de Melissa O'Neill (2014) es el estado del arte estadístico actual para PRNG no criptográficos, combinando avance de estado al estilo LCG con permutación de salida para excelentes propiedades estadísticas a bajo coste.

Los PRNG criptográficamente seguros (CSPRNG) son una bestia distinta. Propiedad definitoria: aunque un atacante conozca cada salida que el generador haya producido, no puede predecir la siguiente con mejor que una ventaja despreciable. La llamada al sistema getrandom() de Linux (añadida en el kernel 3.17, octubre de 2014) y el /dev/urandom subyacente usan un generador basado en ChaCha20 sembrado por fuentes de entropía de hardware (RDRAND, tiempos de interrupciones, ruido de audio). BCryptGenRandom de Windows usa una construcción AES-CTR-DRBG (NIST SP 800-90A) sembrada desde varias fuentes de entropía. macOS / iOS usan la familia arc4random, originalmente un CSPRNG basado en RC4 y reescrito sobre ChaCha20 alrededor de 2013. La diferencia entre PRNG y CSPRNG importa enormemente: un PRNG sirve para aleatoriedad de juego, asignación de buckets en pruebas A/B o simulaciones; para cualquier cosa que un atacante podría intentar predecir (tokens de sesión, generación de contraseñas, identificadores de seguridad), solo un CSPRNG es seguro.

Las dos API aleatorias de JavaScript

Math.random() es la API más antigua y más simple, devuelve un número en coma flotante distribuido aproximadamente uniforme en [0, 1). La especificación ECMAScript deja deliberadamente el algoritmo subyacente sin especificar («approximately uniform distribution between 0 and 1, exclusive»), y los motores han ido cambiando lo que usan a lo largo de los años. V8 (Chrome) usó durante años un generador multiplicativo con acarreo (MWC1616), después pasó a xorshift128+ en 2015 por mejores propiedades estadísticas. SpiderMonkey (Firefox) y JavaScriptCore (Safari) usan generadores no criptográficos rápidos similares. Math.random() es lo bastante rápido y uniforme para mecánicas de juego, simulaciones y cualquier aplicación donde la imprevisibilidad no sea un requisito de seguridad. No es criptográficamente seguro, el período lo define la implementación, el estado puede recuperarse con pocas salidas, y la secuencia no es segura para generar contraseñas o casos de uso sensibles a la seguridad. crypto.getRandomValues() es el CSPRNG de la Web Crypto API. Llena un array tipado con bytes aleatorios criptográficamente seguros tomados del CSPRNG del sistema operativo (la misma fuente que TLS usa para sus claves de sesión). Disponible en todos los navegadores modernos desde aproximadamente 2014; el tamaño máximo de búfer en una sola llamada es de 65.536 bytes. La elección correcta para cualquier número aleatorio que importe, generación de tokens, identificadores de seguridad, generación de contraseñas, cualquier cosa que un atacante pudiera intentar predecir.

La trampa del sesgo de módulo

Generar un entero uniforme en un rango específico a partir de un CSPRNG es más difícil de lo que parece. El enfoque ingenuo, crypto.getRandomValues(new Uint8Array(1))[0] % 6 para un lanzamiento de dado, produce una distribución sesgada porque 256 no se divide de forma exacta entre 6. Los valores 0-3 aparecen 43 veces cada uno en el rango 0-255; los valores 4-5 aparecen 42 veces. El sesgo es pequeño en rangos pequeños pero real, y detectable en tiradas largas. El arreglo estándar es el muestreo por rechazo: generar un byte aleatorio, comprobar si cae en el mayor múltiplo de tu rango que quepa (aquí, 252 = 42 × 6), usarlo si sí, descartarlo y reintentar si no. La tasa de descarte está acotada por (rango / siguiente potencia de 2), así que para «1-6» desperdicias alrededor del 1,5 % de los bytes; para «1-1000000» contra un entero aleatorio de 32 bits desperdicias alrededor del 0,02 %. Toda biblioteca aleatoria seria implementa muestreo por rechazo; el Math.floor(Math.random() * (max - min + 1)) + min basado en Math.random() esquiva el sesgo porque la precisión de Math.random() es lo bastante alta (53 bits de mantisa) como para que el sesgo quede por debajo de los niveles humanamente detectables en cualquier rango razonable. Este generador usa salida CSPRNG con muestreo por rechazo, salida uniforme en cualquier rango entero que pidas.

Casos de uso y nivel de aleatoriedad necesario en cada uno

• Sorteos y rifas. Para sorteos no monetarios (intercambios de oficina, asignación de equipos para un hackathon, plan de aula), Math.random() sirve. Para sorteos monetarios o cualquier cosa regulada, usa un CSPRNG y, idealmente, publica la semilla para que sea verificable.
• Mecánicas de juego. Lanzamientos de dados, barajados de cartas, botín, generación procedural. Math.random() es la elección estándar, rápido, suficientemente uniforme, suficientemente impredecible para que los jugadores no detecten patrones. Los CSPRNG se reservan para juegos de cartas en línea donde el lado servidor debe impedir trampa.
• Asignación de buckets para pruebas A/B. Hashea el ID de usuario con un secreto estable para colocar a cada usuario en un bucket de manera determinista; usar Math.random() haría que un usuario cayera en buckets distintos entre cargas de página, lo que arruinaría el experimento. La asignación basada en hash es el patrón correcto; la aleatoriedad solo se usa para elegir la semilla del experimento, una sola vez.
• Muestreo aleatorio para encuestas. Tomar un subconjunto representativo de una población. Math.random() sirve; la pregunta estadística es si tu muestra es lo bastante grande, no si la fuente aleatoria es criptográfica.
• Generación de datos de prueba. Faker, datos de maqueta, fixtures sintéticos de base de datos. Math.random() con una semilla fija (para reproducibilidad) es la elección correcta.
• Claves criptográficas, tokens de sesión, generación de contraseñas. Solo CSPRNG, crypto.getRandomValues() en el navegador, el módulo secrets en Python, crypto/rand en Go, nunca el aleatorio por defecto del lenguaje. Un fallo en esta capa compromete todo lo que dependa de ella; las consecuencias van desde «todas las sesiones son secuestrables» hasta «la clave de cifrado es recuperable».

RANDOM.ORG y la distinción del aleatorio verdadero

RANDOM.ORG se lanzó en 1998 por Mads Haahr en el Trinity College Dublin y sigue siendo la referencia del «aleatorio verdadero» en línea. Donde cada CSPRNG en última instancia deriva sus bits de transformaciones algorítmicas de un estado sembrado por hardware (un proceso determinista, aunque imprevisible para un atacante), RANDOM.ORG mide el ruido atmosférico captado por receptores de radio y convierte ese ruido analógico directamente en bits. Esto lo convierte en un True Random Number Generator (TRNG) en lugar de un Pseudo-Random Number Generator: los bits vienen de un proceso físico genuinamente no determinista, no de un algoritmo determinista. RANDOM.ORG lo usan operadores de lotería, investigadores académicos que llevan a cabo estudios doble-ciego y juegos donde la aleatoriedad verificable importa. La contrapartida: un viaje de ida y vuelta de red por petición, una cuota diaria para el plan gratuito, y la cuestión filosófica de si confías en la fuente de entropía afirmada por RANDOM.ORG por encima de tu CSPRNG local. Para la mayoría de usos el CSPRNG local basta; para casos donde una tercera parte debe verificar la aleatoriedad de forma independiente, RANDOM.ORG ofrece certificados firmados de aleatoriedad como servicio de pago.

Muestreo sin reemplazo, el barajado de Fisher-Yates

Cuando necesitas N números únicos de un rango, sacar 6 números entre 1 y 49 para una lotería, escoger 10 ganadores entre 1.000 inscritos, el ingenuo «genera y descarta si se repite» funciona para N pequeños pero se degrada bruscamente cuando N se acerca al tamaño del rango (la probabilidad de sacar un número fresco baja a medida que el pool encoge). El algoritmo estándar es el barajado de Fisher-Yates, originario de las tablas estadísticas de Fisher y Yates de 1938 y formalizado en su forma moderna en informática por Donald Knuth en 1969 (a veces llamado Knuth shuffle). El algoritmo es absolutamente simple: escribe los números 1 a N en un array; para i de N-1 a 1, intercambia el elemento i con un elemento aleatorio entre 0 e i (inclusive); el array queda barajado uniformemente. Toma los primeros K elementos para K números aleatorios únicos. Detalle crucial: el índice aleatorio debe estar en [0, i], inclusive, usar [0, i-1] introduce un sesgo sutil que la comunidad criptográfica tardó años en caracterizar (la variante de Sattolo, a veces usada por error en lugar del verdadero Fisher-Yates). Para rangos muy grandes donde asignar un array con todos los N valores es impráctico (por ejemplo elegir 100 valores únicos entre 1 y 10⁹), el muestreo por reservorio (Vitter, 1985) maneja entradas en flujo o no acotadas en una sola pasada con memoria acotada.

Convenciones de lanzamientos de dados

Los generadores de números aleatorios son dados disfrazados. El D6 (dado de seis caras) es el predeterminado universal de los juegos de mesa, rango 1-6. El D20 (dado de veinte caras) es el dado icónico de Dungeons & Dragons usado para tiradas de habilidad, ataques y salvaciones, el sistema de modificadores de D&D hace que una sola tirada de D20 más un bono de stat decida la mayoría de las acciones. El D100 (porcentaje, 1-100) se usa para tiradas porcentuales en La Llamada de Cthulhu, Warhammer Roleplay y muchos sistemas de probabilidad de crítico. La notación NdM significa «lanzar N dados de M caras cada uno y sumar»; NdM+B añade un bono. 3d6 lanza tres dados de seis caras y suma (rango 3-18, el rango clásico de puntuaciones de habilidad de D&D, con una distribución triangular centrada en 10-11). Para una simulación justa, generar un entero uniforme en [1, M] para cada dado y sumar es exactamente equivalente a lanzar dados físicos, la distribución CSPRNG subyacente es más uniforme que cualquier dado físico que pudieras comprar. Casinos y juegos regulados usan RNG certificados que se prueban contra baterías estadísticas (BigCrush de TestU01, NIST SP 800-22) para demostrar uniformidad ante reguladores; los mismos estándares aplican a los RNG de lotería.

Semillas y reproducibilidad

Una propiedad sutil pero importante de los PRNG: son deterministas dada una semilla. Fija la semilla a un valor conocido y la secuencia de números «aleatorios» es exactamente reproducible. Esto es invaluable para pruebas (un test unitario que use datos aleatorios debería fijar una semilla para que los fallos sean reproducibles) y para sorteos verificables (publicar la semilla antes del sorteo, luego cualquiera puede verificar el resultado). El módulo random de Python tiene random.seed(value) para esto; Random de Java toma una semilla en el constructor. El Math.random() de JavaScript deliberadamente no expone una API de semilla, los motores tratan la semilla como estado interno, pero varias bibliotecas puramente JS (seedrandom, pcg-random) ofrecen PRNG con semilla. Los CSPRNG son distintos por diseño: no exponen semillas porque el sentido mismo es la imprevisibilidad. Si necesitas reproducibilidad, usa un PRNG con semilla explícita; si necesitas seguridad, usa un CSPRNG y asume que no podrás reproducir la secuencia más tarde.

Privacidad: por qué solo navegador, incluso para números aleatorios

Los números aleatorios en sí mismos rara vez contienen información sensible, entonces ¿por qué importa la arquitectura puramente de navegador? Dos razones. Primero, cuando un número aleatorio se usa como token de sesión, clave de idempotencia, desafío de autenticación o cualquier otro valor parecido a un secreto, generarlo en un servidor de terceros significa que ese servidor vio el valor antes que tú lo usaras, una exposición pequeña pero real. Segundo, los generadores del lado del servidor que prometen «aleatoriedad criptográfica» no pueden ser verificados por el usuario; un servidor con bug o malicioso podría devolver valores no aleatorios o sesgados que parezcan aleatorios, y no tendrías forma de detectar el sesgo sin un muestreo masivo. Un generador puramente de navegador ejecuta la misma llamada crypto.getRandomValues() que tu aplicación ejecutaría en el lado servidor; la entropía viene de la misma fuente del sistema operativo (Linux getrandom(), Windows BCryptGenRandom, macOS); ninguna tercera parte ve la salida. Puedes verificar abriendo la pestaña Network de las DevTools mientras pulsas Generar, no hay solicitudes salientes. Pon la página en modo avión después de que cargue y el generador sigue funcionando.

Preguntas frecuentes