Generator psevdonaključnih števil

Generátor psévdonakljúčnih števíl (angleško pseudorandom number generator, 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)

$x_{n+1}\equiv \left(ax_{n}+b\right)\!\!\!\!{\pmod {m}},\quad (m>0,m>a\geq 2,m\geq x_{0}>0,m>b\geq 0,n\geq 0)$

• multiplikativni (linearni) kongruenčni generatorji

$x_{n+1}\equiv ax_{n}\!\!\!\!{\pmod {m}},\quad (b=0)$

• Lehmerjevi generatorji

• večkratni rekurzivni generatorji (MRG)

$x_{n+1}\equiv (a_{1}x_{n}+a_{2}x_{n-1}\dots +a_{k}x_{n-k+1}+b)\!\!\!\!{\pmod {m}},\quad (k>1)$

• zastajajoči Fibonaccijevi generatorji (LFG)

$x_{n+1}\equiv x_{n-j}\star x_{n-k+1}\!\!\!\!{\pmod {m}},\quad (m>j,k>j,j>0)$

• 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č 2ⁿ, 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 2ⁿ−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 2^n/2 v povprečju, po navadi za neponovljivim začetnim zaporedjem. Dolžina period mešanih reverzibilnih generatorjev (permutacije) je približno 2ⁿ⁻¹ v povprečju, perioda pa bo vedno vsebovala izvorno notranje stanje (npr. [1]). Č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

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:

$x_{n+1}\equiv {\frac {x_{n}^{2}}{2^{3a/4}}}\!\!\!\!{\pmod {2^{a/4}}}\!\,.$

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 2¹⁹⁹³⁷ − 1 iteracij (> 4,3×10^{7003600100000000000♠6001}), 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.
• posebne izvedbe, ki temeljijo na predpostavki matematične strogosti, med katerimi sta na primer algoritem Micali-Schnorr in algoritem BBS, ki zagotavljata močno varnostno zanesljivost. Takšni algoritmi so v primerjavi s tradicionalnimi izvedbami počasni in za mnoge aplikacije nepraktični.

Kriteriji vrednotenja BSI

Nemški Zvezni urad za varnost v informacijski tehnologiji (BSI) je uvedel štiri kriterije/razrede za kakovost determinističnih generatorjev naključnih števil. Ti so:

• K1 — zaporedje naključnih števil z majhno verjetnostjo vsebovanja enakih zaporednih elementov.
• K2 — zaporedje števil, ki jih ni moč razlikovati od 'resnično naključnih' števil glede na določene statistične teste. Testi so: test monobitnosti (enako število ničel in enic v zaporedju), test poker (poseben primer testa hi-kvadrat), test sekvenca (šteje frekvenco sekvenc različnih dolžin), test dolge sekvence (preverja ali obstaja sekvenca z dolžino 34 ali več v 20.000 bitih zaporedja) — oba iz BSI2 (AIS 20, v. 1, 1999) in FIPS (140-1, 1994), ter test avtokorelacije. V bistvu so te zahteve preskus kako dobro je zaporedje bitov: ali ima enako pogosto ničle in enice; po zaporedju n ničel (ali enic), je naslednji bit enica (ali ničla) z verjetnostjo 1/2; vsako izbrano podzaporedje ne vsebuje podatkov o naslednjem elementu ali elementih v zaporedju.
• K3 — za kateregakoli napadalca je (za vse praktične namene) nemogoče izračunati, ali drugače uganiti, iz poljubno danega podzaporedja kakšno predhodno ali naslednjo vrednost v zaporedju, kot tudi ne kakšno notranje stanje generatorja.
• K4 — za vse praktične namene je za kateregakoli napadalca iz notranjega stanja generatorja nemogoče izračunati ali uganiti kakšna predhodna števila v zaporedju ali kakšna predhodna notranja stanja generatorja.

Za kriptografsko rabo so spremenljivi le generatorji, ki so v skladu s standardoma K3 ali K4.

Neenakomerni generatorji

Števila izbrana iz neenakomerne porazdelitve se lahko tvorijo z generatorji psevdonaključnih števil s pomočjo enakomerne porazdelitve in funkcije, ki povezuje ti dve porazdelitvi.

