thermodynamics shannon number information google theory random entropy

theory - number - shannon entropy



Fuentes alternativas de entropía (15)

De acuerdo, creo que esto es completamente subjetivo y otras cosas, pero estaba pensando en fuentes de entropía para generadores de números aleatorios. Resulta que la mayoría de los generadores están sembrados con la hora actual, ¿correcto? Bueno, tenía curiosidad sobre qué otras fuentes podrían usarse para generar números aleatorios perfectamente válidos (The loose definition).

¿Usaría varias fuentes (como el tiempo de HDD actual + tiempo de búsqueda [Estamos siendo fantásticos aquí]) juntas para crear un número "más aleatorio" que una sola fuente? ¿Cuáles son los límites lógicos de la cantidad de fuentes? ¿Cuánto es realmente suficiente? ¿Se elige el tiempo simplemente porque es conveniente?

Discúlpenme si este tipo de cosas no están permitidas, pero tengo curiosidad sobre la teoría detrás de las fuentes.

Algunos usan entrada de teclado (tiempos de espera entre pulsaciones de tecla), oí hablar de una novela en la que se puede usar la recepción estática de radio, pero por supuesto requiere otro hardware y software ...

El artículo de Wikipedia sobre el generador de números aleatorios de hardware enumera un par de fuentes interesantes para números aleatorios que usan propiedades físicas.

Mis favoritos:

  • Una fuente de radiación de descomposición nuclear detectada por un contador Geiger conectado a una PC.
  • Fotones que viajan a través de un espejo semitransparente. Los eventos mutuamente excluyentes (reflexión - transmisión) se detectan y se asocian a valores de bit "0" o "1" respectivamente.
  • Ruido térmico de una resistencia, amplificado para proporcionar una fuente de voltaje aleatorio.
  • Ruido de avalancha generado por un diodo de avalancha. (¿Cuan genial es eso?)
  • Ruido atmosférico, detectado por un receptor de radio conectado a una PC

La sección de problemas del artículo de Wikipedia también describe la fragilidad de muchas de estas fuentes / sensores. Los sensores casi siempre producen números decrecientes al azar a medida que envejecen / se degradan. Estas fuentes físicas se deben revisar constantemente mediante pruebas estadísticas que puedan analizar los datos generados, asegurando que los instrumentos no se hayan roto silenciosamente.

El kernel de Linux usa el tiempo de interrupción del dispositivo (mouse, teclado, discos duros) para generar entropía. Hay un buen artículo en Wikipedia sobre entropía.

Encontré HotBits hace varios años: los números se generan a partir de la desintegración radiactiva, números genuinamente aleatorios .

Hay límites en la cantidad de números que puede descargar al día, pero siempre me ha divertido usarlos como semillas realmente, realmente aleatorias para RNG.

No se preocupe por una semilla "buena" para un generador de números aleatorios. Las propiedades estadísticas de la secuencia no dependen de cómo se siembra el generador. Sin embargo, hay otras cosas. preocuparse de. Ver trampas en la generación de números aleatorios .

En cuanto a los generadores de números aleatorios de hardware, estas fuentes físicas tienen que medirse, y el proceso de medición tiene errores sistemáticos. Es posible que los números aleatorios "pseudo" tengan una calidad superior a los números aleatorios "reales".

Ruido en la parte superior del espectro de fondo de microondas cósmicos. Por supuesto, primero debe eliminar algo de anisotropía, objetos en primer plano, ruido de detector correlacionado, velocidades de galaxias y grupos locales, polarizaciones, etc. Se mantienen muchas dificultades .

SGI una vez usó fotos de una lámpara de lava en varias "fases globales" como fuente de entropía, que eventualmente se convirtió en un generador de números aleatorios de código abierto llamado LavaRnd .

Uso Random.ORG , proporcionan datos aleatorios gratuitos del ruido de la atmósfera, que utilizo para volver a sembrar periódicamente un RNG Mersene-Twister. Es casi tan aleatorio como puedes obtener sin dependencias de hardware.

Utilicé un programa de encriptación que usaba el movimiento del mouse de los usuarios para generar números aleatorios. El único problema fue que el programa tuvo que pausar y pedirle al usuario que moviera el mouse al azar durante unos segundos para que funcionase correctamente, lo que podría no ser siempre práctico.

La fuente de semilla no es tan importante. Más importante es el algoritmo del generador de pseudo números. Sin embargo, hace un tiempo escuché sobre generar semillas para algunas operaciones bancarias. Tomaron muchos factores juntos:

  • hora
  • temperatura del procesador
  • velocidad del ventilador
  • voltaje de la CPU
  • No recuerdo más :)

Incluso si algunos de estos parámetros no cambian mucho en el tiempo, puede ponerlos en una buena función de hash.

¿Cómo generar un buen número aleatorio?

¿Tal vez podamos tener en cuenta un número infinito de universos? Si esto es cierto, siempre que se creen nuevos universos paralelos, podemos hacer algo como esto:

int Random() { return Universe.object_id % MAX_INT; }

