¿En qué se diferencian los números pseudoaleatorios y verdaderamente aleatorios y por qué es importante?

Nunca he entendido esto. Simplemente diga que escribe un pequeño programa en cualquier idioma que arroje algunos dados (solo usando dados como ejemplo). Después de 600,000 rollos, cada número habría sido rodado alrededor de 100,000 veces, que es lo que esperaría.

¿Por qué hay sitios web dedicados a la "verdadera aleatoriedad"? Seguramente, dada la observación anterior, las posibilidades de obtener cualquier número son casi exactamente 1 sobre cuántos números puede elegir.

Lo probé en Python : aquí está el resultado de 60 millones de rollos. La variación más alta es como 0.15. ¿No es eso tan aleatorio como va a ser?

1 - 9997653 2347.0
2 - 9997789 2211.0
3 - 9996853 3147.0
4 - 10006533 -6533.0
5 - 10002774 -2774.0
6 - 9998398 1602.0

Juguemos un poco de póker informático, solo tú, yo y un servidor en el que ambos confiamos. El servidor usa un generador de números pseudoaleatorios que se inicializa con una semilla de 32 bits justo antes de jugar. Así que hay alrededor de cuatro mil millones de mazos posibles.

Tengo cinco cartas en mi mano, aparentemente no estamos jugando Texas Hold 'Em. Supongamos que las cartas se reparten una para mí, una para ti, una para mí, una para ti, y así sucesivamente. Así que tengo la primera, tercera, quinta, séptima y novena cartas en el mazo.

Anteriormente ejecuté el generador de números pseudoaleatorios cuatro mil millones de veces, una vez con cada semilla, y escribí la primera tarjeta generada para cada uno en una base de datos. Supongamos que mi primera carta es la reina de espadas. Eso solo aparece como la primera carta en una de cada 52 de esas barajas posibles, por lo que hemos reducido las posibles barajas de cuatro mil millones a alrededor de 80 millones más o menos.

Supongamos que mi segunda carta es el tres de corazones. Ahora corro mi RNG 80 millones más de veces usando los 80 millones de semillas que producen la reina de espadas como primer número. Esto me lleva un par de segundos. Escribo todas las barajas que producen los tres corazones como la tercera carta, la segunda carta en mi mano. De nuevo, eso es solo alrededor del 2% de las cubiertas, por lo que ahora tenemos 2 millones de cubiertas.

Supongamos que la tercera carta en mi mano es la 7 de los clubes. Tengo una base de datos de 2 millones de semillas que reparten mis dos cartas; Ejecuto mi RNG otros 2 millones de veces para encontrar el 2% de esas barajas que producen el 7 de clubes como la tercera carta, y solo tenemos 40,000 barajas.

Ya ves cómo va esto. Ejecuté mi RNG 40000 más veces para encontrar todas las semillas que producen mi cuarta carta, y eso nos lleva a 800 mazos, y luego lo ejecuto 800 veces más para obtener las ~ 20 semillas que producen mi quinta carta, y ahora solo genera esas veinte barajas de cartas y sé que tienes una de las veinte manos posibles. Además, tengo una muy buena idea de lo que voy a dibujar a continuación.

¿Ahora ves por qué es importante la aleatoriedad verdadera? La forma en que lo describe, cree que la distribución es importante, pero la distribución no es lo que hace que un proceso sea aleatorio. La imprevisibilidad es lo que hace que un proceso sea aleatorio.

ACTUALIZAR

Según los comentarios (ahora eliminados debido a su naturaleza poco constructiva), al menos el 0.3% de las personas que han leído esto están confundidos en cuanto a mi punto. Cuando las personas argumentan en contra de puntos que no he hecho, o peor, argumentan por puntos que sí hice suponiendo que no los hice, entonces sé que necesito explicar más clara y cuidadosamente.

Parece haber una confusión particular en torno a la distribución de palabras, por lo que quiero mencionar los usos con cuidado.

Las preguntas a la mano son:

• ¿Cómo difieren los números pseudoaleatorios y los números verdaderamente aleatorios?
• ¿Por qué es importante la diferencia?
• ¿Las diferencias tienen algo que ver con la distribución de la salida del PRNG?

Comencemos considerando la manera perfecta de generar una baraja de cartas al azar con la que jugar al póker. Luego veremos cómo otras técnicas para generar mazos son diferentes, y si es posible aprovechar esa diferencia.

Comencemos suponiendo que tenemos una caja mágica etiquetada TRNG. Como su entrada le damos un número entero n mayor o igual a uno, y como su salida nos da un número verdaderamente aleatorio entre uno yn, inclusive. La salida de la caja es completamente impredecible (cuando se le da un número distinto de uno) y cualquier número entre uno yn es tan probable como otro; es decir que la distribución es uniforme . (Hay otras comprobaciones estadísticas más aleatorias de aleatoriedad que podríamos realizar; estoy ignorando este punto ya que no está relacionado con mi argumento. TRNG es perfectamente estadísticamente aleatorio por suposición).

Comenzamos con una baraja de cartas sin barajar. Pedimos a la caja de un número entre uno y 52 - es decir, TRNG(52). Independientemente del número que devuelva, contamos esas cartas de nuestro mazo ordenado y eliminamos esa carta. Se convierte en la primera carta del mazo barajado. Luego pedimos TRNG(51)y hacemos lo mismo para seleccionar la segunda tarjeta, y así sucesivamente.

Otra forma de verlo es: ¡hay 52! = 52 x 51 x 50 ... x 2 x 1 posibles mazos, que es aproximadamente 2 ²²⁶ . Hemos elegido uno de ellos al azar al azar.

Ahora repartimos las cartas. Cuando miro mis cartas, no tengo idea de qué cartas tienes. (Aparte del hecho obvio de que no tienes ninguna de las cartas que yo tengo.) Podrían ser cualquier carta, con la misma probabilidad.

