Verdadero generador de números aleatorios [cerrado]

Question

Perdón por no ser una pregunta "real", pero hace algún tiempo recuerdo haber visto una publicación aquí sobre la aleatorización de un aleatorizador para generar números verdaderamente aleatorios, no solo pseudoaleatorios.No lo veo si lo busco.

¿Alguien sabe sobre ese artículo?

Answer 1

Creo que eso estaba en thedailywtf.com - es decir.no es algo que quieras hacer.

No es posible obtener un número verdaderamente aleatorio a partir de números pseudoaleatorios, sin importar cuántas veces llames a randomize().

Tú poder obtener números aleatorios "verdaderos" de especiales hardware.También puedes recolectar entropía de los movimientos del mouse y cosas así.

Answer 2

No estoy de acuerdo con muchas de las respuestas a esta pregunta.

Es posible recopilar datos aleatorios en una computadora.SSL, SSH y VPN no serían seguros si usted no pudiera hacerlo.

La forma en que funciona el software del generador de números aleatorios es que existe una piscina de datos aleatorios que se recopilan de muchos lugares diferentes, como derivas de reloj, tiempos de interrupción, etc.

El truco de estos esquemas está en estimar correctamente el entropía (el nombre elegante para la aleatoriedad).No importa si la fuente es parcial, siempre y cuando estimes la entropía correctamente.

Para ilustrar esto, la posibilidad de que acierte la letra mi en este comentario es mucho mayor que el de z , por lo que si tuviera que usar interrupciones clave como fuente de entropía, sería un sesgo, pero todavía hay algo de aleatoriedad en esa entrada.No se puede predecir exactamente qué secuencia de letras aparecerá a continuación en este párrafo.Puede extraer entropía de esta incertidumbre y usarla como parte de un byte aleatorio.

Generadores aleatorios reales de buena calidad como Milenrama tienen una estimación de entropía bastante sofisticada incorporada y solo emitirán tantos bytes como pueda decir de manera confiable que tiene en su "grupo de aleatoriedad".

Answer 3

Al final de la publicación, responderé a tu pregunta de por qué es posible que desees utilizar varios generadores de números aleatorios para obtener "más aleatoriedad".

Existen debates filosóficos sobre lo que significa aleatoriedad.Aquí, me referiré a "indistinguible en todos los aspectos de una distribución iid uniforme (0,1) sobre las muestras extraídas". Estoy ignorando por completo las cuestiones filosóficas sobre qué es el azar.

Knuth volumen 2 tiene un análisis en el que intenta crear un generador de números aleatorios como usted sugiere, y luego analiza por qué falla y cuáles son los verdaderos procesos aleatorios.El volumen 2 examina los RNG en detalle.

Los demás recomiendan utilizar procesos físicos aleatorios para generar números aleatorios.Sin embargo, como podemos ver en la interacción Espo/vt, estos procesos pueden tener elementos periódicos sutiles y otros elementos no aleatorios, en parte debido a factores externos con comportamiento determinista.En general, es mejor no asumir nunca la aleatoriedad, sino siempre probarla y, por lo general, se pueden corregir dichos artefactos si se tiene conocimiento de ellos.

Es posible crear un flujo "infinito" de bits que parezca completamente aleatorio y determinista.Desafortunadamente, estos enfoques crecen en memoria con la cantidad de bits solicitados (como deberían hacerlo, para evitar ciclos repetidos), por lo que su alcance es limitado.

En la práctica, casi siempre es mejor utilizar un generador de números pseudoaleatorios con propiedades conocidas.Los números clave a buscar son la dimensión del espacio de fase (que está aproximadamente compensada entre muestras y aún puede contar con que estarán distribuidas uniformemente) y el ancho de bits (el número de bits en cada muestra que son uniformemente aleatorios entre sí). ) y el tamaño del ciclo (el número de muestras que puede tomar antes de que la distribución comience a repetirse).

