Kako stvoriti slučajni broj

U svetu u kome živimo ne postoji slučajnost – svaki događaj, počev od drhtaja pipka na glavi mrava pa do kataklizmičkih zemljotresa, supervulkana i pada asteroida, ima svoj uzrok. Možemo reći da su i naše misli, dok prividno „lutaju“ po prostranstvima sećanja, imaginacije i kreativnosti, samo posledica rasporeda neuronskih mreža, prisustva hormona i energetskih stanja u ćelijama našeg mozga.

Elektroničari su se zaista našli u nevolji kad su pokušali da naprave generator slučajnih brojeva, jer se pokazalo da nikakva matematička kombinatorika niti bilo kakav elektronski sklop ne mogu da stvore čak ni jedan bit informacije koji nije unapred određen i koji ne zavisi ni od čega. Ako pokušate da rešite ovaj problem, sva vrata će vam se pre ili kasnije zatvoriti i shvatićete da nema rešenja. Da ne bismo otišli predaleko pre nego što odredimo o kojoj vrsti slučajnosti govorimo, navešćemo dva osnovna pitanja koja bi trebalo da razjasnimo: zašto su nam potrebni slučajni brojevi i kako da ih generišemo.

Prvo pitanje: zašto?

Navedite bilo koju naučnu disciplinu, i u njoj ćete naći primenu slučajnih brojeva. Čak i u svakodnevnom životu se susrećemo sa problemom zaštite naših podataka od neovlašćenog pristupa pomoću šifre koja je dovoljno „slučajna“ da je niko ne bi mogao pogoditi. Postoje i ozbiljne naučne discipline kao što je kriptografija, koja ne bi ni postojala bez nauke o (pseudo)slučajnim nizovima. Pomenućemo još neke – teorija igara (studija matematičkih modela sukoba i saradnje), teorija verovatnoće, zabavna elektronika (društvene i kazino igre), kao i mnogi naučni eksperimenti i sociološka istraživanja, a u novije vreme i umetnički projekti. Pored nabrojanih, postoji još mnogo disciplina i delatnosti koje imaju potrebu za kvalitetnim slučajnim nizovima.

Šta znači kvalitetan niz slučajnih brojeva? Ako slučajan broj može da bude bilo koji, zar onda nije svaki broj slučajan? Recimo, da li je sekvenca cifara 999999 slučajna? U beskrajnom nizu cifara broja Pi, koji mnogi matematičari smatraju odličnim izvorom pseudoslučajnih cifara, pronaći ćemo svaku sekvencu koju zamislimo. Pomenuta sekvenca od šest devetki počinje već na 761. mestu iza decimalnog zareza, a čak osam devetki u nizu imamo na 36.356.691. mestu. Na piworld.calico.jp/epivalue1.html postoji niz od bilion (milion miliona) cifara broja Pi, podeljen na deset hiljada fajlova od po sto miliona cifara u ASCII formatu. Potražite u njemu datum svog rođenja, ili neki drugi značajan broj, i verovatno je da ćete ga naći već u prvom fajlu.

Kako se kriptuje poruka
U postupku kriptografske zaštite poruka najpre se generiše niz pseudoslučajnih brojeva, a onda se po jedan deo iz svakog člana tog niza iskoristi da se modifikuje bajt iz originalne poruke. Da bismo poruku „Zdravo“ zaštitli od neovlačćenog čitanja, moramo da imamo niz naizgled haotičnih bajtova. U procesu kodiranja poruke, svaki bit poruke će sa svojim „parom“ iz niza pseudoslučajnih bajtova izvršiti logičku operaciju isključivo-ili (XOR). Evo kako to izgleda:

Na ovom primeru je zaokruženo kodiranje samo četiri bita, ali se ta operacija, naravno, obavlja na svakom bitu poruke. U ovom slučaju se poruka „L XU5u“ šalje primaocu, kod koga će se isti niz operacija izvesti sa istim pseudoslučajnim nizom, posle čega se dobija originalna poruka:

