Utilizzo del generatore di numeri casuali di Arduino: le funzioni Random e RandomSeed. Corso Arduino - Temporizzazione e generazione casuale di sequenze di bit casuali Arduino

Quando si programma Arduino, ci sono momenti in cui è necessario ottenere un numero che non sarà noto in anticipo né al programmatore che scrive lo sketch né all'utente che utilizzerà Arduino con tale programma. In questo caso viene in soccorso un generatore di numeri casuali (o meglio pseudo-casuali).

Per attivare questo generatore è sufficiente utilizzare la funzione random() o randomSeed(). Questo articolo mostrerà come lavorare con queste funzioni e come eliminare la pseudo-casualità durante la generazione di numeri.

In generale, un generatore di numeri pseudo-casuali imita la casualità o la casualità dell'apparizione dei numeri, ma in realtà, se analizzi alcuni di questi numeri per un periodo sufficientemente lungo, puoi notare un certo schema.

Pertanto, la funzione casuale per generare numeri pseudocasuali può avere fino a due parametri ed essere scritta come casuale(max) o casuale(min, max). Qui, il parametro max, che è obbligatorio, imposta il limite superiore dell'intervallo di generazione dei numeri pseudo-casuali. Usando parametro aggiuntivo min può essere utilizzato per impostare il limite inferiore dell'intervallo. Di conseguenza, la funzione restituirà un numero pseudo-casuale compreso tra min e max-1.

È importante comprendere che quando si utilizza la funzione random(), verrà generato ogni volta esattamente lo stesso elenco di numeri pseudocasuali. Ad esempio, se realizzi una slot machine e la prima volta che premi la maniglia, uscirà una combinazione vincente, allora puoi stare sicuro che se resetti Arduino e premi nuovamente la maniglia, questa slot machine mostrerà la stessa combinazione vincente combinazione. In effetti, su Arduino non è facile implementare una macchina da gioco con generazione di numeri completamente casuale, come, ad esempio, è implementata nelle macchine da gioco www.igrovye-apparati-vulcan.com/, ma è possibile risolvere parzialmente il problema utilizzando il comando funzione randomSeed().

Questa funzione accetta un valore (ad esempio un numero intero) e utilizza un numero per modificare l'elenco casuale generato dalla funzione random(). Puoi inserire randomSeed() nella funzione setup e utilizzare la funzione random() in un infinito ciclo continuo. Ma in questo caso ci sarà un problema: sebbene la sequenza di numeri casuali sarà diversa quando si utilizza la funzione randomSeed(), sarà comunque la stessa ogni volta che viene eseguito lo sketch.

L'unica soluzione in questo caso potrebbe essere un'opzione che utilizza periferiche analogiche (ADC) e la corrispondente funzione analogRead (). Se non colleghi l'ingresso analogico a nulla, cioè lo lasci "sospeso" in aria, grazie al rumore su questa linea puoi ottenere numeri davvero casuali. Quindi nelle impostazioni di configurazione, puoi scrivere in questo modo randomSeed(analogRead(A0)). A condizione che la porta analogica A0 non sia collegata da nessuna parte.

Molto è stato scritto sui generatori di numeri casuali, ma quasi sempre, quando si parla di implementazione, è implicito (o dichiarato esplicitamente) che noi stiamo parlando su x86/x64 e altre architetture "per adulti". Allo stesso tempo, i forum dedicati allo sviluppo di dispositivi su microcontrollori sono pieni di domande "come posso generare un numero casuale su %controllername%?". Inoltre, la gamma di risposte va da “vedi Google/Wikipedia” a “usa la funzione standard”. Questa "funzione standard" non è sempre presente e si adatta allo sviluppatore sotto tutti gli aspetti, più spesso è il contrario: o i numeri sono tutt'altro che casuali, o la velocità di lavoro è troppo bassa, oppure il codice risultante non lo fa non si adatta affatto alla memoria libera.
Proviamo a capire quali sono gli algoritmi per generare numeri casuali, come scegliere quello giusto e, soprattutto, quali sono le caratteristiche dell'implementazione di questi algoritmi sui controller.

Punteggio di casualità

