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


Nunca he conseguido esto. Solo di que escribes un pequeño programa en cualquier idioma y tira algunos dados (solo usa los dados como ejemplo). Después de 600,000 rollos, cada número habría sido lanzado alrededor de 100,000 veces, que es lo que yo 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 la cantidad de números que puede elegir.

Lo intenté en Pitón: Aquí está el resultado de 60 millones de rollos. La mayor variación es como 0.15. ¿No es 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

651


origen


Echa un vistazo al artículo de Wikipedia en números aleatorios generados por hardware También mira esto - stats.stackexchange.com/questions/32794/... - steadyfish
¿A qué te refieres con "tira algunos dados"? ¿Tiene un brazo de robot y cámara adjunta? - starblue
aunque estoy de acuerdo con la esencia general de su tono, a menudo nos preocupamos demasiado por esto, pero ha sido explotado en la vida real: en.wikipedia.org/wiki/Ronald_Dale_Harris - Grady Player
Ver esta artículo sobre un juego de póquer en línea que falta la verdadera aleatoriedad de por qué es importante. - Varaquilex
Si mantiene un contador de 0-5 y tira un dado en consecuencia, 666 billones de veces, también obtendrá una distribución igual. - jcora


Respuestas:


Juguemos un poco al poker de computadora, solo tú, yo y un servidor en el que ambos confiamos. El servidor usa un generador de números pseudoaleatorio que se inicializa con una semilla de 32 bits justo antes de jugar. Entonces hay alrededor de cuatro mil millones de barajas posibles.

Tengo cinco cartas en la mano, aparentemente no jugamos 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 la baraja.

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 una en una base de datos. Supongamos que mi primera carta es la reina de espadas. Eso solo muestra a uno como la primera carta en una de cada 52 de esas posibles mazos, así que hemos reducido las posibles mazos 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 de veces más 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 de corazones como la tercera carta, la segunda carta en mi mano. De nuevo, solo se trata de aproximadamente el 2% de las cubiertas, por lo que ahora tenemos 2 millones de barajas.

Supongamos que la tercera carta en mi mano es el 7 de los palos. Tengo una base de datos de 2 millones de semillas que reparten mis dos cartas; Corro mi RNG otras 2 millones de veces para encontrar el 2% de esas barajas que producen el 7 de tréboles como la tercera carta, y solo tenemos 40 mil mazos.

Ya ves cómo va esto. Corro 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 ejecutamos 800 veces más para obtener las ~ 20 semillas que producen mi quinta carta, y ahora solo genera esos veinte mazos 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é la verdadera aleatoriedad es importante? La forma en que lo describes, piensas que distribución es importante, pero la distribución no es lo que hace que un proceso sea aleatorio. Impredecibilidad es lo que hace que un proceso sea aleatorio.

ACTUALIZAR

