Uporaba generatorja naključnih števil v Arduinu: funkciji Random in RandomSeed. Tečaj Arduino - Čas in naključno Arduino generira naključno bitno zaporedje

Pri programiranju Arduina pridejo trenutki, ko je treba dobiti številko, ki ne bo vnaprej znana niti programerju, ki piše skico, niti uporabniku, ki bo Arduino uporabljal s takšnim programom. V tem primeru na pomoč priskoči generator naključnih (ali bolje rečeno psevdonaključnih) števil.

Če želite aktivirati ta generator, preprosto uporabite funkciji random() ali randomSeed(). To gradivo vam bo pokazalo, kako delati s temi funkcijami, pa tudi, kako se znebiti psevdonaključnosti pri ustvarjanju števil.

Na splošno generator psevdonaključnih števil simulira kaotično ali naključno pojavljanje števil, vendar v resnici, če analizirate niz teh števil v dovolj dolgem obdobju, lahko opazite določen vzorec.

Torej ima lahko naključna funkcija za generiranje psevdo-naključnih števil do dva parametra in je zapisana kot random(max) ali random(min, max). Tukaj max parameter, ki je obvezen, določa zgornjo mejo obsega za generiranje psevdonaključnih števil. Z uporabo dodatni parameter min lahko nastavite spodnjo mejo območja. Kot rezultat bo funkcija vrnila neko psevdo-naključno število v območju od min do max-1.

Pomembno je razumeti, da bo pri uporabi funkcije random() vsakič ustvarjen povsem enak seznam psevdonaključnih števil. Na primer, če naredite igralni avtomat in ko prvič pritisnete na ročico, prikaže dobitno kombinacijo, potem ste lahko prepričani, da bo ta igralni avtomat prikazal isto zmagovalno kombinacijo, če ponastavite Arduino in ponovno pritisnete na ročico. . Na Arduinu res ni lahko implementirati igralnega avtomata s popolnoma naključnim generiranjem števil, kot je to na primer implementirano v igralnih avtomatih www.igrovye-apparati-vulcan.com/, vendar lahko težavo delno rešite z randomSeed. () funkcijo.

Ta funkcija sprejme vrednost (kot je celo število) in uporabi številko za spreminjanje naključnega seznama, ki ga ustvari funkcija random(). V funkcijo nastavitve lahko postavite randomSeed() in uporabite funkcijo random() v neskončnem zanka. Toda tudi takrat je ulov v tem, da čeprav bo zaporedje naključnih števil drugačno pri uporabi funkcije randomSeed(), bo še vedno enako ob vsakem zagonu skice.

Edina rešitev v tem primeru je lahko uporaba analognih perifernih naprav (ADC) in ustrezne funkcije analogRead(). Če analogni vhod ni povezan z ničemer, torej ostane "visi" v zraku, potem lahko zaradi hrupa v tej vrstici dobite resnično naključne številke. Nato lahko v nastavitveni nastavitvi zapišete randomSeed(analogRead(A0)). Pod pogojem, da analogna vrata A0 niso nikjer povezana.

Veliko je bilo napisanega o generatorjih naključnih števil, toda skoraj vedno, ko gre za implementacijo, je implicirano (ali izrecno navedeno), da govorimo o o x86/x64 in drugih "odraslih" arhitekturah. Hkrati so forumi, posvečeni razvoju naprav na mikrokontrolerjih, polni vprašanj »kako lahko generiram naključno število na %controllername%?« Poleg tega se razpon odgovorov razteza od »poglej Google/Wikipedia« do »uporabi standardno funkcijo«. Ta »standardna funkcija« ne obstaja vedno in razvijalcu ustreza v vseh pogledih; pogosteje je ravno obratno: včasih številke še zdaleč niso naključne, včasih je hitrost delovanja prenizka ali včasih nastala koda ne ustreza sploh v prosti pomnilnik.
Poskusimo ugotoviti, kaj so algoritmi za generiranje naključnih števil, kako izbrati pravega, in kar je najpomembnejše, kakšne so značilnosti izvajanja teh algoritmov na krmilnikih.

Ocenjevanje "naključnosti"