Le applicazioni per RNG possono essere molto diverse, dai giocattoli alla crittografia seria. Di conseguenza, anche i requisiti per il generatore variano notevolmente. Per valutare la qualità (livello di "casualità") del generatore, esistono test speciali. Ecco quelli più basilari:

• prova di frequenza. Consiste nel contare il numero di zeri e uno in una sequenza di bit. Uno e zero dovrebbero essere approssimativamente uguali.
• Testare una sequenza di bit identici. Vengono cercate righe di bit identici, come 000...0 o 111...1. La distribuzione delle frequenze incontrate dalle serie, a seconda della loro lunghezza, dovrebbe corrispondere a tale distribuzione per un segnale veramente casuale.
• Prova spettrale. La trasformata discreta di Fourier viene applicata alla sequenza originale. Lo spettro risultante non dovrebbe presentare picchi significativi che indicherebbero la presenza di proprietà periodiche della sequenza.
• Test di autocorrelazione. Viene calcolato il valore di correlazione tra le copie della sequenza spostate l'una rispetto all'altra. Il test consente di trovare sezioni ripetute in una sequenza.

Esistono kit speciali che includono decine di test simili:
NIST: utilizzato nella competizione AES per valutare gli algoritmi di crittografia.
DIEHARD è uno dei set più rigorosi esistenti.

Algoritmi PRNG

Qualsiasi sequenza generata secondo un algoritmo hardcoded non può essere considerata veramente casuale, quindi, quando si parla di generatori algoritmici, si usa il termine pseudo-casuale sotto sequenza. Qualsiasi generatore di numeri pseudo-casuali (PRNG) si ripete prima o poi, un'altra cosa è che questo "tardi" potrebbe arrivare in pochi millisecondi o forse in pochi anni. La lunghezza del ciclo dipende dalla dimensione dello stato interno del generatore N (questa è infatti la quantità di memoria necessaria al generatore) e varia da 2 (N / 2) a 2 N bit.
Sono stati inventati numerosi algoritmi PRNG, ma non tutti sono convenienti per l'implementazione sui microcontrollori. Siamo molto limitati in termini di velocità e memoria disponibile, molti controller non supportano i comandi aritmetici reali e persino le moltiplicazioni. Tenendo presenti queste limitazioni, diamo un'occhiata ad alcuni algoritmi ben noti.

Metodo della congruenza lineare

Il membro successivo della sequenza viene calcolato dalla formula
X i+1 = (aX i + c) mod m
Numero M specifica il periodo massimo della sequenza, numeri interi UN E C- coefficienti "magici". Numero Mè ragionevole scegliere uguale alla potenza di due, nel qual caso l'operazione di riduzione del modulo si riduce allo scarto dei bit alti. Per ottenere il periodo massimo è necessario che siano soddisfatte le seguenti condizioni:
- C e m deve essere coprimo,
- a-1 dovrebbe essere un multiplo P per tutti i divisori primi P numeri M,
- Se Mè multiplo di 4 (e nel nostro caso sarà multiplo), allora a-1 deve essere un multiplo di 4.
C'è un'altra sottigliezza: come risultato dovrebbero essere presi solo i bit alti della variabile di stato X, poiché i parametri statistici della casualità sono molto peggiori per i bit bassi. L'algoritmo congruenziale lineare è solitamente implementato come rand() standard in molte librerie.

Professionisti:

• il periodo massimo possibile per una determinata dimensione della variabile statale;
• abbastanza veloce;
• spesso già implementato nella libreria del compilatore.

Aspetti negativi:

• è richiesta l'operazione di moltiplicazione;
• non tutti i bit sono ugualmente casuali.

Riepilogo: algoritmo veloce e semplice per applicazioni non molto responsabili.

Metodo Fibonacci con ritardi

Questo algoritmo utilizza la relazione
X io \u003d X i-a - X i-b,
dove è la variabile di stato Xè un numero intero senza segno. Valori di ritardo UN E B non vengono prese tutte, ma quelle strettamente definite; si consigliano coppie (17.5), (55.24) o (97.33) per ottenere la massima qualità. Maggiore è il ritardo, più lungo è il periodo e migliori sono le proprietà spettrali della sequenza. D'altra parte, affinché il generatore funzioni, è necessario memorizzare il massimo (a,b) dei numeri precedenti, il che non è sempre accettabile. Inoltre, per eseguire il generatore, sono necessari i numeri max(a,b), che di solito si ottengono utilizzando un PRNG più semplice.

