Bruke en tilfeldig tallgenerator i Arduino: Tilfeldig og RandomSeed-funksjoner. Arduino Course - Tid og tilfeldig Arduino genererer en tilfeldig bitsekvens

Når du programmerer Arduino, er det tider når du trenger å få et nummer som ikke vil være kjent på forhånd verken for programmereren som skriver skissen eller for brukeren som skal bruke Arduino med et slikt program. I dette tilfellet kommer en tilfeldig (eller rettere sagt pseudo-tilfeldig) tallgenerator til unnsetning.

For å aktivere denne generatoren, bruk bare random() eller randomSeed() funksjonene. Dette materialet vil vise deg hvordan du arbeider med disse funksjonene, samt hvordan du kan bli kvitt pseudo-tilfeldighet når du genererer tall.

Generelt simulerer en pseudotilfeldig tallgenerator det kaotiske eller tilfeldige utseendet til tall, men faktisk, hvis du analyserer en serie av disse tallene over en tilstrekkelig lang periode, kan du legge merke til et visst mønster.

Så den tilfeldige funksjonen for å generere pseudo-tilfeldige tall kan ha opptil to parametere og skrives som tilfeldig(maks) eller tilfeldig(min, maks). Her maks parameter, som er obligatorisk, spesifiserer den øvre grensen for området for generering av pseudotilfeldige tall. Ved bruk av tilleggsparameter min kan du angi den nedre grensen for området. Som et resultat vil funksjonen returnere et pseudo-tilfeldig tall i området fra min til maks-1.

Det er viktig å forstå at når du bruker random()-funksjonen, vil den nøyaktig samme listen med pseudo-tilfeldige tall genereres hver gang. For eksempel, hvis du lager en spilleautomat og første gang du trykker på håndtaket, viser det en vinnende kombinasjon, så kan du være sikker på at hvis du tilbakestiller Arduinoen og trykker på håndtaket igjen, vil den spilleautomaten vise den samme vinnerkombinasjonen . Det er faktisk ikke lett å implementere en spillmaskin med helt tilfeldig tallgenerering på Arduino, slik det for eksempel er implementert i spillmaskiner www.igrovye-apparati-vulcan.com/, men du kan delvis løse problemet ved å bruke randomSeed () funksjon.

Denne funksjonen tar en verdi (som et heltall), og bruker tallet til å endre den tilfeldige listen generert av random()-funksjonen. Du kan sette randomSeed() i oppsettfunksjonen, og bruke tilfeldig()-funksjonen i en uendelig Løkke. Men selv da er fangsten at selv om den tilfeldige tallsekvensen vil være forskjellig når du bruker randomSeed()-funksjonen, vil den fortsatt være den samme hver gang skissen kjøres.

Den eneste løsningen i dette tilfellet kan være å bruke analoge perifere enheter (ADC) og den tilsvarende analogRead()-funksjonen. Hvis den analoge inngangen ikke er koblet til noe, det vil si at den blir "hengende" i luften, kan du takket være støyen på denne linjen få virkelig tilfeldige tall. Så i oppsett-innstillingen kan du skrive randomSeed(analogRead(A0)). Forutsatt at analog port A0 ikke er tilkoblet noe sted.

Det er skrevet mye om tilfeldige tallgeneratorer, men nesten alltid når det kommer til implementering er det underforstått (eller eksplisitt uttalt) at vi snakker om om x86/x64 og andre "voksne" arkitekturer. Samtidig er fora dedikert til utvikling av enheter på mikrokontrollere fulle av spørsmål "hvordan kan jeg generere et tilfeldig tall på %controllername%?" Dessuten strekker utvalget av svar seg fra "se på Google/Wikipedia" til "bruk standardfunksjonen." Denne "standardfunksjonen" eksisterer ikke alltid og passer utvikleren på alle måter; oftere er det omvendt: noen ganger er tallene langt fra tilfeldige, noen ganger er operasjonshastigheten for lav, eller noen ganger er den resulterende koden ikke passe inn i ledig minne i det hele tatt.
La oss prøve å finne ut hva generasjonsalgoritmer for tilfeldige tall er, hvordan du velger den rette, og viktigst av alt, hva er funksjonene ved å implementere disse algoritmene på kontrollere.

Vurdere "tilfeldighet"

