Pseudonaključno število: metode pridobivanja, prednosti in slabosti

Psevdonaključno število je posebno število, ki ga ustvari poseben generator. Generator psevdonaključnih števil (PRNG), znan tudi kot deterministični generator naključnih števil (DRBG), je algoritem za generiranje zaporedja števil, katerega lastnosti se približujejo lastnostim zaporedij naključnih števil. Zaporedje, ki ga generira PRNG, ni resnično naključno, saj je v celoti odvisno od začetne vrednosti, imenovane začetno število PRNG, ki lahko vključuje resnično naključne vrednosti. Čeprav je zaporedja, ki so bližje naključnim, mogoče generirati s strojnimi generatorji naključnih števil, so generatorji psevdonaključnih števil v praksi pomembni zaradi hitrosti generiranja števil in ponovljivosti.

Aplikacije

PRNG so osrednjega pomena za aplikacije, kot so modeliranje (npr. za metode Monte Carlo), elektronske igre (npr. za proceduralno generiranje) in kriptografija. Kriptografske aplikacije zahtevajo, da izida ni mogoče predvideti na podlagi predhodnih informacij. Potrebni so kompleksnejši algoritmi, ki ne podedujejo linearnosti preprostih PRNG.

Zahteve in pogoji

Dobre statistične lastnosti so osrednja zahteva za pridobitev PRNG. Na splošno je potrebna skrbna matematična analiza, da bi lahko z gotovostjo trdili, da PRNG generira števila, ki so dovolj blizu naključnim, da ustrezajo predvideni uporabi.

John von Neumann je svaril pred napačno interpretacijo PRNG kot resnično naključnega generatorja in se šalil, da je "vsakdo, ki razmišlja o aritmetičnih metodah proizvodnje naključnih števil, zagotovo v grehu".

Uporaba spletne strani

PRNG je mogoče zagnati iz poljubnega začetnega stanja. Vedno bo ustvaril enako zaporedje, ko bo inicializiran s tem stanjem. Obdobje PRNG je opredeljeno na naslednji način: največje število vseh začetnih stanj neponovljivega zaporedja z dolžino predpone. Obdobje je omejeno na število stanj, ki se običajno meri v bitih. Ker se dolžina periode lahko podvoji z vsakim dodanim bitom "stanja", je enostavno ustvariti PRNG z dovolj velikimi periodami za številne praktične aplikacije.

Če notranje stanje PRNG vsebuje n bitov, njegova perioda ne more biti daljša od 2n rezultatov, temveč je veliko krajša. Pri nekaterih PRNG je trajanje mogoče izračunati, ne da bi obkrožili celotno obdobje. Registri z linearno povratno zvezo (LFSR) so običajno izbrani tako, da so njihove periode enake 2n − 1.

Linearni kongruentni generatorji imajo periode, ki jih lahko izračunamo s faktorjem. Čeprav PRNG ponovijo svoje rezultate, ko dosežejo konec periode, ponavljajoči se rezultat ne pomeni, da je bil dosežen konec periode, saj je lahko njegovo notranje stanje večje od njegovega izhoda; to je zlasti očitno pri PRNG z enobitnim izhodom.

Možne napake

Napake, ki jih zaznajo okvarjeni PRNG, segajo od neopaznih (in neznanih) do očitnih. Primer je algoritem naključnih števil RANDU, ki se že desetletja uporablja na glavnih računalnikih. To je bila resna pomanjkljivost, ki pa je dolgo časa ostala neopažena.

Na številnih področjih so raziskovalni članki, v katerih je bila uporabljena naključna izbira, simulacija Monte Carlo ali druge metode, ki temeljijo na LCNG, veliko manj zanesljivi, kot bi lahko bili v primeru nekakovostnih PRNG. Še danes je včasih potrebna previdnost, kot je razvidno iz opozorila v Mednarodni enciklopediji statističnih znanosti (2010).

Primer uspešne vloge

Za ponazoritev si oglejte pogosto uporabljeno programski jezik Java. Od leta 2017 se Java še vedno zanaša na linearni kongruentni generator (LCG) za svoj PRNG.

Zgodovina

Prvi PRNG, ki se je izognil resnim težavam in še vedno deloval precej hitro, je bil Mersenne Twister (opisan spodaj), ki je bil objavljen leta 1998. Od takrat so bili razviti tudi drugi visokokakovostni PRNG.

Vendar se zgodovina psevdonaključnih številk s tem ne konča. V drugi polovici 20. stoletja je standardni razred algoritmov za PRNG vključeval linearne kongruentne oscilatorje. Znano je bilo, da je kakovost LCG neustrezna, vendar boljše metode niso bile na voljo. Press in drugi (2007) so rezultate opisali takole: "Če bi s knjižničnih polic izginili vsi znanstveni članki, katerih rezultati so bili vprašljivi zaradi [LCG in sorodnih], bi na vsaki polici nastala vrzel v velikosti pesti.".

Največji napredek na področju psevdonaključnih generatorjev je bila uvedba metod, ki temeljijo na linearni rekurenci v polju dveh elementov; takšni generatorji so povezani z linearnimi premikalnimi registri s povratno informacijo. Služili so podlaga za Izum senzorjev psevdonaključnih števil.

