Generador de números pseudoaleatorios

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 10 de enero de 2022; las comprobaciones requieren 6 ediciones .

El generador de números pseudoaleatorios ( PRNG , en inglés pseudorandom number generator , PRNG ) es un algoritmo que genera una secuencia de números , cuyos elementos son casi independientes entre sí y obedecen a una distribución determinada (normalmente uniforme discreta ).

La informática moderna hace un uso extensivo de los números pseudoaleatorios en una variedad de aplicaciones, desde Monte Carlo y la simulación hasta la criptografía . Al mismo tiempo, la calidad de los resultados obtenidos depende directamente de la calidad de los PRNG utilizados. Esta circunstancia es enfatizada por el conocido aforismo del matemático del ORNL Robert Caviu: " La generación de números aleatorios es demasiado importante para dejarla al azar ".

Fuentes de números aleatorios

Las fuentes de números aleatorios reales son extremadamente difíciles de encontrar. Los ruidos físicos [1] como los detectores de eventos de radiación ionizante , el ruido de disparo en una resistencia o la radiación cósmica [2] pueden ser tales fuentes. Sin embargo, estos dispositivos rara vez se utilizan en aplicaciones de seguridad de red. Los ataques brutales a tales dispositivos también causan dificultades.

Las fuentes físicas de números aleatorios tienen una serie de desventajas:

Costos de tiempo y mano de obra durante la instalación y configuración en comparación con el software PRNG;
Alto costo;
La generación de números aleatorios es más lenta que con la implementación de software de PRNG;
La imposibilidad de reproducir una secuencia de números aleatorios previamente generada. [3]

Al mismo tiempo, los números aleatorios obtenidos de una fuente física se pueden utilizar como elemento generador (semilla inglesa) para los PRNG de software. Dichos generadores combinados se utilizan en criptografía, loterías, máquinas tragamonedas. [3]

Requisitos cualitativos para PRNG

Un período suficientemente largo para garantizar que la secuencia no se repita dentro del problema que se está resolviendo. La duración del período debe demostrarse matemáticamente;
Eficiencia : la velocidad del algoritmo y los bajos costos de memoria;
Reproducibilidad : la capacidad de reproducir una secuencia de números generada previamente cualquier número de veces;
Portabilidad : el mismo funcionamiento en diferentes hardware y sistemas operativos;
La velocidad de obtención de un elemento de una secuencia de números, al especificar un elemento, para cualquier valor; esto permite dividir la secuencia en varios flujos (secuencias de números). [3] ${\ Displaystyle X_ {n+i}}$ $X_{{n}}$ $i$

Primeros enfoques para la formación de PRSPs

John von Neumann consideró inaceptable el uso de generadores físicos de números aleatorios en tecnología informática, ya que si fuera necesario verificar cálculos, repetir acciones anteriores requeriría la reproducción de un número aleatorio, mientras que generar un nuevo número aleatorio es inaceptable. El registro y almacenamiento preliminar de los números aleatorios generados implicaría la posibilidad de leerlos. El mecanismo de lectura de datos era uno de los eslabones más débiles de las computadoras de la década de 1940. John von Neumann dio el siguiente método del cuadrado medio [4] para obtener números pseudoaleatorios de diez dígitos:

Se eleva al cuadrado un número de diez cifras, luego se toma un número de diez cifras de la mitad del cuadrado del número, que se vuelve a elevar al cuadrado, y así sucesivamente.

Por ejemplo, para números de 4 dígitos, a partir de 1234, obtenemos , donde tomamos los 4 dígitos del medio (agregando un cero al principio, si es necesario). Luego elevamos al cuadrado el número resultante , y así sucesivamente. La desventaja de este método es el conjunto limitado de PSCH debido al hecho de que la secuencia hace un bucle - . ${\ estilo de visualización 1234 ^ {2} = 1522756}$ $01{\overline{5227}}56$ $5227^{2}=27{\overline {3215}}29$ $5000^{2}=25{\overline {0000}}00.0^{2}=0,\puntos$

En 1951, D. G. Lemer propuso un método lineal congruente , [5] cuya esencia es especificar una secuencia de números enteros mediante una fórmula recursiva donde son números enteros y cumplen las siguientes condiciones: . La desventaja de este método es la dependencia de , ya que , así como el hecho de que el PFC realiza un bucle. $X_{n+1}=(aX_{n}+c)~{\bmod {~}}m,$ ${\ estilo de visualización a, \ m, \ c}$ $0<m,\ \ 0<a<m,\ \ 0<c<m,\ \ X_{0}<m$ ${\ estilo de visualización X_ {n}, \ n> 0}$ $X_{{0}}$ $X_{n}=\left(a^{n}X_{0}+{\frac {c(a^{n}-1)}{(a-1)))\right)~{\ bmod {~}}m$

PRNG deterministas

Algoritmo