En base a los comentarios (ahora eliminados debido a su naturaleza no 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 discuten contra puntos que yo no hice, o peor, discuten para puntos que yo hizo hacer en el suposición de que no los hice, entonces sé que tengo que explicar más clara y cuidadosamente.

Parece haber una confusión particular alrededor de la palabra distribución entonces quiero llamar usos cuidadosamente.

Las preguntas a mano son:

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

Comencemos considerando el Perfecto forma de generar un mazo de cartas al azar con el que jugar al póquer. Luego veremos cómo otras técnicas para generar cubiertas son diferentes, y si es posible aprovechar esa diferencia.

Comencemos por suponer que tenemos una caja mágica etiquetada TRNG. Como su entrada le damos un entero n mayor que o igual a uno, y como su salida nos da un número verdaderamente aleatorio entre uno y n, 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 y n es tan probable como otro; es decir que el distribución es uniforme. (Hay otras comprobaciones estadísticas más avanzadas de aleatoriedad que podríamos realizar, estoy ignorando este punto, ya que no es pertinente a mi argumento. TRNG es perfectamente estadísticamente aleatorio por suposición).

Comenzamos con una baraja de cartas sin barajar. Le pedimos a la caja un número entre uno y 52, es decir, TRNG(52). Cualquiera que sea el número que devuelve, contabilizamos muchas cartas de nuestro mazo ordenado y eliminamos esa carta. Se convierte en la primera carta en la baraja barajada. Entonces pedimos TRNG(51) y haz lo mismo para seleccionar la segunda carta, y así sucesivamente.

Otra forma de verlo es: ¡hay 52! = 52 x 51 x 50 ... x 2 x 1 cubiertas posibles, que es aproximadamente 2226. Elegimos uno de ellos al azar.

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

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

Todo bien.

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

APARTE: Por qué 32? ¿No podría ser sembrado con un número de 64, 256 o 10000 bits? Por supuesto. Pero (1) en la práctica, la mayoría de los PRNG disponibles vienen con un número de 32 bits, y (2) si tiene 10000 bits de aleatoriedad para hacer la semilla, ¿por qué está usando un PRNG? ¡Ya tienes una fuente de 10000 bits de aleatoriedad!

De todos modos, volviendo a cómo funciona el PRNG: después de que se haya sembrado, puede usarlo de la misma manera que usa TRNG. Es decir, le pasa un número n y le devuelve un número entre 1 y n inclusive. Además, la distribución de esa salida es más o menos uniforme. Es decir, cuando preguntamos PRNG para un número entre 1 y 6, obtenemos 1, 2, 3, 4, 5 o 6 cada uno aproximadamente una sexta parte del tiempo, sin importar la semilla.

Quiero enfatizar este punto varias veces porque parece ser el que está confundiendo a ciertos comentaristas. La distribución del PRNG es uniforme en al menos dos formas. Primero, supongamos que elegimos una semilla en particular. Es de esperar que la secuencia PRNG(6), PRNG(6), PRNG(6)... un millón de veces produciría una distribución uniforme de números entre 1 y 6. Y segundo, si elegimos un millón de semillas diferentes y llamamos PRNG(6)  una vez para cada semilla, otra vez 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 de la caja es en realidad completamente determinista; elige de uno de 232 posibles comportamientos basados ​​en la semilla. Es decir, una vez que se siembra, PRNG(6), PRNG(6), PRNG(6), ...  produce un secuencia de números con una distribución uniforme, pero esa secuencia es enteramente determinado por la semilla. Para una secuencia dada de llamadas, digamos, PRNG (52), PRNG (51) ... y así sucesivamente, solo hay 232 posibles secuencias 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, similar a antes.

Este sistema es susceptible al ataque que describí. Para atacar al servidor, primero debemos sembrar nuestra propia copia del cuadro con 0 y pedir PRNG(52) y escribe eso. Luego volvemos a sembrar con 1, preguntamos por PRNG(52), y anótalo, todo el camino hasta 232-1.

Ahora, el servidor de póquer que está utilizando 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 la hora actual como una semilla, que es apenas aleatoria en absoluto; Sé a 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 tarjeta, puedo eliminar el 98% más, y así sucesivamente, hasta que eventualmente pueda llegar a un puñado de posibles semillas y saber con gran probabilidad lo que está en tu mano.

Ahora, de nuevo, 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) uniformey si la uniformidad de esa distribución es todo lo que le importa, esta bien. El objetivo de la pregunta era ¿hay otras cosas que la distribución de PRNG(6) que nos importa? y la respuesta es . Nos importa impredecibilidad también.

Otra forma de ver el problema es que a pesar de la distribución de un millón de llamadas a PRNG(6) podría estar bien, porque el PRNG está eligiendo entre solo 232 posibles comportamientos, no puede generar todos los mazos posibles.  Solo puede generar 232 de los 2226 posibles mazos; una pequeña fracción. Entonces la distribución sobre el conjunto de todas las cubiertas es muy malo. Pero, una vez más, el ataque fundamental aquí se basa en que nosotros podamos exitosamente predecir el comportamiento pasado y futuro de PRNG de una pequeña muestra de su salida.

Permítanme decir esto una tercera o cuatro veces para asegurarme de que esto se esclavice. Aquí hay tres distribuciones. 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. En tercer lugar, la distribución de mazos elegidos por el proceso pseudoaleatorio que he descrito. Esa distribución es extremadamente pobre; solo una pequeña fracción de las cubiertas posibles de IRL puede ser elegida. El ataque depende de la previsibilidad del comportamiento del PRNG basado en el conocimiento parcial de su producción.

