Hva er en tilfeldig tallgenerator?
En tilfeldig tallgenerator (RNG) er et system som produserer tilfeldige tall eller pseudotilfeldige tall. Hvorvidt det neste tallet faktisk kan forutsies, avhenger av typen generator. Noen generatorer henter data fra en fysisk prosess, noen beregner tallene sine med en algoritme, og noen algoritmer er bygget slik at selv noen som har sett resultatene deres, ikke kan forutsi hva som kommer etterpå. Å se tilfeldig ut og å være uforutsigbar er ulike egenskaper, og mesteparten av denne artikkelen handler om denne forskjellen.
Maskinvarebaserte tilfeldige tallgeneratorer
En maskinvarebasert tilfeldig tallgenerator (HRNG), også kalt en ekte tilfeldig tallgenerator (TRNG), henter tallene sine fra en fysisk prosess. De eldste formene fungerer rett foran øynene våre: en mynt som kastes, en terning som ruller, et ruletthjul. Mekanikken beskriver hver av dem fullstendig, men et godt laget hjul er likevel uforutsigbart i praksis, fordi ørsmå forskjeller i hvordan hvert spinn starter vokser til helt forskjellige utfall.
Moderne maskinvaregeneratorer måler mikroskopiske fenomener i stedet: haglskuddstøy og termisk støy i elektroniske kretser, atmosfærisk støy, kvanteeffekter. Dette er gode kilder til entropi — uforutsigbarhet som kan måles — men en fysisk kilde er ikke perfekt av natur: den kan ha skjevheter, den kan drive og den kan svikte, så kvaliteten må vurderes og overvåkes, og verdiene må etterbehandles der det er nødvendig, noe standarder som NIST SP 800-90B beskriver. Maskinvarekilder brukes der garantien betyr mest — fremfor alt i kryptografi, der de leverer det uforutsigbare utgangsmaterialet for nøklene bak protokoller som Transport Layer Security (TLS).
Pseudotilfeldige tallgeneratorer
Alternativet til en fysisk enhet er en algoritme. En pseudotilfeldig tallgenerator (PRNG) produserer en sekvens som ser tilfeldig ut, men som er fullstendig bestemt av en startverdi kalt seed. Gir du samme startverdi til samme algoritme, får du nøyaktig samme sekvens hver gang. Det er en svakhet der et resultat må være uforutsigbart og startverdien eller den interne tilstanden kan gjettes eller rekonstrueres, og en styrke der et resultat må være reproduserbart — en simulering eller test kan kjøres på nytt helt identisk. PRNG-er er også raske, rimelige og enkle å implementere, og derfor er de fleste programmer avhengige av dem. Kjente algoritmer inkluderer lineær kongruent generator (LCG), xorshift-generatorene og Mersenne Twister.
Mersenne Twister
Mersenne Twister, utgitt i 1997 av Makoto Matsumoto og Takuji Nishimura, er en av de mest brukte pseudotilfeldige tallgeneratorene og standarden i mange programmeringsspråk. Navnet kommer fra perioden — lengden på sekvensen før den gjentar seg — som i standardvarianten, MT19937, er Mersenne-primtallet 219937 − 1. Den består de fleste statistiske tester for tilfeldighet og egner seg godt til simuleringer. Den ble imidlertid ikke designet for å bevare hemmeligheter: fra 624 påfølgende 32-bits verdier kan hvem som helst rekonstruere den interne tilstanden og forutsi hver verdi som følger, så den må ikke brukes til nøkler, passord eller annet som må forbli uforutsigbart.
Kryptografisk sikre generatorer og entropi
Mange bruksområder trenger begge deler samtidig: farten til en algoritme og uforutsigbarheten til en fysisk kilde. Svaret er en kryptografisk sikker pseudotilfeldig tallgenerator (CSPRNG). Det er fortsatt en PRNG, men bygget slik at det å se en del av verdiene ikke gir noen praktisk mulighet til å forutsi resten, og den tilføres en startverdi, og fornyes jevnlig, fra en kilde med ekte entropi. En startverdi fra en fysisk kilde gjør ikke en vanlig PRNG sikker; algoritmen må være utformet for det. En fysisk kilde som termisk støy eller tidsintervaller for maskinvarehendelser leverer en liten mengde ekte tilfeldighet, og CSPRNG-en lager av den en lang rekke verdier langt raskere. Denne kombinasjonen er hva et operativsystem tilbyr programmene som kjører på det, og det er hva "tilfeldig tallgenerator" i praksis som oftest betyr i dag. Den produserer krypteringsnøkler, sesjonstokener og passord.
Tilfeldige tall i nettleseren
JavaScript gir en nettside to innebygde måter å hente tilfeldige verdier på, og de tilhører ulike klasser. Math.random() er en vanlig PRNG: språkstandarden overlater algoritmen til hver enkelt nettleser og lover ingenting om sikkerhet — greit for en animasjon, uegnet for en trekning noen kan bestride. Den andre er Web Crypto API. Metoden crypto.getRandomValues() returnerer kryptografisk sterke tilfeldige verdier, produsert av en CSPRNG med startverdi hentet fra operativsystemets entropi.
Vår tilfeldige tallgenerator på nett bruker Web Crypto API for hver trekning, og tallene produseres i nettleseren din i stedet for på en server. Samme kilde driver de andre generatorene på dette nettstedet, enten du skal kaste terninger, slå kron eller mynt eller generere et passord.
Fra tilfeldige biter til et tall i ditt intervall
En kryptografisk sikker generator er bare halve jobben for en rettferdig trekning. Den leverer rå biter, og programmet må likevel gjøre dem om til et tall innenfor ditt intervall — og her kan skjevheter snike seg inn. Anta at kilden gir verdiene 0 til 9 med like sjanser, og du trenger et tall fra 0 til 5. Å ta resten etter divisjon med 6 virker naturlig, men 0, 1, 2 og 3 kan da oppstå på to måter hver, og 4 og 5 bare på én måte, slik at hvert av tallene 0 til 3 har 20 % sjanse, og 4 og 5 bare 10 % hver. Én måte å fjerne skjevheten på er å forkaste verdiene som ikke passer og trekke på nytt; veiledningene om tilfeldige tall går i dybden på dette.
Ytterligere to ting overrasker ofte folk. Gjentakelser er normale: når et heltall fra 1 til 10 trekkes uavhengig og hvert tall er like sannsynlig, har tallet som nettopp ble trukket nøyaktig samme sjanse på 1 av 10 til å dukke opp igjen som alle andre. En trekning uten gjentakelser er en annen type trekning, ikke en mer tilfeldig en. Og en rettferdig generator alene gjør ikke hele prosedyren rettferdig: listen over deltakere og antall forsøk betyr like mye, som forklart i veiledningen vår om hvordan velge en tilfeldig konkurransevinner.