Arduino funkcija slučajnog broja. Korištenje generatora slučajnih brojeva u Arduinu: Random i RandomSeed funkcije

O generatorima slučajnih brojeva se dosta pisalo, ali se gotovo uvijek, kada je implementacija u pitanju, podrazumijeva (ili eksplicitno) da je riječ o x86/x64 i drugim "odraslim" arhitekturama. Istovremeno, forumi posvećeni razvoju uređaja na mikrokontrolerima puni su pitanja "kako mogu generirati nasumični broj na %controllername%?" Štaviše, raspon odgovora se proteže od "pogledajte Google/Wikipedia" do "koristite standardnu ​​funkciju". Ova “standardna funkcija” ne postoji uvijek i odgovara programeru u svakom pogledu; češće je obrnuto: ponekad su brojevi daleko od slučajnih, ponekad je brzina rada preniska, ili ponekad rezultirajući kod ne odgovara u slobodnu memoriju uopšte.
Pokušajmo shvatiti koji su algoritmi za generiranje slučajnih brojeva, kako odabrati pravi, i što je najvažnije, koje su karakteristike implementacije ovih algoritama na kontrolere.

Procjena "slučajnosti"

Aplikacije za RNG mogu biti vrlo različite, od igračaka do ozbiljne kriptografije. Shodno tome, zahtjevi za generatorom također se uvelike razlikuju. Postoje posebni testovi za procjenu kvaliteta (nivoa „slučajnosti“) generatora. Evo najosnovnijih od njih:

• Test frekvencije. Sastoji se od brojanja broja nula i jedinica u nizu bitova. Trebao bi biti približno jednak broj jedinica i nula.
• Testirajte niz identičnih bitova. Pretražuju se redovi identičnih bitova, poput 000...0 ili 111...1. Raspodjela frekvencija s kojima se nizovi javljaju, ovisno o njihovoj dužini, treba odgovarati ovoj raspodjeli za istinski slučajan signal.
• Spektralni test. Diskretna Fourierova transformacija se primjenjuje na originalni niz. Rezultirajući spektar ne bi trebao imati značajne pikove koji bi ukazivali na prisustvo periodičnih svojstava niza.
• Autokorelacioni test. Izračunava se vrijednost korelacije između kopija sekvence pomjerenih jedna u odnosu na drugu. Test vam omogućava da pronađete regije koje se ponavljaju u nizu.

Postoje posebni setovi koji uključuju desetke sličnih testova:
NIST - koristi se u AES takmičenju za procjenu algoritama šifriranja.
DIEHARD je jedan od najrigoroznijih skupova koji postoje.

PRNG algoritmi

Bilo koji niz generiran prema strogo definiranom algoritmu ne može se smatrati istinski slučajnim, stoga, kada govore o algoritamskim generatorima, koriste izraz pseudoslučajan podsekvenca. Bilo koji generator pseudo-slučajnih brojeva (PRNG) će prije ili kasnije ući u petlju, druga stvar je što ovo „kasno“ može doći za nekoliko milisekundi, ili možda za nekoliko godina. Dužina ciklusa zavisi od veličine unutrašnjeg stanja generatora N (u stvari, ovo je količina memorije koja je potrebna generatoru), i kreće se od 2 (N/2) do 2 N bita.
Izmišljen je veliki broj PRNG algoritama, ali nisu svi pogodni za implementaciju na mikrokontrolerima. Jako smo ograničeni u brzini i dostupnoj memoriji; mnogi kontroleri ne podržavaju stvarnu aritmetičku ili čak instrukciju množenja. Imajući na umu ova ograničenja, pogledajmo neke dobro poznate algoritme.

Linearna kongruentna metoda

Sljedeći član niza se izračunava pomoću formule
X i+1 = (aX i + c) mod m
Broj m definira maksimalan period niza, cijeli brojevi a I c- “magični” koeficijenti. Broj m Razumno je odabrati jednak stepen dva; u ovom slučaju, modulo konverzijska operacija se svodi na odbacivanje najznačajnijih bitova. Da bi se postigao maksimalni period, moraju biti ispunjeni sljedeći uslovi:
- c i m mora biti relativno prost,
- a-1 mora biti višestruka str za sve osnovne faktore str brojevi m,
- Ako m je višekratnik od 4 (a u našem slučaju će biti višekratnik), onda a-1 mora biti višekratnik od 4.
Postoji još jedna suptilnost: kao rezultat treba uzeti samo najznačajnije bitove varijable stanja X, jer su za najniže bitove statistički parametri slučajnosti mnogo gori. Linearni kongruentni algoritam se obično implementira kao standardni rand() u mnogim bibliotekama.

