Generisanje slučajnih brojeva

Generator slučajnih brojeva (engl. random number generator, RNG) je računarski ili fizički uređaj dizajniran da generiše niz brojeva ili simbola koji se ne mogu razumno predvideti bolje nego što bi slučajnošću.

Kada se baci kockica, dobije se slučajan broj između 1 i 6.

Razne primene slučajnosti su dovele do razvoja više različitih metoda za generisanje slučajnih brojeva, neke od tih metoda su postojale još od drevnih vremena, uključujući kocke, bacanje novčića, mešanje karata, korišćenje stabljika hajdučke trave za proricanje u „Ji đingu”, i mnoge druge tehnike. Zbog mehaničke prirode ovih tehnika, generisanje velikog broja dovoljno slučajnih brojeva (bitno u statistici) zahteva puno posla i/ili vremena. Tako, rezultati bi ponekad bili sakupljani i distribuirani kao tabele slučajnih brojeva. Danas, nakon dolaska računarskih generatora slučajnih brojeva, veliki broj lutrija kojima upravljaju vlade su počele da koriste generatore slučajnih brojeva umesto tradicionalnijih metoda izvlačenja. Takođe se koriste za određivanje šansi modernih slot mašina.

Više računarskih metoda postoji za generisanje slučajnih brojeva. Mnogi ne uspevaju da dostignu cilj prave slučajnosti, iako ispunjavaju, sa varirajućim uspehom, neke od statističkih testova slučajnosti namenjenih da mere koliko su nepredvidivi njihovi rezultati (to jest, do kog stepena su njihovi šabloni primetni). Ipak, pažljivo dizajnirani kriptografsko osigurani metodi generisanja slučajnih brojeva takođe postoje, kao što su oni koji su zasnovani na algoritmu hajdučke trave, Fortuna (GPNB), i drugi.

Praktične primene i upotrebe

Generatori slučajnih brojeva imaju primene u kockanju, statističkom uzimanju primeraka, računarskoj simulaciji, kriptografiji, kompletno stohastičkom dizajnu, i drugim oblastima gde je poželjno stvarati nepredvidiv rezultat. Generalno, u primenama gde je nepredvidljivost glavna, kao što je u bezbednostnim primenama, hardverski generatori slučajnih brojeva su uglavnom poželjniji od pseudo-slučajnih algoritama.

Generatori slučajnih brojeva su vrlo korisni pri razvijanju simulacija Monte Karlo metoda, jer je debagovanje olakšano mogućnošću da se stvaraju isti nizovi slučajnih brojeva počevši od istog slučajnog semena (енгл. random seed). Takođe se koriste u kriptografiji - dok god je seme tajna. Pošiljalac i primalac mogu da generišu isti skup brojeva i da ih automatski koriste kao ključeve.

Generisanje pseudo slučajnih brojeva je bitan i čest zadatak u programiranju. Dok kriptografija i određeni numerički algoritmi zahtevaju veoma visok stepen pseudo slučajnosti, mnoge druge operacije zahtevaju samo skromnu količinu nepredvidljivosti. Neki prosti primer bi mogao biti prikazivanje korisniku „Slučajni citat dana”, ili određivanje kojim putem bi se kompjuterski kontrolisan neprijatelj kretao u video igri. Slabiji oblici slučajnosti se koriste u heš algoritmima i u pravljenju amortizovanih pretraga i algoritama za sortiranje.

Neke primene koje na prvi pogled izgledaju da su prikladne za slučajnost u stvari nisu tako proste. Na primer, sistem koji "slučajno" odabira pesme za pozadinsku muziku mora samo da izgleda slučajno, i možda čak ima načine da kontroliše izbor muzike: pravi slučajni sistem ne bi imao ograničenja da se ista stvar pojavi dva ili tri puta zaredom.

"Pravi" naspram pseudo-slučajnih brojeva

Postoje dve glavne metode koje se koriste za generisanje slučajnih brojeva. Prva metoda meri neku fizički pojavu za koju se očekuje da će biti slučajna, a zatim se u procesu merenja eliminiše ne-slučajnost. Izvorni primeri uključuju merenje atmosferskog šuma, termičkog šuma, i ostalih eksternih elektromagnetnih i kvantnih pojava. Na primer, kosmičko pozadinsko zračenje ili radioaktivni raspad mereni tokom kratkih perioda predstavljaju izvor prirodne entropije.

