Generador de números pseudoaleatorios

Un generador de números pseudoaleatorios ( PRNG ), también conocido como generador de bits aleatorios determinista ( DRBG ), ^{[ 1 ]} es un algoritmo para generar una secuencia de números cuyas propiedades se aproximan a las de secuencias de números aleatorios . La secuencia generada por el PRNG no es verdaderamente aleatoria , ya que está completamente determinada por un valor o estado inicial, generalmente llamado semilla del PRNG (que puede basarse en valores verdaderamente aleatorios). Si bien se pueden generar secuencias más cercanas a la aleatoriedad utilizando generadores de números aleatorios por hardware , los generadores de números pseudoaleatorios son importantes en la práctica por su velocidad de generación de números y su reproducibilidad. ^{[ 2 ]}

Los generadores de números pseudoaleatorios (PRNG) son fundamentales en aplicaciones como simulaciones (por ejemplo, para el método de Monte Carlo ), juegos electrónicos (por ejemplo, para la generación procedimental ) y criptografía . Las aplicaciones criptográficas requieren que el resultado no sea predecible a partir de resultados anteriores, y se necesitan algoritmos más elaborados que no hereden la linealidad de los PRNG más simples.

Las propiedades estadísticas adecuadas son un requisito fundamental para la salida de un generador de números pseudoaleatorios (GNA). Se requiere un análisis matemático cuidadoso para tener una confianza razonable en que un GNA genere números suficientemente cercanos a la aleatoriedad para el uso previsto. John von Neumann advirtió sobre la posible interpretación errónea de un GNA como un generador verdaderamente aleatorio, bromeando con que «cualquiera que considere métodos aritméticos para producir dígitos aleatorios está, por supuesto, en estado de pecado». ^{[ 3 ]}

En la práctica, la salida de muchos generadores de números pseudoaleatorios comunes presenta artefactos que provocan que fallen en las pruebas estadísticas de detección de patrones. Estos incluyen:

• Períodos más cortos de lo esperado para algunos estados semilla (dichos estados semilla pueden denominarse "débiles" en este contexto);
• Falta de uniformidad en la distribución de grandes cantidades de números generados;
• Correlación de valores sucesivos;
• Distribución dimensional deficiente de la secuencia de salida;
• Las distancias entre los puntos donde aparecen ciertos valores se distribuyen de forma diferente a las de una distribución de secuencia aleatoria.

Los defectos que presentan los generadores de números pseudoaleatorios defectuosos van desde imperceptibles (e incluso desconocidos) hasta muy evidentes. Un ejemplo fue el algoritmo de números aleatorios RANDU, utilizado durante décadas en ordenadores centrales . Tenía graves fallos, pero su deficiencia pasó desapercibida durante mucho tiempo.

En muchos campos, los trabajos de investigación anteriores al siglo XXI que se basaban en la selección aleatoria o en simulaciones de Monte Carlo , o que de alguna otra manera dependían de generadores de números pseudoaleatorios (GPR), eran mucho menos fiables de lo ideal debido al uso de GPR de baja calidad. ^{[ 4 ]} Incluso hoy en día, a veces se requiere precaución, como lo ilustra la siguiente advertencia en la Enciclopedia Internacional de Ciencias Estadísticas (2010). ^{[ 5 ]}

La lista de generadores ampliamente utilizados que deberían descartarse es mucho más larga [que la lista de buenos generadores]. No confíe ciegamente en los proveedores de software. Verifique el generador de números aleatorios predeterminado de su software favorito y esté preparado para reemplazarlo si es necesario. Esta última recomendación se ha repetido una y otra vez durante los últimos 40 años. Sorprendentemente, sigue siendo tan relevante hoy como lo era hace 40 años.

Como ejemplo, consideremos el lenguaje de programación ampliamente utilizado Java . Hasta 2020, Java todavía dependía de un generador congruencial lineal (LCG) para su PRNG, ^{[ 6 ] [ 7 ]} que es de baja calidad (ver más adelante). El soporte de Java se actualizó con Java 17 .

Un generador de números pseudoaleatorios (PRNG) conocido por evitar problemas importantes y funcionar con relativa rapidez es el Mersenne Twister (que se describe más adelante), publicado en 1998. Otros PRNG de mayor calidad, tanto en términos de rendimiento computacional como estadístico, se desarrollaron antes y después de esta fecha; estos se pueden consultar en la Lista de generadores de números pseudoaleatorios .