Aplikacije za RNG so lahko zelo različne, od igrač do resne kriptografije. V skladu s tem so tudi zahteve za generator zelo različne. Obstajajo posebni testi za oceno kakovosti (stopnje »naključnosti«) generatorja. Tukaj so najbolj osnovni med njimi:

• Frekvenčni test. Sestoji iz štetja ničel in enic v zaporedju bitov. Enic in ničel naj bo približno enako.
• Preizkusite zaporedje enakih bitov. Iščejo se vrstice enakih bitov, na primer 000...0 ali 111...1. Porazdelitev frekvenc, s katerimi se serije pojavljajo, glede na njihovo dolžino, bi morala ustrezati tej porazdelitvi za resnično naključen signal.
• Spektralni test. Za izvirno zaporedje se uporabi diskretna Fourierjeva transformacija. Nastali spekter ne sme imeti pomembnih vrhov, ki bi kazali na prisotnost periodičnih lastnosti zaporedja.
• Avtokorelacijski test. Izračuna se korelacijska vrednost med kopijami zaporedja, ki so premaknjene glede na drugo. Preizkus vam omogoča iskanje ponavljajočih se regij v zaporedju.

Obstajajo posebni kompleti, ki vključujejo na desetine podobnih testov:
NIST - uporablja se na tekmovanju AES za ocenjevanje šifrirnih algoritmov.
DIEHARD je eden najstrožjih sklopov, ki obstajajo.

PRNG algoritmi

Vsako zaporedje, ustvarjeno v skladu s strogo določenim algoritmom, ni mogoče šteti za resnično naključno, zato, ko govorimo o algoritemskih generatorjih, uporabljamo izraz psevdonaključno podzaporedje. Vsak generator psevdonaključnih števil (PRNG) bo šel prej ali slej v zanko, druga stvar je, da lahko ta "pozno" pride v nekaj milisekundah ali morda v nekaj letih. Dolžina cikla je odvisna od velikosti notranjega stanja generatorja N (pravzaprav je to količina pomnilnika, ki ga potrebuje generator) in se giblje od 2 (N/2) do 2 N bitov.
Izumljenih je bilo veliko različnih algoritmov PRNG, vendar niso vsi primerni za implementacijo na mikrokrmilnike. Močno smo omejeni glede hitrosti in razpoložljivega pomnilnika; veliko krmilnikov ne podpira pravih aritmetičnih ali celo navodil za množenje. Ob upoštevanju teh omejitev si poglejmo nekaj dobro znanih algoritmov.

Linearna kongruentna metoda

Naslednji člen zaporedja se izračuna po formuli
X i+1 = (aX i + c) mod m
številka m določa največjo periodo zaporedja, cela števila a in c- "čarobni" koeficienti. številka m Smiselno je izbrati enako potenci dvojke; v tem primeru se operacija modulo pretvorbe zmanjša na zavrženje najpomembnejših bitov. Za pridobitev najdaljšega obdobja morajo biti izpolnjeni naslednji pogoji:
- c in m mora biti relativno praštevilo,
- a-1 mora biti večkratnik str za vse prafaktorje strštevilke m,
- Če m je večkratnik 4 (in v našem primeru bo večkratnik), potem a-1 mora biti večkratnik 4.
Obstaja še ena subtilnost: kot rezultat je treba vzeti le najpomembnejše bite spremenljivke stanja X, saj so za najnižje bite statistični parametri naključnosti veliko slabši. Linearni kongruentni algoritem je običajno implementiran kot standardni rand() v številnih knjižnicah.

Prednosti:

• največje možno obdobje za dano velikost spremenljivke stanja;
• dovolj hitro;
• pogosto že implementiran v knjižnici prevajalnika.

Minuse:

• potrebna je operacija množenja;
• niso vsi bitovi enako naključni.

Povzetek: hiter in enostaven algoritem za manj zahtevne aplikacije.

Fibonaccijeva metoda z zamiki

Ta algoritem uporablja relacijo
X i = X i-a - X i-b,
kje je spremenljivka stanja X- celo število brez predznaka. Vrednosti zakasnitve a in b ne jemljejo se kateri koli, ampak strogo določeni, za doseganje največje kakovosti pa se priporočajo pari (17,5), (55,24) ali (97,33). Večja kot je zakasnitev, daljša je doba in boljše so spektralne lastnosti zaporedja. Po drugi strani pa je za delovanje generatorja potrebno shraniti max(a,b) prejšnjih števil, kar ni vedno sprejemljivo. Poleg tega za zagon generatorja potrebujete max(a,b) števila, ki se običajno pridobijo z enostavnejšim PRNG.