Applikasjonene for RNG kan være svært forskjellige, fra leker til seriøs kryptografi. Følgelig varierer kravene til generatoren også sterkt. Det er spesielle tester for å vurdere kvaliteten (nivået av "tilfeldighet") til generatoren. Her er de mest grunnleggende av dem:

• Frekvenstest. Består av å telle antall nuller og enere i en sekvens av biter. Det skal være omtrent like mange enere og nuller.
• Test for en sekvens med identiske biter. Det søkes i rader med identiske biter, som 000...0 eller 111...1. Fordelingen av frekvenser som seriene oppstår med, avhengig av lengden, bør tilsvare denne fordelingen for et virkelig tilfeldig signal.
• Spektral test. En diskret Fourier-transformasjon påføres den opprinnelige sekvensen. Det resulterende spekteret bør ikke ha signifikante topper som ville indikere tilstedeværelsen av periodiske egenskaper til sekvensen.
• Autokorrelasjonstest. Korrelasjonsverdien mellom sekvenskopier forskjøvet i forhold til hverandre beregnes. Testen lar deg finne gjentatte områder i en sekvens.

Det er spesielle sett som inkluderer dusinvis av lignende tester:
NIST - brukes i AES-konkurransen for å evaluere krypteringsalgoritmer.
DIEHARD er et av de mest strenge settene som finnes.

PRNG-algoritmer

Enhver sekvens generert i henhold til en strengt definert algoritme kan ikke betraktes som virkelig tilfeldig, derfor bruker de begrepet når de snakker om algoritmiske generatorer pseudorandom etterfølge. Enhver pseudo-tilfeldig tallgenerator (PRNG) vil gå i sløyfe før eller senere, den andre tingen er at denne "sen" kan komme om noen få millisekunder, eller kanskje om noen år. Lengden på syklusen avhenger av størrelsen på den interne tilstanden til generatoren N (faktisk er dette mengden minne som trengs av generatoren), og varierer fra 2 (N/2) til 2 N bits.
Et stort utvalg av PRNG-algoritmer er oppfunnet, men ikke alle er praktiske for implementering på mikrokontrollere. Vi er sterkt begrenset i hastighet og tilgjengelig minne; mange kontrollere støtter ikke ekte aritmetiske eller til og med multiplikasjonsinstruksjoner. Med disse begrensningene i bakhodet, la oss se på noen kjente algoritmer.

Lineær kongruent metode

Det neste medlemmet av sekvensen beregnes ved hjelp av formelen
X i+1 = (aX i + c) mod m
Antall m definerer den maksimale perioden for sekvensen, heltall en Og c- "magiske" koeffisienter. Antall m Det er rimelig å velge lik en potens på to; i dette tilfellet reduseres modulokonverteringsoperasjonen til å forkaste de mest signifikante bitene. For å oppnå maksimal periode må følgende betingelser være oppfylt:
- c og m må være relativt primtall,
- a-1 må være et multiplum s for alle hovedfaktorer s tall m,
- Hvis m er et multiplum av 4 (og i vårt tilfelle vil det være et multiplum), da a-1 må være et multiplum av 4.
Det er enda en subtilitet: bare de mest signifikante bitene av tilstandsvariabelen X bør tas som resultat, siden for de laveste bitene er de statistiske parametrene for tilfeldighet mye dårligere. Den lineære kongruente algoritmen er vanligvis implementert som standard rand() i mange biblioteker.

Fordeler:

• den maksimalt mulige perioden for en gitt størrelse på tilstandsvariabelen;
• fort nok;
• ofte allerede implementert i kompilatorbiblioteket.

Minuser:

• en multiplikasjonsoperasjon er nødvendig;
• ikke alle biter er like tilfeldige.

Sammendrag: en rask og enkel algoritme for lite krevende applikasjoner.

Fibonacci-metoden med etterslep

Denne algoritmen bruker relasjonen
X i = X i-a - X i-b ,
hvor er tilstandsvariabelen X- usignert heltall. Forsinkelsesverdier en Og b ikke hvilke som helst, men strengt definerte er tatt; for å oppnå maksimal kvalitet anbefales par (17,5), (55,24) eller (97,33). Jo større forsinkelsen er, desto lengre er perioden og desto bedre er spektralegenskapene til sekvensen. På den annen side, for at generatoren skal fungere, er det nødvendig å lagre maks(a,b) av tidligere tall, noe som ikke alltid er akseptabelt. For å kjøre generatoren trenger du også maks(a,b) tall, som vanligvis oppnås ved å bruke en enklere PRNG.

