Usando un generador de números aleatorios en Arduino: funciones Random y RandomSeed. Curso Arduino - Tiempo y Aleatorio Arduino generando una secuencia de bits aleatoria

Al programar Arduino, hay ocasiones en las que es necesario obtener un número que no será conocido de antemano ni por el programador que escribe el boceto ni por el usuario que utilizará el Arduino con dicho programa. En este caso, un generador de números aleatorios (o más bien pseudoaleatorios) viene al rescate.

Para activar este generador, simplemente use las funciones random() o randomSeed(). Este material le mostrará cómo trabajar con estas funciones, así como cómo deshacerse de la pseudoaleatoriedad al generar números.

En general, un generador de números pseudoaleatorios simula la apariencia caótica o aleatoria de los números, pero de hecho, si analizas una serie de estos números durante un período suficientemente largo, puedes notar un patrón determinado.

Entonces, la función aleatoria para generar números pseudoaleatorios puede tener hasta dos parámetros y se escribe como aleatorio(max) o aleatorio(min, max). Aquí parámetro máximo, que es obligatorio, especifica el límite superior del rango para generar números pseudoaleatorios. Mediante el uso parámetro adicional min puede establecer el límite inferior del rango. Como resultado, la función devolverá algún número pseudoaleatorio en el rango del mínimo al máximo-1.

Es importante comprender que cuando se utiliza la función aleatoria(), cada vez se generará exactamente la misma lista de números pseudoaleatorios. Por ejemplo, si haces una máquina tragamonedas y la primera vez que presionas la manija, muestra una combinación ganadora, entonces puedes estar seguro de que si reinicias el Arduino y presionas la manija nuevamente, esa máquina tragamonedas mostrará la misma combinación ganadora. . De hecho, no es fácil implementar una máquina de juego con generación de números completamente aleatoria en Arduino, como se implementa, por ejemplo, en las máquinas de juego www.igrovye-apparati-vulcan.com/, pero se puede resolver parcialmente el problema usando randomSeed. () función.

Esta función toma un valor (como un número entero) y usa el número para modificar la lista aleatoria generada por la función random(). Puede poner randomSeed() en la función de configuración y usar la función random() en un número infinito. bucle. Pero incluso entonces, el problema es que aunque la secuencia de números aleatorios será diferente cuando se use la función randomSeed(), seguirá siendo la misma cada vez que se ejecute el boceto.

La única solución en este caso puede ser utilizar periféricos analógicos (ADC) y la función analogRead() correspondiente. Si la entrada analógica no está conectada a nada, es decir, se deja "colgando" en el aire, entonces gracias al ruido en esta línea se pueden obtener números verdaderamente aleatorios. Luego, en la configuración de configuración puede escribir randomSeed(analogRead(A0)). Siempre que el puerto analógico A0 no esté conectado en ningún lugar.

Se ha escrito mucho sobre generadores de números aleatorios, pero casi siempre cuando se trata de implementación, se da a entender (o se afirma explícitamente) que estamos hablando acerca de sobre x86/x64 y otras arquitecturas "para adultos". Al mismo tiempo, los foros dedicados al desarrollo de dispositivos con microcontroladores están llenos de preguntas: "¿Cómo puedo generar un número aleatorio en %controllername%?" Además, la gama de respuestas se extiende desde "mirar en Google/Wikipedia" hasta "utilizar la función estándar". Esta "función estándar" no siempre existe y se adapta al desarrollador en todos los aspectos; más a menudo es al revés: a veces los números están lejos de ser aleatorios, a veces la velocidad de funcionamiento es demasiado baja o, a veces, el código resultante no caben en la memoria libre.
Intentemos descubrir qué son los algoritmos de generación de números aleatorios, cómo elegir el correcto y, lo más importante, cuáles son las características de implementar estos algoritmos en los controladores.

Evaluación de la "aleatoriedad"

Las aplicaciones del RNG pueden ser muy diferentes, desde juguetes hasta criptografía seria. Por consiguiente, los requisitos para el generador también varían mucho. Existen pruebas especiales para evaluar la calidad (nivel de “aleatoriedad”) del generador. Aquí están los más básicos de ellos:

• Prueba de frecuencia. Consiste en contar el número de ceros y unos en una secuencia de bits. Debe haber aproximadamente la misma cantidad de unos y ceros.
• Pruebe una secuencia de bits idénticos. Se buscan filas de bits idénticos, como 000...0 o 111...1. La distribución de frecuencias con las que se producen las series, dependiendo de su longitud, debe corresponder a esta distribución para una señal verdaderamente aleatoria.
• Prueba espectral. Se aplica una transformada de Fourier discreta a la secuencia original. El espectro resultante no debería tener picos significativos que indiquen la presencia de propiedades periódicas de la secuencia.
• Prueba de autocorrelación. Se calcula el valor de correlación entre copias de secuencia desplazadas entre sí. La prueba le permite encontrar regiones repetidas en una secuencia.

Existen kits especiales que incluyen decenas de pruebas similares:
NIST: utilizado en la competencia AES para evaluar algoritmos de cifrado.
DIEHARD es uno de los sets más rigurosos que existen.

Algoritmos PRNG

Cualquier secuencia generada según un algoritmo estrictamente definido no puede considerarse verdaderamente aleatoria, por eso, cuando se habla de generadores algorítmicos, se utiliza el término pseudoaleatorio subsecuencia. Cualquier generador de números pseudoaleatorios (PRNG) entrará en bucle tarde o temprano, lo otro es que este “tarde” puede llegar en unos milisegundos, o tal vez en unos años. La duración del ciclo depende del tamaño del estado interno del generador N (de hecho, esta es la cantidad de memoria que necesita el generador) y varía de 2 (N/2) a 2 N bits.
Se ha inventado una gran variedad de algoritmos PRNG, pero no todos son convenientes para su implementación en microcontroladores. Estamos severamente limitados en velocidad y memoria disponible; muchos controladores no soportan aritmética real o incluso instrucciones de multiplicación. Teniendo en cuenta estas limitaciones, veamos algunos algoritmos conocidos.

Método lineal congruente

El siguiente miembro de la secuencia se calcula usando la fórmula
X i+1 = (aX i + c) mod m
Número metro define el período máximo de la secuencia, números enteros a Y C- coeficientes “mágicos”. Número metro Es razonable elegir igual a una potencia de dos, en este caso la operación de conversión de módulo se reduce a descartar los bits más significativos. Para obtener el plazo máximo se deberán cumplir las siguientes condiciones:
- C y m debe ser primo relativo,
- a-1 debe ser un múltiplo pag para todos los factores primos pag números metro,
- Si metro es múltiplo de 4 (y en nuestro caso será múltiplo), entonces a-1 debe ser múltiplo de 4.
Hay una sutileza más: solo se deben tomar como resultado los bits más significativos de la variable de estado X, ya que para los bits más bajos los parámetros estadísticos de aleatoriedad son mucho peores. El algoritmo lineal congruente se implementa comúnmente como rand() estándar en muchas bibliotecas.

Ventajas:

• el período máximo posible para un tamaño dado de la variable de estado;
• suficientemente rapido;
• a menudo ya está implementado en la biblioteca del compilador.

Desventajas:

• se requiere una operación de multiplicación;
• No todos los bits son igualmente aleatorios.

Resumen: un algoritmo rápido y sencillo para aplicaciones no muy exigentes.

Método de Fibonacci con rezagos

Este algoritmo utiliza la relación
X i = X i-a - X i-b,
¿Dónde está la variable de estado? X- entero sin signo. Valores de retardo a Y b no se toman cualquiera, sino estrictamente definidos; para conseguir la máxima calidad se recomiendan los pares (17,5), (55,24) o (97,33). Cuanto mayor sea el retraso, mayor será el período y mejores serán las propiedades espectrales de la secuencia. Por otro lado, para que el generador funcione es necesario almacenar el máximo (a,b) de los números anteriores, lo cual no siempre es aceptable. Además, para ejecutar el generador necesita números máximos (a, b), que generalmente se obtienen usando un PRNG más simple.