Prednosti:

• ne zahteva operacij množenja;
• vsi biti naključnega števila so enakovredni v statističnih lastnostih.

Minuse:

• zahteva veliko količino pomnilnika;
• za izvajanje potrebuje velik niz številk.

Povzetek: zelo kakovosten algoritem, ki zahteva veliko virov.

Shift register z linearno povratno zvezo

Spremenljivka stanja je shranjena v registru dolžine N. Generiranje naslednjega stanja vključuje dva koraka:

1. Vrednost bita se izračuna C = X i1 xor X i2 xor… X ik, kjer je i1, i2…ik- registrirane bitne številke, klicane zavoji.
2. Register se premakne za 1 bit v desno, skrajno levi bit prevzame vrednost Z.

Izhod generatorja je skrajno desni (ali skrajno levi, ali kateri koli drug) bit registra, kar pomeni, da se psevdonaključno zaporedje ustvari en bit na ponovitev. S pravilno izbranimi številkami pipa bo obdobje generatorja 2 N - 1. "Minus ena", ker je prepovedano ničelno stanje registra. Številke poslovalnic za n od 3 do 168 najdete v tem dokumentu.
Poleg zgoraj opisane konfiguracije, ki se mimogrede imenuje Fibonaccijeva konfiguracija (ne zamenjujte je z istoimensko metodo PRNG!), obstaja tako imenovana. Konfiguracija Galois.


Namesto da bi za generiranje novega skrajno levega bita uporabil vsoto bitov v zaporedju odcepov, izvede XOR vsak bit v zaporedju odcepov s skrajnim desnim bitom, nato pa zavrti celoten register v desno. To shemo je težje razumeti, vendar jo je lažje implementirati, saj se vse operacije XOR lahko izvajajo hkrati. Glede na dolžino obdobja in kakovost psevdonaključnih števil sta Fibonaccijeva in Galoisova shema enakovredni.

Prednosti:

• zelo preprosta izvedba, ne zahteva niti aritmetike, samo bitne operacije in premike;
• zelo hiter algoritem (predvsem Galoisova shema);
• dobre statistične lastnosti.

Minuse:

• morate preveriti začetno vrednost za neenakost na nič.

Povzetek: zelo hiter in dokaj kvaliteten algoritem.

Kriptoodporni algoritmi

Za uporabo v kriptografiji imajo PRNG še eno bistveno zahtevo: nepovratnost. Vsi zgoraj navedeni algoritmi nimajo te lastnosti: če poznate več izhodnih vrednosti PRNG, lahko z reševanjem preprostega sistema enačb najdete parametre algoritma (iste "čarobne" konstante a, b, c itd). In če poznate parametre, lahko reproducirate celotno psevdo-naključno zaporedje.
Vsako dovolj močno blokovno šifro je mogoče uporabiti kot kriptografsko močan algoritem PRNG. Z izbiro skrivnega ključa lahko pridobite bloke psevdonaključnih števil z uporabo algoritma za zaporedna naravna števila. Za N-bitno blokovno šifro obdobje ne bo več kot 2 N. Varnost takšne sheme je v celoti odvisna od tajnosti ključa.
Vsi sodobni kriptografski algoritmi so testirani za uporabo kot PRNG, kar pomeni, da z uporabo certificiranega algoritma ni treba posebej skrbeti za statistične in spektralne lastnosti izhodnega toka. Skrbi vas le računska "požrešnost" kripto algoritmov. Če morate opraviti veliko število operacij šifriranja, je smiselno izbrati krmilnik s strojnimi kriptografskimi bloki. Pogosto imajo takšni krmilniki tudi zelo dobro kripto odporno strojno PRNG.

Viri entropije

Kot že omenjeno, z uporabo samo determinističnih algoritmov ni mogoče ustvariti resnično naključnega števila. Zato se običajno uporablja kombinacija PRNG + zunanji vir entropije. Vir entropije se uporablja za nastavitev začetne vrednosti za PRNG, naloga slednjega pa je zagotoviti spektralno in statistično čistost zaporedja. Kaj lahko uporabimo kot vir entropije? Da, skoraj vse.