Professionisti:

• non richiede operazioni di moltiplicazione;
• tutti i bit di un numero casuale sono statisticamente equivalenti.

Aspetti negativi:

• richiede una grande quantità di memoria;
• richiede una vasta gamma di numeri per essere eseguito.

Riepilogo: algoritmo di altissima qualità, ma ad alta intensità di risorse.

Registro a scorrimento con feedback lineare

La variabile di stato è memorizzata in un registro di lunghezza N. La generazione dello stato successivo prevede due passaggi:

1. Viene calcolato il valore del bit C = X i1 xor X i2 xor… X ik, dove i1, i2…ik- registrare i numeri di bit, chiamati si piega.
2. Il registro viene spostato di 1 bit a destra, il bit più a sinistra assume il valore CON.

L'output del generatore è il bit più a destra (o più a sinistra, o qualsiasi altra cosa) del registro, il che significa che la sequenza pseudo-casuale viene generata un bit per iterazione. Con il numero di prese correttamente selezionato, il periodo del generatore sarà 2 N - 1. "Meno uno", poiché esiste uno stato zero proibito del registro. Numeri di filiale per N da 3 a 168 possono essere visualizzati in questo documento.
Oltre alla configurazione sopra descritta, che, tra l'altro, è chiamata configurazione di Fibonacci (da non confondere con l'omonimo metodo PRNG!), Esiste la cosiddetta. Configurazione di Galois.


Invece di utilizzare la somma dei bit nella sequenza di tap per generare un nuovo bit più a sinistra, esegui XOR su ciascun bit della sequenza di tap con il bit più a destra, quindi ruota l'intero registro verso destra. Questo schema è più difficile da comprendere, ma più semplice da implementare, poiché tutte le operazioni XOR possono essere eseguite contemporaneamente. Gli schemi di Fibonacci e Galois sono equivalenti in termini di durata del periodo e qualità dei numeri pseudocasuali.

Professionisti:

• implementazione molto semplice, non è richiesta nemmeno l'aritmetica, solo operazioni di bit e spostamenti;
• algoritmo molto veloce (in particolare lo schema di Galois);
• buone proprietà statistiche.

Aspetti negativi:

• è necessario controllare il valore iniziale per la disuguaglianza zero.

Riepilogo: algoritmo molto veloce e di qualità abbastanza elevata.

Algoritmi resistenti alla criptovaluta

Per l'applicazione in crittografia, PRNG ha un altro requisito essenziale: irreversibilità. Tutti gli algoritmi sopra elencati non hanno questa proprietà: conoscendo diversi valori di uscita del PRNG, è possibile, risolvendo un semplice sistema di equazioni, trovare i parametri dell'algoritmo (le stesse costanti “magiche” a, b, c eccetera). E conoscendo i parametri, puoi riprodurre l'intera sequenza pseudo-casuale.
Qualsiasi cifrario a blocchi sufficientemente potente può essere utilizzato come algoritmo PRNG crittograficamente potente. Scegliendo una chiave segreta si possono ottenere blocchi di numeri pseudo-casuali applicando l'algoritmo a numeri naturali consecutivi. Per un codice a blocchi da N bit, il periodo sarà al massimo 2 N . La sicurezza di un tale schema dipende interamente dalla segretezza della chiave.
Tutti i moderni algoritmi crittografici sono testati per l'uso come PRNG, ovvero, utilizzando un algoritmo certificato, non è necessario prestare particolare attenzione alle proprietà statistiche e spettrali del flusso di output. Devi solo preoccuparti della "voracità" computazionale degli algoritmi crittografici. Se è necessario eseguire un numero elevato di operazioni di crittografia, è opportuno scegliere un controller con blocchi crittografici hardware. Spesso in tali controller è presente anche un ottimo PRNG hardware resistente alla crittografia.

Fonti di entropia

Come già accennato, utilizzando esclusivamente algoritmi deterministici, è impossibile generare un numero realmente casuale. Pertanto, di solito viene utilizzato un gruppo di PRNG + esterno fonte di entropia. La sorgente di entropia viene utilizzata per impostare il valore iniziale del PRNG, e il compito di quest'ultimo è quello di garantire la purezza spettrale e statistica della sequenza. Cosa può essere utilizzato come fonte di entropia? Sì, praticamente qualsiasi cosa.