ASESOR: Este ataque requiere que el atacante sepa o sea capaz de 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 denomina "clave". Si su sistema depende de su seguridad en los algoritmos que utiliza siendo un secreto, entonces tu clave contiene esos algoritmos. Eso es un extremadamente posición débil para estar adentro!

Continuando.

Ahora supongamos que tenemos una tercera caja mágica etiquetada CPRNG. Es una versión cripto-fuerte de PRNG. Se necesita una semilla de 256 bits en lugar de una semilla de 32 bits. Comparte con PRNG la propiedad que la semilla elige de uno de 2256 comportamientos posibles. Y al igual que nuestras otras máquinas, tiene la propiedad de que una gran cantidad de llamadas a CPRNG(n) producen una distribución uniforme de resultados entre 1 y n: cada uno ocurre 1 / n del tiempo. ¿Podemos ejecutar nuestro ataque contra eso?

Nuestro ataque original requiere que almacenemos 232 mapeos de semillas a PRNG(52). Pero 2256 es un número mucho más grande; es completamente inviable correr CPRNG(52)eso muchas veces y almacena los resultados.

Pero supongamos que hay algunos otro manera de tomar el valor de CPRNG(52) y de eso deducir un hecho sobre la semilla? Hemos sido bastante tontos hasta el momento, solo fuerza bruta todas las combinaciones posibles. ¿Podemos mirar dentro de la caja mágica, descubrir cómo funciona y deducir hechos sobre la semilla en función de la producción?

No. Los detalles son demasiado complicados de explicar, pero los CPRNG están inteligentemente diseñados para que no sea factible deducir alguna hecho útil sobre la semilla de la primera producción de CPRNG(52) o desde alguna subconjunto de la salida, no importa cuán grande.

OK, entonces supongamos que el servidor está usando CPRNG para generar mazos. Necesita una semilla de 256 bits. ¿Cómo elige esa semilla? Si elige cualquier valor que un atacante pueda predecir luego, de repente, el ataque vuelve a ser viable. Si podemos determinar el de los 2256 posibles semillas, solo cuatro mil millones de ellas serán elegidas por el servidor, luego estamos de vuelta en el negocio. Podemos volver a montar este ataque, solo prestando atención al pequeño número de semillas que se pueden generar.

Por lo tanto, el servidor debería hacer un trabajo para asegurarse de que el número de 256 bits sea distribuido uniformemente - es decir, cada posible semilla se elige con probabilidad de 1/2256. Básicamente, el servidor debería llamar TRNG(2^256)-1 para generar la semilla para CPRNG.

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

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

OK, entonces la semilla debe ser secreta y estar uniformemente distribuida porque si no es así, podemos montar un ataque. Tenemos por supuesto que la distribución de los productos de CPRNG(n) es uniforme. ¿Qué pasa con la distribución en el conjunto de todas las cubiertas posibles?

Usted podría decir: hay 2256 posibles secuencias emitidas por el CPRNG, pero solo hay 2226 posibles mazos. Por lo tanto, hay más secuencias posibles que cubiertas, así que estamos bien; cada mazo posible de IRL es ahora (con alta probabilidad) posible en este sistema. Y ese es un buen argumento, excepto ...

2226 es solo un aproximaciónde 52 !. Divídalo. 2256/ 52! no puede ser un número entero porque, por un lado, ¡52! es divisible por 3 pero no es poder de dos! Dado que esto no es un número entero ahora tenemos la situación en la que todas las cubiertas son posible, pero algunos mazos son más probables que otros.

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 resultados posibles de 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 pareja por 3. Tiene que haber un pequeño sesgo hacia uno de ellos.

Del mismo modo, 52 no se divide uniformemente en 2256, por lo que debe haber algún sesgo hacia algunas cartas como la primera carta elegida y un sesgo alejado de los demás.

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

Ahora la pregunta es: ¿tenemos un ataque basado en este defecto? y la respuesta es en la práctica, probablemente no. Los CPRNG están diseñados para que si la semilla es verdaderamente aleatoria entonces es computacionalmente inviable decir la diferencia entre CPRNG y TRNG.

