Kaj je generator naključnih števil?
Generator naključnih števil (RNG) je sistem, ki ustvarja naključna ali psevdonaključna števila. Ali je naslednje število dejansko mogoče predvideti, je odvisno od vrste generatorja. Nekateri generatorji izhajajo iz fizikalnega procesa, drugi računajo števila z algoritmom, nekateri algoritmi pa so zasnovani tako, da niti nekdo, ki je videl njihove dosedanje rezultate, ne more predvideti, kaj sledi. Biti videti naključen in biti nepredvidljiv sta različni lastnosti, in večina tega članka se posveča prav tej razliki.
Strojni generatorji naključnih števil
Strojni generator naključnih števil (HRNG), imenovan tudi pravi generator naključnih števil (TRNG), svoja števila črpa iz fizikalnega procesa. Najstarejši delujejo pred našimi očmi: vržen kovanec, vržena kocka ali ruletno kolesce. Mehanika vsakega od njih popolnoma opisuje, vendar je dobro izdelano kolesce v praksi še vedno nepredvidljivo, saj majhne razlike v začetku vsakega vrtenja privedejo do povsem različnih izidov.
Sodobni strojni generatorji namesto tega merijo mikroskopske pojave: zrnati in toplotni šum v elektronskih vezjih, atmosferski šum, kvantne učinke. To so dobri viri entropije — merljive nepredvidljivosti —, toda fizikalni vir po svoji naravi ni popoln: lahko ima neenake možnosti, se sčasoma spreminja in lahko odpove, zato je treba njegovo kakovost ocenjevati in nadzorovati ter njegove rezultate po potrebi dodatno obdelati, kar opisujejo standardi, kot je NIST SP 800-90B. Strojni viri se uporabljajo tam, kjer je jamstvo najpomembnejše — predvsem v kriptografiji, kjer zagotavljajo nepredvidljiv začetni material za ključe v protokolih, kot je Transport Layer Security (TLS).
Generatorji psevdonaključnih števil
Alternativa fizikalni napravi je algoritem. Generator psevdonaključnih števil (PRNG) proizvaja zaporedje, ki je videti naključno, vendar ga popolnoma določa začetna vrednost (seed). Če istemu algoritmu podate isto začetno vrednost, boste vsakič dobili enako zaporedje. To je slabost povsod, kjer mora biti rezultat nepredvidljiv ter je začetno vrednost ali notranje stanje mogoče uganiti ali rekonstruirati, in prednost povsod, kjer mora biti rezultat ponovljiv — simulacijo ali preizkus je mogoče natančno ponoviti. Generatorji PRNG so tudi hitri, poceni in enostavni za implementacijo, zato se nanje zanaša večina programske opreme. Med znane družine spadajo linearni kongruenčni generator (LCG), generatorji xorshift in Mersenne Twister.
Mersenne Twister
Mersenne Twister, ki sta ga leta 1997 objavila Makoto Matsumoto in Takuji Nishimura, je eden najpogosteje uporabljenih generatorjev psevdonaključnih števil in privzeta izbira v številnih programskih jezikih. Njegovo ime izhaja iz njegove periode — dolžine zaporedja, preden se začne ponavljati —, ki pri standardni različici MT19937 znaša Mersennovo praštevilo 219937 − 1. Prestane večino statističnih testov naključnosti in je dobro primeren za simulacije. Vendar ni bil zasnovan za varovanje skrivnosti: iz 624 zaporednih 32-bitnih rezultatov lahko kdorkoli rekonstruira njegovo notranje stanje in napove vsako naslednjo vrednost, zato se ne sme uporabljati za ključe, gesla ali karkoli drugega, kar mora ostati nepredvidljivo.
Kriptografsko varni generatorji in entropija
Številne aplikacije potrebujejo oboje hkrati: hitrost algoritma in nepredvidljivost fizikalnega vira. Odgovor je kriptografsko varen generator psevdonaključnih števil (CSPRNG). Še vedno gre za PRNG, vendar zgrajen tako, da vpogled v del njegovih rezultatov ne ponuja praktičnega načina za napovedovanje preostanka, njegova začetna vrednost pa se pridobiva in redno obnavlja iz vira prave entropije. Začetna vrednost iz fizikalnega vira navadnega PRNG ne naredi varnega; za to mora biti zasnovan algoritem sam. Fizikalni vir, kot je toplotni šum ali časovni razmik med dogodki strojne opreme, zagotavlja majhno količino prave naključnosti, CSPRNG pa iz nje veliko hitreje pridobi dolgo zaporedje vrednosti. To kombinacijo operacijski sistem ponuja programom, ki se izvajajo v njem, in prav to danes v praksi običajno pomeni »generator naključnih števil«. Ustvarja šifrirne ključe, sejne žetone in gesla.
Naključna števila v brskalniku
JavaScript spletni strani ponuja dva vgrajena načina za pridobivanje naključnih vrednosti, ki spadata v različna razreda. Math.random() je običajen PRNG: jezikovni standard prepušča izbiro algoritma posameznemu brskalniku in ne zagotavlja varnosti — primeren je za animacijo, neprimeren pa za žrebanje, ki bi ga kdo lahko izpodbijal. Druga možnost je Web Crypto API. Njegova metoda crypto.getRandomValues() vrača kriptografsko močne naključne vrednosti, ki jih ustvarja CSPRNG, napajan z entropijo operacijskega sistema.
Naš spletni generator naključnih števil pri vsakem žrebanju uporablja Web Crypto API, števila pa se ustvarjajo v vašem brskalniku in ne na strežniku. Isti vir poganja tudi druge generatorje na tej spletni strani, ne glede na to, ali mečete kocke, mečete kovanec ali ustvarjate geslo.
Od naključnih bitov do števila v vašem razponu
Kriptografsko varen generator je le polovica poštenega žrebanja. Zagotavlja surove bite, program pa jih mora pretvoriti v število v vašem razponu — in tu se lahko prikrade pristranskost. Predpostavimo, da vir ponuja vrednosti od 0 do 9 z enakimi možnostmi, vi pa potrebujete število od 0 do 5. Uporaba ostanka pri deljenju s 6 se zdi samoumevna, toda števila 0, 1, 2 in 3 se lahko pojavijo na dva načina, 4 in 5 pa le na en način, zato ima vsako od števil od 0 do 3 20-odstotno možnost, 4 in 5 pa le 10-odstotno možnost. Eden od načinov za odpravo pristranskosti (modulo bias) je zavrženje vrednosti, ki ne ustrezajo, in ponovni žreb; to podrobno pojasnjujejo naša gradiva o naključnih številih.
Dve dodatni stvari ljudi pogosto presenetita. Ponavljanje je običajno: ko se celo število od 1 do 10 žreba neodvisno in je vsako število enako verjetno, ima pravkar izžrebano število enako možnost 1 proti 10, da bo izžrebano znova, kot katerokoli drugo. Žrebanje brez ponavljanja je drugačna vrsta izbire, ne bolj naključna. Sam pošten generator pa še ne zagotavlja poštenosti celotnega postopka: seznam udeležencev in število poskusov sta enako pomembna, kot pojasnjuje naš članek o tem, kako izbrati zmagovalca nagradne igre.