Mis on juhuslike arvude generaator?
Juhuslike arvude generaator (RNG) on süsteem, mis loob juhuslikke või pseudojuhuslikke arve. See, kas järgmist arvu on tegelikult võimalik ette ennustada, sõltub generaatori tüübist. Mõned generaatorid tuginevad füüsikalistele protsessidele, teised arvutavad väärtusi algoritmiga ja teatud algoritmid on loodud nii, et isegi varasemaid tulemusi näinud inimene ei suuda järgmist ette aimata. Juhuslikuna näimine ja ettearvamatus on kaks eri omadust ning suurem osa sellest artiklist keskendub just sellele erinevusele.
Riistvaralised juhuslike arvude generaatorid
Riistvaraline juhuslike arvude generaator (HRNG), mida nimetatakse ka tõeliseks juhuslike arvude generaatoriks (TRNG), tuletab oma arvud füüsikalisest protsessist. Neist vanimad toimivad otse silme all: mündi viskamine, täringu veeretamine või ruletiratas. Mehaanikaseadused kirjeldavad neist igaüht täielikult, kuid hästi valmistatud ruletiratas on praktikas siiski ettearvamatu, sest vähimadki erinevused pöörlema panemisel viivad täiesti erinevate tulemusteni.
Tänapäevased riistvaralised generaatorid mõõdavad selle asemel mikroskoopilisi nähtusi: haavlilühimüra ja soojusmüra elektroonikalülitustes, atmosfäärimüra või kvantefekte. Need on head entroopia allikad — mõõdetav ettearvamatus —, kuid füüsikaline allikas pole loomu poolest täiuslik: selles võib tekkida nihe, see võib ajas nihkuda ja tõrkuda. Seetõttu tuleb selle kvaliteeti hinnata ja jälgida ning vajaduse korral selle tulemusi edasi töödelda, mida kirjeldavad sellised standardid nagu NIST SP 800-90B. Riistvaralisi allikaid kasutatakse seal, kus tagatis on kõige olulisem — eelkõige krüptograafias, kus need annavad ettearvamatut lähteainet selliste protokollide võtmetele nagu Transport Layer Security (TLS).
Pseudojuhuslike arvude generaatorid
Alternatiiv füüsilisele seadmele on algoritm. Pseudojuhuslike arvude generaator (PRNG) loob jada, mis näib juhuslik, kuid on täielikult määratud algväärtusega, mida nimetatakse seemneks (seed). Kui anda samale algoritmile sama seeme, saab iga kord täpselt sama jada. See on puudus igal pool, kus tulemus peab olema ettearvamatu ning seemet või siseolekut saab ära arvata või taastada; ja see on eelis seal, kus tulemus peab olema korratav — simulatsiooni või testi saab täpselt uuesti käivitada. Samuti on PRNG-d kiired, odavad ja hõlpsasti teostatavad, mistõttu enamik tarkvara toetub just neile. Tuntud algoritmide hulka kuuluvad lineaarne kongruentne generaator (LCG), xorshift-generaatorid ja Mersenne Twister.
Mersenne Twister
Mersenne Twister, mille 1997. aastal avaldasid Makoto Matsumoto ja Takuji Nishimura, on üks enim kasutatavaid pseudojuhuslike arvude generaatoreid ja paljudes programmeerimiskeeltes vaikimisi valik. Selle nimi tuleneb perioodist — jada pikkusest enne kordumist —, mis standardvariandis MT19937 on Mersenne'i algarv 219937 − 1. See läbib enamiku juhuslikkuse statistilisi teste ja sobib hästi simulatsioonideks. Kuid see polnud loodud saladuste hoidmiseks: 624 järjestikuse 32-bitise tulemuse põhjal võib igaüks taastada selle siseoleku ja ennustada kõiki järgnevaid väärtusi, mistõttu seda ei tohi kasutada võtmete, paroolide ega muu ettearvamatuna püsiva teabe jaoks.
Krüptograafiliselt turvalised generaatorid ja entroopia
Paljud rakendused vajavad korraga mõlemat: algoritmi kiirust ja füüsikalise allika ettearvamatust. Lahenduseks on krüptograafiliselt turvaline pseudojuhuslike arvude generaator (CSPRNG). See on samuti PRNG, kuid ehitatud nii, et osa tulemuste nägemine ei anna mingit praktilist võimalust ülejäänut ennustada, ning seda varustatakse ja uuendatakse regulaarselt reaalsest entroopiaallikast pärit seemnega. Füüsikalisest allikast pärit seeme ei muuda tavalist PRNG-d turvaliseks; selleks peab olema spetsiaalselt loodud algoritm ise. Füüsikaline allikas, nagu soojusmüra või riistvarasündmuste ajastus, annab väikese koguse ehtsat juhuslikkust ja CSPRNG teeb sellest palju suurema kiirusega pika väärtuste jada. Just seda kombinatsiooni pakub operatsioonisüsteem selles töötavatele programmidele ja seda mõeldakse tänapäeval praktikas tavaliselt „juhuslike arvude generaatori” all. See toodab krüpteerimisvõtmeid, seansilubasid ja paroole.
Juhuslikud arvud brauseris
JavaScript pakub veebilehele kahte sisseehitatud viisi juhuslike väärtuste saamiseks ja need kuuluvad eri klassidesse. Math.random() on tavaline PRNG: keele standard jätab algoritmi iga brauseri otsustada ega luba midagi turvalisuse kohta — animatsiooni jaoks sobilik, kuid kõlbmatu loosimiseks, mida keegi võiks vaidlustada. Teine on Web Crypto API. Selle meetod crypto.getRandomValues() tagastab krüptograafiliselt turvalisi juhuslikke väärtusi, mille loob operatsioonisüsteemi entroopiaga varustatud CSPRNG.
Meie juhuslike arvude generaator kasutab iga genereerimise jaoks Web Crypto API-t ja arvud luuakse sinu brauseris, mitte serveris. Sama allikas toidab ka teisi selle saidi generaatoreid, olgu sinu sooviks täringuid veeretada, kulli või kirja visata või parooli genereerida.
Juhuslikest bittidest arvuni sinu valitud vahemikus
Krüptograafiliselt turvaline generaator on vaid pool ausast loosimisest. See annab tooreid bitte ja programm peab need ikkagi muutma arvuks sinu valitud vahemikus — ning just siin võib tekkida nihe. Oletame, et allikas annab võrdse tõenäosusega väärtusi vahemikus 0 kuni 9 ja sul on vaja arvu vahemikus 0 kuni 5. Jäägi võtmine pärast jagamist 6-ga tundub loomulik, kuid arvud 0, 1, 2 ja 3 võivad siis tulla kahel viisil ning 4 ja 5 ainult ühel viisil; seega on igal arvul vahemikus 0 kuni 3 tervelt 20% võimalus ning arvudel 4 ja 5 vaid 10%. Üks viis selle nihke eemaldamiseks on sobimatud väärtused kõrvale jätta ja uuesti genereerida; juhuslike arvude generaatori materjalid käsitlevad seda üksikasjalikult.
Inimesi üllatab veel kaks asjaolu. Kordumised on normaalsed: kui täisarv vahemikus 1 kuni 10 loositakse sõltumatult ja iga arv on võrdselt tõenäoline, on äsja loositud arvul täpselt sama 1 võimalus 10-st uuesti tulla kui mis tahes muul arvul. Kordusteta loosimine on lihtsalt teist tüüpi loosimine, mitte kuidagi juhuslikum. Lisaks ei tee aus generaator üksi tervet protseduuri ausaks: osalejate nimekiri ja katsete arv loevad sama palju, nagu selgitab meie artikkel sellest, kuidas valida loosimise võitjat juhuslikult.