La mayoría de los PRNG deterministas corresponden a la 1994:en]1 [estructura propuesta por P. Lecuer . Por lo general , y el estado del generador viene dado por la fórmula recursiva para . valor de salida del generador ; es una secuencia de números pseudoaleatorios. Como es finito, deben existir unos finitos y tales que . Esto significa que las condiciones y se cumplirán para todos , porque las funciones y son deterministas. Por lo tanto, resulta que la secuencia es periódica. El período PRNG se denomina mínimo positivo . [3] $({\mathcal {S)),\mu,f,{\mathcal {U)),g)$ $\mathcal{S}$ $\mu$ $\mathcal{S}$ ${\displaystyle {\mathcal {s_{0))))$ $f:{\mathcal {S}}\rightarrow {\mathcal {S}}$ ${\ matemáticas {U}}$ $g:{\mathcal {S}}\rightarrow {\mathcal {U}}$ ${\mathcal {U}}=(0,1)$ ${\ estilo de visualización s_ {i} = f \ (s_ {i-1})}$ ${\ estilo de visualización i \ geq 1}$ $u_{i}=g\ (s_{i})\in {\mathcal {U))$ $u_{0},\u_{1},\u_{2}\ ...$ ${\ matemáticas {U}}$ ${\ estilo de visualización l \ geq 0}$ ${\ estilo de visualización j> 0}$ ${\displaystyle s_{l+j}=s_{l))$ ${\ Displaystyle i \ geq l}$ $s_{i+j}=s_{i}$ $u_{i+j}=u_{i}$ ${\ estilo de visualización f}$ $gramo$ $j$

Los más comunes son el método congruencial lineal , el método de Fibonacci con retrasos , el registro de desplazamiento con retroalimentación lineal , el registro de desplazamiento con retroalimentación generalizada .

De los PRNG modernos, también se ha generalizado el " vórtice de Mersenne " propuesto en 1997 por Matsumoto y Nishimura . Sus ventajas son un período colosal (2 19937 −1), una distribución uniforme en 623 dimensiones (el método lineal congruente da una distribución más o menos uniforme en un máximo de 5 dimensiones), generación rápida de números aleatorios (2-3 veces más rápido que PRNG estándar utilizando el método lineal congruente). Sin embargo, existen algoritmos que reconocen la secuencia generada por el vórtice de Mersenne como no aleatoria.

Se incluye un generador de números pseudoaleatorios en muchos procesadores modernos , por ejemplo, RdRand se incluye en el conjunto de instrucciones IA-32. [6]

Una variación de PRNG son GPSB (PRBG), generadores de bits pseudoaleatorios, así como varios cifrados de flujo .

Lista de generadores de números pseudoaleatorios

La siguiente es una lista de generadores que históricamente se han destacado en el campo de la generación de números pseudoaleatorios, ya sea por su importancia histórica o porque fueron un modelo innovador para su época. Además, a pesar de que se trata de un PRNG, algunos de ellos pueden ser aplicables en el campo de la criptografía.

Algoritmo	Los autores		Enlaces	Descripción
medio cuadrado	Juan von Neummann	1946	[7]	PRNG, que se considera de baja calidad pero de gran importancia histórica como uno de los primeros algoritmos.
Generador de Lehmer / Método congruencial lineal	DH Lehmer	1951	[ocho]	También es conocido como el método de las congruencias lineales multiplicativas y ha sido muy influyente en esta área de investigación. También se conoce como el Método Lineal Congruencial, cuya base ha mejorado con el tiempo.
Generador de retrasos de Fibonacci	GJ Mitchell; DP Moore	1958	[9]	Un algoritmo muy influyente en el estudio de los procesos de generación de números aleatorios, inspirando a otros grandes autores posteriores como G. Marsaglia, creador de un test de calidad de números aleatorios llamado "Diehard", por ejemplo.
Registro de desplazamiento de retroalimentación lineal (LFSR) / Oscilador Tausworthe	RC Tausworth	1965	[diez]	Un generador cuyo diseño influyó en muchos otros PRNG posteriores. Por lo tanto, es muy importante históricamente. También conocido como el generador de Tausworthe.
Generador Wichmann & Hill	BA Wichmann; Colina DI	mil novecientos ochenta y dos	[once]	Una combinación de tres LCG pequeños adecuados para procesadores de 16 bits. Ampliamente utilizado en muchos programas, por ejemplo, se usó en Excel 2003 y algunas versiones posteriores para la función RAND en Excel y fue el generador predeterminado en Python hasta la versión 2.2.
Regla 30	Wolfram, Esteban	1983	[12]	Generador basado en autómatas celulares.
Generador Blum-Blum-Shub	Bloom, Manuel ; L.Blum; M. Shub	1986	[13]	Es considerado uno de los generadores más seguros desde el punto de vista criptográfico, principalmente por la incorporación en su fórmula de investigaciones y conceptos tomados de la teoría de números. Por este algoritmo de Blum , Manuel recibió el Premio Alan Turing de 1995.
generador park-miller	Parque SK; kw molinero	1988	[catorce]	Una implementación concreta del generador Lehmer, muy utilizado porque está incluido en C++ como la función minstd_rand0 desde C++11.
BELLOTA	RS Wikramaratna	1989	[quince]	Su nombre proviene del acrónimo inglés ACORN, que significa ″Número aleatorio congruente aditivo″.
MIXMAX	GK Sabiduría; NG Ter-Arutyunyan-Savvidy	1991	[dieciséis]	Este es un generador que pertenece a la clase de generadores lineales congruentes de matrices, una generalización del método de congruencias lineales. La lógica de la familia de generadores MIXMAX se basa en los resultados de la teoría ergódica y la mecánica clásica.
Agregar con llevar	G. Marsaglia	1991	[17]	Modificación de generadores de Fibonacci con retraso.
Restar con préstamo	G. Marsaglia; A. Zamán	1991	[17]	Algoritmo derivado de generadores de Fibonacci con retardo.
isaac	RJ Jenkins Jr.	1993	[Dieciocho]	Generador de datos criptográficos criptográficamente seguros (CSPRNG) desarrollado por Robert J. Jenkins.
Mersenne Twister, Montana	M. Matsumoto; T. Nishimura	1996	[19]	Este es probablemente el generador más conocido de esta lista, principalmente porque es un algoritmo implementado en la función RAND de los lenguajes de programación Python y R, además de su fuerte presencia en juegos electrónicos como Pro Evolution Soccer (PES).
Xorshift	G. Marsaglia	2003	[veinte]	Este es un subtipo muy rápido de generadores LFSR. Marsaglia también propuso un generador xorwow como mejora, en el que la salida del generador xorshift se suma con una secuencia de Weyl. El generador xorwow es el generador predeterminado en la biblioteca nVidia CUDA API CURAND para GPU.
Algoritmo de fortuna	Schneier, Bruce ; nils ferguson	2003	[21]	El algoritmo se considera criptográficamente seguro. CSPRNG, bien conocido por estar integrado en los sistemas y productos de Apple.
Lineal de período largo bien equidistribuido (WELL)	F. Panneton; P. L'Ecuyer; Matsumoto	2006	[22]	Un algoritmo conocido como complemento del Mersenne Twister (MT), que busca deliberadamente ocultar sus debilidades.
Sistema de Aleatorización Avanzado (ARS)	J. Salmón; M. Moraes; R. Dror; d shaw	2011	[23]	Una versión simplificada del cifrado de bloque AES que proporciona un rendimiento muy alto en un sistema compatible con AES-NI.
tres fritos	J. Salmon, M. Moraes, R. Dror y D. Shaw	2011	[23]	Una versión simplificada del cifrado de bloques Threefish adecuado para la implementación de GPU.
filox (filox)	J. Salmon, M. Moraes, R. Dror y D. Shaw	2011	[23]	Simplificación y modificación del cifrado de bloque Threefish con la adición de S-box.
Generador Congruencial Permutado (PCG)	ME O'Neill	2014	[24]	Modelo obtenido por el método lineal congruente.
Generador de bits de ciclo aleatorio (RCB)	R. Cookman	2016	[25]	El RCB se describe como un generador de patrones de bits diseñado para superar algunas de las deficiencias de Mersenne Twist (MT) y la limitación de período corto/longitud de bits de los generadores de desplazamiento/módulo.
Secuencia de Weyl cuadrada media RNG	B. Widynski	2017	[26]	Una variación del método original de cuadrados medios de John von Neumann.
Xoroshiro128+	D. Blackman; Santa Vigna	2018	[27]	Modificación del generador Xorshift de G. Marsaglia, uno de los generadores más rápidos en los procesadores modernos de 64 bits. Los generadores relacionados son xoroshiro128, xoshiro256+ y xoshiro256*.
MELG de 64 bits (MELG-64)	S. Harase; t.kimoto	2018	[28]	Implementación de generadores F2 lineales de 64 bits con período de Mersenne primario.
Cuadrados RNG	B. Widynski	2020	[29]	Una versión basada en contador de Middle Square Weyl Sequence RNG. Similar en diseño al Philox, pero mucho más rápido.
Itamaracá (Ita)	DH Pereira	2021	[treinta]	Conocido como el primer algoritmo PRNG basado en la función de valor absoluto. Itamaracá es también un modelo simple y rápido que genera secuencias aperiódicas de números aleatorios.

Libreta desechable

Una solución alternativa es crear un conjunto de una gran cantidad de números aleatorios y publicarlo en algún tipo de diccionario , llamado " bloque de una sola vez ". Sin embargo, incluso estos conjuntos proporcionan una fuente de números muy limitada en comparación con el número requerido por las aplicaciones de seguridad de la red. Si bien estos conjuntos proporcionan aleatoriedad estadística, no son lo suficientemente seguros, ya que un atacante podría obtener una copia del diccionario.

Desventajas de PRNG

Ningún algoritmo determinista puede generar números completamente aleatorios, solo puede aproximar algunas de sus propiedades. Como dijo John von Neumann , " Cualquiera que tenga debilidad por los métodos aritméticos para obtener números aleatorios es un pecador sin duda ".

Cualquier PRNG con recursos limitados tarde o temprano se atasca: comienza a repetir la misma secuencia de números. La duración de los ciclos PRNG depende del propio generador y es aproximadamente , donde es el tamaño del estado interno en bits, aunque los generadores lineales congruentes y LFSR tienen ciclos de orden máximo [31] . Si la secuencia PRNG generada converge en ciclos demasiado cortos, dicho PRNG se vuelve predecible e inadecuado para aplicaciones prácticas. ${\ estilo de visualización 2 ^ {\ frac {n} {2}}}$ $norte$ $2^{n}$

La mayoría de los generadores aritméticos simples, aunque rápidos, adolecen de muchas deficiencias graves:

Período/períodos demasiado cortos.
Los valores consecutivos no son independientes.
Algunos bits son "menos aleatorios" que otros.
Distribución unidimensional no uniforme.
Reversibilidad.

En particular, el algoritmo RANDU , que se ha utilizado en computadoras centrales durante décadas , resultó ser muy pobre [32] [33] , lo que genera dudas sobre la confiabilidad de los resultados de muchos estudios que utilizan este algoritmo.

PRNG con fuente de entropía o RNG

Junto con la necesidad de generar secuencias fácilmente reproducibles de números aleatorios, también existe la necesidad de generar números completamente impredecibles o simplemente completamente aleatorios. Dichos generadores se denominan generadores de números aleatorios (RNG - English random number generator, RNG ). Dado que dichos generadores se usan con mayor frecuencia para generar claves simétricas y asimétricas únicas para el cifrado, generalmente se crean a partir de una combinación de un PRNG criptográficamente fuerte y una fuente de entropía externa (y esta combinación ahora se conoce comúnmente como RNG).

Casi todos los principales fabricantes de microchips suministran RNG de hardware con varias fuentes de entropía, utilizando varios métodos para eliminar la previsibilidad inevitable. Sin embargo, por el momento, la velocidad de recolección de números aleatorios por parte de todos los microchips existentes (varios miles de bits por segundo) no iguala la velocidad de los procesadores modernos.

En la investigación moderna, se están haciendo intentos de utilizar la medición de las propiedades físicas de los objetos (por ejemplo, la temperatura ) o incluso las fluctuaciones cuánticas del vacío como fuente de entropía para RNG. [34]

En las computadoras personales, los autores de software RNG utilizan fuentes de entropía mucho más rápidas, como el ruido de la tarjeta de sonido o el contador del reloj del procesador . La recolección de entropía fue el punto más vulnerable del RNG. Este problema aún no está completamente resuelto en muchos dispositivos (como las tarjetas inteligentes ) que siguen siendo vulnerables de esta manera. [35] Muchos RNG utilizan métodos tradicionales probados, aunque lentos, de recolección de entropía, como medir la respuesta del usuario ( movimiento del mouse , etc.), como en PGP y Yarrow [36] , o interacciones entre hilos , como en Java seguro al azar.

Un ejemplo de un RNG simple con una fuente de entropía

Si se utiliza la hora actual como fuente de entropía, entonces para obtener un número entero de 0 a N , basta con calcular el resto de dividir la hora actual en milisegundos por el número N +1. La desventaja de este RNG es que produce el mismo número por un milisegundo.

Ejemplos de RNG y fuentes de entropía

	Fuente de entropía	PRNG	Ventajas	Defectos
/dev/aleatorio en UNIX / Linux	Contador de reloj del procesador, sin embargo, solo se recopila durante las interrupciones de hardware	LFSR , con hash de salida a través de SHA-1	Disponible en todos los Unixes, una fuente confiable de entropía	Se “calienta” durante mucho tiempo, puede “atascarse” durante mucho tiempo o funciona como un PRNG ( /dev/urandom )
Milenrama de Bruce Schneier [36]	Métodos tradicionales	AES -256 y SHA-1 pequeño estado interno	Diseño flexible criptorresistente	Lento
API criptográfica de Microsoft	Hora actual, tamaño del disco duro, memoria libre, número de proceso y nombre NETBIOS de la computadora	Hash MD5 del estado interno, tamaño de 128 bits	Integrado en Windows, no se atasca	Depende en gran medida del proveedor criptográfico (CSP) utilizado.
Java seguro aleatorio	Comunicación entre hilos	SHA-1 - hash de estado interno (1024 bits)	Gran estado interno	Colección de entropía lenta
RdRand por Intel [37]	corrientes de ruido	Construcción de PFS basada en la lectura de bits "aleatorios" de valores de corrientes [37]	Muy rápido, no se atasca.	El desarrollo original, las propiedades se dan solo de acuerdo con la aprobación de los desarrolladores.

PRNG en criptografía

Uno de los criterios de que PRNG es criptográficamente fuerte es la incapacidad de distinguir los valores de salida de PRNG de una secuencia aleatoria independiente distribuida uniformemente en el intervalo. Sea una familia de PRNG , donde la cardinalidad del conjunto sea igual a . Como se mencionó anteriormente, es un conjunto finito de estados, es una distribución de probabilidad en el espacio de estado utilizado para seleccionar el estado inicial (semilla inglesa), es una función de transición, es el espacio de valores de salida, . Por lo general , y el estado del generador viene dado por la fórmula recursiva para . valor de salida del generador ; es una secuencia de números pseudoaleatorios. Suponga que las funciones de transición y salida se pueden calcular en tiempo polinomial, potencias de . Sea una clase de pruebas estadísticas que intentan en tiempo polinomial distinguir los valores de salida del PRNG de una secuencia aleatoria independiente uniformemente distribuida en el intervalo . Una familia de PRNG se dice buena en términos de tiempo polinomial si existe tal que ninguna de las pruebas puede distinguir los valores de salida del PRNG de una secuencia aleatoria independiente uniformemente distribuida en el intervalo con probabilidad . [3] ${\mathcal {U}}=(0,1)$ ${\xi _{k}=({\mathcal {S_{k))},\mu _{k},f_{k},{\mathcal {U_{k))},g_{k} ),k=1,2,...}$ ${\ Displaystyle {\ mathcal {S_ {k}}}}$ $2^k$ $\mathcal{S}$ $\mu$ $\mathcal{S}$ ${\displaystyle {\mathcal {s_{0))))$ $f:{\mathcal {S}}\rightarrow {\mathcal {S}}$ ${\ matemáticas {U}}$ $g:{\mathcal {S}}\rightarrow {\mathcal {U}}$ ${\mathcal {U}}=(0,1)$ ${\ estilo de visualización s_ {i} = f \ (s_ {i-1})}$ ${\ estilo de visualización i \ geq 1}$ $u_{i}=g\ (s_{i})\in {\mathcal {U))$ $u_{0},\u_{1},\u_{2}\ ...$ $F$ $gramo$ $k$ $\mathcal{T}$ $k$ ${\mathcal {U}}=(0,1)$ ${\ estilo de visualización \ xi _ {k}}$ $\epsilon > 0$ $k$ $\mathcal{T}$ ${\mathcal {U}}=(0,1)$ ${\displaystyle 1/2+e^{-k\epsilon))$

Las aplicaciones criptográficas utilizan algoritmos deterministas para generar números aleatorios, generando así una secuencia de números que teóricamente no puede ser aleatoria estadísticamente. Al mismo tiempo, si elige un buen algoritmo, la secuencia numérica resultante ( números pseudoaleatorios ) pasará la mayoría de las pruebas de aleatoriedad. Una de las características de tal secuencia es un largo período de repetición. [3]

Ejemplos de PRNG criptográficamente fuertes conocidos son RC4 [31] , ISAAC [38] , SEAL [39] , SNOW [40] , un algoritmo Blum-Blum-Shub teórico muy lento [31] , así como contadores con hash criptográfico funciones o cifrados de bloque criptográficamente seguros en lugar de la función de salida [31] .

Además, los cifrados criptográficamente fuertes incluyen generadores con múltiples registros de desplazamiento , generadores con transformaciones no lineales y generadores de cifrado mayoritario A5/x . [31]

Ejemplos de PRNG criptorresistentes

Cifrado por turnos

El generador de números aleatorios se cifra utilizando varias claves secretas obtenidas en cada etapa. Se utiliza un contador con un período largo como entrada al dispositivo de cifrado. Cuando se usa una clave DES de 56 bits , se puede usar un contador con un punto . ${\ estilo de visualización X_ {i}}$ $norte$ $2^{56}$

En el momento de la inicialización, se generan una clave secreta y una constante . debe ser aleatorio y solo usado para este generador. $k$ $C$ $k$
En cada etapa sucede lo siguiente:

X_{i}=E_{K}(C)

{\ estilo de visualización C = C + 1}

La secuencia pseudoaleatoria obtenida por este esquema tiene un período completo: cada valor de salida , , ... se basa en un valor de contador diferente, por lo tanto . Dado que la clave es secreta, cualquier clave secreta no depende del conocimiento de una o más claves secretas anteriores. Para aumentar la fuerza criptográfica del algoritmo, es necesario en cada paso cifrar un número aleatorio con un RNG - . [41] $X_{{0}}$ ${\ estilo de visualización X_ {1}}$ ${\ estilo de visualización X_ {N-1}}$ ${\displaystyle X_{0}\neq X_{1}\neq ...\neq X_{N-1))$ $k$ ${\ estilo de visualización X_ {i}}$ $Rhode Island}$ ${\ estilo de visualización X_ {i} = E_ {K} (R_ {i})}$

