Generador de numeros aleatorios
523 views
Skip to first unread message
martin ribelotta
Dec 29, 2015, 1:52:16 PM12/29/15
to embeb...@googlegroups.com
Buenas gente, ando con un tema bastante esoterico entre manos, la generación de numeros pseudo-aleatorios.
Especificamente, estoy implementando la función urandom de uos en micropython:
Primero que nada, me fije si el micro no tenia hardware para hacer esto y no, los que tienen el TRNG (true random number generator) son la seria LPC43SXX (con control de exportaciones parece)
Segundo, intente armar un PRNG simple iniciando con el numero de milisegundos la semilla y pareció andar muy bien.
Hasta que reinicie varias veces imprimiendo el primer numero aleatorio que genero, oh sorpresa, es siempre el mismo.
Entonces, me lei un par de papares sobre semillas de entropia y creí que la mejor manera de inicializar la semilla era usando una porción de la RAM.
De esto termine en este código:
- static __attribute__ ((section(".noinit"))) char entropy_pool[32];
- static __attribute__ ((section(".noinit"))) uint32_t s_seed;
- uint32_t lfsr (uint32_t input) {
- entropy_pool[input&0x1F] = input;
- return (input >> 1) ^ (-(input & 0x01) & 0x00E10000); // Standar LFSR PRNG
- }
- uint32_t get_rnd(void) {
- int i = 0;
- for(i=0; i<sizeof(entropy_pool); i++)
- s_seed += entropy_pool[i];
- s_seed = lfsr(s_seed);
- return s_seed;
- }
Ahora parece andar bien, pero mi punto viene por el lado de si esto es realmente "aleatorio".
Creo que estoy bien al pensar que los 256 bits de entropy_pool no tienen casi ninguna posibilidad de arrancar todos en el mismo estado (como calcularia eso? 1/2+1/4+1/8+...1/256????) pero me surgen mas dudas:
¿Esta bien lo de "agitar" el entropy pool con los datos del LFSR?
Relacionado a lo anterior ¿No terminaría en algún momento con datos "predecibles"? Es decir, dado un tamaño suficientemente grande de números aleatorios, terminaría viendo el patrón.
La inicialización no garantiza que s_seed no sea cero ¿como podría hacer eso sin perrearle ningún valor?
¿Como pruebo el nivel de aleatoriedad de esto?
¿Que otra fuente de entropia podria usar? La recepción serial seria uno, pero en un entorno desatendido eso podria no existir nunca
¿Como mido la "entropia" del entropy_pool??? Lo que se de entropia, es que se define como los estados internos de un sistema sobre sus estados externos (ok, log de eso) ¿Como defino "externo" o "interno"? ¿Hay alguna forma mas facil? ¿Algun experto en linux sabe como funciona el entropy pool de /dev/random bien?
Bueno, eso, felices fiestas y mejor coding!
Alejandro Sosa
Dec 29, 2015, 2:01:48 PM12/29/15
to embeb...@googlegroups.com
Martin..te comento algo q hice hace mucho. Pero te advierto q era super basico, para un producto que tenia q temporizar en forma aleatoria entre un T1 y T2 y usando un micro de 8 bits.
Simplemente, deje un pin analogico de entrada leyendo ruido..y muestreando en no multiplo de 50 hz, obvio.
Para esta app reducida en recursos me anduvo joya
--
-- Recibiste este mensaje porque estás suscripto al Grupo Google Embebidos32. Para postear en este grupo, escribe un email a embeb...@googlegroups.com. Para des-suscribirte, envía un email a embebidos32...@googlegroups.com. Para más opciones, visita el sitio del grupo en https://groups.google.com/d/forum/embebidos32?hl=es
---
Has recibido este mensaje porque estás suscrito al grupo "Embebidos32" de Grupos de Google.
Para anular la suscripción a este grupo y dejar de recibir sus mensajes, envía un correo electrónico a embebidos32...@googlegroups.com.
Para acceder a más opciones, visita https://groups.google.com/d/optout.
Alejandro Sosa - cel 011 15 5346 5912 
CUIT 20-22592457-1
Diseño y fabricación de equipos electrónicos para la industria.
- Desarrollos a medida para sustitución de importaciones -
Facebook:
Pagina web :
"Disfruta este momento, este momento es tu vida."
martin ribelotta
Dec 29, 2015, 2:09:56 PM12/29/15
to embeb...@googlegroups.com
El 29 de diciembre de 2015, 16:01, Alejandro Sosa <alejand...@gmail.com> escribió:
Martin..te comento algo q hice hace mucho. Pero te advierto q era super basico, para un producto que tenia q temporizar en forma aleatoria entre un T1 y T2 y usando un micro de 8 bits.Simplemente, deje un pin analogico de entrada leyendo ruido..y muestreando en no multiplo de 50 hz, obvio.Para esta app reducida en recursos me anduvo joya
Como solución especifica esta bueno, pero lo que busco es algo mas generico.
De hecho, espero poder generar numeros con calidad criptografica (tiempo de retransmición para paquetes de red)
Te pongo un ejemplo en el que siempre podrias tener el mismo numero:
* Medis el consumo de tu aparato (o su emición electromagnetica)
* Sacas un patron de ese consumo que te dice por donde esta ejecutando tu micro
* Correlacionas con lo que está haciendo y estimas (experimentalmente) cuando lee el pin.
* Por los mismos medios electromagneticos, forzas a ese pin a inducirse en un estado determinado.
Eso de mala leche, pero, donde yo vivo (bariloche) hay muy poca humedad ambiente, lo que hace inducir MUCHOS milivoltios en circuitos CMOS y dejar un pin al aire es MALA idea, y aunque no lo fuera, poner el aparato cerca de una fuente de EMI fierte garantiza el leer 1 (o cero) todo el tiempo en ese pin.
Otra posibilidad descartable es usar el bit menos significativo del ADC por las mismas razones.
Juan Cecconi
Dec 29, 2015, 2:10:56 PM12/29/15
to embebidos32
Hola Martín,
Yo alguna vez en una implementación sencillo usaba una combinación de varios registros donde en el estado de reset no estaba garantizado el estado inicial, más otros que podían depender del estado anterior (acumuladores, timers, etc) al menos para la semilla...El 29 de diciembre de 2015, 16:01, Alejandro Sosa <alejand...@gmail.com> escribió:
Alejandro Sosa
Dec 29, 2015, 2:16:06 PM12/29/15
to embeb...@googlegroups.com
si lo se, obvio si lo encerras en una jaula de faraday...chau, pero bue no era el caso.
Creo recordar q en los libros de estadistica hay unos formulones para generar esos numeros..suerte
Mariano Cerdeiro
Dec 29, 2015, 2:33:41 PM12/29/15
to embebidos32
Hola Martin,
cada cuanto necesitas un número aleatorio, que tan estable es tu fuente de corriente? Podrias guardar el estado del PRNG asi no lo tenes que reiniciar todo, o si lo haces solo parcialmente. de esta forma tenes un menor riesgo. Esto claro te cuesta almacenar cada x tiempo en flash/Eeprom el valor y depende que tan seguro es tu fuente si sirve este metodo o no.
Fernando Lichtschein
Dec 29, 2015, 2:33:46 PM12/29/15
to embebidos32@
Martín,
La mejor fuente de algoritmos es la serie de libros de Donald Knuth The Art of Computer Programming, la parte de números aleatorios está en el volumen 2 "Seminumerical algorithms". Hay una corrección al algoritmo en la página de él http://www-cs-faculty.stanford.edu/~uno/news02.html.
Aparentemente por los comentarios funciona bien sin semilla, nosotros cuando teníamos que hacer algo como eso tomábamos los últimos dígitos de la hora del sistema (mili o micro segundos), supongo que en un Cortex-M se puede hacer algo con el Systick o alguno de esos.
De todas maneras es bueno leer a Knuth.
Saludos y buen año,
El 29 de diciembre de 2015, 15:51, martin ribelotta <martinr...@gmail.com> escribió:
Maximiliano Antonelli
Dec 29, 2015, 9:13:04 PM12/29/15
to embeb...@googlegroups.com
Hola. Mi tesis es sobre cuantificados de aleatoriedad. Si me mandás una serie de 10 millones de bits (o el equivalente en la aritmética que trabaje el sistema) puedo darte un par de números que te dicon si está andando bien.
Otra opción es que les corras los test de marsaglia o la batería NIST o DieHard, que están disponibles online.
Estoy por entrar al cine y por quedarme sin pareja, mañana te mando los link.
Saludos.
Reply all
Reply to author
Forward
0 new messages