Najprej se potrebuje porazdelitvena funkcija $F(b)$ ciljne porazdelitve $f(b)$:

$F(b)=\int _{-\infty }^{b}f(b'){\rm {d}}b'\!\,.$

Pri tem je $0=F(-\infty )\leq F(b)\leq F(\infty )=1$. S pomočjo naključnega števila c iz enakomerne porazdelitve kot verjetnostne gostote za »premostitev« se dobi:

$F(b)=c\!\,,$

tako, da je:

$b=F^{-1}(c)\!\,$

število, naključno izbrano iz porazdelitve $f(b)$.

Inverzna zbirna normalna porazdelitev $\operatorname {erf} ^{-1}(x)$ z idealnim enakomernim generatorjem psevdonaključnih števil z območjem (0, 1) kot vhodom $x$ bi na primer dala zaporedje (le pozitivnih) vrednosti z normalno porazdelitvijo, pri čemer

• je treba pri praktičnih predstavitvah števil neskončne »konce« porazdelitve odrezati na končne vrednosti,
• je treba ponavljajoče izračunavanje funkcije $\operatorname {erf} ^{-1}(x)$ skrčiti za hitrejše tvorjenje števil, na primer z metodo, kot je algoritem zigurat.

Podobni premisleki veljajo za druge neenakomerne porazdelitve, kot sta Rayleighjeva ali Poissonova porazdelitev.

Glej tudi

• seznam generatorjev naključnih števil
• psevdonaključnost
• psevdonaključno dvojiško zaporedje
• naključnost

Viri

• Coddington, Paul D. (1997). »Random number generators for parallel computers« (PDF). Northeast Parallel Architecture Center. Paper 13.
• Entacher, Karl (1997). »A collection of selected pseudorandom number generators with linear structures« (PDF).
• Jarno, Aurelien (2007). »strfry() gives skewed distributions«. Bugzilla, Bug 4403 (v angleščini). Pridobljeno 14. februarja 2012.
• Macumoto, Makoto; Nišimura, Takudži (1998). »Dynamic Creation of Pseudorandom Number Generators« (PDF) (v angleščini). Pridobljeno 21. februarja 2012.
• Macumoto, Makoto; Nišimura, Takudži; Hagita, Mariko; Saito, Macuo (2005). »Cryptographic Mersenne Twister and Fubuki stream/block cipher« (PDF) (v angleščini). Pridobljeno 15. februarja 2012.
• Mareković, Nikola. »Generatori slučajnih brojeva/Primjer implementacije«. FER, ZEMRIS (v hrvaščini). Arhivirano iz prvotnega spletišča dne 28. avgusta 2009. Pridobljeno 21. januarja 2012.
• Rahimov, Hamed; Babaie, Majid; Hassanabadi, Hassan (april 2011). »Improving Middle Square Method RNG Using Chaotic Map«. Applied Mathematics. Zv. 2, št. 4. str. 482–486. doi:10.4236/am.2011.24062.{{navedi revijo}}: Vzdrževanje CS1: samodejni prevod datuma (povezava)
• Schindler, Werner (1999). »Functionality Classes and Evaluation Methodology for Deterministic Random Number Generators« (PDF). Zvezni urad za varnost v informacijski tehnologiji (v angleščini). Arhivirano iz prvotnega spletišča (PDF) dne 27. februarja 2012. Pridobljeno 17. februarja 2012.
• Soban, Bogdan (Oktober–november 1999). »Izvirni način ustvarjanja računalniških grafik« (PDF). Organizacija. Zv. 32, št. 8–9. str. 519–524. Arhivirano iz prvotnega spletišča (PDF) dne 4. marca 2016. Pridobljeno 21. januarja 2012.
• Yan, Song. Y. (2007). Cryptanalytic Attacks on RSA. Springer. ISBN 9780387487410.
• »Probabilistic Algorithms: Spring 2001 Course« (v angleščini). 2001. Pridobljeno 22. januarja 2012.

Zunanje povezave

• Random Number Generators Arhivirano 2012-01-29 na Wayback Machine., stran o generatorjih PNŠ skupine pLab, Oddelek za matematiko, Univerza v Salzburgu (angleško)
• Introduction to Random Number Generators Univerza v Notre Damu (angleško)