Sin embargo, dado que los números aleatorios de un generador determinado están de manera determinista en una secuencia conocida, su procedimiento podría quedar expuesto si alguien busca en el generador y encuentra una secuencia de alineación.Por lo tanto, es probable que pueda evitar que su distribución sea reconocida inmediatamente como proveniente de un generador de números aleatorios particular si mantiene dos generadores.Desde el primero, toma una muestra de i y luego asigna esto uniformemente sobre uno a n, donde n es como máximo la dimensión de fase.Luego, en el segundo, muestras i veces y devuelves el iésimo resultado.Esto reducirá el tamaño de su ciclo a (tamaño de ciclo original/n) en el peor de los casos, pero para ese ciclo aún generará números aleatorios uniformes, y lo hará de una manera que haga que la búsqueda de alineación sea exponencial en n.También reducirá la duración de la fase independiente.No utilice este método a menos que comprenda lo que significan para su aplicación ciclos reducidos y longitudes de fases independientes.

Answer 4

Un algoritmo para números verdaderamente aleatorios no puede existir como definición de números aleatorios es:

Tener resultados impredecibles y, en el caso ideal, todos los resultados igualmente probables;resultante de dicha selección;Falta de correlación estadística.

Hay generadores de números pseudoaleatorios (PRNG) mejores o peores, es decir,secuencias de números completamente predecibles que son difíciles de predecir sin conocer un dato, llamado semilla.

Ahora, los PRNG cuya semilla es extremadamente difícil de inferir son criptográficamente seguro.Quizás quieras buscarlos en Google si eso es lo que buscas.

Otra forma (si esto es realmente aleatorio o no es una cuestión filosófica) es utilizar fuentes de datos aleatorias.Por ejemplo, cantidades físicas impredecibles, como el ruido o la medición de la desintegración radiactiva.

Estos todavía están sujetos a ataques porque pueden medirse de forma independiente, tienen sesgos, etc.Entonces es realmente complicado.Esto se hace con hardware personalizado, que suele ser bastante caro.no tengo idea de lo bueno /dev/random Lo es, pero apuesto a que no es lo suficientemente bueno para la criptografía (la mayoría de los programas de criptografía vienen con su propio RNG y Linux también busca un RNG de hardware al inicio).

Answer 5

Según Wikipedia /dev/random, en sistemas operativos tipo Unix, es un archivo especial que sirve como un verdadero generador de números aleatorios.

El controlador /dev/random recopila ruido ambiental de varias fuentes no deterministas que incluyen, entre otras, tiempos entre teclados y tiempos entre interrupciones que ocurren dentro del entorno del sistema operativo.Los datos de ruido se muestrean y se combinan con una función de mezcla similar a CRC en un "grupo de entropía" que se actualiza continuamente.Las cadenas de bits aleatorias se obtienen tomando un hash MD5 del contenido de este grupo.La función hash unidireccional destila los verdaderos bits aleatorios de los datos del grupo y oculta el estado del grupo a los adversarios.

La rutina /dev/random mantiene una estimación de la verdadera aleatoriedad en el grupo y la reduce cada vez que se solicita el uso de cadenas aleatorias.Cuando la estimación baja a cero, la rutina se bloquea y espera a que ocurran eventos no deterministas para actualizar el grupo.

El módulo del kernel /dev/random también proporciona otra interfaz, /dev/urandom, que no espera a que el grupo de entropía se recargue y devuelve tantos bytes como se solicite.Como resultado, /dev/urandom es considerablemente más rápido en generación en comparación con /dev/random, que se usa sólo cuando se desea una aleatoriedad de muy alta calidad.

Answer 6

John von Neumann dijo una vez algo en el sentido de que "cualquiera que intente generar números aleatorios a través de medios algorítmicos está, por supuesto, viviendo en pecado".

Ni siquiera /dev/random es aleatorio, en el sentido de la palabra que le dan un matemático o un físico.Ni siquiera la medición de la desintegración de los radioisótopos es aleatoria.(La tasa de decadencia es.La medida no lo es.Los contadores Geiger tienen un pequeño tiempo de reinicio después de cada evento detectado, tiempo durante el cual no pueden detectar nuevos eventos.Esto conduce a sesgos sutiles.Hay maneras de mitigar sustancialmente esto, pero no de eliminarlo por completo).