Así que déjenme asegurarme de explicar esto claramente. Tenemos una distribución uniforme de cada salida individual de TRNG(n); cada uno escoge un número entre 1 yn con probabilidad 1 / n. ¡Además, el resultado de este proceso es que hemos elegido uno de 52! posibles mazos con una probabilidad de 1/52 !, por lo que la distribución sobre el conjunto de mazos posibles también es uniforme.

Todo bien.

Ahora supongamos que tenemos una caja menos mágica, etiquetada PRNG. Antes de poder usarlo, debe sembrarse con un número sin signo de 32 bits.

Aparte: ¿Por qué 32 ? ¿No podría sembrarse con un número de 64 o 256 o 10000 bits? Seguro. Pero (1) en la práctica, la mayoría de los PRNG estándar se siembran con un número de 32 bits, y (2) si tiene 10000 bits de aleatoriedad para crear la semilla, ¿por qué está utilizando un PRNG? ¡Ya tienes una fuente de 10000 bits de aleatoriedad!

De todos modos, volvamos a cómo funciona el PRNG: después de sembrarlo, puede usarlo de la misma manera que lo hace TRNG. Es decir, le pasa un número, n, y le devuelve un número entre 1 yn, inclusive. Además, la distribución de esa salida es más o menos uniforme . Es decir, cuando pedimos PRNGun número entre 1 y 6, obtenemos 1, 2, 3, 4, 5 o 6 cada uno aproximadamente una sexta parte del tiempo, sin importar cuál sea la semilla.

Quiero enfatizar este punto varias veces porque parece ser el que confunde a ciertos comentaristas. La distribución del PRNG es uniforme en al menos dos formas. Primero, supongamos que elegimos cualquier semilla en particular. Esperaríamos que la secuencia PRNG(6), PRNG(6), PRNG(6)...un millón de veces produjera una distribución uniforme de números entre 1 y 6. Y segundo, si elegimos un millón de semillas diferentes y solicitamos PRNG(6) una vez para cada semilla, nuevamente esperaríamos una distribución uniforme de números del 1 al 6. La uniformidad del PRNG en cualquiera de estas operaciones no es relevante para el ataque que estoy describiendo .

Se dice que este proceso es pseudoaleatorio porque el comportamiento del cuadro es en realidad completamente determinista; elige entre uno de los 2 ³² posibles comportamientos basados ​​en la semilla. Es decir, una vez que se siembra, PRNG(6), PRNG(6), PRNG(6), ... produce una secuencia de números con una distribución uniforme, pero esa secuencia está completamente determinada por la semilla. Para una secuencia de llamadas dada, por ejemplo, PRNG (52), PRNG (51) ... y así sucesivamente, solo hay 2 ³² secuencias posibles. La semilla esencialmente elige cuál obtenemos.

Para generar un mazo, el servidor ahora genera una semilla. (¿Cómo? Volveremos a ese punto). Luego llaman PRNG(52), PRNG(51)y así sucesivamente para generar el mazo, como antes.

Este sistema es susceptible al ataque que describí. Para atacar el servidor, primero, con anticipación, sembramos nuestra propia copia del cuadro con 0 y pedimos PRNG(52)y escribimos eso. Luego volvemos a sembrar con 1, pedimos PRNG(52)y escribimos eso, hasta 2 ³² -1.

Ahora, el servidor de póker que usa PRNG para generar mazos tiene que generar una semilla de alguna manera. No importa cómo lo hagan. Podrían llamar TRNG(2^32)para obtener una semilla verdaderamente aleatoria. O podrían tomar el tiempo actual como una semilla, que no es al azar en absoluto; Sé qué hora es tanto como tú. El punto de mi ataque es que no importa, porque tengo mi base de datos . Cuando veo mi primera carta, puedo eliminar el 98% de las posibles semillas. Cuando veo mi segunda carta, puedo eliminar un 98% más, y así sucesivamente, hasta que finalmente pueda llegar a un puñado de posibles semillas y saber con alta probabilidad lo que hay en su mano.

Ahora, nuevamente, quiero enfatizar que la suposición aquí es que si llamamos PRNG(6)un millón de veces obtendríamos cada número aproximadamente una sexta parte del tiempo . Esa distribución es (más o menos) uniforme , y si lo único que le importa es la uniformidad de esa distribución , está bien. El punto de la pregunta era: ¿hay otras cosas aparte de esa distribución PRNG(6)que nos interesan? Y la respuesta es sí . También nos preocupamos por la imprevisibilidad .

Otra forma de ver el problema es que, aunque la distribución de un millón de llamadas PRNG(6)podría estar bien, porque el PRNG está eligiendo entre solo 2 ³² posibles comportamientos, no puede generar todos los mazos posibles. Solo puede generar 2 ³² de los 2 ²²⁶ mazos posibles; Una pequeña fracción. Por lo tanto, la distribución en el conjunto de todos los mazos es muy mala. Pero nuevamente, el ataque fundamental aquí se basa en nuestra capacidad de predecir con éxito el comportamiento pasado y futuro de PRNGuna pequeña muestra de su producción.

Permítanme decir esto una tercera o cuatro veces para asegurarse de que esto se asimile. Hay tres distribuciones aquí. Primero, la distribución del proceso que produce la semilla aleatoria de 32 bits. Eso puede ser perfectamente aleatorio, impredecible y uniforme, y el ataque seguirá funcionando . En segundo lugar, la distribución de un millón de llamadas a PRNG(6). Eso puede ser perfectamente uniforme y el ataque seguirá funcionando. Tercero, la distribución de mazos elegidos por el proceso pseudoaleatorio que he descrito. Esa distribución es extremadamente pobre; solo se puede elegir una pequeña fracción de los posibles mazos IRL. El ataque depende de la previsibilidad del comportamiento del PRNG en función del conocimiento parcial de su salida .