Pros:

• maksimalni mogući period za datu veličinu varijable stanja;
• dovoljno brzo;
• često već implementiran u biblioteci kompajlera.

minusi:

• potrebna je operacija množenja;
• nisu svi bitovi jednako nasumični.

Sažetak: brz i jednostavan algoritam za ne baš zahtjevne aplikacije.

Fibonačijev metod sa kašnjenjima

Ovaj algoritam koristi relaciju
X i = X i-a - X i-b ,
gdje je varijabla stanja X- cijeli broj bez predznaka. Vrijednosti kašnjenja a I b uzimaju se ne bilo koji, već strogo definisani, a za postizanje maksimalnog kvaliteta preporučuju se parovi (17,5), (55,24) ili (97,33). Što je kašnjenje veće, duži je period i bolja su spektralna svojstva niza. S druge strane, da bi generator radio, potrebno je pohraniti max(a,b) prethodnih brojeva, što nije uvijek prihvatljivo. Također, za pokretanje generatora potrebni su vam max(a,b) brojevi, koji se obično dobijaju jednostavnijim PRNG-om.

Pros:

• ne zahtijeva operacije množenja;
• svi bitovi slučajnog broja su ekvivalentni u statističkim svojstvima.

minusi:

• zahtijeva veliku količinu memorije;
• zahtijeva veliki niz brojeva za pokretanje.

Sažetak: vrlo kvalitetan algoritam koji zahtijeva puno resursa.

Registar pomaka s linearnom povratnom spregom

Varijabla stanja je pohranjena u registru dužine N. Generiranje sljedećeg stanja uključuje dva koraka:

1. Vrijednost bita se izračunava C = X i1 xor X i2 xor… X ik, gdje je i1, i2…ik- registarski brojevi bitova, tzv krivine.
2. Registar se pomjera za 1 bit udesno, krajnji lijevi bit poprima vrijednost WITH.

Izlaz generatora je krajnji desni (ili krajnji lijevi, ili bilo koji drugi) bit registra, to jest, pseudoslučajni niz se generiše jedan bit po iteraciji. Sa ispravno odabranim brojevima slavina, period generatora će biti 2 N - 1. “Minus jedan”, pošto postoji zabranjeno nulto stanje registra. Brojevi filijala za N od 3 do 168 se mogu naći u ovom dokumentu.
Pored gore opisane konfiguracije, koja se, inače, zove Fibonačijeva konfiguracija (ne brkati je sa istoimenom PRNG metodom!), postoji i tzv. Galois konfiguracija.


Umjesto da koristi zbir bitova u tap sekvenci za generiranje novog krajnjeg lijevog bita, vrši XOR svaki bit u tap sekvenci s krajnjim desnim bitom, a zatim rotira cijeli registar udesno. Ovu shemu je teže razumjeti, ali je lakše implementirati, budući da se sve XOR operacije mogu izvoditi istovremeno. U smislu dužine perioda i kvaliteta pseudoslučajnih brojeva, Fibonačijeve i Galoisove šeme su ekvivalentne.

Pros:

• vrlo jednostavna implementacija, ne zahtijeva čak ni aritmetiku, samo bitne operacije i pomake;
• vrlo brz algoritam (posebno Galois shema);
• dobra statistička svojstva.

minusi:

• morate provjeriti početnu vrijednost za nejednakost na nulu.

Sažetak: vrlo brz i prilično kvalitetan algoritam.

Kriptootporni algoritmi

Za upotrebu u kriptografiji, PRNG-ovi imaju još jedan bitan zahtjev: ireverzibilnost. Svi gore navedeni algoritmi nemaju ovo svojstvo: znajući nekoliko izlaznih vrijednosti PRNG-a, možete, rješavanjem jednostavnog sistema jednadžbi, pronaći parametre algoritma (iste "magične" konstante a, b, c itd). A znajući parametre, možete reproducirati cijeli pseudo-slučajni niz.
Bilo koja dovoljno jaka blok šifra može se koristiti kao kriptografski jak PRNG algoritam. Odabirom tajnog ključa možete dobiti blokove pseudoslučajnih brojeva primjenom algoritma na sekvencijalne prirodne brojeve. Za N-bitnu blok šifru, period neće biti veći od 2 N. Sigurnost takve sheme u potpunosti ovisi o tajnosti ključa.
Svi moderni kriptografski algoritmi su testirani za upotrebu kao PRNG-ovi, odnosno, koristeći sertifikovani algoritam, nema potrebe posebno voditi računa o statističkim i spektralnim svojstvima izlaznog toka. Trebate samo da brinete o računskoj „proždrljivosti“ kripto algoritama. Ako trebate izvršiti veliki broj operacija šifriranja, ima smisla odabrati kontroler s hardverskim kriptografskim blokovima. Često takvi kontroleri imaju i vrlo dobar hardverski PRNG otporan na kriptovalute.