Ventajas:

• no requiere operaciones de multiplicación;
• Todos los bits de un número aleatorio son equivalentes en propiedades estadísticas.

Desventajas:

• requiere una gran cantidad de memoria;
• requiere una gran variedad de números para ejecutarse.

Resumen: un algoritmo de muy alta calidad, pero que requiere muchos recursos.

Registro de desplazamiento de retroalimentación lineal

La variable de estado se almacena en un registro de longitud N. Generar el siguiente estado implica dos pasos:

1. El valor del bit se calcula C = X i1 xor X i2 xor… X ik, donde i1, i2…ik- registrar números de bits, llamados enfermedad de buzo.
2. El registro se desplaza 1 bit hacia la derecha, el bit más a la izquierda toma el valor CON.

La salida del generador es el bit más a la derecha (o más a la izquierda, o lo que sea) del registro, es decir, la secuencia pseudoaleatoria se genera un bit por iteración. Con los números de grifo seleccionados correctamente, el período del generador será 2 N - 1. "Menos uno", ya que el estado cero del registro está prohibido. Números de sucursales para norte del 3 al 168 se pueden encontrar en este documento.
Además de la configuración descrita anteriormente, que, por cierto, se llama configuración de Fibonacci (¡no debe confundirse con el método PRNG del mismo nombre!), existe la llamada. Configuración de Galois.


En lugar de utilizar la suma de los bits en la secuencia de derivación para generar un nuevo bit más a la izquierda, aplica XOR a cada bit de la secuencia de derivación con el bit más a la derecha y luego gira todo el registro hacia la derecha. Este esquema es más difícil de entender, pero más fácil de implementar, ya que todas las operaciones XOR se pueden realizar simultáneamente. En términos de duración del período y calidad de los números pseudoaleatorios, los esquemas de Fibonacci y Galois son equivalentes.

Ventajas:

• implementación muy simple, ni siquiera requiere aritmética, solo operaciones y desplazamientos de bits;
• algoritmo muy rápido (especialmente el esquema de Galois);
• buenas propiedades estadísticas.

Desventajas:

• es necesario verificar que el valor inicial de la desigualdad sea cero.

Resumen: Algoritmo muy rápido y de bastante alta calidad.

Algoritmos a prueba de criptomonedas

Para su uso en criptografía, los PRNG tienen un requisito esencial más: irreversibilidad. Todos los algoritmos enumerados anteriormente no tienen esta propiedad: conociendo varios valores de salida del PRNG, puede, resolviendo un sistema simple de ecuaciones, encontrar los parámetros del algoritmo (las mismas constantes "mágicas" a B C etc). Y conociendo los parámetros, puedes reproducir toda la secuencia pseudoaleatoria.
Cualquier cifrado de bloque suficientemente fuerte se puede utilizar como algoritmo PRNG criptográficamente fuerte. Al elegir una clave secreta, puede obtener bloques de números pseudoaleatorios aplicando el algoritmo a números naturales secuenciales. Para un cifrado de bloque de N bits, el período no será superior a 2 N. La seguridad de tal esquema depende enteramente del secreto de la clave.
Todos los algoritmos criptográficos modernos se prueban para su uso como PRNG, es decir, al utilizar un algoritmo certificado, no es necesario preocuparse especialmente por las propiedades estadísticas y espectrales del flujo de salida. Sólo debe preocuparse por la “glotonería” computacional de los algoritmos criptográficos. Si necesita realizar una gran cantidad de operaciones de cifrado, tiene sentido elegir un controlador con bloques criptográficos de hardware. A menudo, estos controladores también tienen un PRNG de hardware resistente a las criptomonedas muy bueno.

Fuentes de entropía

Como ya se dijo, utilizando únicamente algoritmos deterministas, es imposible generar un número verdaderamente aleatorio. Por lo tanto, se suele utilizar una combinación de PRNG + externo. fuente de entropía. La fuente de entropía se utiliza para establecer el valor inicial del PRNG, y la tarea de este último es garantizar la pureza espectral y estadística de la secuencia. ¿Qué se puede utilizar como fuente de entropía? Sí, casi cualquier cosa.