A UN LADO: Este ataque requiere que el atacante sepa o pueda adivinar cuál es el algoritmo exacto utilizado por el PRNG. Si eso es realista o no es una pregunta abierta. Sin embargo, al diseñar un sistema de seguridad, debe diseñarlo para que sea seguro contra ataques, incluso si el atacante conoce todos los algoritmos del programa . Dicho de otra manera: la parte de un sistema de seguridad que debe permanecer en secreto para que el sistema sea seguro se llama "clave". Si su sistema depende de su seguridad en los algoritmos que usa como secretos, entonces su clave contiene esos algoritmos . ¡Esa es una posición extremadamente débil para estar!

Hacia adelante.

Ahora supongamos que tenemos una tercera caja mágica etiquetada CPRNG. Es una versión de fuerza criptográfica de PRNG. Se necesita una semilla de 256 bits en lugar de una semilla de 32 bits. Comparte con PRNGla propiedad que la semilla elige entre uno de los 2 ²⁵⁶ posibles comportamientos. Y al igual que nuestras otras máquinas, tiene la propiedad de que una gran cantidad de llamadas CPRNG(n)producen una distribución uniforme de resultados entre 1 yn: cada una ocurre 1 / n de las veces. ¿Podemos ejecutar nuestro ataque contra él?

Nuestro ataque original requiere que almacenemos 2 ³² asignaciones de semillas a PRNG(52). Pero 2 ²⁵⁶ es un número mucho mayor; es completamente inviable ejecutar CPRNG(52)eso muchas veces y almacenar los resultados.

Pero supongamos que hay alguna otra forma de tomar el valor CPRNG(52)y de eso deducir un hecho acerca de la semilla. Hasta ahora hemos sido bastante tontos, forzando a todas las combinaciones posibles. ¿Podemos mirar dentro de la caja mágica, descubrir cómo funciona y deducir datos sobre la semilla en función de la salida?

No. Los detalles son demasiado complicados de explicar, pero los CPRNG están inteligentemente diseñados para que no sea factible deducir ningún hecho útil sobre la semilla desde el primer resultado CPRNG(52)o desde cualquier subconjunto del resultado, sin importar cuán grande sea .

Bien, ahora supongamos que el servidor está usando CPRNGpara generar mazos. Necesita una semilla de 256 bits. ¿Cómo elige esa semilla? Si elige cualquier valor que un atacante pueda predecir , de repente el ataque vuelve a ser viable . Si podemos determinar que de las 2 ²⁵⁶ semillas posibles, es probable que solo cuatro mil millones de ellas sean elegidas por el servidor, entonces estamos de vuelta en el negocio . Podemos montar este ataque nuevamente, solo prestando atención a la pequeña cantidad de semillas que posiblemente se pueden generar.

Por lo tanto, el servidor debe trabajar para garantizar que el número de 256 bits se distribuya de manera uniforme , es decir, cada semilla posible se elige con una probabilidad de 1/2 ²⁵⁶ . Básicamente, el servidor debería llamar TRNG(2^256)-1para generar la semilla CPRNG.

¿Qué sucede si puedo hackear el servidor y mirarlo para ver qué semilla se eligió? En ese caso, el atacante conoce el pasado y el futuro completos del CPRNG . ¡El autor del servidor debe protegerse contra este ataque! (Por supuesto, si puedo montar con éxito este ataque, entonces probablemente también pueda transferir el dinero directamente a mi cuenta bancaria, así que tal vez eso no sea tan interesante. El punto es: la semilla debe ser un secreto difícil de adivinar, y un un número verdaderamente aleatorio de 256 bits es bastante difícil de adivinar).

Volviendo a mi punto anterior sobre la defensa en profundidad: la semilla de 256 bits es la clave de este sistema de seguridad. La idea de un CPRNG es que el sistema es seguro siempre que la clave sea segura ; incluso si se conoce cualquier otro hecho sobre el algoritmo, siempre que pueda mantener la clave secreta, las cartas del oponente son impredecibles.

OK, entonces la semilla debe ser secreta y distribuida uniformemente porque si no es así, podemos lanzar un ataque. Suponemos que la distribución de las salidas de CPRNG(n)es uniforme. ¿Qué pasa con la distribución sobre el conjunto de todas las cubiertas posibles?

Podría decir: el CPRNG emite 2 ²⁵⁶ secuencias posibles, pero solo hay 2 ²²⁶ mazos posibles. Por lo tanto, hay más secuencias posibles que mazos, así que estamos bien; ahora es posible (con alta probabilidad) cada mazo de IRL posible en este sistema. Y ese es un buen argumento, excepto ...

2 ²²⁶ es solo una aproximación de 52 !. Divídelo. 2 ^256/52 ! no puede ser un número entero porque, por un lado, ¡52! es divisible por 3 pero no hay potencia de dos Como este no es un número entero ahora, tenemos la situación de que todas las cubiertas son posibles , pero algunas cubiertas son más probables que otras .

Si eso no está claro, considere la situación con números más pequeños. Supongamos que tenemos tres cartas, A, B y C. Supongamos que usamos un PRNG con una semilla de 8 bits, por lo que hay 256 semillas posibles. Hay 256 salidas posibles PRNG(3)dependiendo de la semilla; no hay forma de que un tercio de ellos sea A, un tercio de ellos sea B y un tercio de ellos sea C porque 256 no es divisible de manera equitativa entre 3. Tiene que haber un pequeño sesgo hacia uno de ellos.

Del mismo modo, 52 no se divide de manera equitativa en 2 ²⁵⁶ , por lo que debe haber algún sesgo hacia algunas cartas como la primera carta elegida y un sesgo lejos de otras.

