Kaip veikia CSPRNG atsitiktinių skaičių ir statistikos variklis
Tikrai nenuspėjamų skaičių generavimas deterministiniame silicio mikroprocesoriuje yra vienas pamatinių šiuolaikinės kriptografijos, Monte Karlo fizikinių simuliacijų, klinikinių tyrimų randomizavimo ir sąžiningų loterijų iššūkių. Dauguma paprastų internetinių atsitiktinių skaičių generatorių naudoja standartinę JavaScript funkciją Math.random() – greitą, tačiau deterministinį pseudoatsitiktinių skaičių generatorių (PRNG), kuris netinka saugumui, burtų traukimui ar statistiniam auditui, nes jo vidinę būseną galima atkurti vos iš kelių išvesties reikšmių.
Mūsų darbo stotis įprastus pseudoatsitiktinius algoritmus pakeičia kelių skirstinių kriptografiškai saugiu pseudoatsitiktinių skaičių generatoriumi (CSPRNG), tiesiogiai sujungtu su jūsų operacinės sistemos aparatiniu entropijos šaltiniu per window.crypto.getRandomValues():
- Nešališki sveikieji ir didelio tikslumo dešimtainiai skaičiai: Pasirinkite bet kurį rėžį [Min, Max] ir vienu ypu sugeneruokite iki
1 000 skaičių– sveikaisiais skaičiais (ℤ) arba slankiojo kablelio dešimtainiais skaičiais (2, 4 arba 6 skaitmenų po kablelio tikslumu), sukonstruotais iš 53 bitų IEEE 754 mantisos. - Nepriklausomi traukimai prieš unikalų loterijos / burtų režimą: Perjunkite tarp ėmimo grąžinant (nepriklausomi kauliuko metimai, kai tie patys skaičiai gali pasikartoti natūraliai) ir ėmimo negrąžinant (unikalus loterijos režimas, garantuojantis nulį pasikartojimų „6 iš 49“, „Eurojackpot 5/50“ ar konkursų laimėtojų traukimui).
- Realaus laiko statistinė ir Šenono (Shannon) entropijos telemetrija: Kiekvieno traukimo metu automatiškai apskaičiuojama imties suma (Σ), aritmetinis vidurkis (µ) ir jo palyginimas su teorine matematine viltimi E[X] = (Min+Max)/2, mediana (Q2), lyginių/nelyginių santykis, standartinis nuokrypis (σ) bei bendra Šenono entropija bitais (H = N log2(|Ω|)).
Kodėl naivi liekanos aritmetika (rand() % N) sukuria modulio paklaidą
Net ir tada, kai programuotojas naudoja kriptografinį 32 bitų beženklį sveikąjį skaičių R ∈ [0, 232-1], jo suspaudimas į vartotojo pasirinktą rėžį, kurio plotis K = Max - Min + 1, naudojant paprastą dalybos liekanos operatorių (min + (R % K)), įveda sisteminę matematinę klaidą, vadinamą modulio paklaida (Modulo Bias).
32 bitų beženklis sveikasis skaičius turi lygiai 232 = 4 294 967 296 galimas būsenas. Jei jūsų pasirinkto intervalo plotis K nėra tikslus dvejeto laipsnis (2, 4, 8, 16, …), skaičius 232 nesidalija iš K be liekanos. Įsivaizduokime paprastą pavyzdį su mažu 3 bitų generatoriumi, kuris grąžina skaičius nuo 0 iki 7 (8 būsenos), kai norime išrinkti vieną iš K = 3 reikšmių ($0, 1, 2$):
0 % 3 = 0,3 % 3 = 0,6 % 3 = 0→ Rezultatą 0 duoda 3 būsenos (37,5% tikimybė).1 % 3 = 1,4 % 3 = 1,7 % 3 = 1→ Rezultatą 1 duoda 3 būsenos (37,5% tikimybė).2 % 3 = 2,5 % 3 = 2→ Rezultatą 2 duoda tik 2 būsenos (25,0% tikimybė).
Kadangi 8 mod 3 = 2, mažesnės reikšmės (0 ir 1) gauna papildomą atvaizdavimą iš nepilno paskutinio ciklo! Norėdamas visiškai eliminuoti modulio paklaidą (0,0000% iškraipymo), mūsų variklis taiko griežtą atmetimo metodą (Rejection Sampling):
// Nešališkas CSPRNG Rejection Sampling rėžyje [min, max]:
const range = max - min + 1;
const maxUnbiased = Math.floor(0x100000000 / range) * range;
let r;
do {
r = crypto.getRandomValues(new Uint32Array(1))[0];
} while (r >= maxUnbiased); // Atmetame nepilną viršutinę liekanos zoną!
return min + (r % range);
Apskaičiavus didžiausią K kartotinį, telpantį į 232, ir atmetus bet kurį 32 bitų skaičių, patenkantį į siaurą viršutinę liekanos uodegą [M, 232-1], kiekvienas sveikasis skaičius intervale [Min, Max] turi absoliučiai identišką matematinę tikimybę P(x) = 1/K.
Nuo Johno von Neumanno 1946 m. vidurinio kvadrato iki aparatinio CSPRNG
1946 m., dirbdamas su termobranduolinių neutronų pernašos simuliacijomis (Monte Karlo metodu) pirmajame elektroniniame kompiuteryje ENIAC Los Alamose, matematikas Johnas von Neumannas pasiūlė vidurinio kvadrato metodą (Middle-Square Method): paimamas 4 skaitmenų skaičius, pakeliamas kvadratu (gaunamas 8 skaitmenų skaičius) ir jo viduriniai 4 skaitmenys paimami kaip kitas atsitiktinis skaičius. Von Neumannas tuomet garsiai pajuokavo: „Kiekvienas, kuris svarsto aritmetinius atsitiktinių skaičių gavimo metodus, žinoma, yra nuodėmės būsenoje.“ Jis puikiai suprato, kad deterministinės formulės greitai įkrenta į trumpus pasikartojančius ciklus (pavyzdžiui, pradėjus nuo 3792, seka iškart užsiciklina).
Vėlesniais dešimtmečiais išplito tiesinis kongruentinis generatorius (LCG) Xn+1 = (aXn + c) mod m, tačiau 1968 m. George'as Marsaglia įrodė, kad LCG pasižymi stipria serijine koreliacija – atidėjus taškų trejetus (Xn, Xn+1, Xn+2) trimatėje erdvėje, visi jie išsirikiuoja į nedidelį skaičių lygiagrečių plokštumų. Šiuolaikinės naršyklės Math.random() atnaujino į Xorshift128+ algoritmą, kuris išlaiko bazinius statistinius testus, bet nėra kriptografinis: užfiksavus vos tris iš eilės einančius skaičius, su SMT sprendikliu (pvz., „Microsoft Z3“) galima tiksliai apskaičiuoti 128 bitų vidinius registrus ir nuspėti visus būsimus traukimus.
Priešingai, mūsų generatorius kreipiasi į operacinės sistemos branduolio CSPRNG (/dev/urandom „ChaCha20“ srauto šifrą Linux/macOS/Android sistemose, BCryptGenRandom Windows aplinkoje ir „Secure Enclave TRNG“ iOS įrenginiuose), kuris nuolat renka fizikinę Šenono entropiją iš procesoriaus silicio šiluminio triukšmo (RDRAND / RDSEED žiedinių osciliatorių), disko įvesties/išvesties nanosekundinių pertraukimų ir aparatinių įvykių asimetrijos.
Box–Muller transformacija: Gauso varpo kreivės skaičių generavimas
Nors loterijoms ir lošimo kauliukams reikalingas plokščias tolygusis skirstinys (Uniform Distribution), kuriame kiekvienas skaičius nuo 1 iki 100 yra vienodai tikėtinas, gamtiniai, biologiniai ir ekonominiai reiškiniai – tokie kaip žmonių ūgis, IQ balai, matavimo paklaidos, finansinių aktyvų grąža ir molekulių šiluminis greitis – paklūsta Gauso normaliajam skirstiniui N(µ, σ2), kur reikšmės telkiasi aplink centrinį vidurkį µ ir simetriškai retėja link kraštų.
Kai „Tikimybių skirstinio“ laukelyje pasirenkate Gauso normalųjį (Box–Muller varpas), mūsų variklis pritaiko tikslią analitinę transformaciją, kurią 1958 m. paskelbė George'as Boxas ir Mervinas Mulleris. Paėmęs dvi nepriklausomas tolygiąsias CSPRNG reikšmes U1, U2 ∈ (0, 1), algoritmas sintetina standartinį normalųjį dydį Z0 ∼ N(0, 1):
Z_0 = Math.sqrt(-2.0 * Math.log(U_1)) * Math.cos(2.0 * Math.PI * U_2);
Gautas dydis Z0 tuomet masteliuojamas į jūsų pasirinktą [Min, Max] langą, centruojant vidurkį ties µ = (Min + Max) / 2 ir nustatant standartinį nuokrypį σ = (Max - Min) / 6 (kad intervalas ± 3σ apimtų 99,73% jūsų rėžio pagal empirinę 68–95–99,7 taisyklę).