Kas yra atsitiktinių skaičių generatorius?
Atsitiktinių skaičių generatorius (RNG) yra sistema, kurianti atsitiktinius arba pseudatsitiktinius skaičius. Ar kitą skaičių iš tiesų įmanoma nuspėti, priklauso nuo generatoriaus tipo. Vieni generatoriai remiasi fizikiniais procesais, kiti skaičius apskaičiuoja pagal algoritmą, o tam tikri algoritmai sukurti taip, kad net ir matęs ankstesnius rezultatus niekas negalėtų atspėti tolesnės reikšmės. Atrodyti atsitiktinai ir būti nenuspėjamam yra dvi skirtingos savybės, ir didžioji šio straipsnio dalis skirta būtent šiam skirtumui paaiškinti.
Aparatiniai atsitiktinių skaičių generatoriai
Aparatinis atsitiktinių skaičių generatorius (HRNG), dar vadinamas tikruoju atsitiktinių skaičių generatoriumi (TRNG), skaičius gauna iš fizikinio proceso. Seniausi iš jų veikia tiesiog mūsų akyse: mestas kauliukas, mesta moneta, ruletės ratas. Nors mechanikos dėsniai juos aprašo iki smulkmenų, gerai pagamintas ratas praktiškai išlieka nenuspėjamas, nes mažiausi kiekvieno sukimo pradžios skirtumai lemia visiškai skirtingus rezultatus.
Šiuolaikiniai aparatiniai generatoriai matuoja mikroskopinius reiškinius: elektroninių grandinių šratinį ir šiluminį triukšmą, atmosferos triukšmą, kvantinius efektus. Tai geri entropijos — išmatuojamo nenuspėjamumo — šaltiniai, tačiau fizinis šaltinis iš prigimties nėra tobulas: jis gali būti šališkas, jo parametrai laikui bėgant gali kisti, be to, jis gali sugesti. Todėl jo kokybę būtina vertinti bei stebėti, o rezultatus prireikus papildomai apdoroti, kaip numato tokie standartai kaip NIST SP 800-90B. Aparatiniai šaltiniai naudojami ten, kur garantija yra svarbiausia — visų pirma kriptografijoje, kur jie tiekia nenuspėjamas pradines reikšmes tokių protokolų kaip perdavimo lygmens saugumo (TLS) šifravimo raktams.
Pseudatsitiktinių skaičių generatoriai
Alternatyva fiziniam įrenginiui yra algoritmas. Pseudatsitiktinių skaičių generatorius (PRNG) sukuria seką, kuri atrodo atsitiktinė, tačiau yra visiškai nulemta pradinės reikšmės (angl. seed). Tam pačiam algoritmui pateikę tą pačią pradinę reikšmę, kaskart gausite identišką seką. Tai yra trūkumas ten, kur rezultatas privalo būti nenuspėjamas, o pradinę reikšmę ar vidinę būseną galima atspėti arba atkurti. Kita vertus, tai privalumas, kai rezultatą reikia tiksliai pakartoti — pavyzdžiui, simuliacijose ar programinės įrangos testuose. PRNG taip pat yra greiti, nebrangūs ir lengvai įgyvendinami, todėl jais remiasi dauguma programų. Tarp gerai žinomų algoritmų yra tiesinis kongruentinis generatorius (LCG), xorshift generatoriai ir Mersenne Twister.
Mersenne Twister
Mersenne Twister, kurį 1997 m. pristatė Makoto Matsumoto ir Takuji Nishimura, yra vienas plačiausiai naudojamų pseudatsitiktinių skaičių generatorių bei numatytasis pasirinkimas daugelyje programavimo kalbų. Jo pavadinimas kilo iš periodo — sekos ilgio iki jai pradedant kartotis, kuris standartinėje modifikacijoje MT19937 yra Merseno pirminis skaičius 219937 − 1. Jis sėkmingai praeina daugumą statistinių atsitiktinumo testų ir gerai tinka simuliacijoms. Vis dėlto jis nebuvo sukurtas paslaptims saugoti: iš 624 nuoseklių 32 bitų išvesties reikšmių bet kas gali atkurti jo vidinę būseną ir numatyti visus vėlesnius skaičius, todėl jo negalima naudoti raktams, slaptažodžiams ar bet kam, kas privalo likti nenuspėjama.
Kriptografiškai saugūs generatoriai ir entropija
Daugeliui sistemų vienu metu reikia abiejų savybių: algoritmo greičio ir fizinio šaltinio nenuspėjamumo. Atsakymas yra kriptografiškai saugus pseudatsitiktinių skaičių generatorius (CSPRNG). Tai vis dar yra PRNG, tačiau suprojektuotas taip, kad net ir žinant dalį jo rezultatų praktiškai neįmanoma nuspėti likusių, be to, jis yra inicijuojamas ir reguliariai papildomas iš tikros entropijos šaltinio. Vien pradinė reikšmė iš fizinio šaltinio nepadaro paprasto PRNG saugaus; pats algoritmas turi būti tam pritaikytas. Fizinis šaltinis, pavyzdžiui, šiluminis triukšmas ar aparatinės įrangos įvykių laikas, suteikia nedidelį kiekį tikro atsitiktinumo, o CSPRNG iš jo daug greičiau išgauna ilgą reikšmių seką. Būtent šį derinį operacinė sistema siūlo joje veikiančioms programoms, ir būtent tai šiandien dažniausiai reiškia terminas „atsitiktinių skaičių generatorius“. Jis generuoja šifravimo raktus, sesijų žetonus ir slaptažodžius.
Atsitiktiniai skaičiai naršyklėje
JavaScript suteikia tinklalapiui du integruotus būdus atsitiktinėms reikšmėms gauti, ir jie priklauso visiškai skirtingoms kategorijoms. Math.random() yra paprastas PRNG: kalbos standartas algoritmo pasirinkimą palieka kiekvienai naršyklei ir nieko negarantuoja dėl saugumo — tai tinka animacijai, bet visiškai netinka traukimui, kurį kas nors galėtų užginčyti. Kitas būdas yra Web Crypto API. Jo metodas crypto.getRandomValues() grąžina kriptografiškai patikimas atsitiktines reikšmes, kurias sukuria CSPRNG, inicijuotas operacinės sistemos entropija.
Mūsų atsitiktinių skaičių generatorius internete kiekvienam traukimui naudoja Web Crypto API, o skaičiai sukuriami jūsų naršyklėje, o ne serveryje. Tas pats patikimas šaltinis naudojamas ir kitiems šios svetainės įrankiams, nesvarbu, ar metate kauliukus, ar metate monetą, ar generuojate slaptažodį.
Nuo atsitiktinių bitų iki skaičiaus jūsų intervale
Kriptografiškai saugus generatorius yra tik pusė sąžiningo traukimo. Jis pateikia neapdorotus bitus, o programa dar turi juos paversti skaičiumi iš jūsų pasirinkto intervalo — ir čia gali atsirasti netolygus tikimybių pasiskirstymas. Tarkime, šaltinis vienodomis galimybėmis pateikia reikšmes nuo 0 iki 9, o jums reikia skaičiaus nuo 0 iki 5. Paimti dalybos iš 6 liekaną atrodo natūralu, tačiau tuomet 0, 1, 2 ir 3 gali iškristi dviem būdais, o 4 ir 5 — tik vienu. Todėl kiekvieno iš skaičių nuo 0 iki 3 tikimybė bus 20 %, o 4 ir 5 — tik po 10 %. Vienas iš būdų šiai paklaidai (angl. modulo bias) pašalinti yra atmesti netelpančias reikšmes ir traukti iš naujo; apie tai išsamiai pasakojama atsitiktinių skaičių generatoriaus medžiagoje.
Žmones dažnai stebina dar du dalykai. Skaičių pasikartojimas yra normalus reiškinys: kai sveikasis skaičius nuo 1 iki 10 traukiamas nepriklausomai ir kiekvienas skaičius turi vienodą tikimybę, ką tik iškritęs skaičius turi lygiai tą pačią 1 iš 10 tikimybę pasirodyti vėl. Traukimas be pasikartojimų yra tiesiog kitokia traukimo taisyklė, o ne didesnis atsitiktinumas. Be to, vien sąžiningas generatorius neužtikrina visos procedūros sąžiningumo: dalyvių sąrašas ir bandymų skaičius yra ne mažiau svarbūs, kaip paaiškinta mūsų straipsnyje, kaip atsitiktinai išrinkti konkurso nugalėtoją.