En nuestro sistema original con una semilla de 32 bits hubo un sesgo masivo y la gran mayoría de los mazos posibles nunca se produjeron. En este sistema, se pueden producir todas las cubiertas, pero la distribución de las cubiertas sigue siendo defectuosa . Algunas cubiertas son muy ligeramente más probables que otras.

Ahora la pregunta es: ¿tenemos un ataque basado en este defecto? y la respuesta está en la práctica, probablemente no . Los CPRNG están diseñados para que, si la semilla es verdaderamente aleatoria , no sea factible computarizar diferenciar entre CPRNGy TRNG.

OK, así que resumámoslo.

¿Cómo difieren los números pseudoaleatorios y los números verdaderamente aleatorios?

Difieren en el nivel de previsibilidad que exhiben.

• Los números verdaderamente aleatorios no son predecibles.
• Todos los números pseudoaleatorios son predecibles si la semilla se puede determinar o adivinar.

¿Por qué es importante la diferencia?

Porque hay aplicaciones donde la seguridad del sistema depende de la imprevisibilidad .

• Si se usa un TRNG para elegir cada tarjeta, entonces el sistema es inatacable.
• Si se utiliza un CPRNG para elegir cada tarjeta, entonces el sistema es seguro si la semilla es impredecible y desconocida.
• Si se utiliza un PRNG ordinario con un pequeño espacio inicial, entonces el sistema no es seguro independientemente de si la semilla es impredecible o desconocida; un espacio de semillas lo suficientemente pequeño es susceptible a los ataques de fuerza bruta del tipo que he descrito.

¿La diferencia tiene algo que ver con la distribución de la salida del PRNG?

La uniformidad de la distribución o la falta del mismo para llamadas individuales a RNG(n)no es relevante para los ataques que he descrito.

Como hemos visto, tanto a PRNGcomo CPRNGproducen distribuciones pobres de la probabilidad de elegir cualquier mazo individual de todos los mazos posibles. El PRNGes considerablemente peor, pero ambos tienen problemas.

Una pregunta más:

Si TRNG es mucho mejor que CPRNG, que a su vez es mucho mejor que PRNG, ¿por qué alguien usa CPRNG o PRNG?

Dos razones.

Primero: gastos. TRNG es caro . Generar números verdaderamente aleatorios es difícil. Los CPRNG dan buenos resultados para muchas llamadas arbitrarias con solo una llamada a TRNG para la semilla. La desventaja es que debes mantener esa semilla en secreto .

Segundo: a veces queremos previsibilidad y lo único que nos importa es una buena distribución. Si está generando datos "aleatorios" como entradas de programa para un conjunto de pruebas, y muestra un error, entonces sería bueno que ejecutar el conjunto de pruebas nuevamente produzca el error.

Espero que ahora esté mucho más claro.

Finalmente, si disfrutaste esto, entonces podrías disfrutar de una lectura adicional sobre el tema de la aleatoriedad y las permutaciones:

• Supongamos que tengo datos aleatorios distribuidos uniformemente. ¿Cómo lo transformo en una distribución no uniforme dada?
• ¿Por qué se generan algunos GUID al azar? ¿Son todos sus bits al azar? (No.) ¿Puedo confiar en un GUID como fuente de aleatoriedad verdadera? (¡No!)
• ¿Cómo puedo generar grandes números aleatorios usando notación factoradic?
  • ¿Cómo puedo convertir eso en una permutación aleatoria?
• ¿Cómo podemos montar el ataque descrito aquí contra la permutación aleatoria?
• La cantidad de sesgo se introduce mediante el uso de la técnica resto de implementar RNG(n)?

Como dice Eric Lippert, no se trata solo de distribución. Hay otras formas de medir la aleatoriedad.

Uno de los primeros generadores de números aleatorios tiene una secuencia en el bit menos significativo: alternaba 0 y 1. Por lo tanto, el LSB era 100% predecible. Pero debes preocuparte por más que eso. Cada bit debe ser impredecible.

Aquí hay una buena manera de pensar sobre el problema. Digamos que estás generando 64 bits de aleatoriedad. Para cada resultado, tome los primeros 32 bits (A) y los últimos 32 bits (B), y cree un índice en una matriz x [A, B]. Ahora realice la prueba un millón de veces y, para cada resultado, incremente la matriz en ese número, es decir, X [A, B] ++;

Ahora dibuje un diagrama 2D, donde cuanto mayor sea el número, más brillante será el píxel en esa ubicación.

Si es realmente aleatorio, el color debe ser gris uniforme. Pero podrías obtener patrones. Tomemos por ejemplo este diagrama de "aleatoriedad" en el número de secuencia TCP del sistema Windows NT:

o incluso este de Windows 98:

Y aquí está la aleatoriedad de la implementación del enrutador Cisco (IOS).

Estos diagramas son cortesía del artículo de Michał Zalewski . En este caso particular, si uno puede predecir cuál será el número de secuencia TCP de un sistema, uno puede hacerse pasar por ese sistema cuando realiza una conexión a otro sistema, lo que permitiría el secuestro de conexiones, la interceptación de la comunicación, etc. E incluso si nosotros no podemos predecir el próximo número el 100% del tiempo, si podemos hacer que se cree una nueva conexión bajo nuestro control , podemos aumentar las posibilidades de éxito. Y cuando las computadoras pueden generar 100,000 conexiones en unos pocos segundos, las probabilidades de un ataque exitoso van de astronómico a posible o incluso probable.

Si bien los números pseudoaleatorios generados por las computadoras son aceptables para la mayoría de los casos de uso encontrados por los usuarios de computadoras, hay escenarios que requieren números aleatorios completamente impredecibles.

