Generátor pseudonáhodných čísel

Generátor pseudonáhodných čísel je efektivní deterministický program, který generuje posloupnost čísel, statistickými testy pokud možno nerozlišitelnou od náhodné. Byť existují zdroje skutečně náhodných jevů (kvantové generátory, šum), pseudonáhodné generátory (a postupy jakými se vytvářejí) jsou klíčovým prostředkem moderní kryptografie. Na nich se zakládají pravděpodobnostní kryptosystémy s veřejným klíčem, digitální podpisová schémata, bit-commitment protokoly a interaktivní zero-knowledge důkazové systémy.

Vstupními daty pro pseudonáhodné generátory jsou skutečně (téměř) náhodné (pokud probíhá útok postranním kanálem navíc záměrně ovlivňované), leč krátké, posloupnosti zvané random seed, které jednoznačně určují další běh programu (generátoru). V důsledku determinističnosti těchto programů jsou na počítači s ohraničenou pamětí nevyhnutelně periodické, tedy po určité době (periodě) se generovaná posloupnost začne opakovat. +more Ta však může být velmi dlouhá, tudíž nedetekovatelná. Standardizované generátory ovšem mohou obsahovat posloupnosti vytvářející u šifrovacích algoritmů „zadní vrátka“ (tj. „univerzální klíč“).

Je otázkou, je-li možné současnými výpočetními prostředky rozlišit náhodnou posloupnost od posloupnosti pseudonáhodné, pokud nedisponujeme znalostí „random seed“ a použitého algoritmu generátoru.

Pseudonáhodné generátory, ať už čísel či binárních posloupností, lze elegantně realizovat použitím jednosměrných funkcí, na jejichž inverzi v současnosti není znám žádný efektivní algoritmus. V takovém případě postačí, když za „random seed“ vezmeme relativně malé číslo, pak iterativně aplikujeme jednosměrnou funkci a do pseudonáhodné posloupnosti postupně zařazujeme hard-core bity pro tyto iterace. +more Tak dostaneme pseudonáhodnou binární posloupnost, která může být polynomiálně delší, než náhodný vstup. Ukázkovým příkladem pseudonáhodného generátoru, založeném na předpokladu nemožnosti efektivní faktorizace, je Blum-Blum-Shub pseudonáhodný generátor. Ten je možno použít na konstrukci Blum-Goldwasser kryptosystému s veřejným klíčem. To je proudová šifra, ve které je zpráva šifrována spočítáním jejího XORu s pseudonáhodně vygenerovaným tajným klíčem stejné délky, tak jako je tomu u Vernamovy šifry.

Pro generování pseudonáhodných čísel na číslicových počítačích existuje celá řada různých algoritmů. Nejčastěji používané generátory využívají princip lineárního kongruentního generátoru. +more Moderní metody, kromě již vzpomínaného Blum-Blum-Shub generátoru, zahrnují např. Mersenne twister.

Periodicita

Generátor pseudonáhodných čísel je nastaven do jakéhokoliv výchozího stavu použitím random seed (náhodné číslo - počáteční stav). Poté vždy vyprodukuje stejnou sekvenci čísel, pokud je inicializován se stejným počátečním stavem. +more Perioda generátoru pseudonáhodných čísel je definována jako maximum nad všemi počátečními stavy délky neopakující se sekvence. Perioda je omezena velikostí stavu měřeného v bitech. Nicméně od té doby, co se délka periody potenciálně zdvojnásobuje s každým stavovým bitem, je snadné vytvořit generátor pseudonáhodných čísel s periodou dostatečně dlouhou pro praktické aplikace.

Pokud vnitřní stav generátoru pseudonáhodných čísel obsahuje n bitů, pak jeho perioda nemůže být delší než 2n výsledných stavů, ale může být mnohem kratší. Pro některé generátory je možné délku periody vypočítat bez procházení skrze celou periodu. +more Posuvný registr s lineární zpětnou vazbou je obvykle volen s periodou 2n−1. Lineární kongruentní generátor mívá periodu, která může být vypočítána faktorizací. Přestože generátor pseudonáhodných čísel bude opakovat výsledky poté, co dosáhne konce periody, opakovaný výsledek nezaručuje dosažení konce periody, poněvadž jeho vnitřní stav může být větší než výsledný. To je zřejmé zejména u generátoru pseudonáhodných čísel s 1bitovým výstupem.