$k$ es la clave utilizada en cada etapa.
${\ estilo de visualización E_ {K}}$ -Función de cifrado de claves . $k$
$Rhode Island}$ - número aleatorio con RNG.

ANSI X9.17

PRNG del estándar ANSI X9.17 se utiliza en muchas aplicaciones de seguridad financiera y PGP . En el corazón de este PRNG se encuentra triple DES . El generador ANSI X9.17 consta de las siguientes partes:

En el momento de la inicialización, se genera una clave secreta . Debe ser aleatorio y solo se usa para este generador. $k$
En cada etapa sucede lo siguiente:

T_{i}=E_{K}(D_{i})

R_{i}=E_{K}(T_{i}\oplus V_{i})

V_{i+1}=E_{K}(T_{i}\oplus R_{i})

${\ Displaystyle D_ {yo}}$ — el valor de la fecha y la hora al comienzo de la ésima etapa de generación. $i$
$V_{yo}$ es el valor inicial para la -ésima etapa de generación. $i$
$Rhode Island}$ es un número pseudoaleatorio creado en la etapa th de generación. $i$
$k$ es la clave utilizada en cada etapa.
${\ estilo de visualización E_ {K}}$ -Función de cifrado de claves . $k$

Los valores aleatorios de entrada son y . es el valor de salida. El cálculo sin conocimiento no es posible en un tiempo razonable y, por lo tanto, el siguiente valor pseudoaleatorio , ya que se realizan tres operaciones de cifrado adicionales para obtener. [42] ${\ Displaystyle D_ {yo}}$ $V_{yo}$ $Rhode Island}$ $V_{i+1}$ $Rhode Island}$ $k$ $R_{i+1}$ $V_{i+1}$

