¿Cómo se puede detectar que un generador de números no es realmente aleatorio?

Escuché que la generación de números aleatorios en las computadoras no es realmente aleatoria, pero no hay un algoritmo eficiente para detectarla. ¿Cómo se puede detectar?

Las computadoras son realmente aleatorias:

La verdadera aleatoriedad es imposible para las máquinas de Turing en un sentido teórico, y la mayoría de las computadoras no pueden generar resultados verdaderamente aleatorios. Por lo tanto, algunas computadoras modernas incluyen hardware que permite que la computadora acceda a una fuente externa que con suerte incluirá algo de aleatoriedad. Un ejemplo de cómo se puede lograr esto es rastrear pequeñas fluctuaciones de temperatura dentro de la computadora. La aleatoriedad se puede obtener de una fuente externa también. Pero por el tono de su publicación, no creo que le interesen fuentes externas de aleatoriedad.

Semillas:

Sin una adición externa, todo lo que hace una computadora es determinista. Esto lleva a un gran problema: si llamas a un programa de generación de números aleatorios, te dará el mismo resultado cada vez que le des la misma entrada. Claramente, necesitamos un programa que genere un número aleatorio para cambiar su comportamiento cada vez que se ejecuta (de lo contrario, seguiremos obteniendo el mismo número "aleatorio", lo que no es particularmente útil). Una idea es dar al programa alguna entrada, que cambia cada vez que se ejecuta el programa, para que se genere un número diferente. Llamamos a esta entrada una "semilla". El generador de números aleatorios necesita tomar una semilla, realizar algunas operaciones y darnos un número aleatorio.

La hora actual del sistema es un ejemplo clásico de una semilla. Esto proporciona una cadena larga con alta entropía, y si el tiempo se registra de manera suficientemente granular (es decir, si el reloj de su sistema usa horas, entonces "tiempo" es una semilla bastante pobre), es poco probable que alimente el número pseudoaleatorio generador el mismo número dos veces.

Algoritmos que son lo suficientemente aleatorios:

Ahora tenemos un algoritmo que al menos tiene alguna forma de ser diferente cada vez que se ejecuta. Le damos una semilla, y aunque el algoritmo da el mismo número cuando se le solicita con la misma semilla, queremos que los números que genera sean aleatorios de lo contrario. Esto actúa como lo anterior: toma algo de entrada y produce algo (es de esperar que sea lo suficientemente diferente de la entrada como para ser "aleatorio").

Ahora supongamos que se le ocurrió su propio algoritmo para hacer esto, y afirma que los números que obtiene son bastante aleatorios cuando le da un montón de semillas diferentes. ¿Cómo probaríamos lo bueno que es?

Ahora queremos un algoritmo que tome una semilla, realice algunas operaciones y produzca un número aleatorio. En el más simple, el algoritmo podría simplemente generar la semilla: no nos da el mismo número cada vez, y las semillas aleatorias nos dan salidas aleatorias. Pero claramente eso no es lo que queremos. Por otro lado, un algoritmo puede ser bastante complicado, como muchos generadores pseudoaleatorios reales. ¿Cómo podemos saber qué algoritmos nos dan números "aleatorios" de nuestras semillas no necesariamente aleatorias? Si no podemos obtenerlo exactamente, ¿cómo podemos saber cuáles son los mejores?

$1$$n$

Suficiente aleatorio para engañar a un atacante:

Ahora a lo que PUEDE referirse es a los generadores pseudoaleatorios criptográficamente seguros. Creo que la mejor manera de explicar esto es en el contexto de lo anterior: aquí, estamos usando nuestra aleatoriedad para la criptografía, por lo que cuando diseñamos pruebas, lo que realmente nos importa es que alguien no pueda romper nuestra seguridad al predecir qué número aleatorio elegimos. No sé tu nivel de familiaridad con la criptografía, pero imagina que estamos haciendo un simple cifrado de reemplazo: cada letra se reemplaza por otra letra. Queremos elegir estos reemplazos al azar, por lo que es difícil de adivinar para un atacante. Pero si puede descubrir cómo funciona mi generador de números aleatorios, ¡podrá resolver todo el cifrado! Por lo tanto, los algoritmos criptográficos requieren generadores de números aleatorios que son específicamente difíciles de adivinar.

Por esta razón, los CSPRG se definen en términos de qué tan bien los resuelven otros algoritmos (que es donde finalmente llegamos a su pregunta). Específicamente, digamos que tengo un CSPRG que llamaré R. R es un CSPRG si y solo si NO hay un algoritmo factible que pueda adivinar qué bit saldrá a continuación. ¡Esto es cierto incluso si conoce todos los bits anteriores que genera!