En aplicaciones sensibles a la seguridad, como el cifrado, un generador de números pseudoaleatorios (PRNG) puede producir valores que, aunque de apariencia aleatoria, de hecho son predecibles por un atacante. Alguien que intente descifrar un sistema de cifrado puede adivinar las claves de cifrado si se utilizó un PRNG y el atacante tiene información sobre el estado del PRNG. Por lo tanto, para tales aplicaciones, es necesario un generador de números aleatorios que produzca valores que no sean cuestionables. Tenga en cuenta que algunos PRNG están diseñados para ser criptográficamente seguros y son utilizables para aplicaciones sensibles a la seguridad.

Se puede encontrar más información sobre los ataques RNG en este artículo de Wikipedia .

Lo probé en Python: aquí está el resultado de 60 millones de rollos. La variación más alta es como 0.15. ¿No es eso tan aleatorio como va a ser?

En realidad, es tan "bueno" que es malo ... Todas las respuestas existentes se centran en la previsibilidad dada una pequeña secuencia de valores iniciales. Quiero plantear otro problema:

    su distribución tiene una desviación estándar mucho menor que las tiradas aleatorias

Aleatoriedad real simplemente no viene bastante que cerca de un promedio de "casi exactamente 1 sobre cómo cada vez los números de muchos puede elegir entre" que está utilizando como una indicación de la calidad.

Si observa esta pregunta de Stack Exchange sobre distribuciones de probabilidad para múltiples tiradas de dados , verá una fórmula para la desviación estándar de N tiradas de dados (suponiendo resultados genuinamente aleatorios):

 sqrt(N * 35.0 / 12.0).

Usando esa fórmula, la desviación estándar para:

• 1 millón de rollos es 1708
• 60 millones de rollos son 13229

Si miramos sus resultados:

• 1 millón de rollos: stddev (1000066, 999666, 1001523, 999452, 999294, 999999) es 804
• 60 millones de rollos: stddev (9997653, 9997789, 9996853, 10006533, 10002774, 9998398) es 3827

No puede esperar que la desviación estándar de una muestra finita coincida exactamente con la fórmula, pero debería acercarse bastante. Sin embargo, con 1 millón de rollos tiene menos de la mitad del estándar adecuado, y en 60 millones tiene menos de un tercio, está empeorando, y eso no es una coincidencia ...

Los pseudo-RNG tienden a moverse a través de una secuencia de números distintos, comenzando con la semilla y sin volver a visitar el número original durante un período específico. Por ejemplo, las implementaciones de la antigua rand()función de biblioteca C generalmente tienen un período de 2 ^ 32, y visitarán cada número entre 0 y 2 ^ 32-1 exactamente una vez antes de repetir la semilla. Entonces, si simulaste 2 ^ 32 dados tira el pre-módulo (%) los resultados incluirían cada número de 0 a 2 ^ 32, los recuentos para cada resultado 1-6 serían 715827883 o 715827882 (2 ^ 32 no es un múltiplo de 6), y la desviación estándar por lo tanto solo trivialmente por encima de 0. Uso según la fórmula anterior, la desviación estándar correcta para 2 ^ 32 rollos es 111924. De todos modos, a medida que aumenta su número de rolos pseudoaleatorios, converge hacia 0 desviación estándar. Se puede esperar que el problema sea significativo cuando el número de rollos es una fracción significativa del período, pero algunos pseudo-RNG pueden presentar problemas peores, o incluso con menos muestras, que otros.

Por lo tanto, incluso si no le importan las vulnerabilidades criptográficas, en algunas aplicaciones puede interesarle tener distribuciones que no tengan resultados excesivos, incluso artificiales. Algunos tipos de simulación están tratando de resolver las consecuencias de los resultados desiguales que ocurren naturalmente con grandes muestras de resultados aleatorios individuales, pero están subrepresentados en algunos resultados de pRNG. Si está tratando de simular cómo reacciona una gran población ante algún evento, este problema podría alterar radicalmente sus resultados y conducir a conclusiones extremadamente inexactas.

Para dar un ejemplo concreto: Digamos que un matemático le dice a un programador de máquinas de póker que después de 60 millones de tiradas simuladas, solía parpadear cientos de pequeñas "luces" alrededor de la pantalla, si ha habido 10,013,229 o más seises, que el matemático espera que sean 1 stddev lejos de la media, debería haber un pequeño pago. De acuerdo con la regla 68–95–99.7 (Wikipedia), esto debería suceder aproximadamente el 16% del tiempo (~ 68% cae dentro de una desviación estándar / solo la mitad afuera está arriba). Con su generador de números aleatorios, esto es de aproximadamente 3.5 desviaciones estándar por encima de la media: Menos de 0.025% de probabilidad: casi ningún cliente obtiene este beneficio. Consulte la tabla Desviaciones más altas en la página que se acaba de mencionar, específicamente:

| Range    | In range   | Outside range | Approx. freq. for daily event  |
| µ ± 1σ   | 0.68268... | 1 in 3        | Twice a week                   |
| µ ± 3.5σ | 0.99953... | 1 in 2149     | Every six years                |

Acabo de escribir este generador de números aleatorios para generar tiradas de dados

def get_generator():
  next = 1
  def generator():
    next += 1
    if next > 6:
      next = 1
    return next
  return generator

Lo usas así

>> generator = get_generator()
>> generator()
1
>> generator()
2
>> generator()
3
>> generator()
4
>> generator()
5
>> generator()
6
>> generator()
1

etc. ¿Estaría encantado de usar este generador para un programa que ejecutara un juego de dados? ¡Recuerde, su distribución es exactamente lo que esperaría de un generador "verdaderamente aleatorio"!

Los generadores de números pseudoaleatorios hacen esencialmente lo mismo: generan números predecibles con la distribución correcta. Son malos por la misma razón que el generador de números aleatorios simplista anterior es malo: no son adecuados para situaciones en las que necesita una imprevisibilidad genuina, no solo la distribución correcta.