Aktivnost uporabnika

Če naprava kakor koli komunicira z uporabnikom, čisto dobra odločitev bo uporabil uporabnika samega kot vir entropije. Na primer, čas pritiska na gumb, izmerjen z natančnostjo mikrosekunde (oziroma njegovih najmanj pomembnih števk), je popolnoma nepredvidljiv. Pogosto pa mora naprava delovati avtonomno, kar pomeni, da smo prikrajšani za ta čudovit kanal informacij.

Analogno-digitalni pretvornik

Veliko krmilnikov ima vgrajene ADC. In v mnogih krmilnikih so zelo povprečne kakovosti, narejeni tako, da bodo. Biti nizkega reda rezultata ADC skoraj vedno vsebujejo znaten šum, tudi pri merjenju enosmerne napetosti. To lahko uporabite: priključite vhod ADC na napajalno napetost prek delilnika, opravite nekaj deset meritev, vzemite najmanj pomembne bite - tukaj imate odlično naključno število. Če ima ADC vgrajen predojačevalnik, ga vklopite, tudi hrupno je.

Asinhroni generatorji

Uporabite lahko razliko v obdobjih dveh nesinhroniziranih generatorjev ure. Večina krmilnikov vsebuje na primer nadzorni časovnik. Za večjo zanesljivost se taktira iz ločenega generatorja, ki ni na noben način povezan z glavnim signalom ure. Dovolj je, da preštejete število ciklov signala glavne ure v enem obdobju časovnika čuvaja. Če izberete obdobja tako, da se števec med merjenjem večkrat preseže, lahko dobite dokaj naključno število. Pomanjkljivost te metode je, da traja veliko časa, do nekaj sekund.

Ura realnega časa

Če ima diagram ura realnega časa, lahko uporabite njihove trenutne odčitke za inicializacijo PRNG. Na primer, s pretvorbo trenutnega datuma/časa v format časa Unix takoj dobimo 32 bitov, kar nikoli se ne bo ponovilo, razen če odčitate več kot enkrat na sekundo. Uporaba realnega časa daje edinstvenost vrednosti, vendar ne zagotavlja nobene nepredvidljivosti, zato je bolje kombinirati ta metoda z drugimi.

RC vezje

Če krmilnik nima št periferne naprave, poleg I/O vrat lahko naredite naslednje: enega od krakov priključite preko kondenzatorja na maso in preko upora na napajalno napetost. Če imajo vhodi krmilnika notranje vlečne upore, zunanji upor ni potreben.

Na ta vrata oddamo signal "0" - kondenzator je izpraznjen. Vrata preklopimo v vhodni način - kondenzator se začne polniti. Ko napetost na njem doseže prag, bo vhod preklopil iz stanja "0" v "1". Čas polnjenja je močno odvisen od številnih dejavnikov: napajalne napetosti, premikanja parametrov vezja RC, nestabilnosti praga, temperature, puščanja, motenj. Če ga merite dovolj natančno in vzamete najmanj pomembne bite, lahko dobite dobro naključnost.

Strojni generator šuma

Za številne resne aplikacije (predvsem kriptografijo) je potreben zanesljivejši vir entropije od zgoraj navedenih. V takšnih primerih uporabijo digitalizacijo signala iz generatorja šuma na podlagi toplotnih, strelnih ali celo kvantnih učinkov. Element šuma je običajno posebna dioda ali zener dioda, signal iz katere se ojača in napaja v primerjalnik, ki generira binarni bitni tok.

Za zagotovitev, da odzivni prag primerjalnika ne vpliva na statistične lastnosti prejetega signala, se uporabljata dva generatorja šuma, ki delujeta na enem primerjalniku:

Zaključek

