Čo je generátor náhodných čísel?
Generátor náhodných čísel (RNG) je systém, ktorý vytvára náhodné alebo pseudonáhodné čísla. To, či je možné nasledujúce číslo skutočne predpovedať, závisí od typu generátora. Niektoré generátory vychádzajú z fyzikálneho procesu, iné počítajú čísla pomocou algoritmu a niektoré algoritmy sú navrhnuté tak, že ani ten, kto videl ich doterajšie výsledky, nedokáže predpovedať, čo príde ďalej. Vyzerať náhodne a byť nepredvídateľný sú dve odlišné vlastnosti a väčšina tohto článku sa venuje práve tomuto rozdielu.
Hardvérové generátory náhodných čísel
Hardvérový generátor náhodných čísel (HRNG), označovaný aj ako generátor skutočne náhodných čísel (TRNG), odvodzuje svoje čísla z fyzikálneho procesu. Tie najstaršie fungujú priamo pred našimi očami: hodená minca, hodená kocka či ruletové koleso. Mechanika každý z nich úplne opisuje, no dobre vyrobené koleso je v praxi stále nepredvídateľné, pretože nepatrné rozdiely na začiatku každého roztočenia vyústia do úplne odlišných výsledkov.
Moderné hardvérové generátory namiesto toho merajú mikroskopické javy: výstrelový a tepelný šum v elektronických obvodoch, atmosférický šum alebo kvantové javy. Sú to dobré zdroje entropie — merateľnej nepredvídateľnosti —, no fyzikálny zdroj nie je zo svojej podstaty dokonalý: môže mať nerovnomerné rozdelenie, môže sa v čase meniť a môže zlyhať, preto je potrebné jeho kvalitu hodnotiť a monitorovať a jeho výsledky v prípade potreby ďalej spracovávať, čo popisujú štandardy ako NIST SP 800-90B. Hardvérové zdroje sa používajú tam, kde na spoľahlivosti záleží najviac — predovšetkým v kryptografii, kde poskytujú nepredvídateľný východiskový materiál pre kľúče v protokoloch, ako je Transport Layer Security (TLS).
Generátory pseudonáhodných čísel
Alternatívou k fyzickému zariadeniu je algoritmus. Generátor pseudonáhodných čísel (PRNG) vytvára postupnosť, ktorá vyzerá náhodne, no je úplne určená počiatočnou hodnotou (seed). Ak zadáte rovnakú počiatočnú hodnotu do rovnakého algoritmu, získate zakaždým rovnakú postupnosť. To predstavuje slabinu všade tam, kde musí byť výsledok nepredvídateľný a počiatočnú hodnotu alebo vnútorný stav je možné uhádnuť či zrekonštruovať, a výhodu všade tam, kde musí byť výsledok reprodukovateľný — simuláciu alebo test možno spustiť znova úplne rovnako. PRNG sú tiež rýchle, nenáročné a ľahko sa implementujú, a preto sa na ne spolieha väčšina softvéru. Medzi známe rodiny patria lineárny kongruentný generátor (LCG), generátory xorshift a Mersenne Twister.
Mersenne Twister
Mersenne Twister, ktorý v roku 1997 publikovali Makoto Matsumoto a Takuji Nishimura, patrí k najpoužívanejším generátorom pseudonáhodných čísel a v mnohých programovacích jazykoch je predvolenou voľbou. Jeho názov vychádza z periódy — dĺžky postupnosti pred jej opakovaním —, ktorou je v štandardnom variante MT19937 Mersennovo prvočíslo 219937 − 1. Prechádza väčšinou štatistických testov náhodnosti a dobre sa hodí na simulácie. Nebol však navrhnutý na uchovávanie tajomstiev: zo 624 po sebe idúcich 32-bitových výsledkov dokáže ktokoľvek zrekonštruovať jeho vnútorný stav a predpovedať každú nasledujúcu hodnotu, takže sa nesmie používať na kľúče, heslá ani na nič iné, čo musí zostať nepredvídateľné.
Kryptograficky bezpečné generátory a entropia
Mnohé aplikácie potrebujú obe veci súčasne: rýchlosť algoritmu aj nepredvídateľnosť fyzikálneho zdroja. Riešením je kryptograficky bezpečný generátor pseudonáhodných čísel (CSPRNG). Je to stále PRNG, no zostavený tak, že znalosť časti jeho výsledkov neposkytuje žiadny praktický spôsob, ako predpovedať zvyšok, a jeho počiatočná hodnota sa získava a pravidelne obnovuje zo zdroja skutočnej entropie. Počiatočná hodnota z fyzikálneho zdroja neurobí z bežného PRNG bezpečný systém; na tento účel musí byť navrhnutý samotný algoritmus. Fyzikálny zdroj, napríklad tepelný šum alebo časovanie hardvérových udalostí, dodáva malé množstvo skutočnej náhodnosti a CSPRNG z nej oveľa rýchlejšie získa dlhú postupnosť hodnôt. Túto kombináciu ponúka operačný systém programom, ktoré na ňom bežia, a práve to sa dnes v praxi zvyčajne chápe pod pojmom „generátor náhodných čísel“. Vytvára šifrovacie kľúče, relačné tokeny a heslá.
Náhodné čísla v prehliadači
JavaScript dáva webovej stránke dva vstavané spôsoby, ako získať náhodné hodnoty, a tie patria do rôznych tried. Math.random() je bežný PRNG: jazykový štandard ponecháva voľbu algoritmu na každom prehliadači a nezaručuje žiadnu bezpečnosť — na animáciu stačí, no na žrebovanie, ktoré by niekto mohol spochybniť, je nevhodný. Druhou možnosťou je Web Crypto API. Jeho metóda crypto.getRandomValues() vracia kryptograficky silné náhodné hodnoty, ktoré vytvára CSPRNG čerpajúci z entropie operačného systému.
Náš online generátor náhodných čísel využíva Web Crypto API pri každom žrebovaní a čísla vznikajú vo vašom prehliadači, nie na serveri. Rovnaký zdroj poháňa aj ostatné generátory na tejto stránke, či už hádžete kockou, hádžete mincou alebo generujete heslo.
Od náhodných bitov k číslu vo vašom rozsahu
Kryptograficky bezpečný generátor predstavuje len polovicu spravodlivého žrebovania. Dodáva surové bity a program ich musí previesť na číslo vo vašom požadovanom rozsahu — a práve tu sa môžu objaviť nerovnaké šance. Predstavte si, že zdroj ponúka hodnoty 0 až 9 s rovnakou pravdepodobnosťou a vy potrebujete číslo od 0 do 5. Zobrať zvyšok po delení číslom 6 vyzerá prirodzene, no 0, 1, 2 a 3 sa potom môžu objaviť dvoma spôsobmi a 4 a 5 iba jedným, takže každé z čísel 0 až 3 má šancu 20 % a 4 a 5 iba 10 %. Jedným zo spôsobov, ako toto vychýlenie (modulo bias) odstrániť, je nevyhovujúce hodnoty zahodiť a žrebovať znova; podrobne sa tomu venujú naše materiály o náhodných číslach.
Dve ďalšie veci ľudí často prekvapia. Opakovanie je normálne: keď sa celé číslo od 1 do 10 žrebuje nezávisle a každé číslo je rovnako pravdepodobné, práve vyžrebované číslo má rovnakú šancu 1 z 10, že padne znova, ako ktorékoľvek iné. Žrebovanie bez opakovania je iný druh výberu, nie náhodnejší. A samotný spravodlivý generátor ešte nezaručuje férovosť celého postupu: zoznam účastníkov a počet pokusov majú rovnakú váhu, ako vysvetľuje náš článok o tom, ako vybrať náhodného výhercu súťaže.