Actividad del usuario

Si el dispositivo interactúa con el usuario de alguna manera, bastante Buena decisión utilizará al propio usuario como fuente de entropía. Por ejemplo, el tiempo de presionar un botón, medido con una precisión de un microsegundo (o más bien, sus dígitos menos significativos), es completamente impredecible. Sin embargo, muchas veces el dispositivo debe funcionar de forma autónoma, lo que significa que nos vemos privados de este maravilloso canal de información.

Conversor analógico a digital

Muchos controladores tienen ADC integrados. Y en muchos controladores son de una calidad muy mediocre, hechos simplemente "para ser". Los bits de orden inferior del resultado del ADC casi siempre contienen un ruido significativo, incluso cuando se mide voltaje de CC. Esto se puede usar: conecte la entrada del ADC al voltaje de suministro a través de un divisor, tome algunas docenas de mediciones, tome los bits menos significativos; aquí tiene un excelente número aleatorio. Si el ADC contiene un preamplificador incorporado, enciéndalo, también hace ruido.

Generadores asíncronos

Puede utilizar la diferencia de períodos de dos generadores de reloj no sincronizados. La mayoría de los controladores contienen, por ejemplo, un temporizador de vigilancia. Para aumentar la confiabilidad, se sincroniza desde un generador separado, que de ninguna manera está conectado con la señal del reloj principal. Es suficiente contar el número de ciclos de la señal del reloj principal durante un período del temporizador de vigilancia. Si elige períodos para que el contador se desborde muchas veces durante la medición, puede obtener un número bastante aleatorio. La desventaja de este método es que lleva mucho tiempo, hasta varios segundos.

Reloj en tiempo real

Si el diagrama tiene reloj en tiempo real, puede utilizar sus lecturas actuales para inicializar el PRNG. Por ejemplo, al convertir la fecha/hora actual al formato de hora Unix, obtenemos inmediatamente 32 bits, lo que nunca No volverá a suceder a menos que tome lecturas más de una vez por segundo. El uso del tiempo real otorga valores únicos, pero no proporciona ninguna imprevisibilidad, por lo que es mejor combinar este método con otros.

circuito RC

Si el controlador no tiene dispositivos periféricos, además de los puertos de E/S, puedes hacer lo siguiente: una de las patas se conecta a través de un condensador a tierra y a través de una resistencia a la tensión de alimentación. Si las entradas del controlador tienen resistencias pull-up internas, no se necesita una resistencia externa.

Enviamos una señal "0" a este puerto: el condensador está descargado. Cambiamos el puerto al modo de entrada: el condensador comienza a cargarse. Cuando el voltaje a través de él alcanza el umbral, la entrada cambiará del estado "0" al "1". El tiempo de carga depende en gran medida de muchos factores: tensión de alimentación, deriva de los parámetros del circuito RC, inestabilidad del umbral, temperatura, fugas, interferencias. Midiéndolo con suficiente precisión y tomando los bits menos significativos, se puede obtener una buena aleatoriedad.

Generador de ruido de hardware

Para muchas aplicaciones serias (sobre todo la criptografía), se requiere una fuente de entropía más confiable que las enumeradas anteriormente. En tales casos, utilizan la digitalización de la señal de un generador de ruido basándose en efectos térmicos, de disparo o incluso cuánticos. El elemento de ruido suele ser un diodo especial o diodo Zener, cuya señal se amplifica y se envía a un comparador que genera un flujo de bits binario.

Para garantizar que el umbral de respuesta del comparador no afecte las propiedades estadísticas de la señal recibida, se utilizan dos generadores de ruido que operan en un comparador:

Conclusión