Jasno je da na obe strane u komunikaciji moramo da imamo identičan pseudoslučajni niz, koji je na našem primeru osnačen crvenom bojom. U nekim slučajevima se, umesto pseudoslučajnog niza, koristi pravi slučajni niz, koji kurir na nekom medijumu fizički nosi do primaoca poruke (takozvani one-time pad). Ovo je skup i spor način ali, ako je korišćen kvalitetan generator slučajnih brojeva, tako zaštićene poruke je zauvek nemoguće dešifrovati.

Drugo pitanje: kako?

Postoje dve osnovne vrste generatora slučajnih brojeva, pseudoslučajni (PRNG, Pseudo Random Number Generator) i generator pravih slučajnih brojeva (TRNG, Truly Random Number Generator). Prvi generator je softverski i u njemu se koristi matematički obrazac po kome se stvara sekvenca brojeva čiji je redosled naoko nasumičan. Postoje različiti algoritmi, a svima je zajedničko da daju predvidiv niz. Naprimer, ako nam treba pseudoslučajni niz brojeva od 0 do 99, možemo da ga napravimo tako što ćemo poći od nekog broja, koji se u stručnoj terminologiji zove seed (seme), pomnožiti ga sa 21 pa dodati 3. Od tako dobijenog rezultata koristimo samo poslednje dve cifre i to će biti sledeći broj u nizu. Onda s njim izvržimo iste operacije i tako napravimo celu tabelu od 100 članova: 6, 29, 12, 55, 58, 21, 44, 27, 70, 73, 36...

Svaki broj se pojavljuje samo po jednom, ali ako bismo, po završenoj tabeli, nastavili isti postupak, videli bismo da poslednji broj (ovde bi to bio 43) ponovo generiše prvi i da tabela kreće od početka. U kriptografiji se nikada ne koristi ceo broj nego samo jedan njegov deo (ovde bi to, recimo, mogla da bude samo druga cifra), jer se sakrivanjem dela broja otežava posao razbijanja šifre.

Opisani algoritam čiji je osnovni oblik X-n 1-=X-n-×A b, samo je jedan od često korišćenih u generatorima pseudoslučajnih nizova, mada ne i za ozbiljne kriptografske primene jer se relativno lako razbija. Naravno da se ne koriste nizovi sa ovako kratkim sekvencama ponavljanja, a u kompjterima, koji su binarne mašine, zgodnije je koristiti binarno „okrugle“ brojeve, pa su šifre obično 64-bitne ili 128-bitne. To znači da njihov „orbitalni period“ (period ponavljanja niza) iznosi 264 ili 2128. Svaki broj u tom nizu se sastoji od 64 ili 128 binarnih cifara, a pošto je „šifra“ zapravo broj kojim će biti „kriptovan“ prvi bajt (ili slovo) poruke i od koga niz počinje, i sama šifra je 64-bitna ili 128-bitna. Ovako dugi nizovi se koriste zato što je u praksi svaku šifru moguće razbiti, samo je pitanje koliko vremena će biti potrebno kompjuterima da to učine. Metoda brute force (sirova snaga), kojoj se pribegava kad je poruka dobro zaštićena pa nije moguće zaobilazno stići do rešenja, zasniva se na isprobavanju svake moguće šifre. Današnji superkompjuter koji radi na razbijanju šifre testira oko sto miliona šifara u dekundi, tako da bi mu za 64-bitnu šifru trebalo oko šest hiljada godina. Ipak postoje razne prečice kojima se taj postupak drastično skraćuje, pa se umesto 64-bitne šifre često koristi i 128-bitna.