Attività dell'utente

Se il dispositivo interagisce con l'utente in qualche modo, è una buona idea utilizzare l'utente stesso come fonte di entropia. Ad esempio, il tempo di pressione di un pulsante, misurato al microsecondo più vicino (o meglio, alle sue cifre meno significative), è completamente imprevedibile. Spesso però il dispositivo deve funzionare in modo autonomo, il che significa che stiamo perdendo questo meraviglioso canale di informazione.

Convertitore da analogico a digitale

Molti controller dispongono di ADC integrati. E in molti controller sono di qualità molto mediocre, fatti semplicemente "per essere". I bit bassi del risultato dell'ADC contengono quasi sempre un rumore significativo, anche se viene misurata la tensione CC. Questo può essere usato: collega l'ingresso dell'ADC alla tensione di alimentazione tramite un divisore, prendi qualche dozzina di misurazioni, prendi i bit meno significativi: ecco un ottimo numero casuale per te. Se l'ADC contiene un preamplificatore integrato, accendilo, fa anche rumore.

Generatori asincroni

È possibile utilizzare la differenza di periodo di due orologi non sincronizzati. La maggior parte dei controllori contiene, ad esempio, un timer watchdog. Per migliorare l'affidabilità, viene sincronizzato da un oscillatore separato che non è collegato in alcun modo al segnale di clock principale. È sufficiente contare il numero di cicli del segnale dell'orologio principale in un periodo del timer watchdog. Se si scelgono i periodi in modo che il contatore trabocchi molte volte durante la misurazione, è possibile ottenere un numero abbastanza casuale. Lo svantaggio di questo metodo è che richiede molto tempo, fino a diversi secondi.

Orologio in tempo reale

Se lo schema ha orologio in tempo reale, è possibile utilizzare le letture correnti per inizializzare il PRNG. Ad esempio, convertendo la data/ora corrente nel formato ora Unix, otteniamo immediatamente 32 bit, che Mai non si verificherà più, a meno che non si effettuino letture più di una volta al secondo. L'uso del tempo reale dà unicità dei valori, ma non dà alcuna imprevedibilità, quindi è meglio combinarli Da questa parte con altri.

Circuito RC

Se il controller non ne ha periferiche, ad eccezione delle porte I / O, puoi fare quanto segue: una delle gambe è collegata tramite un condensatore a terra e tramite un resistore alla tensione di alimentazione. Se gli ingressi del controller dispongono di resistori pull-up interni, non è necessario alcun resistore esterno.

Emettiamo un segnale "0" su questa porta: il condensatore è scarico. Passiamo la porta alla modalità di ingresso: il condensatore inizia a caricarsi. Quando la tensione raggiunge la soglia, l'ingresso passerà dallo stato "0" a "1". Il tempo di carica dipende fortemente da molti fattori: tensione di alimentazione, deriva dei parametri del circuito RC, instabilità della soglia, temperatura, perdite, rumore. Misurandolo con sufficiente precisione e prendendo i bit meno significativi, puoi ottenere una buona casualità.

Generatore di rumore hardware

Per molte applicazioni serie (principalmente la crittografia), è necessaria una fonte di entropia più affidabile di quelle sopra elencate. In questi casi, il segnale viene digitalizzato da un generatore di rumore basato su effetti termici, di sparo o anche quantistici. L'elemento rumoroso è solitamente un diodo speciale o diodo zener, il cui segnale viene amplificato e inviato a un comparatore che forma un flusso di bit binario.

Affinché la soglia di risposta del comparatore non influenzi le proprietà statistiche del segnale ricevuto, vengono utilizzati due generatori di rumore che funzionano su un comparatore:

Conclusione

