Generisanje slučajnih brojeva

Из Википедије, слободне енциклопедије
Kada se baci kockica, dobije se slučajan broj između 1 i 6.

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.

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

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 nepredvidjlivost 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 osmisljenji. 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,[2] 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. [3] 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.[4]

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[5]. Niz vrednosti generisan ovakvim algoritmima je obično odredjen fiksiranom vrednošću koja se naziva seme (енгл. seed). Jedan od najrasprostranjenijih PSGB je linearni kongruentalni generator, koji koristi rekurentnost

da bi generisao brojeve, gde su , and veliki brojevi, i je sledeći u seriji pseudo-slučajnih brojeva. Najveći broj brojeva koje ova formula može proizvesti je modulo . Da bi se izbegla neka ne-slučajna svojstva linearnog kongruentalnog generatora, nekoliko takvih generatora brojeva sa malo drukčijim vrednostima koeficijenta umnozitelja , 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 datoteteke 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 Majkrosoft Vindous. 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 izmedju 0 i 1 radi pravilne raspodele). Druga metoda, koja se naziva metoda prihvatanja-odbijanja, uključuje odabiranje i vrednosti i testiranja da li je funkcija od veća od vrednosti . Ako jeste, prihvata se vrednost , u surpotnom vrednost se odbija i algoritam se pokreće ponovo.[6][7]

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. Medutim, većina istraživanja su pronašla da ljudi imaju neki stepen predvidivosti prilikom pokušaja generisanja slučajnog niza npr. brojeva ili slova.[8]. 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[9] uređaj za generisanje slucajnih 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 [10] 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~χ22 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.
  1. 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.
  1. Random.Org generiše slučajne brojeve čiji je izvor slučajnost u atmosferskom šumu. Posetite njihovu stranicu da biste dobili uzorak.
  1. 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 podatakam, uključujuci 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.[11] 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[12]. 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.[13]

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.[14] 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.[15][16]

Reference[уреди]

  1. „Introduction to Slot Machines”. slotsvariations.com. Приступљено 14. 05. 2010. 
  2. Walker, John. „HotBits: Genuine Random Numbers”. Приступљено 27. 06. 2009. 
  3. Halprin, Ran; Naor, Moni. „Games for Extracting Randomness” (PDF). Department of Computer Science and Applied Mathematics, Weizmann Institute of Science. Приступљено 27. 06. 2009. 
  4. TrueCrypt Foundation. „TrueCrypt Beginner's Tutorial, Part 3”. Приступљено 27. 06. 2009. 
  5. „RANDOM.ORG - True Random Number Service”. www.random.org. Приступљено 14. 01. 2016. 
  6. The MathWorks. „Common generation methods”. Приступљено 13. 10. 2011. 
  7. The Numerical Algorithms Group. „G05 – Random Number Generators” (PDF). NAG Library Manual, Mark 23. Приступљено 09. 02. 2012. 
  8. W. A. Wagenaar (1972). „Generation of random sequences by human subjects: a critical survey of the literature”. Psychological Bulletin. 77 (1): 65—72. doi:10.1037/h0032060. 
  9. Dömstedt, B. (2009). „TRNG9803 True Random Number Generator”. Manufacturer: www.TRNG98.se. 
  10. Wang, Yongge (2014). „Statistical Properties of Pseudo Random Sequences and Experiments with PHP and Debian OpenSSL”. Heidelberg: Springer LNCS. 
  11. matthew Green. „The Many Flaws of Dual_EC_DRBG”. 
  12. Matthew Green. „RSA warns developers not to use RSA products”. 
  13. „We don’t enable backdoors in our crypto products, RSA tells customers”. Ars Technica. 
  14. „Researchers can slip an undetectable trojan into Intel’s Ivy Bridge CPUs”. Ars Technica. 
  15. Theodore Ts'o. „I am so glad I resisted pressure from Intel engineers to let /dev/random rely only on the RdRand instruction.”. Google Plus. 
  16. Theodore Ts'o. „Re: [PATCH] /dev/random: Insufficient of entropy on many architectures”. LWN. 

Literatura[уреди]

Spoljašnje veze[уреди]