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

664

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
Peter
fuente
1
Eche un vistazo al artículo de Wikipedia sobre números aleatorios generados por hardware. También vea esto - stats.stackexchange.com/questions/32794/…
steadyfish
21
¿Qué quieres decir con "tira algunos dados"? ¿Tiene un brazo robot y una cámara conectados?
Starblue
3
Si bien estoy de acuerdo con la esencia general de su tono, que a menudo nos preocupamos demasiado por esto, pero ha sido explotado en la vida real: en.wikipedia.org/wiki/Ronald_Dale_Harris
Grady Player
3
Vea este artículo sobre un juego de póker en línea que carece de aleatoriedad verdadera por qué es importante.
Varaquilex
1
Si mantienes un contador de 0-5 y lanzas un dado en consecuencia, 666 billones de veces, también obtendrás una distribución igual.
jcora

Respuestas:

1382

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 226 . 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 32 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 32 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 32 -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 . 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 32 posibles comportamientos, no puede generar todos los mazos posibles. Solo puede generar 2 32 de los 2 226 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 256 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 32 asignaciones de semillas a PRNG(52). Pero 2 256 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 256 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 256 . 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 256 secuencias posibles, pero solo hay 2 226 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 226 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 256 , 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:

Eric Lippert
fuente
20
Ok chicos y chicas. Eso es suficiente comentar por ahora. Si quieres hablar más sobre esto, ve a buscar una sala de chat, kthnxbye.
Ivo Flipse
1
@Eric Pero la semilla no se reinicia antes de cada nuevo sorteo, ¿verdad? Entonces, si bien tiene razón en que solo hay relativamente pocas trayectorias de las que estamos tomando muestras, no sabe exactamente en qué parte de la trayectoria se encuentra en el momento y las trayectorias se cruzan.
AS
Un buen (pero denso) tratamiento de los problemas relacionados se encuentra en el TAOCP vol. 2 de Knuth, sección 3.5 "¿Qué es una secuencia aleatoria?" (P. 149), comenzando con definiciones esclarecedoras de secuencias equidistribuidas, distribuidas en k y distribuidas en ∞. Las secuencias pseudoaleatorias se analizan en 3.5.F (p. 170). Ver también criterios de pseudoaleatoriedad de teoría de la complejidad y la BSI alemán .
ShreevatsaR
160

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:

Windows NT

o incluso este de Windows 98:

Windows 98

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

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.

Bruce Barnett
fuente
30
Esto es tan brillante que me hace llorar. Debería haber una aplicación que los cree para cada sistema operativo (móvil / escritorio / servidor) y plataforma (JVM / Javascript / etc.).
HDave
55
¡La función rand () de Windows es bastante buena! Produce una nube que no tiene ningún patrón aparente. Vea mi implementación para probarlo (y otros algoritmos): github.com/Zalastax/visualize_random
Zalastax
93

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 .

bwDraco
fuente
99
Existen PRNG criptográficos, y son ampliamente utilizados. A partir de una semilla de tamaño modesto pueden generar un flujo prácticamente ilimitado de números aleatorios. Es computacionalmente inviable distinguir dicha secuencia de números aleatorios verdaderos, por lo tanto, no se puede obtener información adicional de ninguna parte de dicha secuencia, y para cualquier propósito práctico los números son tan buenos como los números aleatorios verdaderos.
aaaaaaaaaaaa
Creo que la forma más fácil de explicar esto es que los algoritmos generadores de números aleatorios tienen que ser programados. Eso significa que hay un conjunto de instrucciones que se siguen. Si hay un conjunto de instrucciones, no puede ser al azar.
Keltari
66
@Keltari Te estás perdiendo el elemento de entropía ... La mayoría de los RNG (al menos los criptográficos) recopilan información de fuentes externas (p. Ej., Movimiento del mouse) y la usan como parte de la condición inicial, por lo tanto, la transformación de Aa Bestá programada, pero El estado inicial de A(debería) ser indiscutible. Linux /dev/randommantendrá una aproximación de cuánta entropía está disponible y dejará de dar números si cae demasiado.
Básico
Por curiosidad, ¿por qué las lámparas de lava se consideran "verdaderamente aleatorias"? Entiendo que exhibe un comportamiento bastante impredecible, pero alguien con una comprensión lo suficientemente firme de la dinámica de los fluidos y cómo interactúan esos fluidos en el entorno gravitacional de la Tierra seguramente puede producir resultados "predecibles", ¿no? Claro, las lámparas de lava son impredecibles, pero para mí, no son aleatorias en absoluto, sino altamente predecibles.
theGreenCabbage
1
@ theGreenCabbage: sospecho que las lámparas de lava son caóticas. Dado un modelo de computadora lo suficientemente bueno y suficientes dígitos de precisión, podría (en principio) predecir el comportamiento por un tiempo. Pero, debido a que el sistema es caótico, dos lámparas de lava con el menor cambio en las condiciones iniciales divergirán rápidamente en su comportamiento. (Y este comentario ignora los atractores caóticos.)
dmm
76

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                |
Tony D
fuente
Estás comparando manzanas y naranjas aquí. Las dos desviaciones estándar no tienen absolutamente nada que ver entre sí.
Jbeuh
50

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.

