Šta je generator slučajnih brojeva?
Generator slučajnih brojeva (RNG) je sistem koji proizvodi nasumične ili pseudoslučajne brojeve. Da li se sljedeći broj zapravo može predvidjeti zavisi od vrste generatora. Neki generatori se oslanjaju na fizički proces, neki računaju brojeve pomoću algoritma, a neki algoritmi su napravljeni tako da čak ni neko ko je vidio njihove dosadašnje rezultate ne može predvidjeti šta slijedi. Izgledati nasumično i biti nepredvidiv dva su različita svojstva, a već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), dobija svoje brojeve iz fizičkog procesa. Najstariji rade pred našim očima: bačeni novčić, bačena kockica, točak ruleta. Mehanika u potpunosti opisuje svaki od njih, ali dobro napravljen točak u praksi je i dalje nepredvidiv, jer male razlike u načinu pokretanja svakog okretanja prerastaju u potpuno različite ishode.
Moderni hardverski generatori umjesto toga mjere mikroskopske pojave: sačmeni i termički šum u električnim krugovima, atmosferski šum, kvantne efekte. To su dobri izvori entropije — nepredvidivosti koja se može izmjeriti — ali fizički izvor po svojoj prirodi nije savršen: može biti pristran, može odstupati tokom vremena i može zakazati, pa se njegov kvalitet mora procjenjivati i pratiti, a njegovi rezultati po potrebi dodatno obrađivati, što opisuju standardi kao što je NIST SP 800-90B. Hardverski izvori se koriste tamo gdje je garancija najvažnija — prije svega u kriptografiji, gdje obezbjeđuju nepredvidiv početni materijal za ključeve koji stoje iza protokola kao što je Transport Layer Security (TLS).
Generatori pseudoslučajnih brojeva
Alternativa fizičkom uređaju je algoritam. Generator pseudoslučajnih brojeva (PRNG) proizvodi niz koji izgleda nasumično, ali je potpuno određen početnom vrijednošću koja se naziva seed (početna vrijednost). Dajte isti seed istom algoritmu i svaki put ćete dobiti isti niz. To je slabost gdje god rezultat mora biti nepredvidiv, a seed ili unutrašnje stanje se mogu pogoditi ili rekonstruisati, i prednost gdje god rezultat mora biti ponovljiv — simulacija ili test se mogu pokrenuti ponovo na potpuno isti način. PRNG-ovi su također brzi, jeftini i jednostavni za implementaciju, zbog čega se većina softvera oslanja na njih. Poznati algoritmi uključuju linearni kongruentni generator (LCG), xorshift generatore i Mersenne Twister.
Mersenne Twister
Mersenne Twister, koji su 1997. godine objavili Makoto Matsumoto i Takuji Nishimura, jedan je od najčešće korištenih generatora pseudoslučajnih brojeva i podrazumijevani izbor u mnogim programskim jezicima. Njegovo ime potiče od njegovog perioda — dužine niza prije nego što počne da se ponavlja — koji u standardnoj varijanti, MT19937, iznosi Mersenneov prosti broj 219937 − 1. Prolazi većinu statističkih testova nasumičnosti i odlično odgovara simulacijama. Međutim, nije dizajniran za čuvanje tajni: iz 624 uzastopna 32-bitna izlazna rezultata svako može rekonstruisati njegovo unutrašnje stanje i predvidjeti svaku vrijednost koja slijedi, tako da se ne smije koristiti za ključeve, lozinke ili bilo šta drugo što mora ostati nepredvidivo.
Kriptografski sigurni generatori i entropija
Mnogim primjenama potrebne su obje stvari odjednom: brzina algoritma i nepredvidivost fizičkog izvora. Odgovor je kriptografski siguran generator pseudoslučajnih brojeva (CSPRNG). To je i dalje PRNG, ali napravljen tako da uvid u dio njegovih rezultata ne pruža praktičan način da se predvidi ostatak, a inicijalizuje se i redovno obnavlja iz izvora prave entropije. Početna vrijednost iz fizičkog izvora ne čini običan PRNG sigurnim; sam algoritam mora biti dizajniran za to. Fizički izvor, kao što je termički šum ili vrijeme hardverskih događaja, pruža malu količinu prave nasumičnosti, a CSPRNG iz nje znatno brže izvodi dug niz vrijednosti. Ovu kombinaciju operativni sistem nudi programima koji se na njemu izvršavaju, i to je ono što "generator slučajnih brojeva" danas obično znači u praksi. On proizvodi ključeve za enkripciju, tokene sesija i lozinke.
Nasumični brojevi u pretraživaču
JavaScript pruža web stranici dva ugrađena načina za dobijanje nasumičnih vrijednosti, i oni pripadaju različitim klasama. Math.random() je običan PRNG: standard jezika prepušta algoritam svakom pretraživaču i ne garantuje nikakvu sigurnost — sasvim dovoljno za animaciju, neprikladno za izvlačenje koje bi neko mogao osporiti. Drugi je Web Crypto API. Njegova metoda crypto.getRandomValues() vraća kriptografski sigurne nasumične vrijednosti, koje proizvodi CSPRNG pokrenut entropijom operativnog sistema.
Naš generator slučajnih brojeva na mreži koristi Web Crypto API za svako izvlačenje, a brojevi se proizvode u vašem pretraživaču, a ne na serveru. Isti izvor pokreće i ostale generatore na ovoj stranici, bilo da bacate kockice, bacate novčić ili generišete lozinku.
Od nasumičnih bitova do broja u vašem rasponu
Kriptografski siguran generator je samo polovina poštenog izvlačenja. On isporučuje sirove bitove, a program ih još mora pretvoriti u broj u vašem rasponu — i tu se može uvući pristranost. Pretpostavimo da izvor daje vrijednosti od 0 do 9 s jednakim šansama, a vama je potreban broj od 0 do 5. Uzimanje ostatka pri dijeljenju sa 6 izgleda prirodno, ali 0, 1, 2 i 3 se tada mogu pojaviti na dva načina, a 4 i 5 na samo jedan način, pa svaki od brojeva od 0 do 3 ima šansu od 20%, a 4 i 5 samo po 10%. Jedan od načina za uklanjanje pristranosti jeste odbacivanje vrijednosti koje ne odgovaraju i ponovno izvlačenje; naši materijali o generatoru slučajnih brojeva se time detaljno bave.
Još dvije stvari često iznenade ljude. Ponavljanja su normalna: kada se cijeli broj od 1 do 10 izvlači nezavisno i svaki broj je jednako vjerovatan, upravo izvučeni broj ima istu šansu 1 od 10 da se ponovo pojavi kao i bilo koji drugi. Izvlačenje bez ponavljanja je drugačija vrsta izvlačenja, a ne nasumičnija. Također, pošten generator sam po sebi ne čini cijeli postupak poštenim: lista učesnika i broj pokušaja jednako su važni, kao što objašnjava naš članak o tome kako izabrati nasumičnog pobjednika nagradne igre.