Izvori entropije

Kao što je već rečeno, koristeći samo determinističke algoritme, nemoguće je generirati istinski slučajan broj. Stoga se obično koristi kombinacija PRNG + eksterni izvor entropije. Entropijski izvor se koristi za postavljanje početne vrijednosti za PRNG, a zadatak potonjeg je osigurati spektralnu i statističku čistoću niza. Šta se može koristiti kao izvor entropije? Da, skoro sve.

Aktivnost korisnika

Ako uređaj na bilo koji način komunicira s korisnikom, prilično dobro rješenje bi bilo korištenje samog korisnika kao izvora entropije. Na primjer, vrijeme pritiska na tipku, mjereno s preciznošću od mikrosekunde (tačnije, njenih najmanje značajnih cifara), potpuno je nepredvidivo. Međutim, često uređaj mora raditi autonomno, što znači da smo uskraćeni za ovaj divan kanal informacija.

Analogno-digitalni pretvarač

Mnogi kontroleri imaju ugrađene ADC. A u mnogim kontrolerima oni su vrlo osrednjeg kvaliteta, napravljeni samo da budu. Bitovi nižeg reda rezultata ADC-a gotovo uvijek sadrže značajan šum, čak i kada se mjere istosmjerni napon. Ovo se može koristiti: spojite ADC ulaz na napon napajanja kroz razdjelnik, napravite nekoliko desetina mjerenja, uzmite najmanje značajne bitove - ovdje imate veliki slučajni broj. Ako ADC ima ugrađeno pretpojačalo, uključite ga, također je bučan.

Asinhroni generatori

Možete koristiti razliku u periodima dva nesinhronizovana generatora takta. Većina kontrolera sadrži, na primjer, watchdog tajmer. Da bi se povećala pouzdanost, taktirano je iz zasebnog generatora, koji ni na koji način nije povezan s glavnim taktnim signalom. Dovoljno je izbrojati broj ciklusa signala glavnog sata tokom jednog perioda watchdog timera. Ako odaberete periode tako da se brojač više puta prelije tokom mjerenja, možete dobiti prilično nasumičan broj. Nedostatak ove metode je što traje dosta vremena, do nekoliko sekundi.

Sat realnog vremena

Ako dijagram ima sat realnog vremena, možete koristiti njihova trenutna očitavanja da inicijalizirate PRNG. Na primjer, pretvaranjem trenutnog datuma/vremena u Unix format vremena, odmah dobijamo 32 bita, što nikad neće se ponoviti osim ako očitavate više od jednom u sekundi. Korištenje realnog vremena daje jedinstvene vrijednosti, ali ne pruža nikakvu nepredvidljivost, pa je bolje kombinirati ovu metodu s drugima.

RC kolo

Ako kontroler nema nikakve periferne uređaje osim I/O portova, možete postupiti na sljedeći način: jedna od nogu je spojena preko kondenzatora na masu, a preko otpornika na napon napajanja. Ako ulazi kontrolera imaju interne pull-up otpornike, eksterni otpornik nije potreban.

Na ovaj port šaljemo signal "0" - kondenzator se ispraznio. Prebacujemo port u način unosa - kondenzator se počinje puniti. Kada napon na njemu dostigne prag, ulaz će se prebaciti iz stanja “0” u “1”. Vrijeme punjenja jako ovisi o mnogim faktorima: napon napajanja, pomjeranje parametara RC kola, nestabilnost praga, temperatura, curenje, smetnje. Mjerenjem sa dovoljnom preciznošću i uzimanjem najmanje značajnih bitova, možete dobiti dobru nasumicu.

Generator hardverske buke

Za mnoge ozbiljne aplikacije (naročito kriptografiju), potreban je pouzdaniji izvor entropije od gore navedenih. U takvim slučajevima koriste digitalizaciju signala iz generatora šuma na osnovu termičkih, udarnih ili čak kvantnih efekata. Element šuma je obično posebna dioda ili zener dioda, signal iz koje se pojačava i dovodi u komparator koji generiše binarni tok bitova.

Kako bi se osiguralo da prag odziva komparatora ne utiče na statistička svojstva primljenog signala, koriste se dva generatora šuma koji rade na jednom komparatoru:

Zaključak

