Fuentes alternativas de entropía

Question

Bueno, supongo 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 o el tiempo actual [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?

Disculpe si este tipo de cosas no está permitido, pero tengo curiosidad sobre la teoría detrás de las fuentes.

Answer 1

El artículo de Wikipedia sobre Hardware random number generator's enumera un par de fuentes interesantes para números aleatorios que usan propiedades físicas.

Mis favoritos:

• una fuente de radiación desintegración nuclear detectado por un contador Geiger unido a un 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. (¿No es genial?)
• El ruido atmosférico, detectado por un receptor de radio conectado a un PC

El problems section 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.

Answer 2

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 Pitfalls in Random Number Generation.

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".

Answer 3

Algunas entrada de teclado uso (tiempo de espera entre las pulsaciones del teclado), oí de pienso en una novela que la recepción de radio estático puede ser utilizado - pero por supuesto que requiere otro hardware y software ...

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

He utilizado un programa de encriptación que usa 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.

Answer 8

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

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

Answer 9

Los RNG modernos se comparan con las correlaciones en las semillas cercanas y se ejecutan varios cientos de iteraciones después de la siembra. Entonces, la desafortunada pero aburrida respuesta es que realmente no importa mucho.

Hablando en términos generales, se debe verificar que los procesos físicos aleatorios se ajusten a una distribución uniforme y de lo contrario se descuidan.

In my opinion, it's often better to use a very well understood pseudo-random number generator.

Answer 10

Algunos TPM (Trusted Platform Module) "chips" tiene un generador de números aleatorios de hardware. 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 inicializar un RNG con fines criptográficos, o cualquier aplicación donde la impredictibilidad sea importante. Usar algunos bits de orden baja del tiempo junto con varias otras fuentes probablemente sea correcto.

A similar question puede serles útil.

Answer 11

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 del detector correlacionado, velocidades de galaxias y grupos locales, polarizaciones, etc. Muchos pitfalls remain.

Answer 12

No se preocupe por una "buena" semilla 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 John D. Cook's advice. 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 acepta, por ejemplo, un valor de 64 bits y siembra el generador para que produzca números aleatorios decentes para cada entrada posible. Entonces, si está utilizando una biblioteca confiable, cualquier simiente funcionará. Pero si pirateas tu propia implementación, entonces debes ser cuidadoso.

Answer 13

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.Ellos tuvieron muchos factores juntos:

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

Incluso si algunos de éstos los 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 ininfinito de universos? Si esto es cierto, que todo el tiempo nuevos universos paralelos que se están creando, podemos hacer algo como esto:

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

En todo momento debemos estar en otra rama de universos paralelos, por lo que debemos tener diferentes ID. El único problema es cómo obtener el objeto del Universo :)

Answer 14

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

Answer 15

Lo siento, llegué tarde a esta discusión (qué ¿Tiene 3 1/2 años de edad ahora?), 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 sobre su blog en fuentes alternas de entropía (que no sea /dev/urandom).

Pero no estoy muy 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 cualquier comentarios/feedback si alguien está dispuesto e interesado:

1. Crear un buffer de serie de 64 bits + 256 bits * número de /proc Archivos 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 archivos siguientes /proc, calcular la suma SHA256:

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

   • /proc/self/stat

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

4. Crea un hash SHA256 de todo este búfer. NOTA: Pude (y probablemente debería) utilizar una función hash diferente completamente independiente de las funciones SHA; esta técnica se ha propuesto como una "salvaguarda" contra funciones hash débiles.

Ahora tienen 256 bits de con suerte aleatorios (suficientes) Datos de la entropía a 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, I podría usar una función de 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 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 nadie 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 ejecutado Diehard tests en esto (por una suma de varios cientos de mil millones bits), y parece estar pasando con gran éxito. Pero eso es probablemente más testimonio de la solidez del Mersenne Twister como PRNG que a la forma en que estoy sembrando ella.

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