Kas ir nejaušu skaitļu ģenerators?
Nejaušu skaitļu ģenerators (RNG) ir sistēma, kas rada nejaušus vai pseidonejaušus skaitļus. Vai nākamo skaitli patiešām ir iespējams paredzēt, ir atkarīgs no ģeneratora veida. Vieni ģeneratori balstās fizikālos procesos, citi skaitļus aprēķina ar algoritmu, un daži algoritmi ir veidoti tā, lai pat tie, kuri redzējuši iepriekšējos rezultātus, nespētu paredzēt nākamo vērtību. Izskatīties nejaušam un būt neparedzamam ir divas dažādas īpašības, un lielākā daļa šī raksta ir veltīta tieši šai atšķirībai.
Aparatūras nejaušo skaitļu ģeneratori
Aparatūras nejaušo skaitļu ģenerators (HRNG), ko sauc arī par īsto nejaušo skaitļu ģeneratoru (TRNG), iegūst skaitļus no fizikāla procesa. Senākie no tiem darbojas mūsu acu priekšā: mesta monēta, mests kauliņš, ruletes rats. Lai gan mehānikas likumi katru no tiem apraksta pilnībā, labi izgatavots rats praksē joprojām ir neparedzams, jo niecīgas atšķirības katra grieziena sākumā pārtop pilnīgi atšķirīgos iznākumos.
Mūsdienu aparatūras ģeneratori tā vietā mēra mikroskopiskas parādības: elektronisko shēmu skrošu un termisko troksni, atmosfēras troksni, kvantu efektus. Tie ir labi entropijas — izmērāmas neparedzamības — avoti, taču fiziskais avots pēc savas būtības nav ideāls: tas var būt nobīdīts, tā parametri laika gaitā var mainīties, un tas var sabojāties. Tāpēc tā kvalitāte ir jānovērtē un nepārtraukti jāuzrauga, un rezultāti vajadzības gadījumā jāapstrādā tālāk, kā aprakstīts tādos standartos kā NIST SP 800-90B. Aparatūras avotus izmanto tur, kur garantijai ir vislielākā nozīme — galvenokārt kriptogrāfijā, kur tie nodrošina neparedzamu izejmateriālu šifrēšanas atslēgām, kas ir tādu protokolu pamatā kā transporta slāņa drošība (TLS).
Pseidonejaušo skaitļu ģeneratori
Alternatīva fiziskai ierīcei ir algoritms. Pseidonejaušo skaitļu ģenerators (PRNG) rada virkni, kas izskatās nejauša, bet to pilnībā nosaka sākotnējā vērtība, ko sauc par sēklu (seed). Ievadiet to pašu sēklu tajā pašā algoritmā, un jūs katru reizi iegūsiet identisku virkni. Tas ir trūkums visur, kur rezultātam jābūt neparedzamam un sēklu vai iekšējo stāvokli var uzminēt vai rekonstruēt, un priekšrocība visur, kur rezultātam jābūt atkārtojamam — simulāciju vai testu var palaist vēlreiz precīzi tādā pašā veidā. PRNG ir arī ātri, lēti un viegli ieviešami, tāpēc lielākā daļa programmatūras paļaujas tieši uz tiem. Labi zināmi algoritmi ir lineārais kongruentais ģenerators (LCG), xorshift ģeneratori un Mersenne Twister.
Mersenne Twister
Mersenne Twister, ko 1997. gadā publicēja Makoto Matsumoto un Takuji Nishimura, ir viens no visplašāk izmantotajiem pseidonejaušo skaitļu ģeneratoriem un noklusējuma izvēle daudzās programmēšanas valodās. Tā nosaukums cēlies no perioda — virknes garuma pirms tās atkārtošanās —, kas standarta variantā MT19937 ir Mersena pirmskaitlis 219937 − 1. Tas iztur lielāko daļu statistisko nejaušības testu un ir labi piemērots simulācijām. Tomēr tas netika izstrādāts noslēpumu glabāšanai: no 624 secīgām 32 bitu vērtībām ikviens var rekonstruēt tā iekšējo stāvokli un paredzēt katru nākamo skaitli, tāpēc to nedrīkst izmantot atslēgām, parolēm vai jebkam citam, kam jāpaliek neparedzamam.
Kriptogrāfiski droši ģeneratori un entropija
Daudzām sistēmām vienlaikus ir vajadzīgas abas lietas: algoritma ātrums un fiziskā avota neparedzamība. Risinājums ir kriptogrāfiski drošs pseidonejaušo skaitļu ģenerators (CSPRNG). Tas joprojām ir PRNG, taču veidots tā, lai pat daļas rezultātu redzēšana nedotu praktisku iespēju paredzēt pārējo, un tas tiek inicializēts un regulāri papildināts no reālas entropijas avota. Sēkla no fiziska avota nepadara parastu PRNG drošu; pašam algoritmam jābūt tam pielāgotam. Fizisks avots, piemēram, termiskais troksnis vai aparatūras notikumu laiks, nodrošina nelielu daudzumu patiesas nejaušības, un CSPRNG no tā daudz ātrāk iegūst garu vērtību virkni. Šo kombināciju operētājsistēma piedāvā tajā strādājošajām programmām, un tieši to mūsdienās praksē parasti saprot ar jēdzienu „nejaušo skaitļu ģenerators“. Tas ģenerē šifrēšanas atslēgas, sesiju žetonus un paroles.
Nejauši skaitļi pārlūkprogrammā
JavaScript tīmekļa lapai nodrošina divus iebūvētus veidus, kā iegūt nejaušas vērtības, un tie pieder pilnīgi atšķirīgām kategorijām. Math.random() ir parasts PRNG: valodas standarts algoritma izvēli atstāj katras pārlūkprogrammas ziņā un neko nesola par drošību — tas ir piemērots animācijai, bet neder izlozei, ko kāds varētu apstrīdēt. Otrs veids ir Web Crypto API. Tā metode crypto.getRandomValues() atgriež kriptogrāfiski spēcīgas nejaušas vērtības, ko rada CSPRNG, kas inicializēts ar operētājsistēmas entropiju.
Mūsu nejaušu skaitļu ģenerators tiešsaistē katrai izlozei izmanto Web Crypto API, un skaitļi tiek ģenerēti jūsu pārlūkprogrammā, nevis serverī. Tas pats uzticamais avots darbina arī citus šīs vietnes rīkus, neatkarīgi no tā, vai jūs metat kauliņus, metat monētu vai ģenerējat paroli.
No nejaušiem bitiem līdz skaitlim jūsu diapazonā
Kriptogrāfiski drošs ģenerators ir tikai puse no godīgas izlozes. Tas nodrošina neapstrādātus bitus, un programmai tie vēl jāpārvērš skaitlī jūsu izvēlētajā diapazonā — un šeit var rasties nobīde. Pieņemsim, ka avots vienādām iespējām dod vērtības no 0 līdz 9, bet jums ir nepieciešams skaitlis no 0 līdz 5. Dalījuma atlikuma ņemšana pēc dalīšanas ar 6 šķiet dabiska, taču 0, 1, 2 un 3 tad var parādīties divos veidos, bet 4 un 5 — tikai vienā. Tādējādi katram no skaitļiem no 0 līdz 3 ir 20 % varbūtība, bet 4 un 5 — tikai 10 % katram. Viens veids, kā novērst šo atlikuma nobīdi (modulo bias), ir atmest nederīgās vērtības un izlozēt vēlreiz; par to sīkāk stāstīts nejaušu skaitļu ģeneratora materiālos.
Cilvēkus bieži pārsteidz vēl divas lietas. Skaitļu atkārtošanās ir normāla parādība: ja vesels skaitlis no 1 līdz 10 tiek izlozēts neatkarīgi un katrs skaitlis ir vienādi iespējams, tikko izlozētajam skaitlim ir tieši tāda pati 1 no 10 iespēja parādīties atkal. Izloze bez atkārtojumiem ir vienkārši cita veida izlozes noteikums, nevis lielāks nejaušums. Turklāt godīgs ģenerators viens pats nepadara visu procedūru godīgu: dalībnieku saraksts un mēģinājumu skaits ir tikpat svarīgi, kā paskaidrots mūsu ceļvedī par to, kā nejauši izvēlēties konkursa uzvarētāju.