Chris Taylor
fuente
2
"Los generadores de números pseudoaleatorios ... generan números predecibles con la distribución correcta". El hecho de que sea un PRNG no garantiza que tenga una distribución perfecta (de hecho, los comerciales en general no lo hacen, por exactamente razones descritas en estas respuestas). Si bien pueden ser predecibles dada la información suficiente (el algoritmo utilizado, semilla inicial, valores de salida, w / e), todavía tienen varianza.
Brian S
3
Además del punto, lo sé, pero get_generator = lambda: itertools.cycle(range(1,7)), generator = get_generator(), next(generator) # and so ones demasiado elegante para no mencionar :)
Janus Troelsen
2
@BrianS En realidad, un PRNG que falló las pruebas de distribución con el tiempo sería predecible por definición. Entonces, sobre algunas N grandes, si obtienes incluso un poco de N / 2 caras en N monedas, puedes comenzar a apostar por caras, y puedes ganar más de lo que pierdes. Del mismo modo, si obtuviste una distribución perfecta de cara contra cruz, pero la cara siempre venía en pares, entonces volverías a tener una receta para ganar. Las pruebas de distribución son cómo sabes que un PRNG es bueno.
Jon Kiparsky
1
Te olvidaste nonlocal next:-).
Kos
55
Ejemplo aún mejor: se cree que Pi es normal , lo que significa que cualquier secuencia de dígitos de cualquier longitud dada en cualquier base aparece con menos frecuencia que cualquier otra secuencia de esa longitud en esa base. Un algoritmo que, cuando se le solicitan n bits aleatorios, toma los siguientes n bits de pi y los devuelve (la "semilla" es el bit en el que comienza), a la larga debería producir una distribución perfectamente uniforme. Pero aún así no lo querría para su generador: alguien que conozca el último grupo de bits que generó podría encontrar la primera vez que se produce esa secuencia, asumir que su semilla está allí y probablemente sea correcta.
cpast
26

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 .

Alex McKenzie
fuente
12
El gran problema es cuando necesita números aleatorios que un atacante no puede predecir por razones de seguridad.
David Schwartz
16
Es muy probable que encuentres un momento en el que necesites un número verdaderamente aleatorio. Es suficiente para abrir una página web que comienza con https://...
Jan Hudec
3
@ JanHudec: Bueno, en el uso diario, necesitará números aleatorios seguros en el momento en que abra cualquier programa, mucho antes de escribir en una barra de direcciones: consulte la aleatorización del diseño del espacio de direcciones . Es por eso que suceden cosas como esta .
Reid
55
@ JanHudec Estaba hablando específicamente en el sentido de que necesitarías usar un generador de números aleatorios en línea. Los números aleatorios verdaderos se usan con frecuencia, pero muy pocas personas realmente necesitan generarlos ellos mismos.
Alex McKenzie
2
Las máquinas tragamonedas también usan un PRNG, no un TRNG. El generador funciona todo el tiempo y se selecciona un número en el momento exacto en que se presiona el botón giratorio. La suma del PRNG y el tiempo de pulsación de botón verdaderamente aleatorio equivale a un TRNG.
Roger Dahl
26

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.

Prabhu
fuente
3
Culparía las cosas WEP a un protocolo mal diseñado usando un cifrado débil. Con los cifrados de flujo modernos puede usar un contador como IV.
CodesInChaos
2
El principal problema con WEP fue repetir la clave en cuadros 2 ^ 24 (casi 16 millones). Fue aún peor con las claves relacionadas que hicieron posible descifrar el código en aproximadamente 40000 cuadros. El punto principal aquí es que la clave no es aleatoria. Está estrechamente relacionado, por lo que es tan fácil de descifrar.
Prabhu
1
La seudoaleatoriedad es mala en criptografía solo cuando se generan claves criptográficas . Está perfectamente bien más allá de eso. De hecho, RC4 es poco más que un generador de números pseudoaleatorio sembrado con la expansión de 128 bits de la clave XORed en el texto sin formato del mensaje.
Matt
12

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