Za konec vam bom povedal eno zgodbo iz svojega življenja. Začelo se je z drugim vprašanjem na forumu: "kako lahko ustvarim naključno število na krmilniku?" Avtor vprašanja je pojasnil, da kot predmetno nalogo izdeluje napravo, ki posnema met kocke. Po več neuspešnih poskusih razumevanja algoritmov je začetnik teme delil svojo rešitev: preprosto je 1000-krat vrgel pravo kocko in z dobljenimi številkami napolnil ves prosti pomnilnik krmilnika. Generator je odlično prestal vse teste »naključnosti«, saj je med demonstracijo porabil manj kot tretjino svoje »rezerve«.
Zato ima taka rešitev tudi pravico do življenja, še posebej, če so naložene zelo stroge zahteve glede naključnosti števil, vendar se ne zahtevajo prepogosto. Ker cene pomnilnika strmo padajo, je morda pametno napravo opremiti z "rezervo kaosa", ki bo trajala celotno življenjsko dobo naprave.
Hvala za pozornost!

UPD1: Kot je bilo pravilno omenjeno v komentarjih, če se pričakuje napad na RNG in ima napadalec strojni dostop do naprave, je treba zunanje vire entropije uporabljati zelo previdno, saj ni zelo težko nadomestiti signala iz zunanji vir. Poleg zunanjih je treba uporabiti notranje vire.
Prav tako je dobra ideja kopičiti entropijo vsega prosti čas in ga uporabite, ko morate ustvariti drugo naključno število. Običajno v takih primerih t.i Entropijski bazen- niz, nad katerim se periodično izvaja ena od funkcij PRNG in v katerega se nenehno mešajo podatki iz entropijskih virov.

UPD2: V mnogih primerih je koristno shraniti vsebino bazena Entropy (žal, ne poznam običajnega ruskega prevoda) v EEPROM, tako da se po izklopu in vklopu naprave ne kopiči znova. To se nanaša predvsem na pridobivanje entropije z metodo asinhronih generatorjev: v dovolj stabilnih pogojih se lahko po vsakem vklopu ustvari isto zaporedje.
Če pričakujete napad, upoštevajte varnostne ukrepe proti poseganju v EEPROM. Če krmilnik to dopušča, blokirajte branje/brisanje/zapisovanje z uporabo zaklepnih bitov, ob vklopu pa spremljajte celovitost EEPROM-a, vsaj z enostavnimi kontrolnimi vsotami.

Oznake:

• RNG
• gpsch
• mikrokontrolerji
• algoritmi

Dodajte oznake

randomSeed(seme)

Nastavi vrednost ali seme kot začetno točko za funkcijo random().

randomSeed(vrednost); // nastavi 'vrednost' kot začetno naključno vrednost

Ker Arduino ne more ustvariti resnično naključnih števil, vam randomSeed omogoča, da v naključno funkcijo vstavite spremenljivko, konstanto ali drugo funkcijo, kar pomaga ustvariti več naključnih števil.

"naključna" števila. Obstaja veliko različnih semen ali funkcij, ki jih je mogoče uporabiti v tej funkciji, vključno z millis() ali celo analogRead() za branje električnega šuma prek analognega zatiča.

naključno (največ)

naključno (najmanj, največ)

Naključna funkcija vam omogoča, da vrnete psevdonaključno število znotraj obsega, določenega z najmanjšo in največjo vrednostjo.

vrednost = naključno (100, 200); // nastavi 'vrednost' na naključno

// število med 100 in 200

Opomba: To uporabite po uporabi funkcije randomSeed(). Naslednji primer ustvari naključno število med 0 in 255 in odda PWM

signal na izhod PWM enak naključni vrednosti:

int randNumber; // spremenljivka za shranjevanje naključne vrednosti

int led = 10; // LED z uporom na pin 10

void setup() () // nastavitev ni potrebna

randomSeed(milis()); // nastavi millis() z začetno številko

naključnoŠtevilko = naključno(255); // naključno število od 0 – 255 analogWrite (led, randNumber); // izhodni signal PWM

zamuda (500); // premor za pol sekunde

Vir: Gololobov V. – Kje se začnejo roboti. O projektu Arduino za šolarje (in ne samo) – 2011

Sorodne objave

