Co je generátor náhodných čísel?
Generátor náhodných čísel (RNG) je systém, který vytváří náhodná nebo pseudonáhodná čísla. Zda lze následující číslo skutečně předpovědět, závisí na typu generátoru. Některé generátory vycházejí z fyzikálního procesu, jiné počítají čísla pomocí algoritmu a některé algoritmy jsou navrženy tak, že ani ten, kdo viděl jejich dosavadní výsledky, nedokáže předpovědět, co přijde dál. Vypadat náhodně a být nepředvídatelný jsou dvě odlišné vlastnosti a většina tohoto článku se věnuje právě tomuto rozdílu.
Hardwarové generátory náhodných čísel
Hardwarový generátor náhodných čísel (HRNG), označovaný také jako generátor skutečně náhodných čísel (TRNG), odvozuje svá čísla z fyzikálního procesu. Ty nejstarší fungují přímo před očima: hozená mince, hozená kostka, ruletové kolo. Mechanika každý z nich dokonale popisuje, přesto je dobře vyrobené kolo v praxi stále nepředvídatelné, protože drobné rozdíly v tom, jak každé roztočení začíná, přerůstají ve zcela odlišné výsledky.
Moderní hardwarové generátory místo toho měří mikroskopické jevy: výstřelový a tepelný šum v elektronických obvodech, atmosférický šum, kvantové jevy. Jedná se o dobré zdroje entropie — měřitelné nepředvídatelnosti — avšak fyzikální zdroj není ze své podstaty dokonalý: může vykazovat odchylky, může se v čase měnit a může selhat, takže je nutné jeho kvalitu hodnotit a sledovat a jeho výsledky v případě potřeby dále zpracovávat, což popisují standardy jako NIST SP 800-90B. Hardwarové zdroje se využívají tam, kde na spolehlivosti záleží nejvíce — především v kryptografii, kde poskytují nepředvídatelný výchozí materiál pro klíče v protokolech, jako je Transport Layer Security (TLS).
Generátory pseudonáhodných čísel
Alternativou k fyzickému zařízení je algoritmus. Generátor pseudonáhodných čísel (PRNG) vytváří posloupnost, která vypadá náhodně, ale je zcela určena počáteční hodnotou nazývanou seed (výchozí hodnota). Zadejte stejný seed do stejného algoritmu a pokaždé získáte identickou posloupnost. To představuje slabinu všude tam, kde musí být výsledek nepředvídatelný a seed nebo vnitřní stav lze uhodnout či zrekonstruovat, a naopak přednost tam, kde musí být výsledek reprodukovatelný — simulaci nebo test lze spustit znovu naprosto stejně. PRNG jsou také rychlé, levné a snadno implementovatelné, a proto na ně spoléhá většina softwaru. Mezi známé algoritmy patří lineární kongruentní generátor (LCG), generátory xorshift a Mersenne Twister.
Mersenne Twister
Mersenne Twister, který v roce 1997 publikovali Makoto Matsumoto a Takuji Nishimura, patří k nejpoužívanějším generátorům pseudonáhodných čísel a v mnoha programovacích jazycích představuje výchozí volbu. Jeho název vychází z periody — délky posloupnosti před jejím opakováním — která u standardní varianty MT19937 představuje Mersennovo prvočíslo 219937 − 1. Úspěšně prochází většinou statistických testů náhodnosti a výborně se hodí pro simulace. Nebyl však navržen pro uchovávání tajemství: z 624 po sobě jdoucích 32bitových výstupů může kdokoli zrekonstruovat jeho vnitřní stav a předpovědět každou následující hodnotu, takže se nesmí používat pro klíče, hesla ani pro cokoli jiného, co musí zůstat nepředvídatelné.
Kryptograficky bezpečné generátory a entropie
Mnoho aplikací potřebuje obě věci současně: rychlost algoritmu i nepředvídatelnost fyzikálního zdroje. Řešením je kryptograficky bezpečný generátor pseudonáhodných čísel (CSPRNG). Je to stále PRNG, ale vytvořený tak, že znalost části jeho výsledků neposkytuje žádný praktický způsob, jak předpovědět zbytek, a je inicializován a pravidelně doplňován ze zdroje skutečné entropie. Výchozí hodnota z fyzikálního zdroje neudělá z běžného PRNG bezpečný systém; pro tento účel musí být navržen samotný algoritmus. Fyzikální zdroj, například tepelný šum nebo časování hardwarových událostí, dodává malé množství skutečné náhodnosti a CSPRNG z ní mnohem rychleji vytváří dlouhou posloupnost hodnot. Tuto kombinaci nabízí operační systém programům, které na něm běží, a právě to se dnes v praxi obvykle rozumí pod pojmem "generátor náhodných čísel". Vytváří šifrovací klíče, relační tokeny a hesla.
Náhodná čísla v prohlížeči
JavaScript dává webové stránce dva vestavěné způsoby, jak získat náhodné hodnoty, a ty patří do různých tříd. Math.random() je běžný PRNG: jazykový standard nechává volbu algoritmu na každém prohlížeči a nezaručuje žádné zabezpečení — pro animaci plně postačuje, pro slosování, které by někdo mohl napadnout, je však nevhodný. Druhou možností je Web Crypto API. Jeho metoda crypto.getRandomValues() vrací kryptograficky bezpečné náhodné hodnoty, které vytváří CSPRNG čerpající z entropie operačního systému.
Náš online generátor náhodných čísel využívá Web Crypto API pro každé losování a čísla vznikají ve vašem prohlížeči, nikoli na serveru. Stejný zdroj pohání i ostatní generátory na tomto webu, ať už házíte kostkou, házíte mincí, nebo generujete heslo.
Od náhodných bitů k číslu ve vašem rozsahu
Kryptograficky bezpečný generátor představuje pouze polovinu spravedlivého losování. Dodává surové bity a program je musí převést na číslo ve vašem požadovaném rozsahu — a právě zde se mohou objevit nerovné šance. Představte si, že zdroj nabízí hodnoty 0 až 9 se stejnou pravděpodobností a vy potřebujete číslo od 0 do 5. Vzít zbytek po dělení číslem 6 vypadá přirozeně, ale 0, 1, 2 a 3 se pak mohou objevit dvěma způsoby, zatímco 4 a 5 pouze jedním, takže každé z čísel 0 až 3 má 20% šanci a 4 a 5 pouze po 10 %. Jedním ze způsobů, jak tuto nerovnost odstranit, je nevyhovující hodnoty zahodit a losovat znovu; podrobně se tomu věnují naše materiály o generátoru náhodných čísel.
Dvě další věci lidi často překvapí. Opakování je normální: když se celé číslo od 1 do 10 losuje nezávisle a každé číslo je stejně pravděpodobné, právě vytažené číslo má stejnou šanci 1 z 10, že padne znovu, jako kterékoli jiné. Losování bez opakování je jiný druh výběru, nikoli náhodnější. A samotný poctivý generátor ještě nezajišťuje spravedlnost celého postupu: seznam účastníků a počet pokusů mají stejnou váhu, jak vysvětluje náš článek o tom, jak vybrat náhodného výherce soutěže.