Un número pseudoaleatorio es un número especial generado por un generador especial. El generador de bits aleatorios deterministas (PRNG), también conocido como generador de bits aleatorios deterministas (DRBG), es un algoritmo para generar una secuencia de números cuyas propiedades se aproximan a las características de las secuencias de números aleatorios. La secuencia PRNG generada no es realmente aleatoria, ya que está completamente determinada por un valor inicial denominado semilla PRNG, que puede incluir valores verdaderamente aleatorios. Aunque las secuencias más cercanas al azar pueden generarse utilizando generadores de números aleatorios de hardware, los generadores de números pseudoaleatorios son importantes en la práctica para la velocidad de generación de números y su reproducibilidad.
Solicitud
Los
PRNG son fundamentales para aplicaciones como la simulación (p. ej., para Monte Carlo), los juegos electrónicos (p. ej., para la generación de procedimientos) y la criptografía. Las aplicaciones criptográficas requieren que la salidalos datos no eran predecibles a partir de información anterior. Se requieren algoritmos más complejos que no hereden la linealidad de los PRNG simples.
Términos y condiciones
Las buenas propiedades estadísticas son un requisito fundamental para obtener un PRNG. En general, se necesita un análisis matemático cuidadoso para asegurarse de que el RNG genere números lo suficientemente cercanos a los aleatorios para que sean apropiados para el uso previsto.
John von Neumann advirtió en contra de malinterpretar PRNG como un generador verdaderamente aleatorio y bromeó diciendo que "Cualquiera que considere métodos aritméticos para generar números aleatorios ciertamente está en un estado de pecado".
Usar
PRNG se puede iniciar desde un estado inicial arbitrario. Siempre generará la misma secuencia cuando se inicialice con este estado. El período PRNG se define como sigue: máximo sobre todos los estados iniciales de la longitud del prefijo de secuencia no repetitiva. El período está limitado por el número de estados, generalmente medido en bits. Debido a que la duración del período se duplica potencialmente con cada bit de "estado" agregado, es fácil crear PRNG con períodos lo suficientemente largos para muchas aplicaciones prácticas.
Si el estado interno del PRNG contiene n bits, su período no puede ser más de 2n resultados, es mucho más corto. Para algunos PRNG, la duración se puede calcular sin pasar por alto el período completo. Los registros de desplazamiento de retroalimentación lineal (LFSR) suelense eligen para tener periodos iguales a 2n − 1.
Los generadores congruentes lineales tienen periodos que se pueden calcular mediante la factorización. Si bien el PPP repetirá sus resultados después de llegar al final del período, un resultado repetido no significa que se haya llegado al final del período, ya que su estado interno puede ser mayor que el de salida; esto es especialmente evidente para los PRNG con salida de un solo bit.
Posibles errores
Los errores encontrados por PRNG defectuosos van desde sutiles (y desconocidos) hasta errores obvios. Un ejemplo es el algoritmo de números aleatorios RANDU, que se ha utilizado en mainframes durante décadas. Era una deficiencia grave, pero su inadecuación pasó desapercibida durante un largo período de tiempo.
En muchas áreas, los estudios de investigación que han utilizado selección aleatoria, simulaciones de Monte Carlo u otros métodos basados en RNG son mucho menos confiables de lo que podría ser el resultado de GNPG de baja calidad. Incluso hoy en día, a veces se requiere precaución, como lo demuestra la advertencia de la Enciclopedia Internacional de Ciencias Estadísticas (2010).
Estudio de caso exitoso
Como ilustración, considere el lenguaje de programación Java ampliamente utilizado. A partir de 2017, Java todavía se basa en el Generador Congruencial Lineal (LCG) para su PRNG.
Historia
El primer PRNG que evita problemas graves y sigue funcionando bastante rápido,fue el Mersenne Twister (discutido a continuación), que se publicó en 1998. Desde entonces, se han desarrollado otros PRNG de alta calidad.
Pero la historia de los números pseudoaleatorios no termina ahí. En la segunda mitad del siglo XX, la clase estándar de algoritmos utilizados para los PRNG incluía generadores lineales congruentes. Se sabía que la calidad de la LCG era inadecuada, pero no se disponía de mejores métodos. Press et al (2007) describieron el resultado de la siguiente manera: "Si todos los artículos científicos cuyos resultados están en duda debido a [LCG y relacionados] desaparecieran de los estantes de las bibliotecas, habría un espacio del tamaño de su puño en cada estante".
El principal logro en la creación de generadores pseudoaleatorios fue la introducción de métodos basados en recurrentes lineales en un campo de dos elementos; tales osciladores están acoplados a registros de desplazamiento de retroalimentación lineal. Sirvieron como base para la invención de los sensores de números pseudoaleatorios.
En particular, la invención de 1997 de Mersen Twister evitó muchos de los problemas de los generadores anteriores. El Mersenne Twister tiene un período de 219937−1 iteraciones (≈4.3 × 106001). Se ha demostrado que se distribuye uniformemente en (hasta) 623 dimensiones (para valores de 32 bits), y en el momento de su introducción era más rápido que otros generadores de sonido estadístico que producen secuencias de números pseudoaleatorios.
En 2003, George Marsaglia introdujo una familia de generadores xorshift también basados en la repetición lineal. Estos generadores son extremadamenteson rápidos y, combinados con una operación no lineal, superan rigurosas pruebas estadísticas.
En 2006, se desarrolló la familia de generadores WELL. Los generadores WELL en cierto sentido mejoran la calidad de Twister Mersenne, que tiene un espacio de estado demasiado grande y una recuperación muy lenta de ellos, generando números pseudoaleatorios con muchos ceros.
Criptografía
PRNG adecuado para aplicaciones criptográficas se denomina PRNG criptográficamente seguro (CSPRNG). El requisito para un CSPRNG es que un atacante que no conozca la semilla solo tenga una ventaja marginal para distinguir la secuencia de salida del generador de una secuencia aleatoria. En otras palabras, mientras que un PRNG solo debe pasar ciertas pruebas estadísticas, un CSPRNG debe pasar todas las pruebas estadísticas que se limitan al tiempo polinomial en el tamaño de la semilla.
Aunque la prueba de esta propiedad está más allá del nivel actual de la teoría de la complejidad computacional, se puede proporcionar una fuerte evidencia al reducir el CSPRNG a un problema que se considera difícil, como la factorización de enteros. En general, pueden ser necesarios años de revisión antes de que un algoritmo pueda certificarse como CSPRNG.
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.
Algoritmos pseudoaleatoriosnumeros
La mayoría de los algoritmos PRNG producen secuencias que se distribuyen uniformemente mediante cualquiera de varias pruebas. Esta es una pregunta abierta. Es uno de los centrales en la teoría y práctica de la criptografía: ¿hay alguna manera de distinguir la salida de un PRNG de alta calidad de una secuencia verdaderamente aleatoria? En esta configuración, el resolutor sabe que se usó un algoritmo PRNG conocido (pero no el estado con el que se inicializó) o se usó un algoritmo verdaderamente aleatorio. Debe distinguir entre ellos.
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 imposible distinguir entre el uso de un PRNG adecuado y el uso de una secuencia verdaderamente aleatoria. Los ejemplos más simples de esta dependencia son los cifrados de flujo, que generalmente funcionan omitiendo o enviando el mensaje de texto sin formato con una salida PRNG, produciendo el texto cifrado. Diseñar PRNG criptográficamente adecuados es extremadamente difícil, ya que deben cumplir criterios adicionales. El tamaño de su período es un factor importante en la idoneidad criptográfica de un PRNG, pero no el único.
Un PRNG computarizado temprano propuesto por John von Neumann en 1946 se conoce como el método de los cuadrados medios. El algoritmo es el siguiente: tome cualquier número, elévelo al cuadrado, elimine los dígitos del medio del número resultante como un "número aleatorio", luego use este número como el número inicial para la siguiente iteración. Por ejemplo, elevar al cuadrado el número 1111 da1234321, que se puede escribir como 01234321, un número de 8 dígitos es el cuadrado de un número de 4 dígitos. Esto da 2343 como un número "aleatorio". El resultado de repetir este procedimiento es 4896, y así sucesivamente. Von Neumann usó números de 10 dígitos, pero el proceso fue el mismo.
Desventajas del "cuadrado medio"
El problema con el método del "cuadrado medio" es que todas las secuencias eventualmente se repiten, algunas muy rápidamente, por ejemplo: 0000. Von Neumann sabía sobre esto, pero encontró un enfoque suficiente para sus propósitos y le preocupaba que el Las "correcciones" matemáticas simplemente ocultarían los errores en lugar de eliminarlos.
Von Neumann consideró que los generadores de números aleatorios y pseudoaleatorios de hardware no eran adecuados: si no registran la salida generada, no se pueden verificar en busca de errores más adelante. Si tuvieran que escribir sus resultados, agotarían la limitada memoria disponible de la computadora y, por lo tanto, la capacidad de la computadora para leer y escribir números. Si los números estuvieran escritos en tarjetas, tomaría mucho más tiempo escribirlos y leerlos. En la computadora ENIAC usó el método del "cuadrado medio" y llevó a cabo el proceso de obtener números pseudoaleatorios varios cientos de veces más rápido que leer números de tarjetas perforadas.
Desde entonces, el cuadrado medio ha sido reemplazado por generadores más complejos.
Método innovador
Una innovación reciente es combinar el cuadrado medio con la secuencia de Weil. Este método asegura productos de alta calidad dentroperíodo largo. Ayuda a obtener las mejores fórmulas de números pseudoaleatorios.