Finalmente, les contaré una historia de mi vida. Comenzó con otra pregunta formulada en el foro: "¿Cómo puedo generar un número aleatorio en el controlador?" El autor de la pregunta explicó que como proyecto del curso está haciendo un dispositivo que emula el lanzamiento de dados. Después de varios intentos fallidos de comprender los algoritmos, el iniciador del tema compartió su solución: simplemente lanzó un dado real 1000 veces y llenó toda la memoria libre del controlador con los números resultantes. El generador pasó brillantemente todas las pruebas de “aleatoriedad”, dado que durante la demostración consumió menos de un tercio de su “reserva”.
Por lo tanto, una solución de este tipo también tiene derecho a la vida, especialmente si se imponen requisitos muy estrictos a la aleatoriedad de los números, pero no se exigen con demasiada frecuencia. Con la caída de los precios de la memoria, puede ser prudente equipar un dispositivo con una "reserva del caos" que dure toda su vida útil.
¡Gracias por su atención!

UPD1: Como se señaló acertadamente en los comentarios, si se espera un ataque al RNG y el atacante tiene acceso de hardware al dispositivo, las fuentes externas de entropía deben usarse con gran precaución, ya que no es muy difícil reemplazar la señal de fuente externa. Se deben utilizar fuentes internas, además de las externas.
También es una buena idea acumular entropía en todo. tiempo libre y úselo cuando necesite generar otro número aleatorio. Generalmente en tales casos el llamado piscina de entropía- una matriz sobre la cual se realiza periódicamente una de las funciones PRNG y en la que se mezclan constantemente datos de fuentes de entropía.

UPD2: En muchos casos, es útil guardar el contenido del grupo de entropía (lo siento, no conozco la traducción normal al ruso) en EEPROM para que después de apagar y encender el dispositivo no lo acumule nuevamente. Se trata, en primer lugar, de la obtención de entropía mediante el método de generadores asíncronos: en condiciones suficientemente estables, se puede generar la misma secuencia después de cada encendido.
Si se espera un ataque, tome precauciones contra la manipulación de la EEPROM. Si el controlador lo permite, bloquee la lectura/borrado/escritura usando bits de bloqueo, y al encenderlo, controle la integridad de la EEPROM, al menos usando sumas de verificación simples.

Etiquetas:

• RNG
• gpsch
• microcontroladores
• algoritmos

Agregar etiquetas

semilla aleatoria(semilla)

Establece el valor, o semilla, como punto de partida para la función aleatoria().

semilla aleatoria(valor); // establece 'valor' como el valor aleatorio inicial

Dado que Arduino no puede generar números verdaderamente aleatorios, randomSeed le permite colocar una variable, constante u otra función en la función aleatoria, lo que ayuda a generar más números aleatorios.

"números al azar. Hay muchas semillas o funciones diferentes que se pueden usar en esta función, incluida millis() o incluso analogRead() para leer ruido eléctrico a través de un pin analógico.

aleatorio (máximo)

aleatorio(mín,máx)

La función aleatoria le permite devolver un número pseudoaleatorio dentro del rango especificado por los valores mínimo y máximo.

valor = aleatorio(100, 200); // establece el 'valor' en aleatorio

// un número entre 100 y 200

Nota: Use esto después de usar la función randomSeed(). El siguiente ejemplo crea un número aleatorio entre 0 y 255 y genera el PWM

señal a la salida PWM igual a un valor aleatorio:

int randNumber; // variable para almacenar un valor aleatorio

LED int = 10; // LED con resistencia en el pin 10

void setup() () // no es necesaria la configuración

semilla aleatoria(millis()); // establece millis() con el número inicial

númerorand = aleatorio(255); // número aleatorio de 0 a 255 analogWrite (led, randNumber); // salida de señal PWM

retraso(500); //pausa de medio segundo

Fuente: Gololobov V. – ¿Dónde empiezan los robots? Sobre el proyecto Arduino para escolares (y no solo) – 2011

Artículos Relacionados