Infine vi racconterò una storia della mia vita. Tutto è iniziato con un'altra domanda posta sul forum "come posso generare un numero casuale sul controller?". L'autore della domanda ha spiegato cosa sta facendo il dispositivo che emula il lancio di un dado come progetto del corso. Dopo diversi tentativi infruttuosi di capire gli algoritmi, il topikstarter ha condiviso la sua soluzione: ha semplicemente lanciato un dado vero 1000 volte e ha segnato tutta la memoria libera del controller con i numeri risultanti. Il generatore ha superato brillantemente tutti i test di “casualità”, dato che durante la dimostrazione ha utilizzato meno di un terzo della sua “riserva”.
Pertanto, una tale soluzione ha anche diritto alla vita, soprattutto se vengono imposti requisiti molto severi sulla casualità dei numeri, ma non sono richiesti molto spesso. Con il crollo dei prezzi della memoria, potrebbe essere saggio dotare un dispositivo di un'unità flash "caos headroom" che durerà per tutta la vita del dispositivo.
Grazie per l'attenzione!

UPD1: Come è stato giustamente notato nei commenti, se si suppone un attacco all'RNG e l'aggressore avrà accesso hardware al dispositivo, le fonti di entropia esterne dovrebbero essere utilizzate con molta cautela, poiché non è molto difficile sostituire il segnale da fonte esterna. Dovrebbero essere utilizzate fonti interne, possibilmente in aggiunta a fonti esterne.
È anche una buona idea accumulare l'entropia di ogni cosa tempo libero e usalo quando devi generare un altro numero casuale. Di solito in questi casi, il cosiddetto. Piscina entropica- un array su cui viene periodicamente eseguita una delle funzioni PRNG e dove i dati provenienti da fonti di entropia vengono costantemente mescolati.

UPD2: In molti casi è utile salvare il contenuto della vasca Entropia (scusate, non conosco la normale traduzione russa) in EEPROM per non accumularlo nuovamente dopo aver spento e riacceso il dispositivo. Ciò vale, innanzitutto, per ottenere entropia con il metodo dei generatori asincroni: in condizioni sufficientemente stabili, dopo ogni accensione, è possibile generare la stessa sequenza.
Se si prevede un attacco, prendere precauzioni contro la manomissione del contenuto della EEPROM. Se il controller lo consente, blocca la lettura/cancellazione/scrittura utilizzando i lock-bit, all'accensione controlla l'integrità della EEPROM, almeno utilizzando i checksum più semplici.

tag:

• RFC
• gpsch
• microcontrollori
• algoritmi

Aggiungere etichette

randomSeed (seme)

Imposta un valore, o seme, come punto iniziale della funzione random().

seme casuale(valore); // imposta 'value' come valore casuale iniziale

Poiché Arduino non può generare numeri veramente casuali, randomSeed ti consente di inserire una variabile, una costante o un'altra funzione nella funzione casuale, che aiuta a generare più numeri casuali.

numeri "casuali". Esistono molti seed o funzioni diversi che possono essere utilizzati in questa funzione, incluso millis() o anche analogRead() per leggere il rumore elettrico attraverso un pin analogico.

casuale (massimo)

casuale (min, max)

La funzione casuale consente di restituire un numero pseudo-casuale all'interno dell'intervallo dato dai valori minimo e massimo.

valore = casuale(100, 200); // imposta 'valore' su casuale

// un numero compreso tra 100 e 200

Nota: Usalo dopo aver usato la funzione randomSeed(). L'esempio seguente genera un numero casuale compreso tra 0 e 255 e restituisce PWM

segnale all'uscita PWM uguale al valore casuale:

int randNumero; // variabile per memorizzare un valore casuale

led intero = 10; // LED con resistenza sul pin 10

void setup() () // la configurazione non è necessaria

seme casuale(millis()); // imposta millis() come seme

randNumero = casuale(255); // numero casuale compreso tra 0 e 255 analogWrite(led, randNumber); // segnale PWM in uscita

ritardo(500); // fai una pausa di mezzo secondo

Fonte: Gololobov V. - Da dove iniziano i robot. Informazioni sul progetto Arduino per gli scolari (e non solo) - 2011

post correlati