Fordeler:

• krever ikke multiplikasjonsoperasjoner;
• alle biter av et tilfeldig tall er ekvivalente i statistiske egenskaper.

Minuser:

• krever en stor mengde minne;
• krever et stort utvalg av tall for å kjøre.

Sammendrag: en svært høy kvalitet, men ressurskrevende algoritme.

Lineært tilbakemeldingsskiftregister

Tilstandsvariabelen lagres i et register med lengde N. Generering av neste tilstand innebærer to trinn:

1. Verdien av biten beregnes C = X i1 xor X i2 xor… X ik, hvor i1, i2…ik- register bitnummer, kalt bøyer.
2. Registeret forskyves 1 bit til høyre, biten lengst til venstre tar på seg verdien MED.

Utgangen fra generatoren er biten lengst til høyre (eller lengst til venstre, eller hva som helst) i registeret, det vil si at pseudorandomsekvensen genereres en bit per iterasjon. Med riktig valgte trykktall vil perioden til generatoren være 2 N - 1. "Minus en", siden det er en forbudt nulltilstand i registeret. Filialnummer for N fra 3 til 168 finnes i dette dokumentet.
I tillegg til konfigurasjonen beskrevet ovenfor, som forresten kalles Fibonacci-konfigurasjonen (ikke å forveksle med PRNG-metoden med samme navn!), er det den såkalte. Galois-konfigurasjon.


I stedet for å bruke summen av bitene i tappesekvensen for å generere en ny bit lengst til venstre, XORser den hver bit i tappesekvensen med biten lengst til høyre, og roterer deretter hele registeret til høyre. Denne ordningen er vanskeligere å forstå, men lettere å implementere, siden alle XOR-operasjoner kan utføres samtidig. Når det gjelder periodelengde og kvalitet på pseudotilfeldige tall, er Fibonacci- og Galois-skjemaer likeverdige.

Fordeler:

• veldig enkel implementering, krever ikke engang aritmetikk, bare bitoperasjoner og skift;
• veldig rask algoritme (spesielt Galois-skjemaet);
• gode statistiske egenskaper.

Minuser:

• du må sjekke startverdien for ulikhet til null.

Sammendrag: veldig rask og ganske høy kvalitet algoritme.

Kryptosikre algoritmer

For bruk i kryptografi har PRNG-er enda et viktig krav: irreversibilitet. Alle algoritmene som er oppført ovenfor har ikke denne egenskapen: Når du kjenner til flere utgangsverdier av PRNG, kan du, ved å løse et enkelt ligningssystem, finne parametrene til algoritmen (de samme "magiske" konstantene a, b, c etc). Og når du kjenner parametrene, kan du reprodusere hele pseudo-tilfeldig sekvens.
Enhver tilstrekkelig sterk blokkchiffer kan brukes som en kryptografisk sterk PRNG-algoritme. Ved å velge en hemmelig nøkkel kan du få blokker med pseudotilfeldige tall ved å bruke algoritmen på sekvensielle naturlige tall. For en N-bit blokkchiffer vil perioden ikke være mer enn 2 N. Sikkerheten til en slik ordning avhenger helt av hemmeligholdet til nøkkelen.
Alle moderne kryptografiske algoritmer er testet for bruk som PRNG-er, det vil si ved å bruke en sertifisert algoritme, det er ikke nødvendig å bry seg spesielt om de statistiske og spektrale egenskapene til utgangsstrømmen. Du trenger bare å bekymre deg for den beregningsmessige "frossigheten" til kryptoalgoritmer. Hvis du trenger å utføre et stort antall krypteringsoperasjoner, er det fornuftig å velge en kontroller med maskinvarekryptografiske blokker. Ofte har slike kontrollere også en veldig god krypto-resistent maskinvare PRNG.

Kilder til entropi