Fatal705
fuente
¡Previsibilidad! = Repetir. Mersenne Twister es un buen ejemplo de eso. En la mayoría de las implementaciones después de 624 Int32, puede predecir todos los números siguientes, pero la secuencia de Mersenne Twister es mucho más larga que eso (2 ^ 19937 - 1).
HoLyVieR
No entiendo por qué esta respuesta no se eleva, ya que me parece que esta es la respuesta precisa y concisa a la pregunta, al menos parcialmente. Los números pseudoaleatorios pueden predecirse fácilmente después de algunos sorteos, y el número de sorteos varía con la "calidad" del algoritmo pseudoaleatorio. Al seleccionar un algoritmo "bueno" se analizan aspectos: 1. cada valor se dibuja en igual frecuencia (distribución), 2. se tarda "mucho tiempo" en reiniciar la secuencia al principio y comenzar a dibujar nuevamente los mismos números en el la misma orden.
minutos
"los números aleatorios verdaderos no son [predecibles]". Por hoy esto es cierto. Ahora, si creemos en la teoría del Big Bang, y tenemos mucho poder para calcular el estado del Universo en cualquier momento después del BB, en función de la física, entonces ... podemos predecir el futuro, incluido el hecho de que Estoy escribiendo este comentario muy exacto. ¿Derecho?
minutos
Sin embargo, eso es hipotéticamente cierto, teniendo en cuenta el vasto grado de entropía involucrado en las acciones reales de los cuerpos reales, la potencia informática requerida sería ridículamente enorme. Piensa en continentes cubiertos de computadoras. Además, debido a la dependencia del estado anterior, el estado de cada cuerpo en el universo en cada punto del tiempo necesitaría ser almacenado, lo que por definición requeriría más espacio del que está disponible en el universo, completamente lleno de aparatos de memoria
TheEnvironmentalist
@TheEnvironmentalist - ¡Ah! "Continentes cubiertos de computadoras" ... ¿no es de lo que se trata "La Guía del autoestopista galáctico"? ;-)
ysap
10

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).

DoubleFission
fuente
10

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.

gnasher729
fuente
8

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

Erwan Legrand
fuente
2
No es necesariamente una pregunta de seguridad. Creo que hay razones para usar números verdaderamente aleatorios que no impliquen seguridad. Si estuviera haciendo una investigación científica que dependa de números aleatorios y fuera por cualquier razón crítica que los números sean lo más aleatorios posible, ciertamente aprovecharía un RNG de hardware para poder estar seguro de que no se deben las propiedades observadas a caprichos del RNG.
Kef Schecter
3
@KefSchecter Si sus PRNG de hardware escuchados generalmente tienen una salida sesgada y / o correlacionada. Necesitan un paso de procesamiento posterior para convertirlo en una salida independiente uniforme. No hay razón para creer que este paso posterior al procesamiento sea más confiable que un cifrado de flujo moderno. Ciertamente confiaría más en el cifrado de flujo. Como beneficio adicional es reproducible, lo cual es valioso en la ciencia.
CodesInChaos
OK bastante justo. ¿Pero no se aplicaría lo mismo a las aplicaciones de criptografía? Incluso la respuesta aquí dice que necesita un RNG de hardware para sembrar el CSPRNG.
Kef Schecter
2
@KefSchecter Sí, las aplicaciones de cifrado necesitan números aleatorios verdaderos para sembrar el CSPRNG. Pero para todo lo demás podemos usar ese CSPRNG.
CodesInChaos
@KefSchecter: las aplicaciones criptográficas requieren que la transmisión no sea reproducible en todo el mundo. Por el contrario, en aplicaciones científicas, es útil poder demostrar que los números "aleatorios" que uno está usando no fueron elegidos simplemente para mostrar el análisis de una buena manera. Por ejemplo, si se anuncia después de anunciar los métodos de uno que generará datos de una determinada manera utilizando los números de lotería estatales del día siguiente, los lectores pueden estar algo seguros de que no se han falsificado los resultados incluso si el sorteo del día de la semana solo tiene un par de docenas pedacitos de entropía.
supercat
7

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 160 secuencias posibles de números aleatorios que pueden provenir de él. Simple como eso. No puede obtener más de 2 160 valores del estado interno. Por lo tanto, no puede obtener más de 2 160 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 320 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 2226 . Por lo tanto, independientemente de la siembra, no puede usar Java.util.SecureRandom para barajar una baraja de cartas. Hay aproximadamente 2 66 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 238 posibilidades.