Serial.begin (rate) Apre la porta seriale e imposta la velocità per il trasferimento dei dati seriali. La velocità di trasmissione tipica per la comunicazione con il computer è 9600, sebbene siano supportate altre velocità di trasmissione. void setup()( Serial.begin…….

Tutte le variabili devono essere dichiarate prima di poter essere utilizzate. Dichiarare una variabile significa definire il tipo del suo valore: int, long, float, ecc., impostare un nome univoco per la variabile e inoltre…….

Ok, abbiamo installato questo programma. Abbiamo eseguito il debug del "meccanismo" di lavoro con il modulo. E guarda alcuni esempi. Ma mi piacerebbe creare qualcosa di utile anch'io. Proviamo. Chiudiamo prima il progetto precedente. Per questo…….

Attenzione! Quando lavori con il modulo Arduino in altri ambienti di sviluppo, dovresti fare attenzione alla configurazione del microcontrollore (fusibili). Fino a quando non saprai esattamente a cosa potrebbe portare il cambiamento…….

Tempo e casualità. Reazione

Questa volta impareremo quali sono i valori "casuali" e impareremo anche come lavorare con il tempo.

Avremo bisogno:

• Pulsante orologio
• cigolio
• Cavi di collegamento "PAPA-PAPA"

Reazione

Il nostro compito per oggi è assemblare un circuito che ci permetta di scoprire la velocità della nostra reazione.

Quando si preme il pulsante sinistro, si sente un segnale dopo un tempo "casuale". E quando si preme il pulsante destro, si nota quanto tempo è trascorso dal cigolio alla pressione del pulsante destro.

Chi è abile, lo prova lui stesso e guardiamo lo schema.

#define BUZ 8 #define START 9 #define STOP 7 tempo int; // Variabile per la sincronizzazione void setup() ( Serial. Begin(9600); pinMode(START, INPUT_PULLUP); pinMode(STOP, INPUT_PULLUP); pinMode(BUZ, OUTPUT); ) void loop() ( if(digitalRead(START) == 0) // Quando si preme il pulsante START.. ( int start_time = millis();// Ricorda l'ora in cui si preme time = start_time; // Scrivilo in una variabile globale. int Rand = random(0, 4000) ; // Genera un tempo di ritardo "casuale" = tempo + Rand; //Aggiungi il tempo di ritardo delay(Rand); //Aspetta tono(BUZ, 3000, 500); //Beep! ) if(digitalRead(STOP) = = 0 && digitalRead( START) == 1)// Quando si preme il pulsante STOP... ( int stop_time = millis(); //Ricorda l'ora di fine. time = stop_time - time; // Calcola la differenza oraria. Serial .println("Time: "); // Stampa l'ora su Serial. Serial. println(time); delay(1000); ) ) // Prima del secondo tentativo, premere nuovamente il pulsante START.

Spiegazioni

int tempo; Alle variabili (non tutte), quando vengono designate, non è necessario assegnare alcun valore. Abbiamo usato questa variabile per collegare due istruzioni if.

In C++, le variabili dichiarate all'interno di un ciclo non saranno disponibili in altri cicli, poiché sono valide solo all'interno di quel ciclo. Questo viene fatto per evitare errori di programmazione. Quando il codice del programma crescerà, capirai di cosa sto parlando.

Per rendere una variabile disponibile per più istruzioni, è necessario renderla globale. Quelli. dichiarare una variabile al di fuori delle funzioni.

milli(); Restituisce il numero di millisecondi trascorsi dall'avvio del programma.

Ne abbiamo bisogno per misurare il tempo trascorso dalla segnalazione alla pressione del pulsante.

casuale(minimo,massimo);È un generatore di numeri "casuali". Assume due valori. Genera un numero compreso tra minimo e massimo.

Numeri "casuali" perché si tratta di una determinata sequenza di valori. Molto lungo, ma uguale. Per ottenere sequenze diverse, dovresti usare CasualeSeme();

Lei, la funzione, inizializza il generatore. E se imposti il ​​parametro su casuale, otterremo le sequenze di cui abbiamo bisogno. La stessa sequenza sarà se il parametro è fisso.

Conclusione

Ora puoi allenare la tua reazione con l'aiuto del tuo dispositivo. E puoi andare avanti.

Elenco degli elementi radio

Designazione	Tipo	Denominazione	Quantità	Nota	Negozio	Il mio blocco note
	Scheda Arduino	ArduinoUno	1			Al blocco note
	Tagliere per il pane	Metà breadboard	1			Al blocco note
	Cicalino piezoelettrico	Passivo	1			Al blocco note
	Pulsante orologio	Senza fermo	2			Al blocco note
	Fili di collegamento	"Papà Papà"	1