Brzina kojom entropija može da bude sakupljena iz prirodnih izvora zavisi od osnovnih fizičkih pojava koje se mere. Prema tome, za izvore prirodnih pojavljivanja „prave” entropije se kaže da su blokirajući – oni su ograničeni dok nije sakupljeno dovoljno zahtevane entropije. Na nekim sistemima sličnim Juniksu, uključujući većinu Linuks distribucija, pseudo datoteka /dev/random neće dopustiti čitanje dok nije sakupljeno dovoljno entropije iz okoline. Zbog ovog blokiranja, velika sjedinjena čitanja iz /dev/random, kao što je popunjavanje hard diska slučajnim bitovima, može često da uspori sistem koji koriste ovaj tip izvora entropije.

Druga metoda koristi računarske algoritme koji mogu da proizvedu duge nizove od navodno slučajnih rezultata, koji su u stvari u potpunosti određeni manjom početnom vrednošću, poznata kao semena vrednost ili ključ. Kao rezultat, ukupni pseudo-slučajni niz se može stvoriti ako je semena vrednost poznata. Ovaj tip generisanja slučajnih brojeva se često naziva pseudo-slučajni generator brojeva. Ovaj tip generatora se ne oslanja na prirodno pojavljivanje entropije, iako može biti periodično ubačeno seme od strane prirodnih izvora. Ovaj tip generatora ne mora da blokira čitanje, pa nisu ograničeni eksternim događajima, što čini velika sjedinjena čitanja mogućim.

Neki sistemi imaju hibridan pristup, pružajući slučajnost sakupljenu iz prirodnih izvora kada je to moguće, i povlače se periodično da ponovo postave seme softverskim kriptografsko sigurnim pseudo-slučajnim generatorima brojeva (KSPNGB). Povlačenje se dešava kada željena brzina čitanja slučajnosti prevazilazi sposobnost prirodnog sakupljanja da bi mogao da zadovolji potražnju. Ovaj pristup zaobilazi ograničeno blokiranje generatora slučajnih brojeva zasnovanih na sporijim i okolinskim metodama.

Dok generator pseudo-slučajnih brojeva baziran samo na determinističkoj logici ne može nikad biti klasifikovan kao „pravi” izvor slučajnih brojeva u najbukvalnijem smislu reči, u praksi su dovoljni čak i za zahtevne sigurnosno-kritične aplikacije. Pažljivo dizajnirani i implementirani pseudo-slučajni generatori brojeva mogu da se koriste za sigurnosno-kritične kriptografske svrhe, kao što je slučaj sa algoritmom hajdučke trave i fortunom. Algoritam hajdučke trave je osnova za /dev/random izvora entropije na FreeBSD, Aiks, OS X, NetBSD i drugima. OpenBSD takođe koristi pseudo-slučajni numerički algoritam zasnovan na ChaCha20 poznat kao arc4random.

Metode generisanja

Fizičke metode

Najranije metode za generisanje slučajnih brojeva, kao što su kocke, bacanje novčića i rulet, se i dalje koriste danas, pre svega u igrama i kockanju jer su prespore za većinu primena u statistici i kriptografiji.

Fizički generator slučajnih brojeva može da se bazira na suštinski slučajnom atomskom ili subatomskom fizičkom fenomenu čija nepredvidivost može da se prati do zakona kvantne mehanike. Izvori entropije uključuju radioaktivnost, termalni šum, statički šum, lavinski šum u Zener diodama, derivacija satova, tempiranje pokreta u tvrdom disku čitaj/piši glave, i radio šuma. Ipak, fizički fenomeni i alati koji se koriste da ih mere generalno sadrže asimetrije i sistematske greške koje čine njihov rezultat ne zaista uniformno slučajan. Izvlačivač slučajnosti, kao što je kriptografska heš funkcija, mogu da se koriste da se približi uniformnoj raspodeli bitova iz neuniformnog slučajnog izvora, mada pri nižoj brzini bitova.

Razni maštoviti načini skupljanja ove entropijske informacije su osmišljeni. Jedna tehnika je da se pokrene heš funkcija na jednu sliku od video striminga iz nepredvidivog izvora. Lavarand je koristio ovu tehniku sa slikama na kojima se nalazi više lava lampi. HotBits meri radioaktivni raspad sa Gajger-Miler cevima, dok Random.org koristi promene u amplitudama atmosferskog šuma snimljenog normalnim radiom.

Drugi čest izvor entropije je ponašanje ljudskih korisnika sistema. Iako se ljudi ne smatraju dobrim generatorom slučajnosti kad se to od njih zahteva, oni generišu slučajna ponašanja prilično dobro u kontekstu igranja igara pomešanih strategija. Neki kompjuterski softveri u vezi sa bezbednošću zahtevaju da korisnik napravi poduži niz pokreta miša ili pritiska tastature da se napravi dovoljna entropija potrebna za generisanje slučajnih ključeva ili da se inicijalizuje pseudo-slučajni generator brojeva.