Deja de buscar la verdadera aleatoriedad.Un buen generador de números pseudoaleatorios es realmente lo que estás buscando.

Answer 7

Si crees en un universo determinista, la verdadera aleatoriedad no existe.:-) Por ejemplo, alguien ha sugerido que la desintegración radiactiva es realmente aleatorio, pero en mi humilde opinión, el hecho de que los científicos aún no hayan descubierto el patrón no significa que no haya un patrón que resolver.Por lo general, cuando desea números "aleatorios", lo que necesita son números para el cifrado que nadie más podrá adivinar.

Lo más cercano al azar que puedes llegar es medir algo natural que ningún enemigo sería capaz de medir.Por lo general, desecha los bits más significativos de su medición, dejando los números que tienen más probabilidades de estar distribuidos uniformemente.Los usuarios de números aleatorios de núcleo duro obtienen hardware especial que mide eventos radiactivos, pero puedes obtener algo de aleatoriedad del ser humano que usa la computadora a partir de cosas como intervalos de pulsación de teclas y movimientos del mouse, y si la computadora no tiene usuarios directos, de sensores de temperatura de la CPU, y del tráfico de red.También puedes usar cosas como cámaras web y micrófonos conectados a tarjetas de sonido, pero no sé si alguien lo hace.

Answer 8

Para resumir algo de lo que se ha dicho, nuestra definición práctica de lo que es una fuente segura de aleatoriedad es similar a nuestra definición de criptográficamente segura:parece aleatorio si personas inteligentes lo han observado y no han podido demostrar que no es completamente impredecible.

Hay No sistema para generar números aleatorios que no se puedan predecir, del mismo modo que no existe ningún cifrado criptográfico que no se pueda descifrar.Las soluciones confiables que se utilizan para trabajos importantes son simplemente aquellas que hasta ahora han demostrado ser difíciles de derrotar.Si alguien te dice lo contrario, te está vendiendo algo.

La inteligencia rara vez se ve recompensada en criptografía.Elija soluciones probadas y verdaderas.

Answer 9

Una computadora generalmente tiene muchas fuentes físicas de ruido aleatorio fácilmente disponibles:

• Micrófono (con suerte en un lugar ruidoso)
• Vídeo comprimido de una cámara web (apuntado a algo variable, como una lámpara de lava o una calle)
• Temporización del teclado y del ratón
• Contenido y temporización de los paquetes de red (el mundo entero contribuye)

Y aveces

• Hardware basado en deriva de reloj
• Contadores Geiger y otros detectores de eventos raros.
• Todo tipo de sensores conectados a convertidores A/D

Lo difícil es estimar la entropía de estas fuentes, que en la mayoría de los casos es baja a pesar de las altas velocidades de datos y muy variable;pero la entropía puede estimarse con suposiciones conservadoras, o al menos no desperdiciarse, para alimentar sistemas como Yarrow o Fortuna.

Answer 10

No es posible obtener números aleatorios "verdaderos", una computadora es una construcción lógica que no puede crear nada "verdaderamente" aleatorio, solo pseudoaleatorio.Sin embargo, existen algoritmos pseudoaleatorios mejores y peores.

Para obtener un número "verdaderamente" aleatorio se necesita una fuente física aleatoria, algunas máquinas de juego en realidad las tienen integradas; a menudo es una fuente radiactiva, la desintegración radiactiva (que hasta donde yo sé es realmente aleatorio) se utiliza para generar los números.

Answer 11

Uno de los mejores métodos para generar un número aleatorio es mediante Deriva del reloj.Esto funciona principalmente con dos osciladores.

Una analogía de cómo funciona esto es imaginar un auto de carreras en un circuito ovalado simple con una línea de tiempo al comienzo de la vuelta y también una línea de tiempo en uno de los neumáticos.Cuando el coche completa una vuelta, se generará un número basado en la diferencia entre la posición de la línea blanca en la carretera y en el neumático.

Muy fácil de generar e imposible de predecir.