PRNG de hardware

Aparte de los obsoletos y conocidos generadores LFSR que se utilizaron ampliamente como PRNG de hardware en el siglo XX, se sabe muy poco sobre los PRNG de hardware modernos, ya que la mayoría de ellos se desarrollan con fines militares o están patentados y se mantienen en secreto . Los generadores RLOS basados en hardware Toyocrypt y LILI-128 fueron pirateados mediante ataques algebraicos [43] [44] .

En la actualidad, se conoce sobre el uso de PRNG hardware implementados en base a ruido de baja potencia en circuitos eléctricos. [45]

Aplicación de PRNG en loterías

El generador de números aleatorios para loterías es un complejo de hardware y software que se utiliza en las loterías en las que es necesario adivinar una combinación de un número determinado de números. Cualquiera de los números posibles tiene la misma probabilidad de ocurrir.

Los intentos de crear un generador de números aleatorios se remontan al 3500 a. mi. y están asociados con el antiguo juego de mesa egipcio Senet . En Senet, dos jugadores juegan en dos lados. Los movimientos se determinan usando 4 palos planos, que pueden considerarse un generador de números aleatorios de esa época. Lanza los cuatro palos a la vez. La puntuación es la siguiente: 1 palo cayó con el lado blanco hacia arriba: 1 punto y un lanzamiento adicional; 2 - 2 puntos; 3 - 3 puntos, 4 - 4 y una tirada extra. Uno de los lados del palo es negro y si los cuatro palos caen con el lado negro hacia arriba, este es el resultado máximo: 5 puntos y un tiro adicional.