Serial.begin (rate) Odpre serijska vrata in nastavi hitrost serijskega prenosa podatkov. Tipična hitrost prenosa za računalniško komunikacijo je 9600, čeprav so podprte tudi druge hitrosti. void setup() (Serial.begin…….

Vse spremenljivke je treba deklarirati, preden jih je mogoče uporabiti. Deklaracija spremenljivke pomeni določitev vrste njene vrednosti: int, long, float itd., dodelitev unikatnega imena spremenljivki in dodatno…….

V redu, namestili smo ta program. Odpravili smo napake v "mehanizmu" dela z modulom. In pogledali smo več primerov. Sam pa bi rad ustvaril kaj uporabnega. Poskusimo. Najprej zaprimo prejšnji projekt. Za to…….

Pozor! Pri delu z modulom Arduino v drugih razvojnih okoljih bodite pozorni na konfiguracijo mikrokrmilnika (varovalke). Dokler ne boste natančno vedeli, do česa lahko sprememba privede …….

Čas in naključnost. Reakcija

Tokrat bomo izvedeli, kaj so "naključne" vrednosti in se tudi naučili delati s časom.

Potrebovali bomo:

• Gumb za takt
• Piščalka
• Povezovalne žice "MALE-MALE"

Reakcija

Naša današnja naloga je sestaviti diagram, ki nam omogoča, da ugotovimo hitrost naše reakcije.

Ko kliknete na levi gumb, se po "naključnem" času oglasi signal. In ko pritisnete desni gumb, se zabeleži, koliko časa je minilo od škripanja do pritiska na desni gumb.

Tisti, ki so vešči, poskusijo sami, mi pa pogledamo shemo.

#define BUZ 8 #define START 9 #define STOP 7 int time; //Spremenljivka za sinhronizacijo void setup() ( Serial. begin(9600); pinMode(START, INPUT_PULLUP); pinMode(STOP, INPUT_PULLUP); pinMode(BUZ, OUTPUT); ) void loop() ( if(digitalRead(START) == 0) // Ko pritisnete gumb START.. ( int start_time = millis(); // Zapomnite si čas pritiska time = start_time; // Zapišite ga v globalno spremenljivko. int Rand = random(0, 4000) ); // Ustvarimo "naključni" čas zakasnitve = čas + Rand; //Dodajmo zakasnitev časa delay(Rand); //Počakaj na ton (BUZ, 3000, 500); //Pisk! ) if(digitalRead( STOP) == 0 && digitalRead( START) == 1) // Ko pritisnete gumb STOP... ( int stop_time = millis(); // Zapomni si čas ustavitve. time = stop_time - time; // Izračunajte časovna razlika. Serial.println("Time: "); // Izdaj čas v Serial. Serial.println(time); delay(1000); ) ) // Pred drugim poskusom znova pritisnite gumb START.

Pojasnila

int čas; Spremenljivkam (ne vsem), ko jih označujemo, ni treba dati nobene vrednosti. To spremenljivko smo uporabili za povezavo dveh stavkov if.

V C++ spremenljivke, deklarirane znotraj zanke, ne bodo dostopne v drugih zankah, saj imajo učinek samo znotraj te zanke. To je narejeno za preprečevanje programskih napak. Ko bo programska koda zrasla, boste razumeli, o čem govorim.

Če želite narediti spremenljivko na voljo za več stavkov, jo morate narediti globalno. Tisti. deklarirati spremenljivko zunaj funkcij.

millis(); Vrne število milisekund, ki so pretekle od zagona programa.

Potrebujemo ga za merjenje časa, ki je pretekel od danega signala do pritiska na gumb.

naključen(min,max); To je generator naključnih števil. Ima dve vrednosti. Generira število v območju od min do max.

"Naključna" števila, ker so določeno zaporedje vrednosti. Zelo dolgo, a enako. Če želite dobiti različna zaporedja, morate uporabiti NaključenSeme();

Ta funkcija inicializira generator. In če parameter nastavimo na naključno, potem bomo dobili zaporedja, ki jih potrebujemo. Zaporedje bo enako, če je parameter fiksen.

Zaključek

Zdaj lahko trenirate svojo reakcijo z napravo, ki ste jo naredili sami. Ali pa lahko nadaljujete s študijem.

Seznam radioelementov

Imenovanje	Vrsta	Denominacija	Količina	Opomba	Trgovina	Moja beležka
	Arduino plošča	Arduino Uno	1			V beležnico
	Deska za kruh	Breadboard-polovica	1			V beležnico
	Piezo oddajnik	Pasivno	1			V beležnico
	Gumb za takt	Brez ključavnice	2			V beležnico
	Povezovalne žice	"Papa-Papa"	1