Som allerede nevnt, ved bruk av bare deterministiske algoritmer, er det umulig å generere et virkelig tilfeldig tall. Derfor brukes vanligvis en kombinasjon av PRNG + ekstern kilde til entropi. Entropikilden brukes til å angi startverdien for PRNG, og sistnevntes oppgave er å sikre den spektrale og statistiske renheten til sekvensen. Hva kan brukes som en kilde til entropi? Ja, nesten hva som helst.

Brukeraktivitet

Hvis enheten samhandler med brukeren på noen måte, ganske Bra valg vil bruke brukeren selv som en kilde til entropi. For eksempel er tidspunktet for å trykke på en knapp, målt med en nøyaktighet på et mikrosekund (eller rettere sagt, dets minst signifikante sifre), helt uforutsigbar. Imidlertid må enheten ofte fungere autonomt, noe som betyr at vi er fratatt denne fantastiske informasjonskanalen.

Analog-til-digital omformer

Mange kontrollere har innebygde ADC-er. Og i mange kontrollere er de av veldig middelmådig kvalitet, laget bare for å være. De lave ordensbitene til ADC-resultatet inneholder nesten alltid betydelig støy, selv ved måling av likespenning. Dette kan brukes: koble ADC-inngangen til forsyningsspenningen gjennom en deler, ta noen dusin målinger, ta de minst signifikante bitene - her har du et flott tilfeldig tall. Hvis ADC-en inneholder en innebygd forforsterker, slå den på, den er også støyende.

Asynkrone generatorer

Du kan bruke forskjellen i perioder for to usynkroniserte klokkegeneratorer. De fleste kontrollere inneholder for eksempel en watchdog-timer. For å øke påliteligheten klokkes den fra en separat generator, som på ingen måte er forbundet med hovedklokkesignalet. Det er nok å telle antall sykluser av hovedklokkesignalet i løpet av en periode av vakthundtimeren. Velger du perioder slik at telleren renner over mange ganger i løpet av målingen, kan du få et ganske tilfeldig tall. Ulempen med denne metoden er at den tar mye tid, opptil flere sekunder.

Sanntidsklokke

Hvis diagrammet har sanntidsklokke, kan du bruke deres nåværende avlesninger til å initialisere PRNG. For eksempel, ved å konvertere gjeldende dato/klokkeslett til Unix-tidsformatet, får vi umiddelbart 32 biter, som aldri vil ikke skje igjen med mindre du tar avlesninger mer enn én gang per sekund. Å bruke sanntid gir unike verdier, men gir ingen uforutsigbarhet, så det er bedre å kombinere denne metoden med andre.

RC-krets

Hvis kontrolleren har nr eksterne enheter, i tillegg til I/O-portene, kan du gjøre følgende: ett av bena er koblet gjennom en kondensator til jord, og gjennom en motstand til forsyningsspenningen. Hvis kontrollerinngangene har interne pull-up-motstander, er det ikke nødvendig med en ekstern motstand.

Vi sender ut et "0" -signal til denne porten - kondensatoren er utladet. Vi bytter porten til inngangsmodus - kondensatoren begynner å lade. Når spenningen over den når terskelen, vil inngangen bytte fra tilstand "0" til "1". Ladetiden avhenger sterkt av mange faktorer: forsyningsspenning, drift av RC-kretsparametere, terskelustabilitet, temperatur, lekkasjer, interferens. Ved å måle den med tilstrekkelig nøyaktighet og ta de minst signifikante bitene, kan du få god tilfeldighet.

Maskinvare støygenerator

For mange seriøse applikasjoner (spesielt kryptografi), kreves det en mer pålitelig kilde til entropi enn de som er oppført ovenfor. I slike tilfeller bruker de digitalisering av signalet fra en støygenerator basert på termiske, skudd- eller til og med kvanteeffekter. Støyelementet er vanligvis en spesiell diode eller zenerdiode, hvorfra signalet forsterkes og føres til en komparator som genererer en binær bitstrøm.

For å sikre at komparatorresponsterskelen ikke påvirker de statistiske egenskapene til det mottatte signalet, brukes to støygeneratorer som opererer på en komparator:

Konklusjon