OK, así que vamos a resumir.

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

Difieren en el nivel de predictibilidad que exhiben.

  • Los números realmente aleatorios no son predecibles.
  • Todos los números pseudoaleatorios son predecibles si la semilla puede determinarse o adivinarse.

¿Por qué la diferencia es importante?

Porque hay aplicaciones donde la seguridad del sistema depende impredecibilidad.

  • Si se usa un TRNG para elegir cada tarjeta, entonces el sistema es inexpugnable.
  • Si se usa un CPRNG para elegir cada tarjeta, entonces el sistema es seguro si la semilla es tanto impredecible como desconocida.
  • Si se utiliza un PRNG ordinario con un espacio de semilla pequeño, 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 producción del PRNG?

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

Como hemos visto, tanto un PRNG y CPRNG producir malas distribuciones de la probabilidad de elegir cualquier mazo individual de todas las mazos posibles. los PRNG es 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: gasto TRNG es costoso. Generar números verdaderamente aleatorios es difícil. CPRNGs dan buenos resultados para arbitrariamente muchas llamadas con solo uno llama a TRNG para la semilla. El lado negativo es, por supuesto, eso tienes que mantener esa semilla en secreto.

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

Espero que ahora sea mucho más claro.

Finalmente, si lo disfrutó, puede disfrutar de lecturas adicionales sobre el tema de la aleatoriedad y las permutaciones:


1371



Ok, chicos y chicas. Eso es suficiente para comentar por el momento. Si quieres hablar de esto más adelante, ve a la sala de chat, ¡ayúdanos! - Ivo Flipse♦
@Eric Pero la semilla no se reinicia antes de cada nuevo sorteo de la cubierta, ¿o sí? Así que, si bien tienes razón, solo hay relativamente pocos trayectorias estamos tomando muestras, usted no sabe exactamente en qué punto de la trayectoria se encuentra en ese momento y las trayectorias se cruzan. - A.S.
Alguien realmente hizo algo así como esto - EJoshuaS
Un buen (pero denso) tratamiento de cuestiones relacionadas está en el TAOCP vol 2 de Knuth, sección 3.5 "¿Qué es una secuencia aleatoria?" (P.149), comenzando con definiciones esclarecedoras de secuencias distribuidas equidistantes, k distribuidas por k. Secuencias pseudoaleatorias se discuten en 3.5.F (p.170). Ver también los criterios de pseudoalegibilidad de teoría de la complejidad y BSI alemán. - ShreevatsaR


Como dice Eric Lippert, no es solo 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: alternó los 0 y los 1. Por lo tanto, el LSB fue 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 dibuja 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 un gris uniforme. Pero puede obtener patrones. Tomemos por ejemplo este diagrama de la "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 de Cisco (IOS). Cisco ISO

Estos diagramas son cortesía de El trabajo 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 suplantar ese sistema al hacer 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 no podemos predecir el próximo número el 100% del tiempo, si podemos causar 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 pocos segundos, las probabilidades de un ataque exitoso van desde lo astronómico a lo posible o incluso probable.


155



Esto es tan brillante que me trae lágrimas a los ojos. Debería haber una aplicación que crea estos para cada sistema operativo (móvil / escritorio / servidor) y plataforma (JVM / Javascript / etc). - HDave
¡La función de Windows rand () es bastante buena! Produce una nube que no tiene ningún patrón aparente. Ver mi implementación para probarlo (y otros algoritmos): github.com/Zalastax/visualize_random - Zalastax


Si bien los números pseudoaleatorios generados por computadoras son aceptables para la mayoría de los casos de uso que enfrentan los usuarios de computadoras, existen escenarios que requieren completamente números aleatorios 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 son verdaderamente imposibles de analizar. Tenga en cuenta que algunos PRNG están diseñados para ser criptográficamente seguros y son utilizables para tales aplicaciones sensibles a la seguridad.

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


91