La generación de números aleatorios que puede realizar su computadora es adecuada para la mayoría de las necesidades, y es poco probable que encuentre un momento en el que necesite un número verdaderamente aleatorio.

Sin embargo, la verdadera generación de números aleatorios tiene sus propósitos. En seguridad informática, juegos de azar, gran muestreo estadístico, etc.

Si está interesado en las aplicaciones de números aleatorios, consulte el artículo de Wikipedia .

Los números aleatorios generados por funciones típicas en la mayoría de los lenguajes de programación no son números puramente aleatorios. Son números pseudoaleatorios. Como no son números puramente aleatorios, se puede adivinar con suficiente información sobre números generados previamente. Entonces esto será un desastre para la seguridad en criptografía .

Por ejemplo, la siguiente función de generador de números aleatorios utilizada glibcno genera un número puramente aleatorio. El número seudoaleatorio generado por esto se puede adivinar. Es un error para los problemas de seguridad. Hay una historia de que esto se ha vuelto desastroso. Esto no debe usarse en criptografía.

glibc random():
    r[i] ← ( r[i-3] + r[i-31] )  % (2^32)
    output  r[i] >> 1

Este tipo de generador de números pseudoaleatorios nunca debe usarse en lugares sensibles a la seguridad, aunque sea estadísticamente muy significativo.

Uno de los famosos ataques en clave pseudoaleatoria es el ataque en 802.11b WEP . WEP tiene una clave a largo plazo de 104 bits, concatenada con IV de 24 bits (contador) para hacer una clave de 128 bits, que a su vez se aplica al algoritmo RC4 para generar una clave seudoaleatoria.

( RC4( IV + Key ) ) XOR (message)

Las teclas estaban estrechamente relacionadas entre sí. Aquí, solo IV aumentó en 1 en cada paso y todos los demás permanecieron iguales. Como esto no fue puramente aleatorio, fue desastroso y se desglosó fácilmente. La clave podría recuperarse analizando aproximadamente 40000 cuadros, que es cuestión de minutos. Si el WEP usara IV de 24 bits puramente aleatorio, entonces podría ser seguro hasta aproximadamente 2 ^ 24 (casi 16.8 millones) de cuadros.

Por lo tanto, uno debe ir con un generador de números aleatorios puros en cuestiones sensibles a la seguridad cuando sea posible.

La diferencia es que los números generados pseudoaleatorios son predecibles (se repiten) después de un tiempo en que los números aleatorios verdaderos no lo son. La longitud que se tarda en repetir depende de la longitud de la semilla que se utiliza para su generación.

Aquí hay un video bastante agradable sobre ese tema: http://www.youtube.com/watch?v=itaMNuWLzJo

Suponga que cualquier persona puede adivinar un número pseudoaleatorio antes de que se genere.

Para aplicaciones triviales, una pseudoaleatoriedad está bien, como con su ejemplo, obtendrá aproximadamente el porcentaje correcto (aproximadamente 1/6 del conjunto de resultados total) con alguna variación menor (que vería si tirara un dado 600k veces);

Sin embargo, cuando se trata de cosas como la seguridad informática; Se requiere verdadera aleatoriedad.

Por ejemplo, el algoritmo RSA comienza con la computadora eligiendo dos números aleatorios (P y Q) y luego realizando varios pasos para esos números para generar los números especiales conocidos como sus claves públicas y privadas. (¡La parte importante de una clave privada es que es privada y nadie más lo sabe!)

Si un atacante puede saber cuáles son los dos números 'aleatorios' que su computadora va a elegir, puede hacer los mismos pasos para calcular su clave privada (¡la que se supone que nadie más debe saber!)

Con su clave privada, un atacante puede hacer cosas como a) Hable con su banco fingiendo ser usted, b) Escuche su tráfico de Internet 'seguro' y pueda decodificarlo, c) Disfrazarse entre usted y otras partes en Internet.

Ahí es donde se requiere una verdadera aleatoriedad (es decir, no poder adivinar / calcular).

El primer número aleatorio que utilicé tenía la excelente propiedad de que de dos números aleatorios consecutivos, el segundo era más grande con una probabilidad de 0.6. No 0.5. Y el tercero era más grande que el segundo con probabilidad 0.6, y así sucesivamente. Puedes imaginar cómo eso causa estragos con una simulación.

Algunas personas no me creerían que esto fuera posible incluso con los números aleatorios distribuidos por igual, pero obviamente es posible si observamos la secuencia (1, 3, 5, 2, 4, 1, 3, 5, 2, 4, ...) donde el segundo de dos números es mayor con probabilidad 0.6.

Por otro lado, para las simulaciones puede ser importante poder reproducir números aleatorios. Supongamos que hace una simulación de tráfico y quiere saber cómo algunas acciones que podría tomar podrían mejorar el tráfico. En ese caso, desea poder volver a crear exactamente los mismos datos de tráfico (como las personas que intentan ingresar a una ciudad) con diferentes acciones que intentó mejorar el tráfico.

La respuesta corta es que, por lo general, las personas requieren "verdadera aleatoriedad" por una mala razón, es decir, que no entienden la criptografía.

Las primitivas criptográficas, como los cifrados de flujo y los CSPRNG, se utilizan para producir grandes flujos de bits impredecibles una vez que se han alimentado con unos pocos bits impredecibles.

El lector cuidadoso ahora se habrá dado cuenta de que hay un problema de arranque aquí: debemos reunir algunos bits de entropía para comenzar todo. Luego, puede alimentarlos a un CSPRNG que a su vez proporcionará felizmente todos los bits impredecibles que necesitamos. Por lo tanto, se requiere un RNG de hardware para sembrar un CSPRNG . Este es el único caso donde la entropía se requiere en verdad.

(Creo que esto debería haberse publicado en Seguridad o Criptografía).