En la segunda mitad del siglo XX, la clase estándar de algoritmos utilizados para los generadores de números pseudoaleatorios (PRNG) comprendía generadores congruenciales lineales ( LCG ). Se sabía que la calidad de los LCG era inadecuada, pero no se disponía de mejores métodos. Press et  al. (2007) describieron el resultado así: «Si todos los artículos científicos cuyos resultados son dudosos debido a [LCG y relacionados] desaparecieran de las estanterías de las bibliotecas, habría un hueco en cada estantería del tamaño de un puño». ^{[ 8 ]}

Un avance importante en la construcción de generadores pseudoaleatorios fue la introducción de técnicas basadas en recurrencias lineales en el campo de dos elementos; dichos generadores están relacionados con los registros de desplazamiento de retroalimentación lineal .

La invención del Mersenne Twister en 1997 , ^{[ 9 ]} en particular, evitó muchos de los problemas de los generadores anteriores. El Mersenne Twister tiene un período de 2 ^{19  937}  −  1 iteraciones (≈  4,3 × 10⁶⁰⁰¹ ), se ha demostrado que está equidistribuido en (hasta) 623 dimensiones (para valores de 32 bits) y, en el momento de su introducción, funcionaba más rápido que otros generadores estadísticamente razonables.

En 2003, George Marsaglia introdujo la familia de generadores xorshift , ^{[ 10 ]} nuevamente basados ​​en una recurrencia lineal. Dichos generadores son extremadamente rápidos y, combinados con una operación no lineal, superan pruebas estadísticas rigurosas. ^{[ 11 ] [ 12 ] [ 13 ]}

En 2006, se desarrolló la familia de generadores WELL . ^{[ 14 ]} Los generadores WELL mejoran en algunos aspectos la calidad del Mersenne Twister, que tiene un espacio de estados demasiado grande y una recuperación muy lenta desde espacios de estados con un gran número de ceros.

Un generador de números aleatorios basado en contador (CBRNG, también conocido como generador de números pseudoaleatorios basado en contador o CBPRNG) es un tipo de PRNG que utiliza únicamente un contador entero como estado interno:

$${\displaystyle {\text{ salida }}=f(n,{\text{ clave}})}$$

Generalmente se utilizan para generar números pseudoaleatorios para grandes cálculos paralelos, como en clústeres de GPU o CPU. ^{[ 15 ]} Tienen ciertas ventajas:

• El único "estado" necesario es el valor del contador y la clave. Para un contador y una clave dados, el resultado siempre es el mismo. Esta propiedad hace que los generadores de números aleatorios codificados sean reproducibles.
• Dado que cada número aleatorio se calcula independientemente de los resultados anteriores, se pueden generar en paralelo. Por ejemplo, en una aplicación de procesamiento masivamente paralelo , a cada hilo o núcleo de la GPU se le puede asignar un rango de valores de contador y calcular números aleatorios sin sincronización ni estado compartido.
• Dado que el generador no requiere pasar por cada estado intermedio, puede "saltar" a cualquier punto de la secuencia en tiempo constante. Esto resulta especialmente útil en aplicaciones como las simulaciones de Monte Carlo, donde se necesitan flujos independientes.

Algunos ejemplos son: ^{[ 15 ]}

• Philox: Utiliza una mezcla basada en la multiplicación para combinar el contador y la tecla.
• Threefry: Basado en una versión de menor seguridad del cifrado por bloques Threefish .

Un generador de números pseudoaleatorios (PRNG) adecuado para aplicaciones criptográficas se denomina generador de números pseudoaleatorios criptográficamente seguro (CSPRNG). Un requisito para un CSPRNG es que un adversario que desconozca la semilla tenga una ventaja insignificante para distinguir la secuencia de salida del generador de una secuencia aleatoria. En otras palabras, mientras que un PRNG solo debe superar ciertas pruebas estadísticas, un CSPRNG debe superar todas las pruebas estadísticas restringidas a un tiempo polinomial en función del tamaño de la semilla. Aunque la demostración de esta propiedad está más allá del estado actual de la teoría de la complejidad computacional , se puede proporcionar evidencia sólida reduciendo al CSPRNG un problema que se supone difícil , como la factorización de enteros . ^{[ 16 ]} En general, pueden ser necesarios años de revisión antes de que un algoritmo pueda certificarse como CSPRNG.

Algunas clases de generadores de números pseudoaleatorios criptográficamente seguros (CSPRNG) incluyen las siguientes:

• cifrados de flujo
• Cifrados de bloques que se ejecutan en modo de contador ^{[ 17 ]} o de retroalimentación de salida .
• PRNG que han sido diseñados específicamente para ser criptográficamente seguros, como la función CryptGenRandom de la interfaz de programación de aplicaciones criptográficas de Microsoft , el algoritmo Yarrow (incorporado en Mac OS X y FreeBSD ) y Fortuna.
• Generadores de números pseudoaleatorios combinados que intentan combinar varios algoritmos primitivos de generadores de números pseudoaleatorios con el objetivo de eliminar cualquier falta de aleatoriedad detectable.
• Diseños especiales basados ​​en supuestos de dureza matemática: ejemplos incluyen el generador de Micali-Schnorr , ^{[ 18 ]} la función pseudoaleatoria de Naor-Reingold y el algoritmo de Blum Blum Shub , que proporcionan una prueba de seguridad sólida (estos algoritmos son bastante lentos en comparación con las construcciones tradicionales y poco prácticos para muchas aplicaciones).
• PRNG genéricos: si bien se ha demostrado que se puede construir un PRNG seguro (criptográficamente) de forma genérica a partir de cualquier función unidireccional , ^{[ 19 ]} esta construcción genérica es extremadamente lenta en la práctica, por lo que es principalmente de interés teórico.

Se ha demostrado que es probable que la NSA haya insertado una puerta trasera asimétrica en el generador de números pseudoaleatorios Dual_EC_DRBG, certificado por el NIST . ^{[ 20 ]}

La mayoría de los algoritmos PRNG producen secuencias que se distribuyen uniformemente según cualquiera de varias pruebas. Es una cuestión abierta, y una central para la teoría y la práctica de la criptografía , si existe alguna manera de distinguir la salida de un PRNG de alta calidad de una secuencia verdaderamente aleatoria. En este contexto, el discriminador sabe que se utilizó el algoritmo PRNG conocido (pero no el estado con el que se inicializó) o se utilizó un algoritmo verdaderamente aleatorio, y tiene que distinguir entre los dos. ^{[ 21 ]} La seguridad de la mayoría de los algoritmos y protocolos criptográficos que utilizan PRNG se basa en la suposición de que es inviable distinguir el uso de un PRNG adecuado del uso de una secuencia verdaderamente aleatoria. Los ejemplos más simples de esta dependencia son los cifradores de flujo , que (en la mayoría de los casos) funcionan aplicando la operación OR exclusiva al texto plano de un mensaje con la salida de un PRNG, produciendo un texto cifrado . El diseño de PRNG criptográficamente adecuados es extremadamente difícil porque deben cumplir criterios adicionales. El tamaño de su período es un factor importante en la idoneidad criptográfica de un generador de números pseudoaleatorios, pero no el único.

La Oficina Federal Alemana de Seguridad de la Información ( Bundesamt für Sicherheit in der Informationstechnik , BSI) ha establecido cuatro criterios para la calidad de los generadores deterministas de números aleatorios. ^{[ 22 ]} Estos se resumen a continuación:

• K1 – Debe existir una alta probabilidad de que las secuencias generadas de números aleatorios sean diferentes entre sí.
• K2 – Una secuencia de números es indistinguible de números "verdaderamente aleatorios" según pruebas estadísticas específicas. Las pruebas son la prueba monobit (igual número de unos y ceros en la secuencia), la prueba poker (una instancia especial de la prueba chi-cuadrado ), la prueba de rachas (cuenta la frecuencia de rachas de varias longitudes), la prueba de rachas largas (verifica si existe alguna racha de longitud 34 o mayor en 20 000 bits de la secuencia) —ambas de BSI ^{[ 22 ]} y NIST , ^{[ 23 ]} y la prueba de autocorrelación . En esencia, estos requisitos son una prueba de qué tan bien una secuencia de bits: tiene ceros y unos con igual frecuencia; después de una secuencia de n ceros (o unos), el siguiente bit es un uno (o cero) con probabilidad de un medio; y cualquier subsecuencia seleccionada no contiene información sobre el/los siguiente(s) elemento(s) en la secuencia.
• K3 – Debería ser imposible para un atacante (a efectos prácticos) calcular o adivinar, a partir de cualquier subsecuencia dada, cualquier valor anterior o futuro en la secuencia, ni ningún estado interno del generador.
• K4 – Debería ser imposible, a efectos prácticos, que un atacante calcule o adivine, a partir de un estado interno del generador, cualquier número anterior en la secuencia o cualquier estado interno anterior del generador.

Para aplicaciones criptográficas, solo se aceptan generadores que cumplan con los estándares K3 o K4.

Dado:

• ${\displaystyle P}$– una distribución de probabilidad sobre${\displaystyle \left(\mathbb {R} ,{\mathfrak {B}}\right)}$(dónde${\displaystyle {\mathfrak {B}}}$es el álgebra sigma de todos los subconjuntos de Borel de la recta real)
• ${\displaystyle {\mathfrak {F}}}$– una colección no vacía de conjuntos de Borel${\displaystyle {\mathfrak {F}}\subseteq {\mathfrak {B}}}$, p.ej${\displaystyle {\mathfrak {F}}=\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}}$. Si${\displaystyle {\mathfrak {F}}}$no está especificado, puede ser cualquiera de las dos${\displaystyle {\mathfrak {B}}}$o${\displaystyle \left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}}$, dependiendo del contexto.
• ${\displaystyle A\subseteq \mathbb {R} }$– un conjunto no vacío (no necesariamente un conjunto de Borel). A menudo${\displaystyle A}$es un conjunto entre${\displaystyle P}$su soporte y su interior ; por ejemplo, si${\displaystyle P}$es la distribución uniforme en el intervalo${\displaystyle \left(0,1\right]}$,${\displaystyle A}$podría ser${\displaystyle \left(0,1\right]}$. Si${\displaystyle A}$no se especifica, se asume que es algún conjunto contenido en el soporte de${\displaystyle P}$y que contiene su interior, según el contexto.

Llamamos a una función${\displaystyle f:\mathbb {N} _{1}\rightarrow \mathbb {R} }$(dónde${\displaystyle \mathbb {N} _{1}=\left\{1,2,3,\dots \right\}}$es el conjunto de enteros positivos) un generador de números pseudoaleatorios para${\displaystyle P}$dado${\displaystyle {\mathfrak {F}}}$tomando valores en${\displaystyle A}$si y solo si :