Sigurno je da nikakvim softverskim postupkom ne možete da dobijete slučajni broj nego samo pseudoslučajni niz, ali gde je tu onda neizvesnost i problem za nekoga ko želi neovlašćeno da pročita poruku? Ona je u samoj šifri, kojom se definiše na kom delu ogromnog pseudoslučajnog niza počinje sekvenca koju ćemo koristiti za kripto-zaštitu. Ova šifra se generiše generatorom pravog slučajnog broja, koji se postupkom javne šifre (public code) šalje primaocu poruke. Taj postupak, posle razmene kodova u čijoj izradi se na obe strane koriste generatori pravih slučajnih brojeva, kao i njihove matematičke obrade po specijalnom algoritmu, sa visokom verovatnoćom garantuje korisnicima da samo oni imaju šifru koja je upravo generisana i da niko ko eventualno prati komunikaciju nema dovoljno brz način da je dozna.

A pravi slučajni brojevi?

Za dobijanje niza pravih slučajnih brojeva koriste se elektronski uređaji koji neku naizgled haotičnu i nepredvidivu fizičku veličinu pretvaraju u bitove. To može da bude atmosferski ili termički šum, kosmičko ili veštačko jonizujuće zračenje, ali i kretanje ljudi, životinja ili saobraćaja. Ima maštovitih načina da se stvori što veći haos, kao što je snimanje oblika koji generiše „lava lampa“, kontakti koje pravi gomila metalnih predmeta koji se obrću u bubnju, akustički signal dečije zvečke, ili bilo šta što se smatra nepredvidivim.

Jedan od najgorih načina da se stvori slučajni niz jeste da ga čovek kreira „iz glave“. Ljudski mozak je sklon raznim paternima i uvek „vuče“ na neku stranu, čak i kad toga nije svestan. Još gore je koristiti imena, adrese, brojeve telefona, značajne datume i slične podatke kao šifre, jer se od toga uvek kreće pri pokušaju neovlašćenog prodora u sistem. Od toga je lošiji samo jedan postupak, koji nam je u februaru 2011. godine protiv svoje volje demonstrirao jedan naš ministar, kada je za pristup sajtu svog ministarstva koristi šifru „12345“. Da njegova nevolja bude veća, prodor u sajt je načinjen usred buke stvorene kada su mediji doznali da je izrada sajta plaćena 26.000 evra. Samo dva meseca posle toga, Odjeljenje za borbu protiv visokotehnološkog kriminala Višeg javnog tužilaštva je prošlo još gore, jer je na njihovom sajtu neko celu noć postavljao svoje poruke, od kojih je jedna glasila „ako neko ovako pravi Vladine sajtove, neće daleko dogurati ni on ni Vlada, a ni država“. Institucija u čijoj nadležnosti je upravo sigurnost na Internetu za svoj sajt je koristila korisničko ime i šifru admin/admin! Zaista, ko bi se toga setio?

Ako ste ipak u situaciji u kojoju morate brzo da smislite slučajne brojeve ili slova, nemojte da koristite podatke koji su vam naprosti pali na pamet, nego se poslužite trikom – pogledajte sekunde na satu, ili treće, peto (ili tako nešto) slovo u naslovima knjiga u određenom redu police, ili bilo šta što nije svojstveno ni vama ni grupi koja napada sistem koji štitite šifrom. Još je bolje da bacite kocku, izvučete kartu iz špila ili da se poslužite bilo kojim rekvizitom za igre na sreću.

Slučajnost u podatomskom svetu

Govorili smo o strogo determinisanom i nimalo slučajnom nizu brojeva, koji u svojoj odrednici ipak ima i izraz „slučajan“, a onda i o nizu koji smo proglasili za „pravi slučajan“, mada je on samo haotičan i praktično nepredvidiv, ali opet nije slučajan. Da li to znači da pravu slučajnost nije moguće postići?