Editar: Al final, uno debe seleccionar un generador de números aleatorios que sea lo suficientemente bueno para la tarea prevista y, en lo que respecta a la generación de números aleatorios, el hardware no necesariamente equivale a bueno. Al igual que los PRNG malos, las fuentes aleatorias de hardware generalmente tienen sesgos.

Editar: Algunas personas aquí asumen un modelo de amenaza en el que un atacante podría leer el estado interno de un CSPRNG y, a partir de ahí, llegar a la conclusión de que los CSPRNG no son una solución segura. Este es un ejemplo de modelado de subprocesos deficiente. Si un atacante posee su sistema, el juego ha terminado, simple y llanamente. No hace ninguna diferencia si usa un TRNG o un CSPRNG en este momento.

Editar: Entonces, para resumir todo esto ... Se requiere entropía para sembrar un CSPRNG. Una vez hecho esto, un CSPRNG proporcionará todos los bits impredecibles que necesitamos para aplicaciones de seguridad mucho más rápido de lo que podemos (generalmente) recolectar entropía. Si no se requiere imprevisibilidad, como para la simulación, un Mersenne Twister proporcionará números con buenas propiedades estadísticas a una tasa mucho más alta.

Editar: Cualquiera que esté dispuesto a comprender el problema de la generación segura de números aleatorios debe leer esto: http://www.cigital.com/whitepapers/dl/The_Importance_of_Reliable_Randomness.pdf

No todos los PRNG son adecuados para todos los usos. Por ejemplo, Java.util.SecureRandom usa el hash SHA1, que tiene un tamaño de salida de 160 bits. Eso significa que hay 2 ¹⁶⁰ secuencias posibles de números aleatorios que pueden provenir de él. Simple como eso. No puede obtener más de 2 ¹⁶⁰ valores del estado interno. Por lo tanto, no puede obtener más de 2 ¹⁶⁰ secuencias únicas de números aleatorios de una sola semilla, sin importar de dónde provenga su semilla. Se cree que Windows CryptGenRandom usa un estado de 40 bytes, tiene 2 ³²⁰ posibles secuencias de números aleatorios.

El número de formas de barajar un mazo estándar de 52 cartas es 52 !, que es aproximadamente ²²²⁶ . Por lo tanto, independientemente de la siembra, no puede usar Java.util.SecureRandom para barajar una baraja de cartas. Hay aproximadamente 2 ⁶⁶ barajaduras posibles que no puede producir. Por supuesto, no sabemos cuáles son ...

Entonces, si tuviera una fuente de, digamos, 256 bits de aleatoriedad verdadera (por ejemplo, de una tarjeta Quantis RNG), podría sembrar un PRNG como CryptGenRandom () con esa semilla y luego usar el PRNG para barajar un mazo de tarjetas Si vuelvo a plantear con verdadera aleatoriedad cada barajado, esto estará bien: impredecible y estadísticamente aleatorio. Si hiciera lo mismo con Java.util.SecureRandom, habría barajaduras que posiblemente no podrían producirse, porque no se puede sembrar con 256 bits de entropía, y su estado interno no puede representar todas las barajaduras posibles.

Tenga en cuenta que los resultados java.util.SecureRandom serían impredecibles y estadísticamente aleatorios. ¡Ninguna prueba estadística identificaría un problema! Pero la salida del RNG no es lo suficientemente grande como para cubrir el dominio completo de todas las salidas posibles necesarias para simular una baraja de cartas.

Y recuerda, si agregas los comodines, ¡son 54! que tienes que cubrir, lo que requiere alrededor de 2 ²³⁸ posibilidades.

Los números pseudoaleatorios se generan usando una función matemática y un valor inicial (llamado semilla ), mientras que los números aleatorios no. Su previsibilidad los hace increíblemente útiles para las repeticiones del juego, ya que solo necesita guardar la semilla y la entrada del jugador: la IA responderá exactamente de la misma manera "aleatoria" cada vez.

La diferencia entre un número aleatorio "verdadero" y un número aleatorio "pseudo" es la previsibilidad. Esta respuesta ya ha sido proporcionada.

Sin embargo, la previsibilidad no es necesariamente algo malo como muestran la mayoría de los ejemplos. Aquí hay un ejemplo práctico de uno de los raros casos en los que la previsibilidad es buena: el Sistema de Posicionamiento Global.

Cada satélite utiliza un código PRN distinto (los códigos Gold ) adecuados para la correlación automática o la correlación cruzada que es necesaria para la medición del tiempo de propagación de la señal. Para estos códigos Gold, la correlación entre ellos es particularmente débil, lo que hace posible una identificación inequívoca del satélite, pero permite el cálculo de la distancia mediante la correlación entre la secuencia emitida y el receptor.

Para una verificación rápida de la aleatoriedad, toma puntos con coordenadas aleatorias en [0; 1) y luego los coloca en un cubo k-dimensional. Luego realice el procedimiento para cortar este cubo en subcubos: cada volumen de subcubo (o subsfera) debe medirse correctamente mediante este procedimiento con fluctuaciones de acuerdo con un teorema bien conocido.

La calidad de la aleatoriedad es importante donde te encuentras ...

1. propósitos de seguridad. Cuando genera un número para usarlo como parámetro para su generación de claves, y es bien predecible, el enemigo lo descubrirá con un 100% de probabilidad y hará que el campo de búsqueda sea mucho más pequeño.

2. fines científicos En ciencia, no solo debe tener una media promedio en buenas condiciones, sino que también deben eliminarse las correlaciones entre varios números aleatorios. Entonces, si toma (a_i - a) (a_ {i + 1} -a) y encuentra su distribución, debe corresponder a las estadísticas.

La correlación de pares se llama "aleatoriedad débil". Si desea aleatoriedad real, debe tener una correlación de alto orden con más de 2 variaciones.

Actualmente, solo los generadores de mecánica cuántica proporcionan una aleatoriedad verdadera.