Računarske metode

Većina računski generisanih slučajnih brojeva koristi pseudo-slučajne generatore brojeva (PSGB) koji su algoritmi sa mogućnošću automatskog generisanja dugačkog niza brojeva sa dobrim slučajnim svojstvima ali se eventualno niz ponavlja (ili količina utrošene memorije raste bez granica). Ovaj tip slučajnih brojeva su dovoljno dobri u mnogim situacijama ali nisu slučajni koliko i bacanje novčića ili kockica. Niz vrednosti generisan ovakvim algoritmima je obično određen fiksiranom vrednošću koja se naziva seme (енгл. seed). Jedan od najrasprostranjenijih PSGB je linearni kongruentalni generator, koji koristi rekurentnost

$X_{n+1}=(aX_{n}+b)\,{\textrm {mod}}\,m$

da bi generisao brojeve, gde su $a$, $b$ and $m$ veliki brojevi, i $X_{n+1}$ je sledeći u $X$ seriji pseudo-slučajnih brojeva. Najveći broj brojeva koje ova formula može proizvesti je modulo $m$. Da bi se izbegla neka ne-slučajna svojstva linearnog kongruentalnog generatora, nekoliko takvih generatora brojeva sa malo drukčijim vrednostima koeficijenta umnožitelja $a$, se mogu koristiti paralelno, sa „master” generatorom brojeva koji odabira između mnoštvo drugih generatora.

Metod olovke i papira za generisanje slučajnih brojeva je takozvani metod srednjeg kvadrata kojeg je za upotrebu predložio Džon fon Nojman. Iako je dati metod jednostavan za implementaciju, njegove izlazne vrednosti su niskog kvaliteta i imaju ozbiljne nedostatke, jedan od tih nedostataka je da dati izlazni niz skoro uvek konvergira ka nuli.

Većina programskih jezika sadrži funkcije ili datoteke zaglavlja sa rutinama koja obezbeđuju generatore slučajnih brojeva. Oni su obično dizajnirani da obezbede slučajan bajt, reč ili broj u pokretnom zarezu ravnomerno raspodeljen između 0 i 1.

Kvalitet slučajnosti ovih funkcija datoteka zaglavlja varira od u potpunosti predvidivih izlaznih vrednosti do kriptografski sigurnih vrednosti. Uobičajen generator slučajnih brojeva u mnogim jezicima, uključujući Pajton, Rubi, R, IDL i PHP je zasnovan na algoritmu Mersenne Twister i nije dovoljan za kriptografske namene, kao što je i rečeno u dokumentaciji nabrojanih programskih jezika. Takve funkcije datoteka zaglavlja obično imaju loša statistička svojstva i neke će ponavljati šablone nakon samo nekoliko desetina hiljada pokušaja. Ove funkcije se obično inicijaliziraju koristeći časovnik samog računara kao seme, pošto takav časovnik obično izračunava vreme u milisekundama, što je daleko više od preciznosti čoveka. Date funkcije mogu da obezbede dovoljno slučajnosti za neke zadatke (npr. video igre) ali su neprikladne za zadatke koji zahtevaju slučajnost visokog kvaliteta, kao što je slučaj u kriptografiji, statistici i numeričkoj analizi.

Izvori slučajnih brojeva mnogo višeg kvaliteta su dostupni na većini operativnih sistema; npr. /dev/random na mnogim Juniks baziranim operativnim sistemima kao što su, Linuks, OS X, IRIKS i Solaris, ili CryptGenRandom za Windows. Većina programskih jezika, uključujući gore navedene, obezbeđuju načine za generisanje visoko kvalitetnih slučajnih brojeva.

Generisanje iz raspodele verovatnoće

Postoji nekoliko metoda generisanja slučajnog broja baziranih na raspodeli verovatnoće. Ove metode uključuju transformisanje (uniformnog) slučajnog broja na neki način. Zbog ovoga, date metode rade podjednako dobro i prilikom generisanja pseudo-slučajnih brojeva i „pravih” slučajnih brojeva. Jedna metoda, koja se naziva metoda inverzije, uključuje integrisanje do površine veće ili jednake slučajnom broju (koja bi trebala da bude generisana između 0 i 1 radi pravilne raspodele). Druga metoda, koja se naziva metoda prihvatanja-odbijanja, uključuje odabiranje $x$ i $y$ vrednosti i testiranja da li je funkcija od $x$ veća od vrednosti $y$. Ako jeste, prihvata se vrednost $x$, u suprotnom $x$ vrednost se odbija i algoritam se pokreće ponovo.

