Generación de números aleatorios - Enciclopedia

La generación de números aleatorios es un proceso mediante el cual, a menudo mediante un generador de números aleatorios (RNG), se genera una secuencia de números o símbolos que no puede predecirse razonablemente mejor de lo que lo haría el azar. Esto significa que la secuencia de resultados particular contendrá algunos patrones detectables a posteriori pero imposibles de prever. Los generadores de números aleatorios verdaderos pueden ser generadores de números aleatorios de hardware (HRNG), en los que cada generación es una función del valor actual de un atributo del entorno físico que cambia constantemente de una manera que es prácticamente imposible de modelar. Esto sería en contraste con lo que se conoce como "generaciones de números aleatorios" realizadas por generadores de números pseudoaleatorios (PRNG), que generan números que solo parecen aleatorios pero que en realidad son predeterminados; estas generaciones pueden reproducirse simplemente conociendo el estado del PRNG.

Diversas aplicaciones de la aleatoriedad han llevado al desarrollo de diferentes métodos para generar datos aleatorios. Algunos de estos han existido desde la antigüedad, incluyendo ejemplos bien conocidos como el lanzamiento de dados, la lanzada de monedas, el barajado de cartas, el uso de tallos de yarrow (para la adivinación) en el I Ching, así como innumerables otras técnicas. Debido a la naturaleza mecánica de estas técnicas, la generación de grandes cantidades de números aleatorios suficientemente aleatorios (importante en la estadística) requería mucho trabajo y tiempo. Por lo tanto, a veces se recopilarían y distribuirían como tablas de números aleatorios.

Existen varios métodos computacionales para la generación de números pseudoaleatorios. Todos están por debajo del objetivo de la verdadera aleatoriedad, aunque pueden cumplir, con diferentes grados de éxito, algunas de las pruebas estadísticas de aleatoriedad destinadas a medir cuán impredecibles son sus resultados (es decir, hasta qué punto sus patrones son discernibles). Esto generalmente los hace inusables para aplicaciones como la criptografía. Sin embargo, también existen generadores de números pseudoaleatorios diseñados con características específicas para su uso en criptografía, conocidos como generadores de números pseudoaleatorios criptográficamente seguros (CSPRNG).

Aplicaciones y usos prácticos

Los generadores de números aleatorios tienen aplicaciones en el juego, la muestreo estadístico, la simulación por computadora, la criptografía, el diseño completamente aleatorio y otras áreas donde se desea producir un resultado impredecible. En general, en aplicaciones donde la impredecibilidad es la característica principal, como en aplicaciones de seguridad, los generadores de hardware son generalmente preferidos sobre los algoritmos pseudoaleatorios, siempre que sea posible.

Los generadores de números pseudoaleatorios son muy útiles en el desarrollo de simulaciones del método de Monte Carlo, ya que la depuración se facilita por la capacidad de ejecutar de nuevo la misma secuencia de números aleatorios mediante el inicio desde la misma semilla aleatoria. También se utilizan en la criptografía, siempre que la semilla sea secreta. El emisor y el receptor pueden generar el mismo conjunto de números automáticamente para usar como claves.

La generación de números pseudoaleatorios es una tarea importante y común en la programación informática. Mientras que la criptografía y ciertos algoritmos numéricos requieren un alto grado de aparente aleatoriedad, muchas otras operaciones solo necesitan una cantidad modesta de impredecibilidad. Algunos ejemplos podrían ser presentar al usuario un "citado del día aleatorio" o determinar hacia qué dirección se moverá un adversario controlado por la computadora en un juego. Formas más débiles de aleatoriedad se utilizan en algoritmos de hash y en la creación de algoritmos de búsqueda y ordenamiento amortizados.

Algunas aplicaciones que a primera vista parecen adecuadas para la aleatoriedad no son tan simples. Por ejemplo, un sistema que "elige aleatoriamente" pistas musicales para un sistema de música de fondo debe solo parecer aleatorio y puede incluso tener formas de controlar la selección de música: un sistema verdaderamente aleatorio no tendría restricciones sobre que el mismo elemento aparezca dos o tres veces consecutivamente.

Números verdaderos vs. números pseudoaleatorios

Existen dos métodos principales utilizados para generar números aleatorios. El primer método mide algún fenómeno físico que se espera que sea aleatorio y luego compensa las posibles desviaciones en el proceso de medición. Ejemplos de fuentes incluyen la medición del ruido atmosférico, el ruido térmico y otros fenómenos electromagnéticos y cuánticos externos. Por ejemplo, la radiación de fondo cósmico o la descomposición radiactiva medida a escalas cortas representan fuentes de entropía natural (como una medida de la impredecibilidad o sorpresa del proceso de generación de números).

