algorithm - sorteos - numeros aleatorios google
Verdadero generador de números aleatorios (11)
Al final de la publicación, responderé a su pregunta de por qué es posible que desee utilizar múltiples generadores de números aleatorios para "más aleatoriedad".
Hay debates filosóficos sobre lo que significa la aleatoriedad. Aquí, quiero decir "indistinguible en todos los aspectos de una distribución uniforme (iid) iid sobre las muestras extraídas". Estoy ignorando totalmente las cuestiones filosóficas de lo aleatorio.
El volumen 2 de Knuth 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 otros recomiendan que use 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, lo mejor es nunca asumir la aleatoriedad, sino siempre probarla, y normalmente puede corregir dichos artefactos si los conoce.
Es posible crear una corriente "infinita" de bits que aparece completamente aleatoria, determinista. Desafortunadamente, tales enfoques crecen en la memoria con la cantidad de bits solicitados (como deberían ser, para evitar ciclos repetitivos), por lo que su alcance es limitado.
En la práctica, casi siempre es mejor utilizar un generador de números pseudoaleatorio con propiedades conocidas. El número clave que se debe buscar es la dimensión del espacio de fases (que se compensa aproximadamente entre las muestras que todavía puede contar con distribución uniforme) y el ancho de bits (el número de bits en cada muestra que son uniformalmente aleatorios entre sí) ), y el tamaño del ciclo (la cantidad 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 son determinísticamente en una secuencia conocida, su procedimiento puede ser expuesto por alguien que busca a través del generador y encuentra una secuencia de alineación. Por lo tanto, es probable que evite que su distribución sea inmediatamente reconocida como proveniente de un generador de números aleatorios particular si mantiene dos generadores. Desde el principio, muestras i, y luego trazas esto uniformalmente sobre uno a n, donde n es como máximo la dimensión de fase. Luego, en el segundo, haz una muestra i veces y devuelve el i-ésimo resultado. Esto reducirá el tamaño de su ciclo a (tamaño del ciclo original / n) en el peor de los casos, pero para ese ciclo generará números aleatorios uniformes, y lo hará de una manera que hace que la búsqueda de la alineación sea exponencial en n. También reducirá la longitud de fase independiente. No use este método a menos que comprenda qué significan ciclos reducidos y longitudes de fase independientes para su aplicación.
Perdón por que esto no sea una pregunta "real", pero en algún momento recuerdo haber visto una publicación aquí sobre aleatorizar aleatoriamente un generador de números aleatorios para generar números verdaderamente aleatorios, no solo pseudoaleatorios. No lo veo si lo busco.
¿Alguien sabe sobre ese artículo?
Creo que 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 llame a randomize ().
Puede obtener números aleatorios "verdaderos" del hardware especial. También puede recopilar entropía de los movimientos del mouse y cosas por el estilo.
John von Neumann dijo una vez algo sobre el efecto de "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 de un matemático o un físico. Ni siquiera la medición de desintegración de radioisótopos es aleatoria. (La velocidad de disminución es. La medición no lo es. Los contadores Geiger tienen un pequeño tiempo de reinicio después de cada evento detectado, durante el cual no pueden detectar nuevos eventos. Esto genera sesgos sutiles. Hay maneras de mitigarlo sustancialmente, pero no eliminarlo por completo).
Deja de buscar la verdadera aleatoriedad. Un buen generador de números pseudoaleatorios es realmente lo que estás buscando.
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 mejores y peores algoritmos pseudoaleatorios.
Para obtener un número "verdaderamente" aleatorio se necesita una fuente física aleatoria, algunas máquinas de juego en realidad las tienen incorporadas; a menudo es una fuente radiactiva, la desintegración radiactiva (que hasta donde sé que es verdaderamente aleatoria) se usa para generar los números.
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 seguridad criptográfica: parece aleatoria si la gente inteligente la ha mirado y no han podido demostrar que no es así. t completamente impredecible.
No existe un sistema para generar números aleatorios que no se podría predecir, así como no existe un cifrado criptográfico que no se pueda descifrar. Las soluciones de confianza utilizadas para trabajos importantes son simplemente aquellas que han demostrado ser difíciles de superar hasta ahora. Si alguien te dice lo contrario, te están vendiendo algo.
La inteligencia rara vez se recompensa en la criptografía. Ve con soluciones probadas y verdaderas.
Si crees en un universo determinista, la verdadera aleatoriedad no existe. :-) Por ejemplo, alguien ha sugerido que la desintegración radiactiva es realmente aleatoria, pero en mi humilde opinión, el hecho de que los científicos aún no hayan resuelto el patrón no significa que no haya un patrón para resolver. Por lo general, cuando quieres números "aleatorios", lo que necesitas son números para el cifrado que nadie más podrá adivinar.
Lo más cerca que puedes llegar al azar es medir algo natural que ningún enemigo también podría medir. Usualmente tiras los bits más significativos de tu medida, dejando que los números con mayor probabilidad se distribuyan uniformemente. Los usuarios de núcleo aleatorio obtienen un hardware especial que mide los eventos radiactivos, pero puede obtener aleatoriedad del humano usando la computadora a partir de intervalos de pulsación de tecla y movimientos del mouse, y si la computadora no tiene usuarios directos, desde los sensores de temperatura de la CPU, y del tráfico de red. También podría usar cosas como cámaras web y micrófonos conectados a tarjetas de sonido, pero no sé si alguien lo hace.
Tengo que estar en desacuerdo 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 no pudieras.
La forma en que funciona el generador de números aleatorios de software es un conjunto de datos aleatorios recopilados de muchos lugares diferentes, como la deriva del reloj, los tiempos de interrupción, etc.
El truco para estos esquemas es la estimación correcta de la entropía (el nombre elegante para la aleatoriedad). No importa si la fuente es sesgada, siempre que estime la entropía correctamente.
Para ilustrar esto, la posibilidad de que pulso la letra e en este comentario es mucho más alta que la de z , así que si tuviera que usar interrupciones de tecla como fuente de entropía, sería un sesgo, pero todavía hay algo aleatorio que se debe tener en esa entrada. No puede predecir exactamente qué secuencia de letras vendrá después en este párrafo. Puede extraer entropía de esta incertidumbre y usarla como parte de un byte aleatorio.
Los generadores aleatorios reales de buena calidad como Yarrow tienen una estimación de entropía bastante sofisticada incorporada y solo emitirán tantos bytes como pueda decir con seguridad en su "conjunto de aleatoriedad".
Un algoritmo para números verdaderamente aleatorios no puede existir ya que la definición de números aleatorios es:
Tener resultados impredecibles y, en el caso ideal, todos los resultados son igualmente probables; resultante de tal selección; sin correlación estadística
Hay mejores o peores generadores de números pseudoaleatorios (PRNG), es decir, secuencias de números completamente predecibles que son difíciles de predecir sin conocer una información, llamada semilla .
Ahora, los PRNG para los cuales es extremadamente difícil inferir que la semilla son criptográficamente seguras . Es posible que desee buscarlos en Google si eso es lo que busca.
Otra forma (si esto es verdaderamente aleatorio o no es una cuestión filosófica) es usar fuentes de datos al azar. Por ejemplo, cantidades físicas impredecibles, como el ruido, o la medición de la desintegración radiactiva.
Estos aún están sujetos a ataques porque pueden medirse independientemente, tener sesgos, etc. Entonces es realmente complicado. Esto se hace con hardware personalizado, que suele ser bastante caro. No tengo idea de qué tan bueno /dev/random es, pero apostarí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 en el arranque).
Una computadora generalmente tiene muchas fuentes físicas de ruido aleatorio fácilmente disponibles:
- Micrófono (con suerte en un lugar ruidoso)
- Video comprimido de una cámara web (señalando algo variable, como una lámpara de lava o una calle)
- Tiempo de teclado y mouse
- Contenido y tiempo de paquetes de red (todo el mundo contribuye)
Y aveces
- Hardware basado en la deriva del reloj
- Contadores Geiger y otros detectores de eventos raros
- Todo tipo de sensores conectados a convertidores A / D
Lo que es 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 tasas de datos y muy variable; pero la entropía puede estimarse con suposiciones conservadoras, o al menos no desperdiciadas, para alimentar sistemas como Yarrow o Fortuna.
Uno de los mejores métodos para generar un número aleatorio es mediante Clock Drift . Esto funciona principalmente con dos osciladores.
Una analogía de cómo funciona esto es imaginar un auto de carrera en un circuito oval simple con una línea de tiempo al inicio de la vuelta y también una línea de tiempo en uno de los neumáticos. Cuando el automóvil complete 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 la llanta.
Muy fácil de generar e imposible de predecir.
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 recoge el ruido ambiental de varias fuentes no deterministas, incluidas, entre otras, las temporizaciones entre teclados y las temporizaciones entre interrupciones que se producen dentro del entorno del sistema operativo. Los datos de ruido se muestrean y combinan con una función de mezcla de tipo CRC en una actualización continua de `` entropy-pool ''''. Las cadenas de bits aleatorias se obtienen tomando un hash MD5 de los contenidos de este grupo. La función hash unidireccional destila los bits aleatorios verdaderos de los datos de la agrupación y oculta el estado de la agrupación de los adversarios.
La rutina / dev / random mantiene una estimación de aleatoriedad real en el grupo y la disminuye cada vez que se solicitan cadenas aleatorias para su uso. Cuando la estimación baja a cero, la rutina se bloquea y espera la ocurrencia de eventos no determinísticos para actualizar el grupo.
El módulo / dev / random kernel también proporciona otra interfaz, / dev / urandom, que no espera a que el pool de entropía vuelva a cargar y devuelve tantos bytes como se solicite. Como resultado, / dev / urandom es considerablemente más rápido en la generación en comparación con / dev / random que se usa solo cuando se desea una aleatoriedad de muy alta calidad.