Ručne metode

Generisanje slučajnih brojeva se može obaviti od strane ljudi, razne ulazne vrednosti se prikupljaju od krajnjih korisnika i koriste kao izvor za generaciju slučajnosti. Međutim, većina istraživanja su pronašla da ljudi imaju neki stepen predvidivosti prilikom pokušaja generisanja slučajnog niza npr. brojeva ili slova.. Tako da ovaj pristup nije u širokoj upotrebi.

Naknadno procesiranje i statističke provere

Čak i kada je dat izvor verovatno slučajnih brojeva (dat od strane generatora zasnovanih na kvantnoj mehanici), dobijanje brojeva koji su u potpunosti slučajni zahteva obazrivost. Pored toga, ponašanje ovih generatora se često menja ujedno sa temperaturom, voltažom napajanja, starošću uređaja ili usled drugih spoljašnjih faktora. Slično tome, softverski bag u algoritmu za generisanje pseudo-slučajnih brojeva, ili hardverski bag u hardveru na kome generator radi, može biti komplikovan za otkrivanje.

Generisani slučajni brojevi su ponekad izloženi statističkim proverama pre upotrebe da bi se garantovalo da osnovni izvor još uvek radi, a onda se taj niz brojeva i naknadno procesuira da bi se poboljšala njegova statistička svojstva. Primer bi bio TRNG9803 uređaj za generisanje slučajnih brojeva, koji koristi veličinu entropije kao hardverski test, a onda naknadno procesuira slučajni niz pomeračko registarskim šifrantom. Obično je teško koristiti statističke testove radi validacije generisanih slučajnih brojeva. Vang i Nikol su predložili metodu statističkog testiranja baziranog na distanci kako bi se ustanovile slabosti nekih generatora slučajnosti.

Ostala razmatranja

Slučajni brojevi ravnomerno raspodeljeni između 0 i 1 mogu biti korišćeni za generisanje slučajnih brojeva bilo koje željene raspodeljenosti njihovim provlačenjem kroz inverznu funkciju raspodele željene raspodele (pogledati Inverse_transform_sampling). Inverzne funkcije raspodele se takođe nazivaju kvantilne funkcije. Da bi se generisao par statistički nezavisnih normalno raspodeljenih slučajnih brojeva (x, y), prvo je potrebno generisati polarne koordinate (r, ϴ), gde je r~χ₂² i θ~uniformno(0,2π) (pogledati Boks-Miler transformaciju).

Neki 0 do 1 generatori slučajnih brojeva uključuju 0 ali isključuju 1, dok drugi uključuju ili isključuju oba.

Izlazi većeg broja nezavisnih generatora slučajnih brojeva se mogu kombinovati (na primer, upotrebom bitovske operacije ekskluzivne disjunkcije) da bi se obezbedila slučajnost brojeva koja je dobra bar toliko koliko je dobar najbolji od pojedinačnih generatora slučajnih brojeva. Ovo se još i naziva beljenje softvera.

Računski i hardverski generatori slučajnih brojeva se nekada kombinuju radi odražavanja kvaliteta oba tipa. Računski generatori obično generišu pseudo-slučajne brojeve mnogo brže nego hardverski generatori, dok hardverski generatori mogu generisati „pravu slučajnost”.

Slabo diskrepantni nizovi kao alternativa

Neka izračunavanja koja koriste generatore slučajnih brojeva se mogu sažeti na izračunavanja konačne ili srednje vrednosti, kao što su izračunavanja integrala Monte Karlovom metodom. Za ovakve probleme moguće je naći preciznija rešenja upotrebom nizova male nedoslednosti koji se još nazivaju kvazi-slučajnim brojevima. Takvi nizovi imaju određeni obrazac koji ravnomerno popunjava praznine, kvalitativno govoreći; pravi slučajni niz može imati, a obično i ima, veće praznine.

Aktivnosti i demonstriranja

Navedene stranice obezbeđuju uzorke slučajnih brojeva:

1. SOCR sadrži brojne interaktivne aktivnosti i demonstracije generisanja slučajnih brojeva upotrebom Java apleta.
2. Kvantna Optička Grupa (енгл. The Quantum Optics Group) na ANU generiše slučajne brojeve poreklom iz kvantnog vakuuma. Vi možete skinuti primerak slučajnih brojeva posetom njihove stranice istraživanja kvantnih generatora slučajnih brojeva.
3. Random.Org Архивирано на сајту Wayback Machine (5. јун 2020) generiše slučajne brojeve čiji je izvor slučajnost u atmosferskom šumu. Posetite njihovu stranicu Архивирано на сајту Wayback Machine (24. фебруар 2011) da biste dobili uzorak.
4. Quantum Random Bit Generator Service na Institutu Ruđer Bošković prikuplja slučajnost iz kvantnog procesa emisije fotona u poluprovodnicima. Oni obezbeđuju raznovrsne načine prikupljanja podataka, uključujući i datoteke zaglavlja za nekoliko programskih jezika.

Bekdor

Pošto kriptografija velikim delom zavisi od kriptografski bezbednog generatora slučajnih brojeva za generisanje ključa i kriptografskog broja, ukoliko je generator brojeva predvidiv, on se može koristiti kao bekdor od strane napadača radi razbijanja enkripcije.

Smatra se da je Državna bezbednosna služba (енгл. National Security Agency / NSA) umetnula bekdor u NIST-ov kriptografski bezbedan generator brojeva Dual_EC_DRBG. Ako se na primer SSL veza formira koristeći ovaj generator slučajnih brojeva, onda bi po Metju Grinu to omogućilo NSA da odredi stanje generatora slučajnih brojeva, i time eventualno bude u stanju da očita sve podatke poslate preko SSL veze. Iako je bilo očigledno da je Dual_EC_DRBG bio jako loš i moguće je da je bio bekdorovan još dugo pre nego što je NSA bekdor bio potvrđen 2013, dati algoritam je video značajnu upotrebu u praksi do 2013, na primer od strane istaknute bezbednosne kompanije RSA Security. Potom je bilo i optužbi da je RSA Obezbeđenje namerno uključilo NSA bekdor u svoju produkciju. RSA je porekla namerno uključivanje bekdora u svoje proizvode.

Takođe je bilo teoretisano da se hardverski generatori slučajnih brojeva mogu tajno modifikovati da imaju manji stepen entropije nego što je navedeno, što bi dovelo do toga da enkripcija koristeći hardverske generatore slučajnih brojeva bude podležna napadima. Jedan od takvih metoda koji je publikovan radi modifikovanjem čipa, što bi bilo neprimetno optičkom obrnutom-inženjeringu. Na primer, za generisanje slučajnih brojeva na Linuksu, smatra se neprihvatljivim da se koristi Intelov RdRand hardver generator slučajnih brojeva bez mešanja RdRand izlaza sa drugim izvorima entropije da bi se neutralisao bilo koji bekdor u hardverskom generatoru slučajnih brojeva, posebno nakon otkrića NSA-ovog Bulran programa.

Literatura

• Donald Knuth (1997). „Chapter 3 – Random Numbers”. The Art of Computer Programming. Vol. 2: Seminumerical algorithms (3 изд.). 
• Kroese, D. P.; Taimre, T.; Botev, Z.I. (2011). „Chapter 1 – Uniform Random Number Generation”. nb Handbook of Monte Carlo Methods. New York: John Wiley & Sons. стр. 772. ISBN 978-0-470-17793-8. 
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). „Chapter 7. Random Numbers”. Numerical Recipes: The Art of Scientific Computing (3rd изд.). New York: Cambridge University Press. ISBN 978-0-521-88068-8. Архивирано из оригинала 11. 08. 2011. г. Приступљено 15. 04. 2016. 
• NIST SP800-90A, B, C series on random number generation

Spoljašnje veze

• Clewett, James. „Random Numbers”. Numberphile. Brady Haran. Архивирано из оригинала 19. 03. 2016. г. Приступљено 15. 04. 2016. 
• jRand Архивирано на сајту Wayback Machine (1. април 2017) a Java-based framework for the generation of simulation sequences, including pseudo-random sequences of numbers
• Random number generators in NAG Fortran Library
• Randomness Beacon at NIST, broadcasting full-entropy bit-strings in blocks of 512 bits every 60 seconds. Designed to provide unpredictability, autonomy, and consistency.
• A system call for random numbers: getrandom(), a LWN.net article describing a dedicated Linux system call
• . doi:10.1007%2F978-3-319-11203-9_26 .  Statistical Properties of Pseudo Random Sequences and Experiments with PHP and Debian OpenSSL. ISBN 978-3-319-11203-9. 
• Cryptographic ISAAC pseudorandom lottery numbers generator
• Random Sequence Generator based on Avalanche Noise
• Example of simple random number generator online