Los PRNG criptográficos existen y son ampliamente utilizados. Pueden partir de una semilla de tamaño modesto generar un flujo prácticamente ilimitado de números aleatorios. Es computacionalmente inviable distinguir tal flujo de verdaderos números aleatorios, por lo que no se puede obtener información adicional de ninguna porción de tal flujo, 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 de generador de números aleatorios deben programarse. Eso significa que hay un conjunto de instrucciones que se siguen. Si hay un conjunto de instrucciones, no puede ser aleatorio. - Keltari
@Keltari Te estás perdiendo el elemento de la entropía ... La mayoría de los RNG (al menos los criptográficos) recopilan información de fuentes externas (por ejemplo, movimiento del mouse) y la usan como parte de la condición de inicio, por lo tanto, la transformación de A a B está programado pero el estado inicial de A (debería) ser indescifrable. Linux /dev/random mantendrá una aproximación de cuánta entropía está disponible y dejará de dar números si es demasiado baja. - Basic
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 fluidos y cómo esos fluidos interactúan 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 nada aleatorias, sino altamente predecibles. - theGreenCabbage
@theGreenCabbage: sospecho que las lámparas de lava son caóticas. Dado un modelo informático 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 cambio más pequeño en las condiciones iniciales diferirán rápidamente en el comportamiento. (Y este comentario ignora los atractores caóticos). - dmm


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

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

tu distribución tiene una desviación estándar mucho más pequeña que los rollos aleatorios

La verdadera aleatoriedad simplemente no viene del todo ese cerca de promediar "casi exactamente 1 sobre cuántos números puede elegir" que está utilizando como una indicación de calidad.

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

 sqrt(N * 35.0 / 12.0).

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

  • 1 millón de rollos es 1708
  • 60 millones de rollos es 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 se puede esperar que la desviación estándar de una muestra finita coincida exactamente con la fórmula, pero debería ser muy cercana. Sin embargo, con 1 millón de rollos tienes menos de la mitad del stddev adecuado, y en 60 millones estás debajo 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 no revisando el número original durante un período específico. Por ejemplo, implementaciones de la antigua biblioteca C rand() la función suele tener 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 simuló 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 de 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. la fórmula anterior, la desviación estándar correcta para 2 ^ 32 rollos es 111924. De todos modos, a medida que su número de rollos pseudoaleatorios aumenta, converge hacia una desviación estándar de 0. Se puede esperar que el problema sea significativo cuando el número de vueltas es una fracción significativa del período, pero algunos pseudo-RNG pueden presentar problemas peores, o problemas incluso con menos muestras, que otros.

Por lo tanto, incluso si no le importan las vulnerabilidades criptográficas, en algunas aplicaciones puede que le interese tener distribuciones que no tengan resultados artificialmente excesivos. Algunos tipos de simulación están tratando específicamente de resolver las consecuencias de la desigual resultados que ocurren naturalmente con muestras grandes de resultados individualmente aleatorios, pero están subrepresentados en algunos resultados de pRNG. Si está tratando de simular cómo reacciona una enorme población a algún evento, este problema podría radicalmente altere sus resultados llevando a conclusiones muy imprecisas.


Para dar un ejemplo concreto: Digamos que un matemático le dice a un programador de póquer que después de 60 millones de rollos simulados, utilizados para centellear cientos de pequeñas "luces" alrededor de la pantalla, si ha habido 10,013,229 o más seises, lo que el matemático espera que sea 1 stddev lejos de la media, debería haber un pequeño pago. Por el Regla 68-95-99.7 (Wikipedia) esto debería suceder dieciséis% del tiempo (~ 68% caen dentro de una desviación estándar / solo la mitad afuera están arriba). Con su generador de números aleatorios, esto es de alrededor de 3.5 desviaciones estándar por encima de la media: bajo 0.025% posibilidad - casi ningún cliente obtiene este beneficio. Consulte la tabla de Desviaciones más altas en la página que acabamos 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                |

75



Estás comparando manzanas y naranjas aquí. Las dos desviaciones estándar no tienen absolutamente nada que ver entre sí. - Jbeuh


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. ¿Te gustaría utilizar 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 simplificado de números aleatorios anterior es malo: no son adecuados para situaciones donde se necesita una imprevisibilidad genuina, no solo la distribución correcta.


50