Entonces, digamos que los primeros cinco bits que mi CSPRG tiene como salida son 10100. No conoce la entrada que usé para el programa, pero tiene acceso al código que usé para escribir mi CSPRG. Entonces, la afirmación es que es imposible para usted escribir un programa para decidir si la próxima salida de bits será 101000 o 101001.

Entonces, por razones de criptografía, a veces lo bien que funciona un generador de números pseudoaleatorios se define en términos de cuán predecible es para otros programas. Tenga en cuenta que esto todavía da mucha de la intuición de "aleatoriedad", ya que (por ejemplo) si sabe que todas las salidas aleatorias serán extrañas, no es criptográficamente seguro ni pasa una prueba de aleatoriedad de sentido común.

Recientemente encontré una buena publicación sobre aleatoriedad en la computación en el blog del Grupo de Teoría de la Computación del MIT CSAIL: ¿Puedes decir si un bit es aleatorio?

La publicación comienza con algunas ideas extraídas de un la maravillosa charla de Avi Wigderson sobre el poder y las limitaciones de la aleatoriedad en la computación, examinando el área hermosa de los algoritmos aleatorios y la sorprendente conexión entre la pseudoaleatoriedad y la intratabilidad computacional .

Luego resume algunos resultados recientes sobre criptografía cuántica; en particular, la forma de probar de manera eficiente si la salida de un cierto tipo de dispositivo es verdaderamente aleatoria (protocolos de expansión de aleatoriedad).

Por ejemplo, vea el trabajo reciente de Umesh Vazirani, Thomas Vidick, Certificable Quantum Dice (O, expansión de aleatoriedad exponencial comprobable)

Resumen: Introducimos un protocolo a través del cual se pueden usar un par de dispositivos de mecánica cuántica para generar n bits de aleatoriedad verdadera a partir de una semilla de bits uniformes O (log n). Los bits generados son certificablemente aleatorios basados ​​solo en una prueba estadística simple que puede realizar el usuario, y en el supuesto de que los dispositivos obedecen el principio de no señalización. No se colocan otras suposiciones en el funcionamiento interno de los dispositivos ...

Asumiendo que está hablando de aleatoriedad estadística , ¡la criptografía tiene otras necesidades! - hay una gran cantidad de pruebas de bondad de ajuste que pueden detectar si una secuencia de números se ajusta a una distribución dada. Puede usarlos para probar si un generador de números (pseudo) aleatorio es sólido (hasta la calidad de su prueba y el significado elegido).

Las suites de pruebas intransigentes combinan diferentes métodos.

Este es un tema amplio / complejo en informática que la otra respuesta de SamM aborda algunos. Su pregunta específica parece ser si las computadoras tienen lo que se llama PRNG , es decir, generadores de números pseudoaleatorios, ¿cómo se puede detectar eso?

La respuesta corta es que los PRNG no triviales se crean de modo que sus algoritmos no se puedan detectar (derivar). En general, si el PRNG es lo que se llama "seguro", incluso si un atacante conoce el algoritmo utilizado para generar la secuencia pseudoaleatoria, no puede adivinar los parámetros particulares utilizados para generar la secuencia. De esta manera, la pseudoaleatoriedad tiene muchos vínculos profundos con la criptografía, y se puede hablar de "romper" un PRNG de la misma manera que se puede "romper" un algoritmo criptográfico. Hay muchos trabajos de investigación en esta área, es un área activa a la vanguardia de la criptografía.

Para PRNG "triviales", por ejemplo, digamos un generador congruencial lineal , si el atacante conoce el algoritmo utilizado para generarlo y no se genera con "bignums" , el espacio de búsqueda es "relativamente pequeño" y el atacante teóricamente también podría encontrar los parámetros utilizado por el PRNG particular básicamente por fuerza bruta y probando todas las combinaciones.

Los PRNG pueden romperse en la práctica (de nuevo dependiendo de su "seguridad") en algunos casos ejecutando un amplio conjunto de pruebas estadísticas de aleatoriedad contra ellos. Por ejemplo, esta es la razón del programa "Dieharder" (por Brown). También hay una suite NIST .

La dificultad / dureza intrínseca de romper PRNGs aún no está estrictamente probada teóricamente, pero está básicamente asociada con lo que se llama "trampilla" o "funciones unidireccionales" que pueden calcularse eficientemente en una dirección pero son "difíciles" de invertir (invertir) . Hay algunos problemas abiertos en la criptografía sobre la dureza de la aleatoriedad. Estas preguntas se relacionan estrechamente con las separaciones de clases de complejidad, por ejemplo, la famosa pregunta P =? NP.

