La generación de números aleatorios es un proceso mediante el cual, a menudo por medio de un generador de números aleatorios ( RNG ), se genera una secuencia de números o símbolos que no se puede predecir razonablemente mejor que por casualidad . Esto significa que la secuencia de resultados particular contendrá algunos patrones detectables en retrospectiva pero imposibles de prever. Los verdaderos generadores de números aleatorios 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 estaría en contraste con las llamadas "generaciones de números aleatorios" realizadas por generadores de números pseudoaleatorios (PRNG), que generan números que solo parecen aleatorios pero que, de hecho, están predeterminados; estas generaciones se pueden reproducir simplemente conociendo el estado del PRNG. [1]
Diversas aplicaciones de la aleatoriedad han llevado al desarrollo de diferentes métodos para generar datos aleatorios . Algunos de ellos han existido desde la antigüedad, incluyendo ejemplos bien conocidos como el lanzamiento de dados , el lanzamiento de monedas , el barajado de naipes , el uso de tallos de milenrama (para adivinación ) en el I Ching , así como innumerables otras técnicas. Debido a la naturaleza mecánica de estas técnicas, generar grandes cantidades de números suficientemente aleatorios (importantes en estadística) requería mucho trabajo y tiempo. Por lo tanto, los resultados a veces se recopilaban y distribuían como tablas de números aleatorios .
Existen varios métodos computacionales para la generación de números pseudoaleatorios. Ninguno de ellos alcanza el objetivo de la aleatoriedad verdadera, aunque pueden cumplir, con éxito variable, 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 inutilizables para aplicaciones como la criptografía . Sin embargo, también existen generadores de números pseudoaleatorios criptográficamente seguros (CSPRNGS) cuidadosamente diseñados , con características especiales diseñadas específicamente para su uso en criptografía.
Los generadores de números aleatorios tienen aplicaciones en juegos de azar , muestreo estadístico , simulación por ordenador , criptografía , diseño completamente aleatorio y otras áreas en las que es deseable producir un resultado impredecible. En general, en aplicaciones que tienen la imprevisibilidad como característica primordial, como en aplicaciones de seguridad, los generadores de hardware suelen preferirse a los algoritmos pseudoaleatorios, cuando sea factible.
Los generadores de números pseudoaleatorios son muy útiles para desarrollar simulaciones con el método Monte Carlo , ya que la depuración se ve facilitada por la capacidad de ejecutar nuevamente la misma secuencia de números aleatorios a partir de la misma semilla aleatoria . También se utilizan en criptografía, siempre que la semilla sea secreta. El emisor y el receptor pueden generar automáticamente el mismo conjunto de números para usarlos 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 grado muy alto de aleatoriedad aparente , muchas otras operaciones solo necesitan una cantidad modesta de imprevisibilidad. Algunos ejemplos simples podrían ser presentarle a un usuario una "cita aleatoria del día" o determinar en qué dirección se moverá un adversario controlado por computadora en un juego de computadora. Las formas más débiles de aleatoriedad se utilizan en algoritmos hash y en la creación de algoritmos de búsqueda y ordenación amortizados .
Algunas aplicaciones que a primera vista parecen adecuadas para la aleatorización en realidad no son tan simples. Por ejemplo, un sistema que selecciona pistas musicales "aleatoriamente" para un sistema de música de fondo debe ser aleatorio en apariencia , e incluso puede tener formas de controlar la selección de música: un sistema verdaderamente aleatorio no tendría ninguna restricción sobre la aparición del mismo elemento dos o tres veces seguidas.
Existen dos métodos principales que se utilizan 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 los posibles sesgos en el proceso de medición. Entre las fuentes de datos se 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 cósmica de fondo o la desintegración radiactiva, medidas en escalas de tiempo cortas, representan fuentes de entropía natural (como medida de la imprevisibilidad 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 midan. Por lo tanto, se dice que las fuentes de entropía "verdadera" que se producen de forma natural son bloqueantes : tienen una velocidad limitada hasta que se obtiene suficiente entropía para satisfacer la demanda. En algunos sistemas tipo Unix, incluidas la mayoría de las distribuciones de Linux , el archivo de pseudodispositivo /dev/random se bloqueará hasta que se obtenga suficiente entropía del entorno. [2] Debido a este comportamiento de bloqueo, las lecturas masivas de gran tamaño de /dev/random , como llenar una unidad de disco duro con bits aleatorios, a menudo pueden ser lentas en sistemas que utilizan este tipo de fuente de entropía.
El segundo método utiliza algoritmos computacionales que pueden producir secuencias largas de resultados aparentemente aleatorios, que en realidad están completamente determinados por un valor inicial más corto, conocido como valor semilla o clave . Como resultado, toda la secuencia aparentemente aleatoria se puede reproducir si se conoce el valor semilla. Este tipo de generador de números aleatorios a menudo se denomina generador de números pseudoaleatorios . Este tipo de generador normalmente no depende de fuentes de entropía de origen natural, aunque puede ser sembrado periódicamente por fuentes naturales. Este tipo de generador no es bloqueante, por lo que no está limitado en velocidad por un evento externo, lo que hace posible las lecturas masivas de gran tamaño.
Algunos sistemas adoptan un enfoque híbrido, que proporciona aleatoriedad extraída de fuentes naturales cuando está disponible y recurre a generadores de números pseudoaleatorios criptográficamente seguros (CSPRNG) basados en software que se renuevan periódicamente. El recurso alternativo se produce cuando la tasa de lectura de aleatoriedad deseada supera la capacidad del enfoque de recolección natural para satisfacer la demanda. Este enfoque evita el comportamiento de bloqueo limitado por la velocidad de los generadores de números aleatorios basados en métodos más lentos y puramente ambientales.
Si bien un generador de números pseudoaleatorios basado únicamente en lógica determinista nunca puede considerarse una fuente de números aleatorios "verdadera" en el sentido más puro de la palabra, en la práctica generalmente son suficientes incluso para aplicaciones críticas de seguridad exigentes. Los generadores de números pseudoaleatorios cuidadosamente diseñados e implementados pueden certificarse para fines criptográficos críticos de seguridad, como es el caso del algoritmo 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 . [ dudoso – discutir ] [3]
Los primeros métodos para generar números aleatorios, como los dados, el lanzamiento de monedas y la ruleta, todavía 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 cuya imprevisibilidad se puede rastrear hasta las leyes de la mecánica cuántica . [4] [5] Las fuentes de entropía incluyen la desintegración radiactiva , el ruido térmico , el ruido de disparo , el ruido de avalancha en los diodos Zener , la deriva del reloj , la sincronización de los movimientos reales de un cabezal de lectura-escritura de un 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 uniformemente aleatorios. Un extractor de aleatoriedad , como una función hash criptográfica , se puede utilizar para aproximarse a una distribución uniforme de bits de una fuente no uniformemente aleatoria, aunque a una tasa de bits más baja.
La aparición de fuentes de entropía fotónica de banda ancha, como el caos óptico y el ruido de emisión espontánea amplificado , contribuye en gran medida al desarrollo del generador físico de números aleatorios. Entre ellos, el caos óptico [6] [7] tiene un alto potencial para producir físicamente números aleatorios de alta velocidad debido a su gran ancho de banda y gran amplitud. En 2013 se construyó un prototipo de un generador físico de bits aleatorios de alta velocidad y en tiempo real basado en un láser caótico. [8]
Se han ideado varias formas imaginativas de recopilar esta información entrópica. Una técnica consiste en ejecutar una función hash contra un fotograma de una secuencia de vídeo procedente de una fuente impredecible. Lavarand utilizó esta técnica con imágenes de varias lámparas de lava . HotBits midió la desintegración radiactiva con tubos Geiger-Muller [9] , mientras que Random.org utiliza variaciones en la amplitud del ruido atmosférico registrado con una radio normal.
Otra fuente común de entropía es el comportamiento de los usuarios humanos del sistema. Si bien no se considera que las personas sean buenos generadores de aleatoriedad cuando se les solicita, generan un comportamiento aleatorio bastante bueno en el contexto de los juegos de estrategia mixta . [10] Algunos programas informáticos relacionados con la seguridad requieren que el usuario realice una larga serie de movimientos del ratón o entradas del teclado para crear la entropía suficiente necesaria para generar claves aleatorias o para inicializar generadores de números pseudoaleatorios. [11]
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 la memoria crece sin límite). Estos números aleatorios son buenos 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. [12] La serie de valores generados por tales algoritmos generalmente está determinada por un número fijo llamado semilla . Uno de los PRNG más comunes es el generador congruencial lineal , que utiliza la recurrencia
para generar números, donde a , b y m son números enteros grandes, y es el siguiente en X como una serie de números pseudoaleatorios. El número máximo de números que la fórmula puede producir 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 . [13] Para evitar ciertas propiedades no aleatorias de un solo generador congruencial lineal, se pueden usar varios generadores de números aleatorios de este tipo con valores ligeramente diferentes del coeficiente multiplicador, a , en paralelo, con un generador de números aleatorios "maestro" que selecciona entre los varios generadores diferentes.
Un método sencillo de lápiz y papel para generar números aleatorios es el llamado método del cuadrado medio sugerido por John von Neumann . Si bien es fácil de implementar, su resultado es de mala calidad. Tiene un período muy corto y graves debilidades, como que la secuencia de resultados casi siempre converge a cero. Una innovación reciente es combinar el cuadrado medio con una secuencia de Weyl . Este método produce resultados de alta calidad a lo largo de un largo período. [14]
La mayoría de los lenguajes de programación informática incluyen funciones o rutinas de biblioteca que proporcionan generadores de números aleatorios. Suelen estar diseñados para proporcionar un byte o una palabra aleatorios, o un número de punto flotante distribuido uniformemente entre 0 y 1.
La calidad, es decir, la aleatoriedad de estas funciones de biblioteca varía ampliamente, desde una salida completamente predecible hasta criptográficamente segura. El generador de números aleatorios predeterminado en muchos lenguajes, incluidos Python, Ruby, R, IDL y PHP, se basa en el algoritmo Mersenne Twister y no es suficiente para fines criptográficos, como se indica explícitamente en la documentación del lenguaje. Estas funciones de biblioteca a menudo tienen propiedades estadísticas deficientes y algunas repetirán patrones después de solo decenas de miles de ensayos. A menudo se inicializan utilizando el reloj de tiempo real de una computadora como semilla, ya que dicho 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, videojuegos), pero no son adecuadas donde se requiere aleatoriedad de alta calidad, como en aplicaciones criptográficas o estadísticas. [15]
Existen fuentes de números aleatorios de mucha mayor calidad en la mayoría de los sistemas operativos; por ejemplo , /dev/random en varias versiones de BSD, Linux, Mac OS X, IRIX y Solaris, o CryptGenRandom para Microsoft Windows. La mayoría de los lenguajes de programación, incluidos los mencionados anteriormente, proporcionan un medio para acceder a estas fuentes de mayor calidad.
La generación de números aleatorios también puede ser realizada por humanos, en forma de recopilación de diversas entradas de usuarios finales y su uso como fuente de aleatorización. Sin embargo, la mayoría de los estudios encuentran que los sujetos humanos tienen cierto grado de no aleatoriedad cuando intentan producir una secuencia aleatoria de, por ejemplo, dígitos o letras. Pueden alternar demasiado entre opciones en comparación con un buen generador aleatorio; [16] por lo tanto, este enfoque no se usa ampliamente. Sin embargo, por la misma razón que los humanos tienen un desempeño deficiente en esta tarea, la generación de números aleatorios humanos puede usarse como una herramienta para obtener información sobre funciones cerebrales a las que de otra manera no se podría acceder. [17]
Incluso si se cuenta con una fuente de números aleatorios plausibles (quizás de un generador de hardware basado en la mecánica cuántica), obtener números que sean completamente imparciales 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.
Los números aleatorios generados a veces se someten a pruebas estadísticas antes de su uso para garantizar que la fuente subyacente aún funciona, y luego se posprocesan para mejorar sus propiedades estadísticas. Un ejemplo sería el generador de números aleatorios de hardware TRNG9803 [18] , que utiliza una medición de entropía como prueba de hardware y luego posprocesa la secuencia aleatoria con un cifrado de flujo de registro de desplazamiento. Generalmente es difícil utilizar pruebas estadísticas para validar los números aleatorios generados. Wang y Nicol [19] propusieron una técnica de prueba estadística basada en la distancia que se utiliza para identificar las debilidades de varios generadores aleatorios. Li y Wang [20] propusieron un método para probar números aleatorios basado en fuentes de entropía caótica láser utilizando propiedades de movimiento browniano.
También se utilizan pruebas estadísticas para dar confianza en que el resultado final posprocesado de un generador de números aleatorios es verdaderamente imparcial; se están desarrollando numerosos conjuntos de pruebas de aleatoriedad .
La mayoría de los generadores de números aleatorios funcionan de forma nativa con números enteros o bits individuales, por lo que se requiere un paso adicional para llegar a la distribución uniforme "canónica" entre 0 y 1. La implementación no es tan trivial como dividir el número entero por su valor máximo posible. En concreto: [21] [22]
El algoritmo principal, utilizado por OpenJDK , Rust y NumPy , se describe en una propuesta para el STL de C++ . No utiliza la precisión adicional y sufre de sesgo solo en el último bit debido al redondeo a par. [23] Se justifican otras preocupaciones numéricas al cambiar esta distribución uniforme "canónica" a un rango diferente. [24] Un método propuesto para el lenguaje de programación Swift afirma utilizar la precisión completa en todas partes. [25]
Los números enteros distribuidos uniformemente se utilizan habitualmente en algoritmos como el shuffle de Fisher-Yates . Nuevamente, una implementación ingenua puede inducir un sesgo de módulo en el resultado, por lo que se deben utilizar algoritmos más complejos. En 2018, Daniel Lemire describió un método que casi nunca realiza divisiones [26] , y el estado actual de la técnica es el "algoritmo óptimo" de 2021 inspirado en la codificación aritmética de Stephen Canon de Apple Inc. [27].
La mayoría de los RNG de 0 a 1 incluyen 0 pero excluyen 1, mientras que otros incluyen o excluyen ambos.
Dada una fuente de números aleatorios uniformes, existen un par de métodos para crear una nueva fuente aleatoria que corresponda a una función de densidad de probabilidad . Un método llamado método de inversión , implica la integración hasta un área mayor o igual que el número aleatorio (que debe generarse entre 0 y 1 para distribuciones adecuadas). Un segundo método llamado método de aceptación-rechazo , implica elegir un valor x e y y probar si la función de x es mayor que el valor y. Si lo es, se acepta el valor x. De lo contrario, se rechaza el valor x y el algoritmo vuelve a intentarlo. [28] [29]
Como ejemplo de muestreo de rechazo, para generar un par de números aleatorios distribuidos normalmente estándar estadísticamente independientes ( x , y ), primero se pueden generar las coordenadas polares ( r , θ ), donde r 2 ~ χ 2 2 y θ ~ UNIFORME(0,2π) (ver transformada de Box-Muller ).
Las salidas de varios RNG independientes se pueden combinar (por ejemplo, mediante una operación XOR bit a bit ) para proporcionar un RNG combinado que sea al menos tan bueno como el mejor RNG utilizado. Esto se conoce como blanqueamiento de software .
Los generadores de números aleatorios computacionales y de hardware a veces se combinan para reflejar los beneficios de ambos tipos. Los generadores de números aleatorios computacionales pueden generar números pseudoaleatorios mucho más rápido que los generadores físicos, mientras que los generadores físicos pueden generar "aleatoriedad real".
Algunos cálculos que utilizan un generador de números aleatorios pueden resumirse como el cálculo de un valor total o promedio, como el cálculo de integrales mediante el método de Monte Carlo . Para tales problemas, puede ser posible encontrar una solución más precisa mediante el uso de las denominadas secuencias de baja discrepancia , también llamadas números cuasialeatorios . Dichas secuencias tienen un patrón definido que llena los espacios de manera uniforme, cualitativamente hablando; una secuencia verdaderamente aleatoria puede dejar espacios más grandes, y generalmente lo hace.
Los siguientes sitios ponen a disposición muestras de números aleatorios:
Dado que gran parte de la criptografía depende de un generador de números aleatorios criptográficamente seguro para la generación de claves y nonce criptográficos , si un generador de números aleatorios se puede hacer predecible, un atacante puede usarlo como puerta trasera para romper el cifrado.
Se informa que la NSA ha insertado una puerta trasera en el generador de números pseudoaleatorios criptográficamente seguro certificado por el NIST Dual EC DRBG . Si, por ejemplo, se crea una conexión SSL utilizando este generador de números aleatorios, entonces, según Matthew Green, permitiría a la NSA determinar el estado del generador de números aleatorios y, por lo tanto, eventualmente poder leer todos los datos enviados a través de la conexión SSL. [30] Aunque era evidente que Dual_EC_DRBG era un generador de números pseudoaleatorios muy pobre y posiblemente con puerta trasera mucho antes de que se confirmara la puerta trasera de la NSA en 2013, había tenido un uso significativo en la práctica hasta 2013, por ejemplo, por parte de la destacada empresa de seguridad RSA Security . [31] Posteriormente ha habido acusaciones de que RSA Security insertó a sabiendas una puerta trasera de la NSA en sus productos, posiblemente como parte del programa Bullrun . RSA ha negado haber insertado a sabiendas una puerta trasera en sus productos. [32]
También se ha teorizado que los RNG de hardware podrían modificarse en secreto para que tengan menos entropía que la indicada, lo que haría que el cifrado que utiliza el RNG de hardware sea susceptible a ataques. Uno de esos métodos que se ha publicado funciona modificando la máscara de dopante del chip, que sería indetectable para la ingeniería inversa óptica. [33] Por ejemplo, para la generación de números aleatorios en Linux, se considera inaceptable utilizar el RNG de hardware RDRAND de Intel sin mezclar la salida de RDRAND con otras fuentes de entropía para contrarrestar cualquier puerta trasera en el RNG de hardware, especialmente después de la revelación del programa Bullrun de la NSA. [34] [35]
En 2010, un sorteo de lotería estadounidense fue manipulado por el director de seguridad informática de la Asociación de Lotería Multiestatal (MUSL), quien instaló subrepticiamente un malware de puerta trasera en la computadora RNG segura de la MUSL durante el mantenimiento de rutina. [36] Durante los ataques, el hombre ganó una cantidad total de $16.500.000 a lo largo de varios años.
