| dbpedia-owl:abstract
|
- 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. 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íč“).Šablona:Zdroj?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. 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. Moderní metody, kromě již vzpomínaného Blum-Blum-Shub generátoru, zahrnují např. Mersenne twister.
|