Las preguntas sobre la ruptura de PRNG también se relacionan con la complejidad de Kolmogorov , un campo que estudia las máquinas de Turing más pequeñas que pueden generar secuencias. romper el PRNG también se relaciona estrechamente con encontrar el programa "más corto" para calcular una secuencia pseudoaleatoria. Y la complejidad de Kolmogorov es indecidible de calcular en general.

Como Gilles señala en un comentario, existen RNG basados ​​en hardware construidos a partir de procesos electrónicos físicos como los relacionados con el ruido cuántico. estos si están diseñados correctamente son irrompibles.

De hecho, todo lo que hace una computadora clásica es determinista, en el sentido de que cuando le das algunas tareas, las sigue de manera determinista. Por lo tanto, si desea tener un número aleatorio, puede calcularlo de acuerdo con el tiempo (en función del tiempo de entrada del usuario), pero si desea tener un conjunto de números aleatorios, no puede usar el tiempo para los siguientes números, porque los números ya no serían independientes.

Lo que la gente hace es usar generadores pseudoaleatorios que tienen una semilla, es decir, un número que se usa para calcular todos los números del generador de números pseudoaleatorios (en algunos casos más sofisticados de simulación u otras tareas, se pueden necesitar más semillas , si se necesita más de un conjunto de números aleatorios independientes). La semilla es generalmente 0 o un número específico si desea resultados reproducibles, o el tiempo si usted y resultados diferentes no reproducibles.

El hecho de que los generadores de números pseudoaleatorios sean lo suficientemente buenos, radica en el hecho de que siguen "las características básicas de una generación de números pseudoaleatorios", para poder computarse de manera eficiente y comportarse como números aleatorios reales:

• los números producidos deben seguir una distribución uniforme (de esta distribución puede lograr cualquier otra distribución);
• los números producidos deben ser estadísticamente independientes;
• la secuencia es reproducible (este punto se impone debido a esa propiedad del hardware de una computadora clásica, y es por eso que se llaman "números pseudoaleatorios");
• el período de la secuencia debe ser lo suficientemente grande;
• La generación de números debe ser rápida.

De cada número de la secuencia de números pseudoaleatorios se calcula un nuevo número (generalmente trabajamos con números enteros). Sin embargo, hay un período, n, en una secuencia de generadores de números pseudoaleatorios preparados para trabajar en una base específica con un número finito de bits disponibles para expresar los números (p. Ej. Binario). Si esta n no fuera lo suficientemente grande, habría serios problemas, pero no se preocupe, los informáticos eligen bien las semillas y otros parámetros de los generadores pseudoaleatorios para tener una buena n.

Por ejemplo, un posible generador de números pseudoaleatorios, con el método congruencial lineal, que es uno de los algoritmos generadores de números pseudoaleatorios más antiguos y mejor conocidos, se puede definir de acuerdo con:

tiene cuatro valores:
- x_0 ≥ 0
- a ≥ 0
- c ≥ 0
- m> x_0, donde:

x0 es el valor inicial, a, c y m son constantes donde: m> a, m> c, y produce la secuencia con la cánula:

x_ {i + 1} = (a * x_i + c) MOD m

Los valores para estas constantes deben elegirse cuidadosamente. Una posibilidad es:

x_ {i + 1} = (1664525 * x_i + 1013904223) MOD 2 ^ 32, refs. [1-2]

Hay otros algoritmos más sofisticados para generar números aleatorios, que evitan algunos de los problemas de algoritmos anteriores, que incluyen: [3]

• períodos más cortos de lo esperado para algunos estados semilla (tales estados semilla pueden llamarse 'débiles' en este contexto);
• falta de uniformidad de distribución para grandes cantidades de números generados;
• correlación de valores sucesivos;
• mala distribución dimensional de la secuencia de salida;
• las distancias entre donde ocurren ciertos valores se distribuyen de manera diferente a las de una distribución de secuencia aleatoria.

En el futuro, las computadoras clásicas pueden unirse a sistemas cuánticos que pueden proporcionar números realmente aleatorios y entregarlos. [4]

referencias:
[1] http://en.wikipedia.org/wiki/linear_congruential_generator
[2] William H., et al. (1992) "Recetas numéricas en fortran 77: El arte de la computación científica" (2ª ed.). ISBN 0-521-43064-X.
[3] http://en.wikipedia.org/wiki/pseudorandom_number_generator
[4] http://www.technologyreview.com/view/418445/first-evidence-that-quantum-processes-generate-truly-random-numbers / /