Generator psevdonaključnih števil

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Generátor psévdonakljúčnih števíl (angleško pseudorandom number generator, kratica PRNG) ali tudi deterministrični generator naključnih bitov (deterministic random bit generator (DRBG)[1]), je algoritem, po navadi računalniški, 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
 x_{n+1} \equiv \left( a x_{n} + b \right) \!\!\!\! \pmod{m}, \quad (m > 0, m > a \ge 2, m \ge x_{0} > 0, m > b \ge 0, n \ge 0)
  • multiplikativni (linearni) kongruenčni generatorji
 x_{n+1} \equiv a x_{n} \!\!\!\! \pmod{m}, \quad (b = 0)
  • 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)
 x_{n+1} \equiv x_{n-j} \star x_{n-k+1} \!\!\!\! \pmod{m}, \quad (m > j, k > j, j > 0)

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[uredi | uredi kodo]

Generator psevdonaključnih števil lahko zaženemo 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 lahko dolžino periode izračunamo brez, da bi jo poznali 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 jih lahko izračunamo 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. [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 poznali algoritem ali algoritme, 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[uredi | uredi kodo]

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-tih 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.[2] 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[uredi | uredi kodo]

Metoda srednjega kvadrata[uredi | uredi kodo]

Von Neumann je leta 1946 predlagal računalniški generator psevdonaključni števil, znan kot metoda srednjega kvadrata.[3] Po njegovem algoritmu so za eno iteracijo potrebni največ štirje koraki: vzamemo poljubno število, ga kvadriramo, mu po potrebi dodamo vodilno ničlo ali več ustreznih ničel. Pridobljeno naključno število ima srednje števke tega števila, ki ga potem uporabimo za začetno vrednost naslednje iteracije. Simbolično lahko metodo zapišemo 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 ponavljamo iteracijo s številom 2343, dobimo 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[uredi | uredi kodo]

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.[4] 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[uredi | uredi kodo]

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 · 106001), 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.[5] Kot dobra izbira za generator naključnih števil pri statističnih simulacijah in generativnem modeliranju dobiva vse večjo veljavo. Imenuje se po 24-tem 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.[6]

Izvirni algoritem Mersenne Twister za vse kriptografske aplikacije ne velja za primernega. Za kriptografsko rabo so predlagali različico Mersenne Twisterja.[7]

Kriptografsko varni generatorji psevdonaključnih števil[uredi | uredi kodo]

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.[8] 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[uredi | uredi kodo]

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.[9]

Neenakomerni generatorji[uredi | uredi kodo]

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

Najprej potrebujemo porazdelitveno funkcijo 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«, dobimo:

 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[uredi | uredi kodo]

Opombe in sklici[uredi | uredi kodo]

  1. ^ "Recommendation for Key Management – Part 1: General" (PDF). NIST (v angleščini). 2007. Pridobljeno dne 2012-1-21. 
  2. ^ Jarno (2007).
  3. ^ Rahimov, Babaie, Hassanabadi (2011).
  4. ^ Coddington (1997).
  5. ^ Macumoto, Nišimura (1998).
  6. ^ "Comparison of speed" (v angleščini). Pridobljeno dne 2012-02-15. 
  7. ^ Macumoto, Nišimura, Hagita, Saito (2005).
  8. ^ Yan (2007), str. 73.
  9. ^ Schindler (1999).

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]