Postoji grana nauke u kojoj ništa nije u skladu s razumom kakav poznajemo, a opet je to ozbiljna nauka u kojoj se sve dokazuje i koja donosi praktične rezultate, naprimer u proizvodnji mikroprocesora. To je kvantna mehanika, o kojoj smo opširno pisali u martu i aprilu 2013. godine, u brojevima 197 i 198. U podatomskom svetu, koji kvantna mehanika izučava, vreme može da teče unazad, jedan objekat postoji na više mesta istovremeno, čestice komuniciraju brzinom višom od brzine svetlosti, pa zašto ne bi mogla da postoji i slučajnost? U podatomskom svetu se zapravo najmanje barata sa izvesnim i određenim događajima, a najviše verovatnoćom. Tamo gde je ta verovatnoća tačno 50% (što je čest slučaj), u prelasku informacije iz podatomskog u naš, makro svet, dolazi do kvantnog skoka (kolapsa talasne funkcije, kako bi se stručno reklo) u kome se neodređenost i istovremenost dva ishoda pretvara u samo jedan nepovratno određen ishod, i tu dobijamo ono što smatramo pravom slučajnošću. Osnovno pitanje – koliko je to zaista slučajnost – ostaće u domenu filozofije, mada ona još nije počela da se bavi time na ozbiljan način. Izgleda da je došlo vreme da filozofi konačno prestanu da razmišljaju o tome koliko anđela može da stane na vrh igle i da se zanimaju samo za svoju istoriju, i da počnu da se bave kvantnom slučajnošću na malo plodonosniji način.

Bez obzira na to koji je odgovor na ovo zanimljivo pitanje, sigurno je da je to „najslučajnija slučajnost“ koju danas možemo da postignemo. Kvantni generatori slučajnih brojeva se proizvode i prodaju (recimo QRBG121, Quantis AIS 31 ili Cerberis QKD), mada i ovde ima puno podvala i pseudonauke, kao što je slučaj i u nadrilekarstvu, u kome skoro svaka druga prevara nosi naziv „kvantno lečenje“. Treba dobro proučiti kvantni generator slučajnih brojeva i raspitati se o njegovom principu rada i rezultatima testova, pre nego što za njega izdvojimo četvorocifrenu ili čak petocifrenu sumu.

Komercijalni kvantni generatori rade tako što mali emiter kontrolisano odašilje jedan po jedan foton, koji se odbija od polupropusnog ogledala ili prolazi kroz njega, a onda se detektuje pomoću fotomultiplikartora ili poluprovodničkog brojača fotona. U stvarnom svetu svetlosni talasi se odbijaju od polupropusnog ogledala, ali sa smanjenim intenzitetom, a u kvantnom svetu fotoni ili prolaze ili se odbijaju, što je rezultat pukog slučaja, na koji nikakva poznata fizička pojava nema uticaja.

Testovi ne lažu

Mada je na neki način tačno to da svaki broj možemo da proglasimo za „slučajan“, postoji niz statističkih testova kojima se podvrgavaju generatori slučajnih, pa i pseudoslučajnih brojeva. Svaki od ovih testova sprovodi se na uzorcima od više stotina miliona ili milijardi brojeva, posle čega dobijamo statističku ocenu kvaliteta testiranog niza. Meri se nekoliko desetina parametara, kao što su proporcija nula i jedinica u celini ili u pojedinačnim blokovima, zastupljenost „vezanih“ nula i jedinica kao i njihova standardna raspodela, učestalost jednakih blokova, test količine entropije (haosa), a vrši se i brza Furijeova analiza kojom se otkriva ponavljanje sličnih paterna proizvoljne dužine i učestalosti. Zanimljivo je to koliko generatora pada na ovim statističkim testovima, čak i onih za koje bi se reklo da korektno pretvaraju termički ili atmosferski šum u slučajne brojeve. Najbolje prolaze kvantni generatori koji imaju skoro savršene rezultate. Da li to „skoro“ znači da ni oni nisu bez mane, ili da bi za savršen rezultat bio potreban i beskrajnu dug niz? Oko toga se još uvek lome koplja, što pokazuje koliko je područje slučajnih brojeva zanimljivo i neistraženo.

U sledećem broju časopisa „PC“ govorićemo o sigurnosti šifara koje svakodnevno koristimo, a posle toga ćemo vam ponuditi projekat – mali hardverski USB menadžer šifara, koji je vrlo zgodan za sigurno i udobno rukovanje brojnim šiframa s kojima se srećemo.