Pseudonáhodné číslo: metody získávání, výhody a nevýhody

Pseudonáhodné číslo je speciální číslice vytvořená speciálním generátorem. Generátor takových čísel (PRNG), také známý jako deterministický generátor náhodných bitů (DRBG), je algoritmus pro generování posloupnosti čísel, jejichž vlastnosti aproximují charakteristiky sekvencí náhodných čísel. Sekvence generovaná PRNG není skutečně náhodná, protože je zcela definována počáteční hodnotou zvanou počáteční číslo PRNG, které může zahrnovat skutečně náhodné hodnoty. Ačkoli sekvence, které jsou blíže náhodnému, mohou být vytvořeny pomocí hardwarových generátorů náhodných čísel, generátory pseudonáhodných čísel jsou v praxi důležité pro rychlost generování čísel a jejich Reprodukovatelnost.

Uplatnění

PRNG jsou Ústřední v aplikacích, jako je modelování (například pro metodu Monte Carlo), elektronické hry (například pro procedurální generování) a kryptografie. Kryptografické aplikace vyžadují, aby výstup nebyl předvídatelný z dřívějších informací. Jsou vyžadovány složitější algoritmy, které nezdědí linearitu jednoduchých PRNG.

Požadavky a podmínky

Dobré statistické vlastnosti jsou ústředním požadavkem pro získání PRNG. Obecně je nutná důkladná Matematická analýza, aby bylo zajištěno, že RNG generuje čísla, která jsou dostatečně blízko náhodnému, aby odpovídala 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 zvažuje aritmetické metody získávání náhodných číslic, je samozřejmě ve stavu hříchu".

Použití

PRNG lze spustit z libovolného počátečního stavu. To bude vždy generovat stejnou sekvenci při inicializaci s tímto stavem. Perioda PRNG je definována následovně: maximum pro všechny počáteční stavy délky bezobslužné předpony sekvence. Perioda je omezena počtem stavů běžně měřených v bitech. Vzhledem k tomu, že délka období se potenciálně zdvojnásobuje s každým přidaným bitem "stavu" , je snadné vytvořit PRNG s obdobími dostatečně velkými pro mnoho praktických aplikací.

Pokud vnitřní stav PRNG obsahuje n bitů, jeho období nemusí být větší než 2N výsledků, je mnohem kratší. U některých PRNG lze dobu trvání vypočítat bez obcházení celého období. Lineární zpětnovazební posuvné registry (LFSR) jsou obvykle vybírány tak, aby měly periody rovné 2N − 1.

Lineární shodné generátory mají periody, které lze vypočítat pomocí factoringu. Ačkoli RNG budou opakovat své výsledky poté, co dosáhnou konce období, opakovaný výsledek neznamená, že byl dosažen konec období, protože jeho vnitřní stav může být větší než výstup; to je zvláště patrné u PRNG s jednobitovým závěrem.

Možné chyby

Chyby zjištěné vadnými PRNG sahají od nenápadných (a neznámých) až po zjevné. Příkladem je RANDUŮV algoritmus náhodných čísel, který se na sálových počítačích používá po celá desetiletí. Byl to vážný nedostatek, ale jeho nedostatečnost zůstala po dlouhou dobu bez povšimnutí.

V mnoha oblastech jsou výzkumné práce, které využívaly náhodný výběr, simulace Monte Carlo nebo jiné způsoby založené na RNG, mnohem méně spolehlivé, než by to mohlo být v důsledku použití GNPG nízké kvality. I dnes je někdy nutná opatrnost, o čemž svědčí varování uvedené v mezinárodní encyklopedii statistické vědy (2010).

Příklad úspěšné aplikace

Pro ilustraci zvažte široce používané programovací jazyk Java. Od roku 2017 se Java stále spoléhá na lineární shodný generátor (LCG) pro svůj PRNG.

Historie

Prvním PRNG, který unikl vážným problémům a stále fungoval poměrně rychle, byl Mersenne Twister (diskutováno níže), o kterém byly zveřejněny informace v roce 1998. Od té doby byly vyvinuty další vysoce kvalitní PRNG.

Ale historie pseudonáhodných čísel tím není vyčerpána. Ve druhé polovině 20. století zahrnovala standardní třída algoritmů používaných pro PRNG lineární shodné generátory. Bylo známo, že kvalita LCG je nedostatečná, ale nejlepší metody nebyly k dispozici. Press et al (2007) popsal výsledek takto: "pokud by všechny vědecké práce, jejichž výsledky jsou sporné kvůli [LCG a souvisejícím] zmizely z knihovních polic, každá police by měla mezeru o velikosti vaší pěsti.".

Hlavním pokrokem ve vytváření pseudonáhodných generátorů bylo zavedení metod založených na lineárních opakováních v poli se dvěma prvky; takové generátory jsou spojeny s lineárními registry posunu se zpětnou vazbou. Sloužili základem pro vynálezy senzorů pseudonáhodných čísel.