Za kraj, ispričaću vam jednu priču iz svog života. Počelo je sa drugim pitanjem postavljenim na forumu: "kako mogu generirati nasumični broj na kontroleru?" Autor pitanja je objasnio da kao kursni projekat izrađuje uređaj koji oponaša bacanje kocke. Nakon nekoliko neuspješnih pokušaja razumijevanja algoritama, topicstarter je podijelio svoje rješenje: jednostavno je bacio pravu kockicu 1000 puta i popunio svu slobodnu memoriju kontrolera rezultirajućim brojevima. Generator je sjajno prošao sve testove “slučajnosti”, s obzirom da je tokom demonstracije potrošio manje od trećine svoje “rezerve”.
Stoga i takvo rješenje ima pravo na život, posebno ako se postavljaju vrlo strogi zahtjevi za slučajnost brojeva, ali se ne zahtijevaju prečesto. S obzirom da cijene memorije naglo padaju, možda bi bilo pametno opremiti uređaj "rezervom haosa" koji će trajati cijeli vijek trajanja uređaja.
Hvala vam na pažnji!

UPD1: Kao što je ispravno navedeno u komentarima, ako je planiran napad na RNG, a napadač ima hardverski pristup uređaju, eksterni izvori entropije moraju se koristiti s velikim oprezom, jer nije teško zamijeniti signal sa eksterni izvor. Treba koristiti interne izvore, pored eksternih.
Takođe je dobra ideja da akumulirate entropiju tokom svog slobodnog vremena i da je koristite kada trebate da generišete sledeći slučajni broj. Obično se u takvim slučajevima koristi tzv Entropijski bazen- niz nad kojim se periodično izvršava jedna od PRNG funkcija iu koji se podaci iz entropijskih izvora stalno miješaju.

UPD2: U mnogim slučajevima, korisno je sačuvati sadržaj Entropy pool-a (izvinite, ne znam normalan ruski prijevod) u EEPROM kako ga nakon isključivanja i uključivanja uređaja ne bi ponovo akumulirao. To se, prije svega, odnosi na dobivanje entropije metodom asinhronih generatora: pod dovoljno stabilnim uvjetima, isti niz može se generirati nakon svakog uključivanja.
Ako se očekuje napad, poduzmite mjere protiv neovlaštenog pristupa EEPROM-u. Ako kontroler to dozvoljava, blokirajte čitanje/brisanje/pisanje pomoću lock bitova, a kada ga uključite, pratite integritet EEPROM-a, barem koristeći jednostavne kontrolne sume.

Tagovi:

• RNG
• gpsch
• mikrokontroleri
• algoritmi

Dodaj oznake

Kada programirate Arduino, postoje slučajevi kada trebate dobiti broj koji neće biti poznat unaprijed ni programeru koji piše skicu, niti korisniku koji će koristiti Arduino sa takvim programom. U ovom slučaju u pomoć dolazi generator slučajnih (ili bolje rečeno pseudo-slučajnih) brojeva.

Da biste aktivirali ovaj generator, samo koristite funkcije random() ili randomSeed(). Ovaj materijal će vam pokazati kako raditi s ovim funkcijama, kao i kako se riješiti pseudo-slučajnosti prilikom generiranja brojeva.

Generalno, generator pseudoslučajnih brojeva simulira haotično ili nasumično pojavljivanje brojeva, ali u stvari, ako analizirate niz ovih brojeva tokom dovoljno dugog perioda, možete uočiti određeni obrazac.

Dakle, slučajna funkcija za generiranje pseudoslučajnih brojeva može imati do dva parametra i zapisuje se kao random(max) ili random(min, max). Ovdje, max parametar, koji je obavezan, postavlja gornju granicu raspona za generiranje pseudoslučajnih brojeva. Pomoću dodatnog parametra min možete postaviti donju granicu raspona. Kao rezultat, funkcija će vratiti neki pseudo-slučajni broj u rasponu od min do max-1.

Važno je shvatiti da kada koristite funkciju random() svaki put će se generirati potpuno ista lista pseudo slučajnih brojeva. Na primjer, ako napravite slot mašinu i prvi put kada pritisnete ručku, ona pokaže dobitnu kombinaciju, onda možete biti sigurni da će, ako resetujete Arduino i ponovo pritisnete ručku, ta slot mašina pokazati istu dobitnu kombinaciju . Zaista, nije lako implementirati mašinu za igre sa potpuno slučajnim generisanjem brojeva na Arduinu, kao što je, na primer, implementirano u mašinama za igre www.igrovye-apparati-vulcan.com/, ali možete delimično rešiti problem koristeći randomSeed () funkcija.