"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, para exactamente el razones resumidas en estas respuestas). Si bien pueden ser predecibles con suficiente información (el algo usado, semilla inicial, valores de salida, w / e), todavía tienen varianza. - Brian S
Además del punto, lo sé, pero get_generator = lambda: itertools.cycle(range(1,7)), generator = get_generator(), next(generator) # and so on es demasiado elegante para no mencionar :) - Janus Troelsen
@BrianS En realidad, un PRNG que no pasó las pruebas de distribución a lo largo del tiempo sería predecible por definición. Por lo tanto, a través de N grande, si se aleja un poco de N / 2 cabezas en N lanzamientos de moneda, puede comenzar a apostar en las cabezas, y puede ganar más de lo que pierde. Del mismo modo, si tienes una distribución perfecta de cabezas v. Colas, pero las cabezas siempre vienen en parejas, entonces de nuevo tendrías una receta para ganar. Las pruebas de distribución son cómo usted sabe que un PRNG es bueno. - Jon Kiparsky
Te olvidaste nonlocal next :-). - Kos
Mejor ejemplo: se cree que Pi normal, lo que significa que cualquier secuencia de dígitos de cualquier longitud dada en cualquier base no aparece más a menudo que cualquier otra secuencia de esa longitud en esa base. Un algoritmo que, cuando se solicita norte bits aleatorios, toma el siguiente norte bits de pi y los devuelve (la "semilla" es el bit en el que comienzas), a la larga deberían producir una distribución perfectamente pareja. Pero aún no lo desearía para su generador: alguien que conozca el último grupo de bits que generó podría encontrar la primera vez que ocurra esa secuencia, suponga que su semilla está allí y probablemente sea la correcta. - cpast


La generación de números aleatorios que su computadora puede realizar 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, grandes muestras estadísticas, etc.

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


26



El gran problema es cuando necesita números aleatorios que un atacante no puede predecir por razones de seguridad. - David Schwartz
Seguro que es probable que encuentres un momento en el que necesites un número verdaderamente aleatorio. Es suficiente abrir una página web que comienza con https://... - Jan Hudec
@JanHudec: Bueno, en el uso diario, necesitarás números aleatorios seguros en el momento de abrir cualquier programa, mucho antes de que estés escribiendo en una barra de direcciones: ver direccionamiento del espacio de aleatorización. Es por eso Cosas como esta sucede. - Reid
@JanHudec Estaba hablando específicamente en el sentido de que necesitaría 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
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 del botón verdaderamente aleatorio equivale a un TRNG. - Roger Dahl


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, pueden adivinarse con suficiente información sobre los números generados previamente. Entonces esto será un desastre para la seguridad en la criptografía.

Por ejemplo, la siguiente función de generador de números aleatorios utilizada en glibc no genera un número puramente aleatorio. Se puede adivinar el número pseudo aleatorio generado por esto. Es un error por cuestiones de seguridad. Hay una historia de esto llegando a ser desastrosa. Esto no debería 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 debería usarse en lugares sensibles a la seguridad aunque estadísticamente significativo.

Uno de los famosos ataques a la clave pseudoaleatoria es el ataque a 802.11b WEP. WEP tiene una clave a largo plazo de 104 bits, concatenada con un IV (contador) de 24 bits para generar una clave de 128 bits, que a su vez se aplica a Algoritmo RC4 para generar clave pseudo aleatoria.

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

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

Entonces uno debería ir con un generador de números aleatorios puros en cuestiones de seguridad cuando sea posible.


26



Yo culparía a las cosas WEP en un protocolo mal diseñado usando un cifrado débil. Con los sistemas de cifrado modernos puede usar un contador como IV. - CodesInChaos
El principal problema con WEP era repetir la clave en 2 ^ 24 (casi 16 millones) de fotogramas. Fue aún peor con las claves relacionadas que hicieron posible descifrar el código en aproximadamente 40000 fotogramas. El punto principal aquí es que la clave no es aleatoria. Está estrechamente relacionado, así que es así de fácil de descifrar. - Prabhu
La pseudoaleatoriedad es mala en la 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 pseudoaleatorios sembrado con la expansión de 128 bits de la clave XORed en el texto claro del mensaje. - Matt