Z izumom Mersen Twister iz leta 1997 so se zlasti izognili številnim težavam s prejšnjimi generatorji. Mersennov twister ima periodo 219937−1 iteracij (≈4,3 × 106001). Dokazana je bila enakomerna porazdelitev v (do) 623 dimenzijah (za 32-bitne vrednosti), v času uvedbe pa je bil hitrejši od drugih statistično zasnovanih generatorjev, ki so proizvajali psevdonaključna zaporedja števil.

Leta 2003 je George Marsaglia predstavil družino generatorjev xorshift, ki prav tako temelji na linearnem ponavljanju. Takšni generatorji so izjemno hitri in v kombinaciji z nelinearnim delovanjem uspešno opravijo stroge statistične teste.

Leta 2006 je bila razvita družina generatorjev WELL. Generatorji WELL v nekem smislu izboljšajo kakovost Twister Mersenne, ki ima prevelik prostor stanj in zelo počasno obnovo iz njih, z generiranjem psevdonaključnih števil z velikim številom ničel.

Kriptografija

PRNG, primeren za kriptografske aplikacije, se imenuje kriptografsko zaščiten PRNG (CSPRNG). Zahteva za CSPRNG je, da ima napadalec, ki ne pozna začetnega števila, le majhno prednost pri razlikovanju izhodnega zaporedja generatorja od naključnega zaporedja. Z drugimi besedami, medtem ko mora PRNG opraviti le nekatere statistične teste, mora CSPRNG opraviti vse statistične teste, ki so omejeni s polinomskim časom glede na velikost semena.

Čeprav dokazovanje te lastnosti presega sedanjo raven teorije računske zahtevnosti, lahko prepričljive dokaze zagotovimo z redukcijo CSPRNG na problem, ki velja za zapletenega, podobno kot faktorizacija celih števil. Na splošno lahko traja več let pregledovanja, preden se algoritem lahko potrdi kot CSPRNG.

Pokazalo se je, da je agencija NSA v generator psevdonaključnih številk Dual_EC_DRBG, ki ga je certificiral NIST, verjetno vstavila asimetrična zadnja vrata.

Algoritmi psevdorandomnih števil

Večina algoritmov PRNG ustvarja zaporedja, ki so enakomerno porazdeljena po katerem koli od več testov. To je odprto vprašanje. To je eno osrednjih vprašanj v teoriji in praksi kriptografije: ali je mogoče na kakršen koli način razlikovati izhod visokokakovostnega PRNG od resnično naključnega zaporedja? Pri tem prepoznavalnik ve, da je bil uporabljen znani algoritem PRNG (vendar ne stanje, v katerem je bil inicializiran) ali pa je bil uporabljen resnično naključni algoritem. Razlikovati mora med njima.

Varnost večine kriptografskih algoritmov in protokolov, ki uporabljajo PRNG, temelji na predpostavki, da je nemogoče razlikovati uporabo ustreznega PRNG od uporabe resnično naključnega zaporedja. Najpreprostejši primeri te odvisnosti so tokovne šifre, ki najpogosteje delujejo tako, da izključijo ali pošljejo sporočila z navadnim besedilom z izhodom PRNG, s čimer ustvarijo šifrirano besedilo. Razvoj kriptografsko ustreznih PRNG je izjemno težaven, saj morajo izpolnjevati dodatna merila. Velikost periode je pomemben dejavnik kriptografske primernosti PRNG, vendar ne edini.

Prvi računalniški PRNG, ki ga je leta 1946 predlagal John von Neumann, je znan kot metoda srednjega kvadrata. Algoritem je naslednji: vzamemo poljubno število, ga kvadriramo, odstranimo srednji števki dobljenega števila kot "naključno število" in to število uporabimo kot začetno število za naslednjo iteracijo. Na primer, če število 1111 delimo v kvadrat, dobimo 1234321, kar lahko zapišemo kot 01234321, osemmestno število, pomnoženo s štirimestnim številom. Tako dobimo 2343 kot "naključno" število. Rezultat ponovitve tega postopka je 4896 in tako naprej. Von Neumann je uporabljal desetmestna števila, vendar je bil postopek enak.

Slabosti metode "povprečnega kvadrata"

Težava pri metodi srednjega kvadrata je, da se vsa zaporedja ponavljajo, nekatera zelo hitro, na primer: 0000. Von Neumann se je tega zavedal, vendar je menil, da pristop zadostuje za njegove namene, in ga je skrbelo, da bi matematični "popravki" napake preprosto skrili, namesto da bi jih odpravili.

Von Neumann je menil, da so strojni generatorji naključnih in psevdonaključnih števil neprimerni: če niso beležili ustvarjenega rezultata, jih pozneje ni bilo mogoče preveriti glede napak. Če bi zapisovali svoje rezultate, bi izčrpali omejeni razpoložljivi pomnilnik računalnika in s tem njegovo zmožnost branja in pisanja številk. Če bi bile številke zapisane na karticah, bi za pisanje in branje potrebovali veliko več časa. Na računalniku ENIAC je uporabil metodo "srednjega kvadrata" in postopek pridobivanja psevdonaključnih številk izvedel nekaj stokrat hitreje kot branje številk s perforiranih kartic.

Metodo srednjega kvadratnega koeficienta so od takrat nadomestili bolj izpopolnjeni generatorji.

Inovativna metoda

Nedavna novost je kombinacija srednjega kvadrata z Weylovim zaporedjem. Ta metoda zagotavlja visoko kakovost izdelkov v daljšem časovnem obdobju. Pomaga pridobiti najboljše formule psevdonaključnih števil.