Generátor psévdonakljúčnih števíl (, kratica PRNG) ali tudi deterministični generator naključnih bitov (deterministic random bit generator (DRBG)) je po navadi računalniški algoritem za tvorjenje številskega zaporedja, ki je približek značilnosti naključnih števil. Zaporedje ni čisto naključno in je popolnoma določeno z relativno majhno množico začetnih vrednosti, ki se imenuje stanje generatorja, in vsebuje resnično naključno začetno vrednost (seme; angleško random seed).
Čeprav se zaporedja števil, ki so bližje resnični naključnosti, tvorijo s pomočjo strojnih generatorjev naključnih števil, so psevdonaključna števila pomembna v praksi zaradi velike hitrosti njihovega tvorjenja in njihove obnovljivosti, tako, da se uporabljajo v simulacijah (npr. fizikalnih sistemih z metodo Monte Carlo, imitacijskem modeliranju), v kriptografiji ali v procesnem izvajanju. Dobre statistične značilnosti so osrednja zahteva za izhod generatorja. Med običajne razrede ustreznih algoritmov za generatorje psevdonaključnih števil spadajo:
linearni kongruenčni generatorji mešani kongruenčni generatorji linearni kongruenčni generatorji (LCG)
multiplikativni (linearni) kongruenčni generatorji
Lehmerjevi generatorji večkratni rekurzivni generatorji (MRG)
zastajajoči Fibonaccijevi generatorji (LFG)
pomikalni registri z linearno povratno vezavo (LFSR) kombinirani generatorji
Kriptografska raba zahteva tudi izhod, ki ni napovedljiv, potrebni pa so bolj izpopolnjeni modeli, ki ne vsebujejo linearnosti proprostih rešitev. V zadnjem času so iznašli več generatorjev psevdonaključnih števil, ki zagotavljajo močno naključnost, mednje pa spadajo algoritmi BBS, Fortuna in Mersenne Twister.
V splošnem je za zaupanje ali dani generator za zahtevano rabo tvori dovolj »naključna« števila potrebna skrbna matematična analiza. Von Neumman je opozarjal na nepravilno podajanje generatorjev psevdonaključnih števil kot resnično naključnih generatorjev ter leta 1949 izjavil: »Vsakdo, ki ima aritmetične metode za tvorjenje naključnih števk, je seveda v stanju greha.« Robert R. Coveyou iz Narodnega laboratorija v Oak Ridgeu je nekoč imenoval svoj članek »Tvorjenje naključnih števil je preveč pomembno, da bi ga prepustili naključju.«
Periodičnost
Generator psevdonaključnih števil se lahko zažene iz poljubnega začetnega stanja s pomočjo naključne začetne vrednosti (semena). Zaporedje bo pri enakem semenu vedno enako. Največja dolžina zaporedja preden se začne ponavljati je določena z velikostjo stanja, merjeno v bitih. Ker se dolžina največje periode lahko podvoji z vsakim bitom iz dodanega stanja, je preprosto izdelati generatorje z dovolj dolgimi periodami za veliko praktičnih rab.
Če notranje stanje generatorja vsebuje n bitov, je lahko njegova perioda dolga največ 2n, lahko pa je veliko krajša. Za nekatere generatorje se lahko dolžina periode izračuna brez, da bi se poznala v celoti. Pomikalni registri z linearno povratno vezavo (LFSR) so po navadi izbrani tako, da imajo dolžine period točno 2n−1. Linearni kongruenčni generatorji (LCG) imajo dolžine period, ki se jih lahko izračuna s faktorizacijo. Dolžine period mešanih generatorjev (brez omejitev) so približno 2n/2 v povprečju, po navadi za neponovljivim začetnim zaporedjem. Dolžina period mešanih reverzibilnih generatorjev (permutacije) je približno 2n−1 v povprečju, perioda pa bo vedno vsebovala izvorno notranje stanje (npr. ). Čeprav se bodo generatorji, ko dosežejo konec periode, ponovili, ponovljen rezultat ne pomeni, da je dosežen konec periode, ker je njegovo notranje stanje lahko večje kot njegov izhod. To je še posebej očitno pri generatorjih z 1-bitnim izhodom.
Večina algoritmov generatorjev psevdonaključnih števil daje zaporedja, ki so enakomerno porazdeljena glede na različne teste. Odprto vprašanje je in zelo pomembno za teorijo in prakso kriptografije, ali obstaja kakšna pot za razlikovanje izhoda zelo kakovostnega generatorja iz resnično naključnega zaporedja brez da bi se poznal algoritem ali algoritmi, ter začetno stanje. Varnost večine kriptografskih algoritmov in protokolov, ki rabijo generatorje psevdonaključnih števil, temelji na predpostavki, da ni mogoče razlikovati med rabo primernega generatorja psevdonaključnih števil in resnično naključnega zaporedja. Najpreprostejši zgled te odvisnosti so tokovne šifre, ki večinoma delujejo prek logične operacije izključitveni ali na odprto besedilo (plaintext) sporočila z izhodom generatorja, ki daje šifrirano besedilo (ciphertext). Izdelava kriptografsko primernih generatorjev je izredno težka, saj morajo zanje veljati dodatni kriteriji. Velikost njegove periode je pomemben činitelj v kriptografski primernosti generatorjev, ni pa edin.
Problemi z determinističnimi generatorji thumb|right|250px|Trirazsežni graf raztrosa 100.000 vrednosti, tvorjenih z generatorjem RANDU. Vsaka točka predstavlja 3 zaporedne psevdonaključne vrednosti. Lepo se vidi kako točke ležijo na 15-ih ravninah.
V praksi so v izhodu mnogih običajnih generatorjev artefakti, ki povzročajo da generatorji ne morejo izpolniti statističnih testov vzorčenj. Sem med drugim spadajo:
periode, ki so krajše od pričakovanih za nekatera stanja semen. V tem smislu se lahko takšna stanja semen imenujejo 'šibka', pomanjkanje enoličnosti porazdelitve za velike količine tvorjenih števil, korelacija zaporednih vrednosti, slaba razsežnostna porazdelitev izhodnega zaporedja, razdalje med določenimi vrednostmi, ki se pojavijo, so porazdeljene različno od tistih pri porazdelitvi z naključnim zaporedjem.
Razpon napak popačenih generatorjev seže od neopaznega (in neznanega) do zelo očitnega. Zgled za to je bil algoritem generatorja RANDU, ki se je več desetletij rabil na osrednjih računalnikih. Bil je zelo popačen, vendar njegove neustreznosti dolgo niso odkrili. Veliko raziskovalnega dela iz tistega časa na mnogih področjih, ki se je opiralo na naključno izbiro, na simulacije vrste Monte Carlo ali drugače, je veliko manj zanesljivo, kakor bi lahko bilo.
Programske napake v generatorjih psevdonaključnih števil je velikokrat težko odkriti, saj se lahko kažejo le v drobnih nepravilnostih v porazdelitvi rezultatov. Zgled takšnega hrošča so odkrili v funkciji strfry() v programski knjižnici GNU C Library.. Podrobno sledenje generatorju korakoma bo težko odkrilo napako, saj je treba tvoriti zelo veliko število izhodov in na njih izvesti pravilen statistični test.
Zgodnji pristopi
Metoda srednjega kvadrata
Von Neumann je leta 1946 predlagal računalniški generator psevdonaključni števil, znan kot metoda srednjega kvadrata.. Po njegovem algoritmu so za eno iteracijo potrebni največ štirje koraki: vzame se poljubno število, se ga kvadrira, se mu po potrebi doda vodilna ničla ali več ustreznih ničel. Pridobljeno naključno število ima srednje števke tega števila, ki se ga potem uporabi za začetno vrednost naslednje iteracije. Simbolično se lahko metoda zapiše kot:
Na primer: 1. 1111 2. 1234321 3. 01234321 8-bitno število kvadrata 4-bitnega števila 4. 2343 iskano 'naključno' število Če se ponavlja iteracija s številom 2343, se dobi naslednji rezultat 4896, nato 9708, 2452, 123, 151, 228, 519, 2693, 2522, 3604, 9888, 7725, 6757, 6435, 4092, 7444, 4131, 651, 4238, 9606, 2752, 5735, 8902, 2456, 319, 1017, 342, 1169, 3665, itn. in zaporedje:
2343489697082452123151228519269325223604988877256756643540927444413165142389606573589022456319101734211693665, ...
Von Neumann je rabil 10 mestna števila, vendar je bil postopek enak.
Problem metode »srednjega kvadrata« je, da se zaporedja sčasoma začnejo ponavljati, nekatera zelo hitro, kot na primer »0000«, »3792« (periodi 1), »5197« (perioda 2) ali »6100« (perioda 4). Von Neumann se je tega zavedal, vendar so bili za njegovo rabo zadovoljivi. Skrbelo ga je le, da bodo matematični »popravki« preprosto skrili napake, namesto da bi jih odstranili.
Za von Neumanna so bili strojni generatorji neprimerni, ker, če niso zapisovali izhoda, ki so ga tvorili, bi porabili omejene računalniške pomnilnike, ki so bili tedaj na voljo, in s tem zmožnost računalnikov pri branju in zapisovanju števil. Če bi bila števila zapisana na karticah, bi bilo potrebno veliko več časa za branje in zapisovanje. Na računalniku ENIAC, ki ga je uporabljal, je metoda »srednjega kvadrata« pridobivala števila nekaj stokrat hitreje kot branje števil iz luknjanih kartic.
Metodo srednjega kvadrata so kasneje zamenjali izpopolnjeni generatorji.
Metoda linearne kongruence
Metodo je predlagal Lehmer leta 1947. Generatorji te vrste so v računalništvu najbolj razširjeni. Sem spadajo na primer genaratorji RAND (32-bitna točnost), DRAND48 in RANF (48-bitna točnost) v programskem jeziku C in operacijskem sistemu Unix.. Ti generatorji za večino aplikacij delujejo zelo dobro, imajo pa nekaj večjih napak. Glavni problem je, da so najmanj značilni biti dobljenih števil v korelaciji, graf raztrosa urejenih trojic prikazanih v enotski hiperkocki pa kaže pravilno mrežasto zgradbo. Poleg tega je problem modul m, ki je po navadi, ker je hiter in priročen za računalnik, potenca števila 2, saj imajo dobljeni biti nizkega reda veliko korelacijo, kakor tudi koreracijo na večji razdalji za intervale, ki so potence 2.
Mersenne Twister
Algoritem Mersenne Twister (MT) iz leta 1997 Makota Macumota in Takudžija Nišimure se ogne mnogim problemov zgodnjih generatorjev. Ima velikansko dolžino periode 219937 − 1 iteracij (> 4,3), 19937 bitov notranjega stanja, je dokazano enakomerno porazdeljen v (do) 623 razsežnostih (za 32-bitne vrednosti), učinkovito uporablja pomnilnik, in se izvaja hitreje kot drugi statistično smiselni generatorji.. Kot dobra izbira za generator naključnih števil pri statističnih simulacijah in generativnem modeliranju dobiva vse večjo veljavo. Imenuje se po 24-em Mersennovem praštevilu, ki je dolžina njegove periode. Izvedba generatorja v programskem jeziku C je približno štirikrat hitrejša od funkcije rand() v običajnem C. SFMT, SIMD-oriented Fast Mersenne Twister, različica algoritma Mersenne Twister, je hitrejša, četudi se ne prevaja s podporo SIMD.
Izvirni algoritem Mersenne Twister za vse kriptografske aplikacije ne velja za primernega. Za kriptografsko rabo so predlagali različico Mersenne Twisterja..
Kriptografsko varni generatorji psevdonaključnih števil
Generator primeren za kriptografske aplikacije se imenuje kriptografsko varen generator psevdonaključnih števil (cryptographically secure PRNG (CSPRNG)). Zahteva za kriptografsko varen generator je, da ima nasprotnik, ki ne pozna semena, nepomembno prednost pri razločevanju generatorjevega izhodnega zaporedja od naključnega zaporedja. Medtem ko morajo generatorji psevdonaključnih števil ustrezati določenim statističnim testom, morajo kriptografsko varni generatorji ustrezati vsem statističnim testom, ki so omejeni na polinomski čas v velikosti semena. Čeprav te značilnosti ni moč dokazati, se lahko zagotovi velika zanesljivost s prevedbo kriptografsko varnega generatorja na problem, ki je privzeto težek, kot na primer praštevilski razcep.. V splošnem je potrebnih več let pregledovanja, da se algoritmu prizna kriptografsko varnost.
Med kriptografsko varne generatorje med drugim spadajo:
tokovne šifre bločne šifre, ki se izvajajo v števčnem ali izhodno-odzivnem načinu. generatorji, ki so bili posebej izdelani za kriptografsko varnost, kot so na primer funkcija CryptGenRandom Microsoftovega programskega vmesnika za kriptografske aplikacije CryptoAPI, algoritem Yarrow (rman) (vključen v operacijska sistema Mac OS X in FreeBSD), ter algoritem Fortuna. kombinirani generatorji psevdonaključnih števil, ki poskušajo združiti več primitivnih algoritmov generatorjev, da bi se odstranile vsakršne nenaključnosti.