En todo momento, deberíamos estar en otra rama de universos paralelos, por lo que deberíamos tener una identificación diferente. El único problema es cómo obtener el objeto del Universo :)

¿Qué le parece girar un hilo que manipulará alguna variable en un ciclo cerrado durante un tiempo fijo antes de matarlo? Con lo que termines dependerá de la velocidad del procesador, la carga del sistema, etc. Muy hokey, pero mejor que srand (time (NULL)) ...

Algunos "chips" TPM (Trusted Platform Module) tienen un hardware RNG. Desafortunadamente, el TPM (Broadcom) en mi computadora portátil Dell carece de esta característica, pero muchas computadoras vendidas hoy vienen con un hardware RNG que utiliza procesos mecánicos cuánticos verdaderamente impredecibles. Intel ha implementado la variedad de ruido térmico.

Además, no utilice el tiempo actual solo para generar un RNG con fines criptográficos, o cualquier aplicación en la que la imprevisibilidad sea importante. Usar algunos bits de orden baja del tiempo junto con varias otras fuentes probablemente sea correcto.

Una pregunta similar puede serle útil.

Lamento llegar tarde a esta discusión (¿qué es exactamente 3 años y medio?), Pero tengo un renovado interés en la generación de PRN y fuentes alternativas de entropía. El desarrollador de kernel de Linux, Rusty Russell, recientemente tuvo una discusión en su blog sobre fuentes alternativas de entropía (que no sea /dev/urandom ).

Pero, no estoy tan impresionado con sus elecciones; la dirección MAC de una NIC nunca cambia (aunque es única de todas las demás), y el PID parece demasiado pequeño como un tamaño de muestra posible.

He incursionado con un Mersenne Twister (en mi caja de Linux) que está sembrado con el siguiente algoritmo. Estoy pidiendo comentarios / comentarios si alguien está dispuesto e interesado:

  1. Cree un búfer de matriz de 64 bits + 256 bits * cantidad de archivos /proc continuación.
  2. Coloque el valor del contador de marca de tiempo (TSC) en los primeros 64 bits de este búfer.

  3. Para cada uno de los siguientes /proc archivos, calcule la suma SHA256:

    • /proc/meminfo
    • /proc/self/maps
    • /proc/self/smaps
    • /proc/interrupts
    • /proc/diskstats

    • /proc/self/stat

      Coloque cada valor hash de 256 bits en su propia área de la matriz creada en (1).

  4. Crea un hash SHA256 de todo este buffer. NOTA: podría (y probablemente debería) usar una función hash diferente completamente independiente de las funciones SHA: esta técnica ha sido propuesta como una "salvaguarda" contra funciones hash débiles.

Ahora tengo 256 bits de datos de entropía ESPERAMENTE aleatorios (suficientes) para sembrar mi Mersenne Twister. Uso lo anterior para rellenar el comienzo de la matriz MT (624 enteros de 32 bits) y luego inicializo el resto de esa matriz con el código del autor MT. Además, podría usar una función hash diferente (por ejemplo, SHA384, SHA512), pero necesitaría un búfer de matriz de tamaño diferente (obviamente).

El código original de Mersenne Twister requería una sola semilla de 32 bits, pero creo que eso es terriblemente inadecuado. Ejecutar "simplemente" 2 ^ 32-1 MT diferentes en busca de romper la criptografía no está más allá del ámbito de la posibilidad práctica en este día y edad.

Me encantaría leer los comentarios de cualquier persona sobre esto. La crítica es más que bienvenida. Defenderé mi uso de los archivos /proc como los anteriores porque están cambiando constantemente (especialmente los archivos /proc/self/* , y el TSC siempre produce un valor diferente (resolución de nanosegundos [o mejor], IIRC). He llevado a cabo pruebas de Diehard (por una cantidad de cientos de miles de millones de bits), y parece estar pasando a toda velocidad. Pero eso es probablemente más un testimonio de la solidez del Mersenne Twister como PRNG que de cómo lo estoy sembrando .

Por supuesto, estos no son totalmente inmunes a que alguien los piratee, pero simplemente no veo todos estos (y SHA *) siendo pirateados y rotos en mi vida.

No se preocupe por una semilla "buena" para un generador de números aleatorios. Las propiedades estadísticas de la secuencia no dependen de cómo se siembra el generador.

No estoy de acuerdo con el consejo de John D. Cook . Si siembras Mersenne Twister con todos los bits configurados en cero, excepto uno, inicialmente generará números que son cualquier cosa menos aleatorios. El generador tarda mucho tiempo en convertir este estado en algo que pase las pruebas estadísticas. Simplemente establecer los primeros 32 bits del generador en una semilla tendrá un efecto similar. Además, si todo el estado se establece en cero, el generador producirá ceros infinitos.

El código RNG correctamente escrito tendrá un algoritmo de siembra correctamente escrito que acepte, por ejemplo, un valor de 64 bits y sembrará el generador para que produzca números aleatorios decentes para cada entrada posible. Entonces, si está utilizando una biblioteca confiable, entonces cualquier simiente funcionará. Pero si pirateas tu propia implementación, entonces debes ser cuidadoso.