Ova funkcija uzima vrijednost (kao što je cijeli broj) i koristi broj za izmjenu nasumične liste koju generira random() funkcija. Možete staviti randomSeed() u funkciju podešavanja i koristiti funkciju random() u beskonačno petlja. Ali čak i tada, kvaka je u tome što će redoslijed nasumičnih brojeva biti drugačiji kada se koristi funkcija randomSeed(), i dalje će biti isti svaki put kada se skica pokrene.

Jedino rješenje u ovom slučaju može biti korištenje analognih perifernih uređaja (ADC) i odgovarajuće funkcije analogRead(). Ako analogni ulaz nije povezan ni sa čim, odnosno ostavljen "visi" u zraku, onda zahvaljujući buci na ovoj liniji možete dobiti zaista nasumične brojeve. Zatim u postavkama za podešavanje možete napisati randomSeed(analogRead(A0)). Pod uslovom da analogni port A0 nije nigde povezan.

Vrijeme i slučajnost. Reakcija

Ovaj put ćemo naučiti šta su „slučajne“ vrijednosti i naučiti kako raditi s vremenom.

trebat će nam:

• Dugme za takt
• Squeaker
• Priključne žice “MUŠKARAC-MUŠKARAC”

Reakcija

Naš današnji zadatak je da sastavimo dijagram koji nam omogućava da saznamo brzinu naše reakcije.

Kada pritisnete lijevo dugme, oglašava se signal nakon "nasumično" vremena. A kada pritisnete desno dugme, bilježi se koliko je vremena prošlo od škripe do pritiska na desno dugme.

Oni koji su vješti probaju sami, a mi gledamo dijagram.

#define BUZ 8 #define START 9 #define STOP 7 int vrijeme; //Varijabla za sinhronizaciju void setup() ( Serial. begin(9600); pinMode(START, INPUT_PULLUP); pinMode(STOP, INPUT_PULLUP); pinMode(BUZ, OUTPUT); ) void loop() ( if(digitalRead(START) == 0) // Kada pritisnete dugme START.. ( int start_time = millis(); // Zapamtite vreme pritiska time = start_time; // Upišite ga u globalnu varijablu. int Rand = random(0, 4000 ); // Generirajmo "slučajno" vrijeme kašnjenja = vrijeme + Rand; //Dodamo vrijeme kašnjenja(Rand); //Pričekajte ton(BUZ, 3000, 500); //Beep! ) if(digitalRead( STOP) == 0 && digitalRead( START) == 1) // Kada pritisnete dugme STOP... ( int stop_time = millis(); // Zapamtite vreme zaustavljanja. time = stop_time - time; // Izračunajte vremenska razlika. Serial.println("Time: "); // Izlaz vremena u Serial. Serial.println(time); delay(1000); ) ) // Prije drugog pokušaja, ponovo pritisnite tipku START.

Objašnjenja

int vrijeme; Varijablama (ne svim), kada ih označavaju, ne mora se dati vrijednost. Koristili smo ovu varijablu da povežemo dva if naredbe.

U C++, varijable deklarisane unutar petlje neće biti dostupne u drugim petljama, jer imaju učinak samo unutar te petlje. Ovo se radi kako bi se spriječile programske greške. Kada programski kod poraste, razumjet ćete o čemu govorim.

Da bi varijabla bila dostupna za više naredbi, morate je učiniti globalnom. One. deklarisati varijablu izvan funkcija.

millis(); Vraća broj milisekundi koje su prošle od pokretanja programa.

Potreban nam je za mjerenje vremena koje je prošlo od signala koji je dat do pritiska na dugme.

nasumično (min,max); Ovo je generator slučajnih brojeva. Uzima dvije vrijednosti. Generiše broj u rasponu od min do max.

"Slučajni" brojevi jer su određeni niz vrijednosti. Vrlo dugo, ali isto. Da biste dobili različite sekvence, trebali biste koristiti SlučajnoSjeme();

Ova funkcija inicijalizira generator. A ako parametar postavimo na nasumičan, onda ćemo dobiti sekvence koje su nam potrebne. Redoslijed će biti isti ako je parametar fiksan.

Zaključak

Sada možete trenirati svoju reakciju koristeći uređaj koji ste sami napravili. Ili možete nastaviti dalje učiti.

Spisak radioelemenata

Oznaka	Tip	Denominacija	Količina	Bilješka	Prodavnica	Moja beležnica
	Arduino ploča	Arduino Uno	1			U notes
	Bread board	Breadboard-pola	1			U notes
	Piezo emiter	Pasivno	1			U notes
	Dugme za takt	Bez brave	2			U notes
	Spojne žice	"tata-tata"	1