Serial.begin (velocidad) Abre el puerto serie y establece la velocidad para la transferencia de datos serie. La velocidad en baudios típica para las comunicaciones por computadora es 9600, aunque se admiten otras velocidades. configuración vacía() (Serial.begin…….

Todas las variables deben declararse antes de poder usarse. Declarar una variable significa definir el tipo de su valor: int, long, float, etc., asignar un nombre único a la variable y además…….

Bien, hemos instalado este programa. Hemos depurado el "mecanismo" de trabajo con el módulo. Y miramos varios ejemplos. Pero me gustaría crear algo útil para mí. Intentemos. Primero, cerremos el proyecto anterior. Para esto…….

¡Atención! Al trabajar con el módulo Arduino en otros entornos de desarrollo, se debe tener cuidado con la configuración del microcontrolador (Fusibles). Hasta que sepas exactamente a qué podría conducir el cambio…….

Tiempo y aleatoriedad. Reacción

En esta ocasión aprenderemos qué son los valores “Aleatorios” y también aprenderemos a trabajar con el tiempo.

Necesitaremos:

• Botón táctil
• Chirriador
• Cables de conexión “MACHO-MACHO”

Reacción

Nuestra tarea de hoy es armar un diagrama que nos permita conocer la velocidad de nuestra reacción.

Cuando haces clic en botón izquierdo, suena una señal después de un tiempo "aleatorio". Y cuando presiona el botón derecho, se observa cuánto tiempo ha pasado desde el chirrido hasta que se presiona el botón derecho.

Los más hábiles lo prueban ellos mismos y nosotros miramos el diagrama.

#definir BUZ 8 #definir INICIO 9 #definir PARADA 7 int tiempo; //Variable para sincronización void setup() ( Serial. comenzar(9600); pinMode(START, INPUT_PULLUP); pinMode(STOP, INPUT_PULLUP); pinMode(BUZ, OUTPUT); ) void loop() ( if(digitalRead(START) == 0) // Cuando presionas el botón INICIO.. ( int start_time = millis(); // Recuerda el momento de presionar time = start_time; // Escríbelo en una variable global. int Rand = random(0, 4000 ); // Generemos un tiempo de retraso "aleatorio" = tiempo + Rand; //Agregue el tiempo de retraso delay(Rand); //Esperar el tono(BUZ, 3000, 500); //¡Bip! ) if(digitalRead( STOP) == 0 && digitalRead( START) == 1) // Cuando presionas el botón STOP... ( int stop_time = millis(); // Recuerda el tiempo de parada. time = stop_time - time; // Calcula el diferencia horaria. Serial.println("Time: "); // Envía la hora a Serial. Serial.println(time); delay(1000); ) ) // Antes del segundo intento, presione el botón INICIO nuevamente.

Explicaciones

En t tiempo; A las variables (no a todas), al denotarlas, no es necesario darles ningún valor. Usamos esta variable para vincular dos declaraciones if.

En C++, las variables declaradas dentro de un bucle no serán accesibles en otros bucles, ya que sólo tienen efecto dentro de ese bucle. Esto se hace para evitar errores de programación. Cuando el código del programa crezca, entenderás de lo que estoy hablando.

Para que una variable esté disponible para varias declaraciones, debe hacerla global. Aquellos. declarar una variable fuera de funciones.

milis(); Devuelve el número de milisegundos que han pasado desde que se lanzó el programa.

Lo necesitamos para medir la cantidad de tiempo que ha pasado desde que se da la señal hasta que se presiona el botón.

aleatorio(minuto,máx); Este es un generador de números aleatorios. Toma dos valores. Genera un número en el rango del mínimo al máximo.

Números "aleatorios" porque son una secuencia específica de valores. Muy largo, pero igual. Para obtener diferentes secuencias, debes usar AleatorioSemilla();

Esta función inicializa el generador. Y si configuramos el parámetro como aleatorio, obtendremos las secuencias que necesitamos. La secuencia será la misma si el parámetro es fijo.

Conclusión

Ahora puedes entrenar tu reacción usando un dispositivo que has creado tú mismo. O puedes continuar estudiando más.

Lista de radioelementos

Designación	Tipo	Denominación	Cantidad	Nota	Comercio	mi bloc de notas
	placa arduino	ArduinoUno	1			al bloc de notas
	tabla de pan	Mitad de placa de pruebas	1			al bloc de notas
	Emisor piezoeléctrico	Pasivo	1			al bloc de notas
	Botón táctil	Sin cerradura	2			al bloc de notas
	Cables de conexión	"Papá-Papá"	1