• ${\displaystyle f\left(\mathbb {N} _{1}\right)\subseteq A}$
• ${\displaystyle \forall E\in {\mathfrak {F}}\quad \forall \varepsilon >0\quad \exists N\in \mathbb {N} _{1}\quad \forall n\geq N,\quad \left|{\frac {\#\left\{i\in \left\{1,2,\dots ,n\right\}:f(i)\in E\right\}}{n}}-P(E)\right|<\varepsilon }$

(${\displaystyle \#S}$denota el número de elementos en el conjunto finito${\displaystyle S}$.)

Se puede demostrar que si${\displaystyle f}$es un generador de números pseudoaleatorios para la distribución uniforme en${\displaystyle \left(0,1\right)}$y si${\displaystyle F}$es la función de distribución acumulada (CDF) de alguna distribución de probabilidad dada${\displaystyle P}$, entonces${\displaystyle F^{*}\circ f}$es un generador de números pseudoaleatorios para${\displaystyle P}$, dónde${\displaystyle F^{*}:\left(0,1\right)\rightarrow \mathbb {R} }$es el percentil de${\displaystyle P}$, es decir${\displaystyle F^{*}(x):=\inf \left\{t\in \mathbb {R} :x\leq F(t)\right\}}$Intuitivamente, se puede simular una distribución arbitraria a partir de una simulación de la distribución uniforme estándar.

Un generador de números pseudoaleatorios (PRNG) informático primitivo, propuesto por John von Neumann en 1946, se conoce como el método del cuadrado medio . El algoritmo es el siguiente: se toma cualquier número, se eleva al cuadrado, se eliminan los dígitos centrales del número resultante para obtener el "número aleatorio" y se utiliza ese número como semilla para la siguiente iteración. Por ejemplo, al elevar al cuadrado el número "1111" se obtiene "1234321", que se puede escribir como "01234321", siendo el cuadrado de un número de 4 dígitos un número de 8 dígitos. Esto da como resultado "2343" como número aleatorio. Repitiendo este procedimiento se obtiene "4896" como siguiente resultado, y así sucesivamente. Von Neumann utilizó números de 10 dígitos, pero el proceso fue el mismo.

Un problema del método del "cuadrado central" es que todas las secuencias se repiten, algunas muy rápidamente, como "0000". Von Neumann era consciente de esto, pero consideró que el método era suficiente para sus propósitos y le preocupaba que las "correcciones" matemáticas simplemente ocultaran los errores en lugar de eliminarlos.

Von Neumann consideró inadecuados los generadores de números aleatorios por hardware, ya que, si no registraban la salida generada, no se podían comprobar posteriormente en busca de errores. Si registraban la salida, agotarían la limitada memoria disponible en la computadora en aquel entonces, y por lo tanto, la capacidad de la computadora para leer y escribir números. Si los números se escribían en tarjetas, el proceso de escritura y lectura sería mucho más lento. En la computadora ENIAC que utilizaba, el método del "cuadrado central" generaba números a una velocidad cien veces mayor que la lectura de números desde tarjetas perforadas .

El método del cuadrado medio ha sido sustituido desde entonces por generadores más elaborados.

Una innovación reciente consiste en combinar el método del cuadrado medio con una secuencia de Weyl . Este método produce resultados de alta calidad durante un período prolongado (véase el método del cuadrado medio ).

Se pueden generar números seleccionados a partir de una distribución de probabilidad no uniforme utilizando un generador de números pseudoaleatorios de distribución uniforme y una función que relacione ambas distribuciones.

En primer lugar, se necesita la función de distribución acumulativa.${\displaystyle F(b)}$de la distribución objetivo${\displaystyle f(b)}$:

${\displaystyle F(b)=\int _{-\infty }^{b}f(b')\,db'}$

Tenga en cuenta que${\displaystyle 0=F(-\infty )\leq F(b)\leq F(\infty )=1}$. Usando un número aleatorio c de una distribución uniforme como densidad de probabilidad de "pasar", obtenemos

${\displaystyle F(b)=c}$

de modo que

${\displaystyle b=F^{-1}(c)}$

es un número seleccionado aleatoriamente de la distribución${\displaystyle f(b)}$Esto se basa en el muestreo de la transformada inversa .

Por ejemplo, la inversa de la distribución gaussiana acumulativa${\displaystyle \operatorname {erf} ^{-1}(x)}$con un generador de números pseudoaleatorios uniforme ideal con rango (0, 1) como entrada${\displaystyle x}$produciría una secuencia de valores (solo positivos) con una distribución gaussiana; sin embargo

• Al utilizar representaciones numéricas prácticas , las "colas" infinitas de la distribución deben truncarse a valores finitos.
• Recálculo repetitivo de${\displaystyle \operatorname {erf} ^{-1}(x)}$debería reducirse mediante métodos como el algoritmo zigurat para una generación más rápida.

Consideraciones similares se aplican a la generación de otras distribuciones no uniformes, como Rayleigh y Poisson .

• Barker E., Kelsey J. , Recomendación para la generación de números aleatorios mediante generadores de bits aleatorios deterministas , NIST SP800-90A, enero de 2012
• Brent RP , "Algunos generadores de números aleatorios de largo período que utilizan desplazamientos y xors", ANZIAM Journal , 2007; 48:C188–C202
• Gentle JE (2003), Generación de números aleatorios y métodos de Monte Carlo , Springer.
• Hörmann W., Leydold J., Derflinger G. (2004, 2011), Generación automática de variables aleatorias no uniformes , Springer-Verlag.
• Knuth DE El arte de la programación informática , Volumen 2: Algoritmos seminuméricos , Tercera edición. Addison-Wesley, 1997. ISBN 0-201-89684-2Capítulo 3. [Cobertura exhaustiva de pruebas estadísticas para detectar la no aleatoriedad.]
• Luby M., Pseudorandomness and Cryptographic Applications , Princeton Univ Press, 1996. ISBN 9780691025469
• von Neumann J., "Varias técnicas utilizadas en relación con dígitos aleatorios", en AS Householder, GE Forsythe y HH Germond, eds., Método de Monte Carlo , Serie de Matemáticas Aplicadas de la Oficina Nacional de Estándares, 12 (Washington, DC: Oficina de Imprenta del Gobierno de los Estados Unidos, 1951): 36–38.
• Peterson, Ivars (1997). Las junglas del azar  : un safari matemático . Nueva York: John Wiley & Sons. ISBN 0-471-16449-6.
• Press WH, Teukolsky SA, Vetterling WT, Flannery BP (2007), Numerical Recipes ( Cambridge University Press ).
• Viega J. , " Generación práctica de números aleatorios en software ", en Actas de la 19.ª Conferencia Anual de Aplicaciones de Seguridad Informática, diciembre de 2003.

• TestU01 : Un conjunto de pruebas de números aleatorios en C++ gratuito y de última generación ( GPL ) .
• DieHarder : Un conjunto de pruebas de números aleatorios en C gratuito ( GPL ) .
• " Generación de números aleatorios " (en sistemas embebidos ) por Eric Uner (2004)
• " Análisis del generador de números aleatorios de Linux " por Zvi Gutterman, Benny Pinkas y Tzachy Reinman (2006)
• " Mejores generadores pseudoaleatorios " de Parikshit Gopalan, Raghu Meka, Omer Reingold , Luca Trevisan y Salil Vadhan ( Microsoft Research , 2012)
• La función rand() se considera perjudicial en YouTube , según Stephan Lavavej (Microsoft, 2013).
• Wsphynx es un generador de números aleatorios en línea sencillo. Los números aleatorios se generan mediante algoritmos de generación de números pseudoaleatorios (PRNG) de JavaScript.