La velocidad a la que se puede obtener entropía de fuentes naturales depende de los fenómenos físicos subyacentes que se miden. Por lo tanto, las fuentes de entropía naturalmente ocurrida se dicen que son bloqueantes; son limitadas por velocidad hasta que se recoge suficiente entropía para satisfacer la demanda. En algunos sistemas Unix-like, incluyendo la mayoría de las distribuciones de Linux, el archivo de dispositivo /dev/random se bloqueará hasta que se reciba suficiente entropía del entorno. Debido a este comportamiento de bloqueo, las lecturas en grandes volúmenes de /dev/random, como llenar un disco duro con bits aleatorios, a menudo son lentas en sistemas que utilizan este tipo de fuente de entropía.

El segundo método utiliza algoritmos computacionales que pueden producir largas secuencias de resultados aparentemente aleatorios, que en realidad están completamente determinados por un valor inicial más corto, conocido como valor de semilla o clave. Como resultado, toda la secuencia aparentemente aleatoria puede reproducirse si se conoce el valor de la semilla. Este tipo de generador de números aleatorios se conoce a menudo como generador de números pseudoaleatorios. Este tipo de generador generalmente no depende de fuentes de entropía naturalmente ocurrida, aunque puede ser resembrado periódicamente por fuentes naturales. Este tipo de generador es no bloqueante, por lo que no está limitado por un evento externo, lo que hace posible las lecturas en grandes volúmenes.

Algunos sistemas adoptan un enfoque híbrido, proporcionando aleatoriedad cosechada de fuentes naturales cuando está disponible, y recayendo en generadores de números pseudoaleatorios criptográficamente seguros (CSPRNG) basados en software, resembrados periódicamente. La recayada ocurre cuando la velocidad de lectura deseada de la aleatoriedad excede la capacidad del enfoque de cosecha natural para mantener el ritmo. Este enfoque evita el comportamiento de bloqueo limitado por velocidad de los generadores de números aleatorios basados en métodos más lentos y puramente ambientales.

Aunque un generador de números pseudoaleatorios basado únicamente en lógica determinista nunca puede considerarse una fuente de números aleatorios verdaderos en el sentido más puro de la palabra, en la práctica son generalmente suficientes incluso para aplicaciones críticas de seguridad. Los generadores de números pseudoaleatorios diseñados y implementados con cuidado pueden certificarse para propósitos criptográficos críticos, como es el caso de los algoritmos yarrow y fortuna. El primero es la base de la fuente de entropía /dev/random en FreeBSD, AIX, macOS, NetBSD y otros. OpenBSD utiliza un algoritmo de números pseudoaleatorios conocido como arc4random.

Métodos de generación


= Métodos físicos =

Los primeros métodos para generar números aleatorios, como los dados, el lanzamiento de monedas y las ruletas, aún se utilizan hoy en día, principalmente en juegos y apuestas, ya que tienden a ser demasiado lentos para la mayoría de las aplicaciones en estadística y criptografía.

Un generador de números aleatorios de hardware puede basarse en un fenómeno físico atómico o subatómico esencialmente aleatorio cuyo impredecible puede rastrearse a las leyes de la mecánica cuántica. Las fuentes de entropía incluyen descomposición radiactiva, ruido térmico, ruido de disparo, ruido de avalancha en diodos Zener, desviación de reloj, el tiempo de los movimientos reales de la cabeza de lectura/escritura del disco duro y el ruido de radio. Sin embargo, los fenómenos físicos y las herramientas utilizadas para medirlos generalmente presentan asimetrías y sesgos sistemáticos que hacen que sus resultados no sean aleatorios uniformemente. Un extractor de aleatoriedad, como una función de hash criptográfica, puede utilizarse para acercarse a una distribución uniforme de bits desde una fuente no uniformemente aleatoria, aunque a una tasa de bits más baja.

El surgimiento de fuentes de entropía fotónica de banda ancha, como el caos óptico y el ruido de emisión espontánea amplificado, ha ayudado enormemente en el desarrollo del generador de números aleatorios físico. Entre ellos, el caos óptico tiene un gran potencial para producir números aleatorios a alta velocidad debido a su alta banda y gran amplitud. En 2013 se construyó un prototipo de un generador de bits aleatorios de alta velocidad y en tiempo real basado en un láser caótico.

Se han ideado varias formas imaginativas de recopilar esta información entropica. Una técnica es ejecutar una función de hash contra un cuadro de un flujo de video de una fuente impredecible. Lavarand utilizó esta técnica con imágenes de varios lava lamps. HotBits medía la descomposición radiactiva con tubos Geiger-Müller, mientras que Random.org utiliza las variaciones en la amplitud del ruido atmosférico registrado con un radio normal.

Otra fuente común de entropía es el comportamiento de los usuarios del sistema. Aunque las personas no se consideran buenas generadoras de números aleatorios a petición, generan un comportamiento aleatorio bastante bien en el contexto de los juegos de estrategia mixta. Algunos software relacionados con la seguridad requieren que el usuario realice una serie larga de movimientos del ratón o entradas del teclado para crear suficiente entropía necesaria para generar claves aleatorias o para inicializar generadores de números pseudoaleatorios.


