Generátor pseudonáhodných čísel (PRNG), také známý jako deterministický generátor náhodných bitů (DRBG), je algoritmus pro generování posloupnosti čísel, který se přibližuje vlastnostem náhodných čísel. Posloupnost není skutečně náhodná v tom, že je zcela určena relativně malým souborem počátečních hodnot, nazývaným stav PRNG, který zahrnuje skutečně náhodné semeno. Ačkoli posloupnosti, které jsou blíže skutečně náhodným, mohou být generovány pomocí hardwarových generátorů náhodných čísel, pseudonáhodná čísla jsou v praxi důležitá pro jejich rychlost při generování čísel a jejich reprodukovatelnost, a jsou tedy ústředními v aplikacích, jako jsou simulace (např. fyzikálních systémů s metodou Monte Carlo), v kryptografii a v procedurálním generování. Dobré statistické vlastnosti jsou ústředním požadavkem pro výstup PRNG a běžné třídy vhodných algoritmů zahrnují lineární kongruentní generátory, zaostalé Fibonacciho generátory a lineární registry posuvu zpětné vazby. Kryptografické aplikace vyžadují, aby byl výstup také nepředvídatelný, a jsou zapotřebí propracovanější konstrukce, které nedědí linearitu jednodušších řešení. Novější případy PRNG se silnými zárukami náhodnosti jsou založeny na předpokladech výpočetní tvrdosti a zahrnují Blum Blum Shub, Fortuna a Mersenne Twister algoritmy.
Obecně platí, že pečlivá matematická analýza je nutná, aby měla jistotu, že PRNG generuje čísla, která jsou dostatečně „náhodná“, aby vyhovovala zamýšlenému použití. John von Neumann varoval před nesprávnou interpretací PRNG jako skutečně náhodného generátoru a žertoval, že „každý, kdo uvažuje o aritmetických metodách výroby náhodných číslic, je samozřejmě ve stavu hříchu.“ Robert R. Coveyou z Oak Ridge National Laboratory jednou nazval článek „Generování náhodných čísel je příliš důležité, aby bylo ponecháno náhodě.“
nazýváme funkci (kde je množina pozitivní celá čísla) pseudo-náhodný generátor čísel pro daný přičemž hodnoty v MFF
( označuje počet prvků v konečné množině .)
To může být prokázáno, že pokud je pseudo-náhodný generátor čísel pro jednotné rozdělení na a pokud je CDF některé dané rozdělení pravděpodobnosti , Pak je pseudo-náhodný generátor čísel pro , Kde je percentil , Tj. Intuitivně, svévolné rozdělení může být simulován ze simulace standardní jednotné rozdělení.
PRNG může být spuštěn z libovolného počátečního stavu pomocí předsádkového stavu. Po inicializaci tímto stavem bude vždy generovat stejnou posloupnost. Perioda PRNG je definována jako maximum nad všemi počátečními stavy délky předpony sekvence bez opakování. Perioda je ohraničena velikostí stavu, měřeno v bitech. Avšak vzhledem k tomu, že délka periody se potenciálně zdvojnásobuje s každým přidaným bitem ‚stavu‘, je snadné sestavit PRNG s periodou dostatečně dlouhou pro mnoho praktických aplikací.
Pokud vnitřní stav PRNG obsahuje n bitů, jeho perioda nemůže být delší než 2n výsledků a může být mnohem kratší. U některých PRNG lze délku periody vypočítat bez procházení celé periody. Registry Linear Feedback Shift (LFSR) se obvykle volí tak, aby měly periody přesně 2n−1. Lineární kongruentní generátory mají periody, které lze vypočítat faktoringem. [citace nutná] Mixy (bez omezení) mají periody v průměru okolo 2n/2, obvykle po procházení neopakující se startovací sekvence. Mixy, které jsou reverzibilní (permutace) mají periody v průměru okolo 2n−1 a perioda bude vždy zahrnovat původní vnitřní stav (např. ). Ačkoli PRNG budou své výsledky opakovat po dosažení konce periody, opakovaný výsledek neznamená, že bylo dosaženo konce periody, protože její vnitřní stav může být větší než její výstup; to je zvláště zřejmé u PRNG s 1-bitovým výstupem.
Většina pseudonáhodných generátorových algoritmů produkuje sekvence, které jsou rovnoměrně distribuovány některým z několika testů. Je otevřenou otázkou, a jednou z ústředních pro teorii a praxi kryptografie, zda existuje nějaký způsob, jak odlišit výstup vysoce kvalitního PRNG od skutečně náhodné sekvence, aniž bychom znali použitý algoritmus (algoritmy) a stav, kterým byl inicializován. Bezpečnost většiny kryptografických algoritmů a protokolů používajících PRNG je založena na předpokladu, že je nemožné odlišit použití vhodného PRNG od použití skutečně náhodné sekvence. Nejjednoduššími příklady této závislosti jsou streamové šifry, které (nejčastěji) pracují tak, že vyloučí nebo vyloží plaintext zprávy s výstupem PRNG, čímž vznikne šifrovaný text. Návrh kryptograficky adekvátních PRNG je extrémně obtížný, protože musí splňovat dodatečná kritéria (viz níže). Velikost jeho periody je důležitým faktorem kryptografické vhodnosti PRNG, ale ne jediným.
Problémy s deterministickými generátory
Vady vykazované vadnými PRNGy se pohybují od nepozorovatelných (a neznámých) až po velmi zjevné. Příkladem byl algoritmus náhodných čísel RANDU používaný desítky let na sálových počítačích. Byl vážně vadný, ale jeho nedostatečnost zůstala po velmi dlouhou dobu neodhalena. V mnoha oborech je mnoho výzkumné práce z tohoto období, která se opírala o náhodný výběr nebo o simulace ve stylu Monte Carla nebo jiným způsobem, méně spolehlivá, než by v důsledku mohla být.
První počítačová metoda PRNG, kterou navrhl John von Neumann v roce 1946, je známá jako metoda prostředního kvadrátu. Algoritmus je následující: vezmeme libovolné číslo, umocníme ho, odstraníme prostřední číslice výsledného čísla jako „náhodné číslo“, pak toto číslo použijeme jako semínko pro další iteraci. Například umocnění čísla „1111“ přinese „1234321“, což lze zapsat jako „01234321“, osmimístné číslo je druhou mocninou čtyřmístného čísla. To dává „2343“ jako „náhodné“ číslo. Opakováním tohoto postupu dostaneme „4896“ jako další výsledek, a tak dále. Von Neumann použil desetimístná čísla, ale proces byl stejný.
Problém s metodou „středního čtverce“ je, že všechny sekvence se nakonec opakují, některé velmi rychle, například „0000“. Von Neumann si toho byl vědom, ale shledal tento přístup dostatečným pro své účely a obával se, že matematické „opravy“ by chyby jednoduše skryly, místo aby je odstranily.
Von Neumann usoudil, že hardwarové generátory náhodných čísel jsou nevhodné, protože pokud by nezaznamenaly generovaný výstup, nemohly by být později testovány na chyby. Pokud by zaznamenaly svůj výstup, vyčerpaly by omezené paměti počítače, které byly tehdy k dispozici, a tím i schopnost počítače číst a psát čísla. Pokud by se čísla zapisovala na karty, trvalo by jim mnohem déle, než by se zapisovala a četla. Na počítači ENIAC, který používal, generovala metoda „prostředního čtverce“ čísla rychlostí zhruba stokrát rychlejší než čtení čísel z děrných štítků.
Metoda středního kvadrátu byla od té doby nahrazena propracovanějšími generátory.
Vynález Mersennova twisterového algoritmu z roku 1997, který provedli Makoto Matsumoto a Takuji Nishimura, se vyhýbá mnoha problémům s dřívějšími generátory. Má kolosální periodu 219937−1 iterací (>4,3×106001
), je prokazatelně rovnoměrně rozložen v (až) 623 rozměrech (pro 32bitové hodnoty) a běží rychleji než jiné statisticky rozumné generátory. V současnosti se stále více stává generátorem náhodných čísel pro statistické simulace a generativní modelování.
SFMT, SIMD orientovaný Rychlý Mersennův twister, varianta Mersennova twisteru, je rychlejší, i když není zkompilován s podporou SIMD.
Rodilý Mersenne Twister není považován za vhodný pro použití ve všech kryptografických aplikacích. Varianta Mersenne Twisteru byla navržena jako kryptografická šifra.
Kryptograficky bezpečné generátory pseudonáhodných čísel
PRNG vhodný pro kryptografické aplikace se nazývá kryptograficky bezpečný PRNG (CSPRNG). Požadavkem pro CSPRNG je, že protivník, který nezná semeno, má pouze zanedbatelnou výhodu v rozlišení výstupní sekvence generátoru od náhodné sekvence. Jinými slovy, zatímco PRNG musí projít pouze určitými statistickými testy, CSPRNG musí projít všemi statistickými testy, které jsou omezeny na polynomiální čas ve velikosti semena. Ačkoli takovou vlastnost nelze prokázat, silný důkaz může být poskytnut snížením CSPRNG na problém, který je považován za těžký, jako je celočíselná faktorizace. Obecně mohou být vyžadovány roky přezkoumání, než může být algoritmus certifikován jako CSPRNG.
Některé třídy CSPRNGů zahrnují následující:
Německý Spolkový úřad pro informační bezpečnost (BSI) stanovil čtyři kritéria kvality deterministických generátorů náhodných čísel. Jsou shrnuta zde:
Pro kryptografické aplikace jsou přijatelné pouze generátory splňující normu K3 nebo K4.
Čísla vybraná z nerovnoměrného rozdělení pravděpodobnosti mohou být generována pomocí stejnoměrného rozdělení PRNG a funkce, která obě rozdělení spojuje.
Za prvé, jeden potřebuje kumulativní distribuční funkci cílového rozdělení :
Všimněte si, že . Použití náhodné číslo c z rovnoměrného rozdělení jako hustota pravděpodobnosti na „projít“, dostaneme
je číslo náhodně vybrané z distribuce .
Například inverzní distribucí kumulativního Gaussova rozdělení
s ideálním jednotným PRNG s rozsahem (0, 1) jako vstupem by vznikla posloupnost (pouze kladných) hodnot s Gaussovým rozdělením; nicméně
Podobné úvahy platí pro generování jiných nerovnoměrných distribucí, jako je Rayleigh a Poisson.