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ě náhodné, 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. Ta však může být velmi dlouhá, tudíž nedetekovatelná.

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“.

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. 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áná spočítaní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.

[editovat] Odkazy

• Lenore Blum, Manuel Blum, and Michael Shub. „Comparison of two pseudo-random number generators“, Advances in Cryptology: Proceedings of Crypto '82.
• 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.
• Program pro testování pseudonáhodných generátorů: http://www.fourmilab.ch/random/