¿Por qué es importante la aleatoriedad verdadera?

Básicamente, hay dos razones principales por las que es necesaria una aleatoriedad verdadera:

1. Si está utilizando el RNG para la criptografía (incluidas cosas como el juego con dinero real y la realización de una lotería), un PRNG lo hará mucho más débil que el análisis matemático (que supone un TRNG) lo haría creer. El PRNG en realidad no será aleatorio, pero tendrá un patrón: los adversarios pueden explotar el patrón para descifrar un cifrado que debería haber sido indescifrable.
2. Si está utilizando el RNG para simular entradas "aleatorias", por ejemplo, para prueba de errores o simulación, entonces un PRNG debilita su enfoque. Cuando descubra que no hay errores, siempre habrá esa duda persistente: ¿hay algún error que no sea notable con el patrón de mi PRNG, pero que hubiera aparecido si solo hubiera usado un TRNG? ¿El hallazgo de mi simulación describe con precisión la realidad, o es el fenómeno que descubrí simplemente un artefacto del patrón del PRNG?

Fuera de estas áreas, realmente no importa. Advertencia: si tu PRNG es muy, muy malo, puede que aún no sea adecuado: no quieres hacer un juego de Craps donde los dados siempre salgan parejos, a tus jugadores no les gustaría.

¿Cómo es que el PRNG de Python no es lo suficientemente bueno?

Es muy poco probable que pueda detectar las trampas de un PRNG real utilizando una metodología tan simple. El análisis estadístico de los RNG es un campo de la ciencia en sí mismo, y algunas pruebas muy sofisticadas están disponibles para comparar la "aleatoriedad" de un algoritmo. Estos son mucho más avanzados que su simple intento.

Todos los desarrolladores de software que crean bibliotecas del mundo real, como los desarrolladores de Python, usan estas pruebas estadísticas como criterio para ver si su implementación de PRNG es lo suficientemente buena. Por lo tanto, a excepción de los casos de supervisión real del desarrollador, es muy poco probable que pueda detectar fácilmente un patrón en un PRNG del mundo real. Eso no significa que no haya un patrón, un PRNG tiene un patrón por definición.

Básicamente, no puede probar que una fuente es aleatoria mediante el análisis matemático de la salida, necesita, por ejemplo, un modelo físico que diga que la fuente es aleatoria (como en la desintegración radiactiva).

Simplemente puede ejecutar pruebas por lotes para encontrar la correlación estadística en los datos de salida, en ese caso, se demuestra que los datos no son aleatorios (pero también una fuente aleatoria puede tener salidas no aleatorias, o no será realmente aleatoria si no puede proporcionar datos específicos salida). De lo contrario, si se pasan las pruebas, puede decir que los datos son pseudoaleatorios.

Pasar algunas pruebas de aleatoriedad solo significa que tiene un buen PRNG (generador de números pseudoaleatorios), que puede ser útil para aplicaciones donde la seguridad no está involucrada.

Si se trata de seguridad (es decir, cifrado, generación de una clave, generación de números aleatorios para juegos de azar ...) no es suficiente tener un buen PRNG, necesita tener cualidades adicionales, como que la salida de la función no se adivina fácilmente de las salidas anteriores, la función debe tener un costo computacional deseable (lo suficientemente limitado como para ser utilizable, pero lo suficientemente alto como para vencer los intentos de fuerza bruta), el hardware que ejecuta la función, o el dispositivo, en el extraño caso de hoy es un dispositivo analógico, no debería ser manipulado fácilmente, etc.

Tener un buen PRNG puede ser útil en los juegos para crear patrones nuevos e impredecibles, y en el cifrado, demasiado engorroso para explicar en una sola publicación, solo piense como un papel que el proceso de cifrado debe ser seudoaleatorio, sin mostrar patrones eso podría relacionar datos cifrados anteriores con los siguientes datos cifrados, o relacionar datos de texto sin formato con datos cifrados, o relacionar dos textos cifrados diferentes entre sí (para que se puedan hacer conjeturas en los textos sin formato) ...

Cuento:

Genera una semilla aleatoria utilizando el microsegundo actual del sistema.

Este truco es bastante antiguo y sigue siendo funcional.

Excluyendo el factor de fuerza bruta, donde puedo determinar cada combinación "apostando" en todos los números posibles y no es el punto de esta pregunta, especialmente cuando la mayoría de los números aleatorios se redondean antes de su uso.

Digamos un ejemplo, puedo determinar la semilla utilizada usando solo 10 valores. Entonces, conociendo la semilla, puedo adivinar el siguiente valor.

Si usara la semilla = 1, entonces podría obtener la siguiente secuencia:

1, 2, 3, 4, 5, 6, 7, 8, 9 ... (y deduzco que la semilla usó id 1 y el siguiente valor 10)

Pero, ¿qué pasará si se cambia el envío de todos los valores "enésimos"? Cambiar la semilla por los microsegundos actuales es un truco barato (es decir, no requiere muchos ciclos de CPU).

Entonces la secuencia ahora es: (semilla = 1) 1, 2, 3, 4, 5, (semilla = 2), 7, 9, 11, 13 ... (15?)

En este caso:

a) No puedo deducir qué semilla se usó.

b) Ergo, no puedo adivinar el siguiente valor.

c) La única suposición que puedo hacer es deducir que la próxima semilla podría ser un número mayor.

De todos modos, los algoritmos de generador aleatorio más modernos ya usan este truco bajo el capó.

El hecho real es que, no necesitamos una computadora cuántica para crear un número aleatorio "verdadero", la imprecisión de nuestro cristal de cuarzo de nuestra computadora actúa como un generador aleatorio, también la eficiencia aleatoria de nuestra CPU también es variable sin tener en cuenta que la CPU generalmente realiza varias tareas al mismo tiempo.