Většina algoritmů pseudonáhodných generátorů produkuje sekvenci s rovnoměrným rozdělením.

Problémy s deterministickými generátory

V praxi výstup z mnoha běžných generátorů pseudonáhodných čísel vykazuje anomálii, která způsobuje jejich selhání při statistické detekci vzoru. Například: * periody pro některé výchozí stavy jsou kratší než očekáváme (takové stavy mohou být v tomto kontextu nazvány „slabými“) * chybějící rovnoměrnost rozdělení pro velké množství generovaných čísel * korelace po sobě následujících hodnot * slabá dimensionální distribuce výsledné sekvence * rozdíl mezi tím, jak jsou určité hodnoty distribuovány od těch s náhodnou distribucí

Chyby vyskytující se ve vadných generátorech pseudonáhodných čísel se objevují od těch nejnepatrnějších (a neznámých) až ke zřejmým. Jako příklad může být uveden RANDU, což je algoritmus náhodných čísel, používaný po celá desetiletí na mainframech. +more Tento algoritmus byl vskutku nedostatečný, ale jeho neadekvátnost zůstala bez povšimnutí po celá léta. V mnoha oborech, bylo velké množství výzkumných prací té doby, která se spoléhala na náhodný výběr nebo na metodu Monte Carlo, jinak řečeno jsou méně spolehlivé než by mohly být v případě výsledků.

Rané způsoby

Raný, počítačově založený generátor pseudonáhodných čísel, navržen Johnem von Neumannem roku 1946, je znám pod názvem metoda prostředku čtverce. Algoritmus funguje takto: vezmi jakékoliv číslo, umocni ho na druhou, vezmi prostřední číslice výsledného čísla jako „náhodné číslo“, poté použij číslo jako výchozí stav pro generátor. +more Například: umocníme číslo „1111“,získáme „1234321“, které může být zapsáno jako „01234321“, čili osmiciferné číslo, které je druhou mocninou čtyřciferného čísla. Vezmeme střední cifry, což je „2343“, tedy máme „náhodné“ číslo. Opakováním této procedury získáme „4896“ jako další výsledek atd. Von Neumann používal deseticiferná čísla, ale proces byl totožný.

Problém s touto metodou je ten, že všechny sekvence se nakonec opakují. Některé se opakuji velmi rychle, například: „0000“. +more Von Neumann se obával, že by matematické úpravy pouze chyby schovaly a neodstranily je, avšak našel způsob dostatečný pro jeho úmysly.

Von Neumann usoudil, že převést generátor pseudonáhodných čísel do hardwaru je nevhodné, protože kdyby nebyl zaznamenáván výstup generátoru, nebylo by možné později testovat jeho kvalitu. Kdyby byl výstup zaznamenáván, vyčerpala by se omezená paměť tehdy dostupná v počítačích a to by znemožnilo čtení a zápis čísel. +more Pokud by byla čísla zaznamenaná na děrné štítky, trvaly by čtení a zápis velmi dlouho. Na počítači ENIAC, který Von Neumann používal, byla metoda prostředku čtverce generující čísla zhruba stokrát rychlejší než čtení z děrných štítků.

Od té doby byla metoda prostředku čtverce nahrazena kvalitnějšími generátory.

Odkazy

Reference

Literatura

Lenore Blum, Manuel Blum, and Michael Shub. „Comparison of two pseudo-random number generators“, Advances in Cryptology: Proceedings of Crypto '82. +more * Lenore Blum, Manuel Blum, and Michael Shub. „A Simple Unpredictable Pseudo-Random Number Generator“, SIAM Journal on Computing, volume 15, pages 364-383, May 1986. * Blum, S. Goldwasser, „An Efficient Probabilistic Public Key Encryption Scheme which Hides All Partial Information“, Proceedings of Advances in Cryptology - CRYPTO '84, pp. 289-299, Springer Verlag, 1985.

Související články

Hardwarový generátor náhodných čísel * Pseudonáhodná čísla - náhodná čísla generovaná na číslicovém počítači

Externí odkazy

http://www.fourmilab.ch/random/ - program pro testování pseudonáhodných generátorů

Kategorie:Kryptografické algoritmy Kategorie:Teoretická informatika Kategorie:Pravděpodobnost a statistika