Zejména vynález Mersena Twistera z roku 1997 se vyhnul mnoha problémům s dřívějšími generátory. Mersenne Twister má období 219937−1 iterace (≈4,3 × 106001). Bylo prokázáno, že je rovnoměrně rozloženo v (až) 623 dimenzích (pro 32bitové hodnoty) a v době jeho implementace běželo rychleji než jiné statisticky založené generátory vytvářející pseudonáhodné posloupnosti čísel.

V roce 2003 představil George Marsaglia rodinu generátorů xorshift založených také na lineárním opakování. Takové generátory jsou extrémně rychlé a-v kombinaci s nelineární operací-procházejí přísnými statistickými testy.

V roce 2006 byla vyvinuta rodina generátorů WELL. Generátory WELL v některých ohledech zlepšují kvalitu Twister Mersenne, který má příliš velký stavový prostor a velmi pomalé zotavení z nich generováním pseudonáhodných čísel s velkým počtem nul.

Kryptografie

PRNG, vhodný pro kryptografické aplikace, se nazývá Kryptograficky zabezpečený PRNG (CSPRNG). Požadavek na CSPRNG je, že útočník, který nezná počáteční číslo, má jen malou výhodu při rozlišování výstupní sekvence generátoru od náhodné sekvence. Jinými slovy, zatímco PRNG je vyžadován pouze k provedení určitých statistických testů, CSPRNG musí projít všemi statistickými testy, které jsou omezeny na polynomiální čas ve velikosti semene.

Ačkoli důkaz této vlastnosti přesahuje současnou úroveň teorie výpočetní složitosti, přesvědčivé důkazy mohou být poskytnuty redukcí CSPRNG na problém, který je považován za složitý, podobně jako celočíselná faktorizace. Obecně může trvat roky přezkumu, než může být algoritmus certifikován jako CSPRNG.

Ukázalo se, že je pravděpodobné, že NSA vložila asymetrický backdoor do NIST certifikovaného pseudonáhodného generátoru čísel Dual_EC_DRBG.

Algoritmy pseudonáhodných čísel

Většina algoritmů PRNG produkuje sekvence, které jsou rovnoměrně rozloženy kterýmkoli z několika testů. Je to otevřená otázka. Je jedním z ústředních v teorii a praxi kryptografie: existuje způsob, jak odlišit výstup vysoce kvalitního PRNG od skutečně náhodné sekvence? V tomto nastavení rozpoznávač ví, že byl použit buď známý algoritmus PRNG (ale ne stav, se kterým byl inicializován), nebo byl použit skutečně náhodný algoritmus. Musí je rozlišovat.

Bezpečnost většiny kryptografických algoritmů a protokolů využívajících PRNG je založena na předpokladu, že není možné rozlišit použití vhodného PRNG od použití skutečně náhodné sekvence. Nejjednoduššími příklady této závislosti jsou šifry pro streamování, které nejčastěji fungují tak, že vylučují nebo odesílají prostý text zprávy s výstupem PRNG a vytvářejí šifrovaný text. Vývoj Kryptograficky odpovídajících PRNG je extrémně složitý, protože musí splňovat další kritéria. Velikost jeho období je důležitým faktorem kryptografické vhodnosti PRNG, ale ne jediným.

Časný počítačový PRNG navržený Johnem von Neumannem v roce 1946 je známý jako metoda středních čtverců. Algoritmus je následující: Vezměte libovolné číslo, na druhou, odstraňte střední číslice výsledného čísla jako "náhodné číslo" a poté použijte toto číslo jako počáteční pro další iteraci. Například umocnění čísla 1111 dává 1234321, které lze zapsat jako 01234321, 8místné číslo je čtvercem čtyřmístného. To dává 2343 jako" náhodné " číslo. Výsledek opakování tohoto postupu je 4896 atd. Von Neumann používal desetimístná čísla, ale proces byl stejný.

Nevýhody "středního čtverce"

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 o tom věděl, ale našel přístup dostatečný pro své účely a obával se, že matematické "opravy" budou chyby spíše skrývat než je odstraňovat.

Von Neumann považoval hardwarové generátory náhodných a pseudonáhodných čísel za nevhodné: pokud nezaznamenávají vygenerovaný výstup, nelze je později zkontrolovat na chyby. Pokud by zaznamenali své výsledky, vyčerpali by omezenou dostupnou paměť počítače a podle toho schopnost počítače číst a zapisovat čísla. Pokud by čísla byla zapsána na karty, trvalo by jim mnohem déle psát a číst. Na počítači ENIAC, který používal, metoda "středního čtverce" a provedla proces získávání pseudonáhodných čísel několik stokrát rychleji, než je čtení čísel z děrných štítků.

Metoda středního čtverce byla od té doby nahrazena složitějšími generátory.

Průkopnická metoda

Nedávnou novinkou je kombinace středního čtverce s Weylovou sekvencí. Tato metoda poskytuje vysoce kvalitní produkty po dlouhou dobu. Pomáhá získat nejlepší vzorce pseudonáhodných čísel.