= Métodos computacionales =

La mayoría de los números aleatorios generados por computadora utilizan PRNG, que son algoritmos que pueden crear automáticamente largas series de números con buenas propiedades aleatorias, pero eventualmente la secuencia se repite (o el uso de memoria aumenta sin límite). Estos números aleatorios son adecuados en muchas situaciones, pero no son tan aleatorios como los números generados a partir del ruido atmosférico electromagnético utilizado como fuente de entropía. La serie de valores generados por estos algoritmos está determinada por un número fijo llamado semilla. Uno de los PRNG más comunes es el generador lineal congruencial, que utiliza la recurrencia

X
n
+
1
=
(
a
X
n
+
b
)
mod
m

para generar números, donde a, b y m son enteros grandes, y

X
n
+
1

es el siguiente en X como una serie de números pseudoaleatorios. El número máximo de números que puede producir la fórmula es el módulo, m. La relación de recurrencia se puede extender a matrices para tener períodos mucho más largos y mejores propiedades estadísticas.

Para evitar ciertas propiedades no aleatorias de un generador lineal congruencial único, se pueden utilizar varios generadores de números aleatorios con valores ligeramente diferentes del coeficiente multiplicador, a, en paralelo, con un generador de números aleatorios maestro que selecciona entre varios generadores diferentes.

Un método simple de papel y lápiz para generar números aleatorios es el llamado método del cuadrado central sugerido por John von Neumann. Aunque es fácil de implementar, su salida es de baja calidad. Tiene un período muy corto y graves debilidades, como que la secuencia de salida casi siempre converge a cero. Una innovación reciente es combinar el cuadrado central con una secuencia de Weyl. Este método produce una salida de alta calidad a través de un período largo.

La mayoría de los lenguajes de programación informática incluyen funciones o rutinas de biblioteca que proporcionan generadores de números aleatorios. A menudo están diseñados para proporcionar un byte o palabra aleatoria, o un número de coma flotante distribuido uniformemente entre 0 y 1. La calidad, es decir, la aleatoriedad, de estas funciones de biblioteca varía mucho, desde una salida completamente predecible hasta la criptográficamente segura. El generador de números aleatorios predeterminado en muchos lenguajes, incluyendo Python, Ruby, R, IDL y PHP, se basa en el algoritmo Mersenne Twister y no es suficiente para propósitos criptográficos, como se indica explícitamente en la documentación del lenguaje. Estas funciones de biblioteca a menudo tienen propiedades estadísticas pobres y algunas repetirán patrones después de solo decenas de miles de pruebas. A menudo se inicializan utilizando el reloj de tiempo real de la computadora como la semilla, ya que este reloj es de 64 bits y mide en nanosegundos, mucho más allá de la precisión de la persona. Estas funciones pueden proporcionar suficiente aleatoriedad para ciertas tareas (por ejemplo, juegos de video) pero no son adecuadas donde se requiere una alta calidad de aleatoriedad, como en aplicaciones criptográficas o estadísticas.

Hay fuentes de números aleatorios de mayor calidad disponibles en la mayoría de los sistemas operativos; por ejemplo, /dev/random en varias variedades de BSD, Linux, Mac OS X, IRIX y Solaris, o CryptGenRandom para Microsoft Windows. La mayoría de los lenguajes de programación, incluyendo los mencionados anteriormente, proporcionan un medio para acceder a estas fuentes de alta calidad.

= Por humanos =

La generación de números aleatorios también puede realizarse por humanos, en la forma de recopilar varias entradas de los usuarios finales y utilizarlas como fuente de aleatoriedad. Sin embargo, la mayoría de los estudios encuentran que los sujetos humanos tienen algún grado de no aleatoriedad cuando intentan producir una secuencia aleatoria de, por ejemplo, dígitos o letras. Pueden alternar demasiado entre las opciones en comparación con un generador de números aleatorios bueno; por lo tanto, este enfoque no se utiliza ampliamente. Sin embargo, por la misma razón por la que los humanos se desempeñan mal en esta tarea, la generación de números aleatorios por humanos puede utilizarse como herramienta para obtener conocimientos sobre las funciones cerebrales de otro modo inaccesibles.


Post-procesamiento y pruebas estadísticas

Incluso dada una fuente plausible de números aleatorios (tal vez de un generador de hardware basado en mecánica cuántica), obtener números completamente no sesgados requiere cuidado. Además, el comportamiento de estos generadores a menudo cambia con la temperatura, el voltaje de la fuente de alimentación, la edad del dispositivo u otras interferencias externas.

A veces se someten los números aleatorios generados a pruebas estadísticas antes de su uso para asegurarse de que la fuente subyacente aún funciona y luego se realizan operaciones posteriores para mejorar sus propiedades estadísticas. Un ejemplo sería el generador de números aleatorios de hardware TRNG9803, que utiliza una medición de entropía como prueba de hardware y luego realiza un post-procesamiento de la secuencia aleatoria con un