Til slutt skal jeg fortelle deg en historie fra livet mitt. Det startet med et annet spørsmål stilt på forumet: "hvordan kan jeg generere et tilfeldig tall på kontrolleren?" Forfatteren av spørsmålet forklarte at han som et kursprosjekt lager en enhet som emulerer terningkasting. Etter flere mislykkede forsøk på å forstå algoritmene, delte emnestarteren sin løsning: han rullet ganske enkelt en ekte terning 1000 ganger og fylte hele det ledige minnet til kontrolleren med de resulterende tallene. Generatoren besto briljant alle "tilfeldighet"-testene, gitt at den under demonstrasjonen brukte opp mindre enn en tredjedel av "reserven".
Derfor har en slik løsning også livets rett, spesielt hvis det stilles svært strenge krav til talls tilfeldighet, men de kreves ikke for ofte. Med minneprisene stuper, kan det være lurt å utstyre en enhet med en «kaosreserve» som varer hele enhetens levetid.
Takk for din oppmerksomhet!

UPD1: Som det med rette ble bemerket i kommentarene, hvis et angrep på RNG forventes, og angriperen har maskinvaretilgang til enheten, må eksterne kilder til entropi brukes med stor forsiktighet, siden det ikke er veldig vanskelig å erstatte signalet fra ekstern kilde. Interne kilder bør brukes, i tillegg til eksterne.
Det er også en god idé å samle entropi alt fritid, og bruk den når du trenger å generere et annet tilfeldig tall. Vanligvis i slike tilfeller den såkalte Entropibasseng- en matrise som en av PRNG-funksjonene periodisk utføres over, og som data fra entropikilder konstant blandes inn i.

UPD2: I mange tilfeller er det nyttig å lagre innholdet i Entropy-poolen (beklager, jeg kjenner ikke den normale russiske oversettelsen) i EEPROM, slik at den ikke akkumuleres igjen etter å ha slått av og på enheten. Dette gjelder først og fremst å oppnå entropi ved å bruke metoden for asynkrone generatorer: under tilstrekkelig stabile forhold kan den samme sekvensen genereres etter hver påkobling.
Hvis et angrep forventes, ta forholdsregler mot tukling av EEPROM. Hvis kontrolleren tillater det, blokker lesing/sletting/skriving ved hjelp av låsebiter, og når du slår den på, overvåk integriteten til EEPROM, i det minste ved å bruke enkle sjekksummer.

Tagger:

• RNG
• gpsch
• mikrokontrollere
• algoritmer

Legg til merkelapper

randomSeed (frø)

Setter verdien, eller frøet, som utgangspunkt for funksjonen tilfeldig().

randomSeed(verdi); // setter 'verdi' som den første tilfeldige verdien

Siden Arduino ikke kan generere virkelig tilfeldige tall, lar randomSeed deg sette inn en variabel, konstant eller annen funksjon i tilfeldig funksjon, noe som bidrar til å generere flere tilfeldige tall.

"tilfeldige" tall. Det er mange forskjellige frø, eller funksjoner, som kan brukes i denne funksjonen, inkludert millis(), eller til og med analogRead() for å lese elektrisk støy gjennom en analog pinne.

tilfeldig (maks.)

tilfeldig (min, maks)

Den tilfeldige funksjonen lar deg returnere et pseudo-tilfeldig tall innenfor området spesifisert av min- og maksverdiene.

verdi = tilfeldig(100, 200); // setter 'verdi' til tilfeldig

// et tall mellom 100 og 200

Merk: Bruk dette etter å ha brukt randomSeed()-funksjonen. Følgende eksempel lager et tilfeldig tall mellom 0 og 255 og sender ut PWM

signal til PWM-utgangen lik en tilfeldig verdi:

int randNumber; // variabel for å lagre en tilfeldig verdi

int led = 10; // LED med motstand på pinne 10

void setup() () // oppsett er ikke nødvendig

randomSeed(millis()); // setter millis() med starttallet

randomTall = tilfeldig(255); // tilfeldig tall fra 0 – 255 analogWrite (led, randNumber); // ut PWM-signal

forsinkelse(500); // pause i et halvt sekund

Kilde: Gololobov V. – Hvor begynner roboter. Om Arduino-prosjektet for skolebarn (og ikke bare) – 2011

Relaterte innlegg

