Što je generator slučajnih brojeva?
Generator slučajnih brojeva (RNG) sustav je koji stvara slučajne ili pseudoslučajne brojeve. Može li se sljedeći broj doista predvidjeti, ovisi o vrsti generatora. Neki se generatori oslanjaju na fizički proces, neki svoje brojeve izračunavaju pomoću algoritma, a pojedini su algoritmi konstruirani tako da čak ni netko tko je vidio njihove dosadašnje rezultate ne može predvidjeti što slijedi. Izgledati slučajno i biti nepredvidiv dva su različita svojstva, i najveći dio ovog članka bavi se upravo tom razlikom.
Hardverski generatori slučajnih brojeva
Hardverski generator slučajnih brojeva (HRNG), koji se naziva i generator pravih slučajnih brojeva (TRNG), svoje vrijednosti izvodi iz fizičkog procesa. Najstariji djeluju pred našim očima: bačeni novčić, bačena kockica, kotač ruleta. Zakoni mehanike u potpunosti opisuju svaki od njih, no dobro izrađen kotač u praksi je ipak nepredvidiv jer se sićušne razlike na početku svake vrtnje pretvaraju u potpuno drukčije ishode.
Moderni hardverski generatori umjesto toga mjere mikroskopske pojave: sačmasti i toplinski šum u elektroničkim sklopovima, atmosferski šum, kvantne učinke. To su dobri izvori entropije — nepredvidivosti koja se može mjeriti — no fizički izvor po svojoj prirodi nije savršen: može biti pristran, može odstupati tijekom vremena i može zakazati. Zbog toga se njegova kvaliteta mora procjenjivati i nadzirati, a njegovi rezultati po potrebi dodatno obrađivati, što opisuju standardi poput NIST SP 800-90B. Hardverski izvori koriste se tamo gdje je jamstvo najvažnije — prije svega u kriptografiji, gdje pružaju nepredvidiv početni materijal za ključeve iza protokola kao što je Transport Layer Security (TLS).
Pseudoslučajni generatori brojeva
Alternativa fizičkom uređaju jest algoritam. Generator pseudoslučajnih brojeva (PRNG) proizvodi niz koji izgleda slučajno, ali je u potpunosti određen početnom vrijednošću koja se naziva sjeme (seed). Dajte isto sjeme istom algoritmu i svaki put dobit ćete potpuno isti niz. To je slabost gdje god rezultat mora biti nepredvidiv, a sjeme ili unutarnje stanje može se pogoditi ili rekonstruirati; s druge strane, to je velika prednost gdje god rezultat mora biti ponovljiv — simulacija ili test mogu se ponovno pokrenuti na identičan način. PRNG-ovi su također brzi, jeftini i jednostavni za implementaciju, zbog čega se većina softvera oslanja na njih. Među poznatim algoritmima nalaze se linearni kongruentni generator (LCG), xorshift generatori i Mersenne Twister.
Mersenne Twister
Mersenne Twister, koji su 1997. objavili Makoto Matsumoto i Takuji Nishimura, jedan je od najčešće korištenih pseudoslučajnih generatora i standardni izbor u mnogim programskim jezicima. Ime je dobio po svojem periodu — duljini niza prije nego što se počne ponavljati — a to je u standardnoj varijanti, MT19937, Mersenneov prost broj 219937 − 1. Prolazi većinu statističkih testova slučajnosti i odlično odgovara simulacijama. Međutim, nije dizajniran za čuvanje tajni: iz 624 uzastopna 32-bitna izlazna rezultata svatko može rekonstruirati njegovo unutarnje stanje i predvidjeti svaku vrijednost koja slijedi, pa se nipošto ne smije koristiti za ključeve, lozinke ili bilo što drugo što mora ostati nepredvidivo.
Kriptografski sigurni generatori i entropija
Mnoge primjene zahtijevaju oboje istovremeno: brzinu algoritma i nepredvidivost fizičkog izvora. Odgovor je kriptografski siguran generator pseudoslučajnih brojeva (CSPRNG). To je i dalje PRNG, ali konstruiran tako da uvid u dio njegovih rezultata ne pruža praktičan način za predviđanje ostatka, a inicijalizira se i redovito osvježava iz izvora stvarne entropije. Sjeme iz fizičkog izvora ne čini običan PRNG sigurnim; algoritam mora biti namjenski dizajniran za to. Fizički izvor poput toplinskog šuma ili preciznog vremena hardverskih događaja osigurava malu količinu stvarne slučajnosti, a CSPRNG iz nje znatno brže izvodi dug niz vrijednosti. Tu kombinaciju operacijski sustav nudi programima koji se na njemu izvode i to je ono što se danas u praksi obično podrazumijeva pod pojmom „generator slučajnih brojeva”. On proizvodi enkripcijske ključeve, tokene sesija i lozinke.
Slučajni brojevi u pregledniku
JavaScript pruža web-stranici dva ugrađena načina za dobivanje slučajnih vrijednosti, i oni pripadaju različitim kategorijama. Math.random() običan je PRNG: jezični standard prepušta algoritam svakom pojedinom pregledniku i ne jamči nikakvu sigurnost — sasvim dovoljno za animaciju, neprikladno za izvlačenje koje bi netko mogao osporiti. Drugi način jest Web Crypto API. Njegova metoda crypto.getRandomValues() vraća kriptografski sigurne slučajne vrijednosti, koje stvara CSPRNG inicijaliziran entropijom operacijskog sustava.
Naš online generator slučajnih brojeva koristi Web Crypto API za svako izvlačenje, a brojevi se generiraju u vašem pregledniku, a ne na poslužitelju. Isti izvor pokreće i druge generatore na ovim stranicama, bilo da želite baciti kockice, baciti novčić ili generirati lozinku.
Od slučajnih bitova do broja u vašem rasponu
Kriptografski siguran generator samo je pola poštenog izvlačenja. On isporučuje sirove bitove, a program ih još mora pretvoriti u broj unutar vašeg raspona — i upravo se tu može uvući pristranost. Pretpostavimo da izvor daje vrijednosti od 0 do 9 s jednakim izgledima, a vama je potreban broj od 0 do 5. Uzimanje ostatka pri dijeljenju sa 6 čini se prirodnim, ali 0, 1, 2 i 3 tada se mogu pojaviti na dva načina, a 4 i 5 samo na jedan. Tako svaki od brojeva od 0 do 3 ima 20 % šanse, a 4 i 5 samo po 10 %. Jedan način uklanjanja pristranosti jest odbacivanje vrijednosti koje ne odgovaraju rasponu i ponovno izvlačenje; naši članci o generatoru slučajnih brojeva to detaljno objašnjavaju.
Dvije stvari često iznenade ljude. Ponavljanja su sasvim normalna: kada se cijeli broj od 1 do 10 izvlači neovisno i svaki broj ima jednaku vjerojatnost, upravo izvučeni broj ima potpuno istu šansu 1 od 10 da se ponovno pojavi kao i bilo koji drugi. Izvlačenje bez ponavljanja drukčija je vrsta izvlačenja, a ne slučajnije izvlačenje. Nadalje, sam pošteni generator ne čini cjelokupni postupak poštenim: popis sudionika i broj pokušaja jednako su važni, kao što objašnjava naš članak o tome kako nasumično izabrati pobjednika nagradne igre.