Paco Hope
fuente
2
¿Por qué te importa que algunas mezclas no puedan suceder? Esa restricción no tiene efecto observable.
CodesInChaos
2
Estoy algo atónito ante la pregunta. Para las compañías de juegos muy reguladas, tal sesgo probaría matemáticamente que sus posibilidades de ganar el juego de cartas son diferentes con la computadora que con una baraja de cartas de papel. No importa si las posibilidades son mejores o peores. Son DIFERENTES La computadora no es moralmente equivalente a una baraja real. Además, no podemos caracterizar la diferencia. A la compañía de juegos que enfrenta fuertes multas regulatorias le importaría mucho.
Paco Hope
1
Pero es detectable. Lo detecto usando un proceso conocido: revisión del código fuente y conocimiento del dominio del problema. Eso es lo notable. NO puedo usar el análisis estadístico automatizado. Es tan detectable como alguien que usa java.util.Random o el Mersenne Twister. El análisis estadístico no es el único mecanismo de detección válido para RNG / falta de coincidencia del dominio del problema. Las fallas que pasan ese detector no son, por definición, éxitos.
Paco Hope
1
Nunca estuve en desacuerdo con esa declaración. Lo que dije es que el análisis estadístico no es una prueba infalible de que el RNG / PRNG es correcto. Este es un ejemplo de falso negativo. Debería ser incorrecto, pero la prueba de salida estadística lo superará. Si uso SHA1 (1), SHA1 (2), SHA1 (3) ... SHA1 (n) como mi "RNG" que también pasará pruebas estadísticas. También está mal. La definición de correcto se extiende más allá de la definición de "pasa pruebas estadísticas". Pasar pruebas estadísticas es necesario, pero no suficiente.
Paco Hope
44
@CodesInChaos: El argumento "no sabemos de un ataque que pueda aprovechar el hecho de que la gran mayoría de las posibles combinaciones de IRL nunca se producirán" no implica que tal ataque sea imposible, solo que no No sé qué es ni cómo defenderse de él. La actitud correcta en ese caso es eliminar la posibilidad de ataque eliminando la condición: hacer un RNG de calidad suficiente para que realmente pueda generar todas las barajas posibles.
Eric Lippert
6

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.

BonzaiThePenguin
fuente
6

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.

radouxju
fuente
2

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.

sanaris
fuente
1

¿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.

Superbest
fuente
0

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) ...

revs Dice9
fuente
-5

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.

magallanes
fuente
2
Esta es una idea bastante mala y es una fuente de vulnerabilidad para las cosas que necesitan una secuencia realmente impredecible. Si toma microsegundos, solo tiene 10 ^ 6 posibilidades de semilla, que es bastante baja.
HoLyVieR
@HoLyVieR: sin duda es una mala idea si le importa la seguridad, pero no es tan malo como parece: normalmente usaría microsegundos desde el inicio del sistema (o unix epoch ...), lo que aumenta significativamente el rango de valores posibles.
mikera
1
@mikera No es mejor, el momento en que se procesó la solicitud es predecible. Es un vector de vulnerabilidad para una buena cantidad de funciones de restablecimiento de contraseña. Esos scripts generaron un token "aleatorio" con su técnica y el atacante podría encontrar el token generado ya que encontrar el momento en que se ejecutó es bastante trivial ... es al mismo tiempo que se envió la solicitud de restablecimiento de contraseña + - 150ms.
HoLyVieR
Claro, esa situación es muy mala. Pero la situación en la que el estado se sembró al inicio del sistema y el atacante no tiene una buena manera de adivinar el tiempo de inicio no es tan mala. Puede tener fácilmente 10 ^ 12 microsoconds posibles para elegir, lo que puede hacer que algunos tipos de ataque sean inviables. Para ser claros: todas estas soluciones son bastante malas desde una perspectiva criptográfica, pero las constantes son importantes .
mikera
Para los servidores en línea, la información del tiempo de actividad del sistema a veces se ofrece públicamente. O puede obtenerlo desde una página de estado "Incidentes. Servidor de nuevo". O puede hacer ping, esperar un gran tiempo de inactividad y tener en cuenta que podría ser un reinicio de la máquina (lo que daría cientos de millones de tiempo para verificar, que es bastante bajo).
Dereckson