Serial.begin (rate) Åpner serieporten og setter hastigheten for seriell dataoverføring. Den typiske overføringshastigheten for datakommunikasjon er 9600, selv om andre hastigheter støttes. void setup() (Serial.begin…….

Alle variabler må deklareres før de kan brukes. Å erklære en variabel betyr å definere typen av dens verdi: int, long, float, etc., tildele variabelen et unikt navn, og i tillegg…….

Ok, vi har installert dette programmet. Vi har feilsøkt "mekanismen" for å jobbe med modulen. Og vi så på flere eksempler. Men jeg vil gjerne lage noe nyttig selv. La oss prøve. Først, la oss avslutte det forrige prosjektet. For dette…….

Merk følgende! Når du arbeider med Arduino-modulen i andre utviklingsmiljøer, bør du være forsiktig med mikrokontrollerkonfigurasjonen (sikringer). Inntil du vet nøyaktig hva endringen kan føre til…….

Tid og tilfeldighet. Reaksjon

Denne gangen vil vi lære hva "Tilfeldige" verdier er og også lære å jobbe med tid.

Vi trenger:

• Taktknapp
• Squeaker
• Koble ledninger «MALE-MALE»

Reaksjon

Vår oppgave for i dag er å sette sammen et diagram som lar oss finne ut hastigheten på reaksjonen vår.

Når du klikker på venstre knapp, høres et signal etter en "tilfeldig" tid. Og når du trykker på høyre knapp, noteres det hvor lang tid som har gått fra knirking til å trykke på høyre knapp.

De som er dyktige prøver det selv, og vi ser på diagrammet.

#define BUZ 8 #define START 9 #define STOP 7 int time; //Variabel for synkronisering void setup() ( Serial. begin(9600); pinMode(START, INPUT_PULLUP); pinMode(STOP, INPUT_PULLUP); pinMode(BUZ, OUTPUT); ) void loop() ( if(digitalRead(START) == 0) // Når du trykker på START-knappen.. ( int start_time = millis(); // Husk tidspunktet for å trykke tid = start_time; // Skriv det til en global variabel. int Rand = random(0, 4000) ); // La oss generere en "tilfeldig" forsinkelsestid = tid + Rand; //Legg til forsinkelsestidsforsinkelsen(Rand); //Vent på tone(BUZ, 3000, 500); //Beep! ) if(digitalRead( STOP) == 0 && digitalRead( START) == 1) // Når du trykker på STOP-knappen... ( int stop_time = millis(); // Husk stopptiden. time = stop_time - time; // Beregn tidsforskjell. Serial.println("Tid: "); // Send ut tiden til Serial. Serial.println(tid); delay(1000); ) ) // Før det andre forsøket, trykk på START-knappen igjen.

Forklaringer

int tid; Variabler (ikke alle), når de angir dem, trenger ikke å gis noen verdi. Vi brukte denne variabelen til å koble to if-utsagn.

I C++ vil variabler deklarert inne i en løkke ikke være tilgjengelige i andre løkker, siden de kun har effekt innenfor den løkken. Dette gjøres for å forhindre programmeringsfeil. Når programkoden vokser, vil du forstå hva jeg snakker om.

For å gjøre en variabel tilgjengelig for flere utsagn, må du gjøre den global. De. erklære en variabel utenfor funksjoner.

millis(); Returnerer antall millisekunder som har gått siden programmet ble lansert.

Vi trenger det for å måle hvor lang tid som har gått fra signalet ble gitt til knappen ble trykket.

tilfeldig(min,maks); Dette er en tilfeldig tallgenerator. Tar to verdier. Den genererer et tall i området fra min til maks.

"Tilfeldige" tall fordi de er en spesifikk sekvens av verdier. Veldig lang, men den samme. For å få forskjellige sekvenser bør du bruke TilfeldigFrø();

Denne funksjonen initialiserer generatoren. Og hvis vi setter parameteren til tilfeldig, vil vi få sekvensene vi trenger. Rekkefølgen vil være den samme hvis parameteren er fast.

Konklusjon

Nå kan du trene reaksjonen din ved hjelp av en enhet du har laget selv. Eller du kan fortsette å studere videre.

Liste over radioelementer

Betegnelse	Type	Valør	Mengde	Merk	Butikk	Notisblokken min
	Arduino-brett	Arduino Uno	1			Til notisblokk
	Brødbrett	Brødbrett-halv	1			Til notisblokk
	Piezo emitter	Passiv	1			Til notisblokk
	Taktknapp	Uten lås	2			Til notisblokk
	Koble ledninger	"Papa-Papa"	1