El conocido generador de números aleatorios ERNIE se ha utilizado durante muchos años para determinar los números ganadores de la lotería británica.

Los principales requisitos para el software y el equipo utilizados para realizar loterías en la Federación Rusa están establecidos por la Ley Federal No. 138-FZ del 11 de noviembre de 2003 "Sobre Loterías":

Las características técnicas de los equipos de lotería deberán garantizar la aleatoriedad de la distribución de las ganancias al sortear el fondo de premios de los sorteos de loterías.
No se deben utilizar procedimientos que implementen algoritmos que permitan predeterminar el resultado del sorteo del fondo de premios antes del inicio de dicho sorteo.
Los equipos de lotería utilizados en el sorteo de lotería deben garantizar la protección de la información contra pérdida, robo, distorsión, acciones no autorizadas para destruirla, modificación, copia y otras acciones similares y acceso no autorizado a través de la red de transmisión de datos. [46]

En las loterías estatales rusas (Gosloto 5 de 36, Gosloto 6 de 36, Gosloto 6 de 45, Gosloto 7 de 49, Gosloto 4 de 20, "Sportloto" 6 de 49 "") [ 47] Se utilizan tambores de lotería de carga para determinar los ganadores . Los sorteos se retransmiten en directo. [48]

En las loterías estatales rusas ("Rapido", "Keno-Sportloto", "Top-3", "12/24", "Todo por cien"), se utiliza un generador de números aleatorios para determinar los ganadores: un hardware y software sistema certificado por ANO “MIC” y cumpliendo las recomendaciones de FSUE VNIIMS . El dispositivo genera un flujo continuo de ruido aleatorio, que se convierte en números. En un momento dado, se arrebatan del flujo los valores actuales, que son la combinación ganadora de la lotería. [49]

En 2015, el ex director de seguridad de la Asociación de Loterías Multiestatales de EE. UU. , después de ganar $ 16,5 millones, que tenía acceso al software utilizado en los sorteos de lotería, fue acusado de usar algoritmos especiales para determinar la combinación ganadora de la lotería durante varios días al año. [cincuenta]

Véase también

Notas

↑ N. G. Bardis, A. P. Markovskyi, N. Doukas, N. V. Karadimas. Generación de números aleatorios verdaderos basada en mediciones de ruido ambiental para aplicaciones militares // Actas de la 8.ª Conferencia internacional WSEAS sobre PROCESAMIENTO DE SEÑALES, ROBÓTICA y AUTOMATIZACIÓN. - 2009. - S. 68-73 . - ISBN 978-960-474-054-3 . — ISSN 1790-5117 . Archivado desde el original el 30 de agosto de 2017.
↑ Random.org . Fecha de acceso: 19 de noviembre de 2017. Archivado desde el original el 24 de febrero de 2011. (indefinido)
↑ 1 2 3 4 5 6 L'Ecuyer, Pierre. Generación de números aleatorios // Springer Handbooks of Computational Statistics: Capítulo. - 2007. - S. 93-137 . -doi : 10.1002 / 9780470172445.ch4 . Archivado desde el original el 1 de diciembre de 2017.
↑ Von Neumann, John. Diversas técnicas utilizadas en relación con dígitos aleatorios // Serie de Matemáticas Aplicadas de la Oficina Nacional de Normas. - 1951. - Nº 12 . - S. 36-38 . Archivado desde el original el 6 de noviembre de 2020.
↑ Lehmer, D. H. Métodos matemáticos en unidades informáticas a gran escala // Ann, Comput Lab. Universidad de Harvard - 1951. - vol. 26. - S. 141-146 . (enlace no disponible)
↑ Intel Digital Random Number Generator (DRNG): Guía de implementación de software, revisión 1.1 (PDF). Corporación Intel (7 de agosto de 2012). Consultado el 25 de noviembre de 2012. Archivado desde el original el 18 de mayo de 2013. (indefinido)
↑ Oficina Nacional de Normas. Informe anual 1951 Oficina Nacional de Normas .
↑ JH Curtiss. Un simposio de maquinaria de cálculo digital a gran escala // Tablas matemáticas y otras ayudas a la computación. - 1947-04. - T. 2 , núm. 18 _ - art. 229 . -doi : 10.2307/ 2002294 . Archivado el 11 de mayo de 2022.
↑ Llave JW. Fe de erratas de la tabla: El arte de la programación informática, vol. 2: Algoritmos semiméricos (Addison-Wesley, Reading, Mass., 1969) por Donald E. Knuth // Matemáticas de computación. - 1970. - vol. 24 , edición. 110 . — Pág. 504 . — ISSN 1088-6842 0025-5718, 1088-6842 . -doi : 10.1090/ S0025-5718-1970-0400642-2 .
↑ Robert C. Tausworth. Números aleatorios generados por recurrencia lineal módulo dos // Matemáticas de Computación. - 1965. - Vol. 19 , edición. 90 . — págs. 201–209 . — ISSN 1088-6842 0025-5718, 1088-6842 . -doi : 10.1090/ S0025-5718-1965-0184406-1 .
↑ BA Wichmann, ID Hill. Algoritmo AS 183: un generador de números pseudoaleatorios eficiente y portátil // Revista de la Royal Statistical Society. Serie C (Estadística Aplicada). - 1982. - T. 31 , núm. 2 . — S. 188–190 . — ISSN 0035-9254 . -doi : 10.2307/ 2347988 . Archivado el 11 de mayo de 2022.
↑ Stephen Wolfram. Mecánica estadística de autómatas celulares // Reseñas de Física Moderna. — 1983-07-01. - T. 55 , n. 3 . — S. 601–644 . -doi : 10.1103 / RevModPhys.55.601 .
↑ L. Blum, M. Blum, M. Shub. Un generador de números pseudoaleatorios impredecible simple // SIAM Journal on Computing. - 1986-05-01. - T. 15 , n. 2 . — S. 364–383 . — ISSN 0097-5397 . -doi : 10.1137/ 0215025 . Archivado desde el original el 27 de abril de 2022.
↑ Parque SK, KW Miller. Generadores de números aleatorios: los buenos son difíciles de encontrar // Comunicaciones del ACM. — 1988-10-01. - T. 31 , n. 10 _ - S. 1192-1201 . — ISSN 0001-0782 . -doi : 10.1145/ 63039.63042 .
↑ RS Wikramaratna. ACORN: un nuevo método para generar secuencias de números pseudoaleatorios distribuidos uniformemente // Journal of Computational Physics. — 1989-07. - T. 83 , n. 1 . — P. 16–31 . — ISSN 0021-9991 . -doi : 10.1016 / 0021-9991(89)90221-0 .
↑ G. K. Savvidy, N. G. Ter-Arutyunyan-Savvidy. Sobre la simulación Monte Carlo de sistemas físicos (inglés) // Journal of Computational Physics. - 1991-12-01. — vol. 97 , edición. 2 . — pág. 566–572 . — ISSN 0021-9991 . -doi : 10.1016 / 0021-9991(91)90015-D . Archivado el 11 de mayo de 2022.
↑ 1 2 George Marsaglia, Arif Zaman. Una nueva clase de generadores de números aleatorios // The Annals of Applied Probability. — 1991-08. - T. 1 , núm. 3 . — S. 462–480 . — ISSN 2168-8737 1050-5164, 2168-8737 . -doi : 10.1214 / aoap/1177005878 . Archivado desde el original el 19 de abril de 2022.
↑ ISAAC, un rápido generador criptográfico de números aleatorios . www.burtleburtle.net . Recuperado: 17 de mayo de 2022. (indefinido)
↑ Makoto Matsumoto, Takuji Nishimura. Mersenne twister: un generador de números pseudoaleatorios uniformes equidistribuidos en 623 dimensiones // Transacciones ACM en modelado y simulación por computadora. — 1998-01-01. - T. 8 , núm. 1 . — Pág. 3–30 . — ISSN 1049-3301 . doi : 10.1145 / 272991.272995 .
↑ Jorge Marsaglia. Xorshift RNGs // Revista de software estadístico. - 2003-07-04. — vol. 8 _ — P. 1–6 . — ISSN 1548-7660 . -doi : 10.18637 / jss.v008.i14 .
↑ Fuentes de libros: Wikipedia . en.wikipedia.org . Consultado el 17 de mayo de 2022. Archivado desde el original el 24 de abril de 2022. (Ruso)
↑ François Panneton, Pierre L'Ecuyer, Makoto Matsumoto. Generadores de período largo mejorados basados en recurrencias lineales módulo 2 // Transacciones ACM en software matemático. — 2006-03-01. - T. 32 , n. 1 . — P. 1–16 . — ISSN 0098-3500 . -doi : 10.1145/ 1132973.1132974 .
↑ 1 2 3 John K. Salmon, Mark A. Moraes, Ron O. Dror, David E. Shaw. Números aleatorios paralelos: tan fácil como 1, 2, 3 // Actas de la Conferencia internacional de 2011 sobre computación, redes, almacenamiento y análisis de alto rendimiento. — Nueva York, NY, EE. UU.: Asociación de Maquinaria Informática, 2011-11-12. — P. 1–12 . - ISBN 978-1-4503-0771-0 . -doi : 10.1145/ 2063384.2063405 .
↑ BG Sileshi, C. Ferrer, J. Oliver. Aceleración de la generación de números aleatorios gaussianos de hardware utilizando algoritmos Ziggurat y CORDIC // 2014 IEEE SENSORS. — 2014-11. — S. 2122–2125 . -doi : 10.1109/ ICSENS.2014.6985457 . Archivado desde el original el 17 de mayo de 2022.
↑ Generador de bits aleatorios // SpringerReference. — Berlín/Heidelberg: Springer-Verlag.
↑ Bernard Widynsky. RNG de secuencia Weyl de cuadrado medio // arXiv:1704.00358 [cs]. — 2022-03-20. Archivado desde el original el 17 de mayo de 2022.
↑ David Blackman, Sebastiano Vigna. Generadores de números pseudoaleatorios lineales codificados // arXiv:1805.01407[cs]. — 2022-03-28. Archivado el 11 de mayo de 2022.
↑ Shin Harase, Takamitsu Kimoto. Implementación de generadores lineales F2 distribuidos al máximo de 64 bits con Mersenne Prime Period // Transacciones ACM en software matemático. — 2018-01-03. - T. 44 , n. 3 . — S. 30:1–30:11 . — ISSN 0098-3500 . -doi : 10.1145/ 3159444 .
↑ Bernard Widynsky. Squares: un RNG rápido basado en contadores // arXiv:2004.06278 [cs]. — 2022-03-13. Archivado el 11 de mayo de 2022.
↑ Daniel Henrique Pereira. Itamaracá: una nueva forma sencilla de generar números pseudoaleatorios (inglés) . — 2022-01-25. -doi : 10.33774 / coe-2022-zsw6t . Archivado desde el original el 27 de abril de 2022.
↑ 1 2 3 4 5 Gabidulin E. M., Kshevetsky A. S., Kolybelnikov A. I., Vladimirov S. M. Seguridad de la información. Guía de estudio . - S. 100-113. Archivado el 24 de noviembre de 2020 en Wayback Machine .
↑ Donald Knuth . Capítulo 3.3. Criterio espectral // El arte de programar. Decreto. Op. - S. 129-130.
↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Recetas Numéricas en C: El Arte de la Computación Científica. — 2ª ed. - Cambridge University Press, 1992. - Pág. 277. - ISBN 0-521-43108-5 .
↑ Números aleatorios obtenidos del vacío cuántico . Consultado el 18 de abril de 2012. Archivado desde el original el 19 de abril de 2012. (indefinido)
↑ Jovan DJ. Goli c. Ataques criptoanalíticos al protocolo MIFARE Classic // Topics in Cryptology - CT-RSA 2013. - Springer, Berlin, Heidelberg, 2013. - No. 7779 . - S. 239-259 . -doi : 10.1007 / 978-3-642-36095-4_16 .
↑ 12 Milenrama . _ Consultado el 10 de septiembre de 2004. Archivado desde el original el 8 de noviembre de 2012. (indefinido)
↑ 1 2 Guía de implementación del software Intel DRNG . Intel . Consultado el 8 de diciembre de 2017. Archivado desde el original el 21 de abril de 2016. (indefinido)
↑ J.-P. Aumasson. Sobre el generador pseudoaleatorio ISAAC // Cryptology ePrint Archive. - 2006. Archivado el 8 de septiembre de 2016.
↑ H. Chen, K. Laine, R. Player. [ https://eprint.iacr.org/2017/224.pdf Biblioteca de aritmética cifrada simple - SEAL v2.1] // Cryptology ePrint Archive. - 2017. Archivado el 10 de julio de 2017.
↑ A. Kircanski y A. M. Youssef. [ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.301.2615&rep=rep1&type=pdf Sobre la propiedad de deslizamiento de SNOW 3G y SNOW 2.0] // Seguridad de la información, IET. - 2010. - Nº 5(4) . - S. 199-206 . Archivado desde el original el 16 de diciembre de 2017.
↑ Laponina O. R. Algoritmos de cifrado simétrico . CONOZCA EL INTUITO . Consultado el 8 de diciembre de 2017. Archivado desde el original el 9 de diciembre de 2017. (indefinido)
↑ Kelsey J., Schneier B., Wagner D., Hall C. Ataques criptoanalíticos a generadores de números pseudoaleatorios // Cifrado rápido de software. FSE 1998. Apuntes de conferencias en Ciencias de la Computación. - Springer, Berlín, Heidelberg, 1998. - Vol. 1372. - doi : 10.1007/3-540-69710-1_12 . Archivado desde el original el 7 de diciembre de 2017.
↑ N. T. Courtois. Ataques de correlación de orden superior, algoritmo XL y criptoanálisis de Toyocrypt // Cryptology ePrint Archive. - 2002. Archivado el 29 de marzo de 2017.
↑ Ed Dawson, Andrew Clark, J Golic, W Millan, L Penna. El generador de flujo de claves LILI-128 . — 2000-12-13. Archivado desde el original el 16 de diciembre de 2017.
↑ C. S. Petrie, J. A. Connelly. Un generador de números aleatorios IC basado en ruido para aplicaciones en criptografía // IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications. - Mayo 2000. - Vol. 47, núm. 5 . — S. 615–621 . — ISSN 1057-7122 . doi : 10.1109 / 81.847868 .
↑ Artículo 12.1. Requisitos para equipos de lotería y terminales de lotería . Consultado el 6 de diciembre de 2017. Archivado desde el original el 6 de diciembre de 2017. (indefinido)
↑ Respuestas a preguntas sobre Stoloto . Loto de los Cien . Consultado el 6 de diciembre de 2017. Archivado desde el original el 6 de diciembre de 2017. (indefinido)
↑ Retransmisiones de sorteos de loterías del Estado . Loto de los Cien . Consultado el 6 de diciembre de 2017. Archivado desde el original el 6 de diciembre de 2017. (indefinido)
↑ Generador de números aleatorios . Loto de los Cien . Consultado el 6 de diciembre de 2017. Archivado desde el original el 6 de diciembre de 2017. (indefinido)
↑ Un hombre pirateó un generador de números aleatorios para manipular las loterías, dicen los investigadores , The Guardian . Archivado desde el original el 23 de diciembre de 2017. Consultado el 6 de diciembre de 2017.

Literatura

Donald E. Knuth . Capítulo 3. Números aleatorios // El arte de la programación informática. - 3ra ed. - M. : Williams , 2000. - V. 2. Algoritmos obtenidos. — 832 pág. - 7000 copias. - ISBN 5-8459-0081-6 (ruso) ISBN 0-201-89684-2 (inglés).
Kelton W., Lowe A. Modelado de simulación. CS clásico. - 3ra ed.- San Petersburgo. : Pedro, 2004. - S. 465, 466. - 487 p. — ISBN 0070592926 . — ISBN 5-94723-981-7 .
L'Ecuyer, Pierre. Generación de números aleatorios // Springer Handbooks of Computational Statistics: Capítulo. - 2007. - S. 93-137 . -doi : 10.1002 / 9780470172445.ch4 .

Enlaces

V. A. Uspensky. Las cuatro caras algorítmicas de la aleatoriedad . - MTSNMO , 2006. - 48 págs. — ISBN 978-5-94057-485-9 .
Yuri Lifshits. Lección 9: Generadores pseudoaleatorios // Problemas modernos de criptografía . - Curso de lectura.
L. Barash. El algoritmo AKS para verificar la simplicidad de los números y buscar constantes de generadores de números pseudoaleatorios // Seguridad de las tecnologías de la información. - 2005. - Nº 2 . - S. 27-38 . Archivado desde el original el 18 de octubre de 2014.
Zhelnikov V. Secuencias pseudoaleatorias de números // Criptografía del papiro a la computadora . - M. : ABF, 1996. - 335 p. - ISBN 5-87484-054-0 .
Números aleatorios criptográficos
Teoría y práctica de la generación de números aleatorios
Zvi Gutterman, Benny Pinkas, Tzachy Reinman. Análisis del generador de números aleatorios de Linux
Un conjunto de pruebas estadísticas para generadores de números aleatorios y seudoaleatorios para aplicaciones criptográficas NIST SP 800-22