Kako računala generiraju slučajne brojeve

Računala generiraju slučajne brojeve za sve, od kriptografije do video igara i kockanja. Postoje dvije kategorije slučajnih brojeva - "istinski" slučajni brojevi i pseudo slučajni brojevi - a razlika je važna za sigurnost sustava šifriranja.

Računala mogu generirati uistinu slučajne brojeve promatranjem nekih vanjskih podataka, poput kretanja miša ili buke ventilatora, što nije predvidljivo, i stvaranjem podataka iz njih. To je poznato kao entropija. Drugi puta generiraju "pseudo slučajne" brojeve pomoću algoritma, tako da se rezultati čine nasumičnim, iako nisu.

Ova je tema u posljednje vrijeme kontroverznija, a mnogi ljudi postavljaju pitanje je li pouzdan Intelov ugrađeni hardverski čip za generiranje slučajnih brojeva. Da biste razumjeli zašto možda nije pouzdan, morat ćete razumjeti kako se uopće generiraju slučajni brojevi i za što se koriste.

Za što se koriste slučajni brojevi

Slučajni brojevi koriste se već tisućama godina. Bilo da se radi o bacanju novčića ili bacanju kocke, cilj je prepustiti krajnji rezultat slučajnoj prilici. Generatori slučajnih brojeva u računalu su slični - oni pokušavaju postići nepredvidiv, slučajan rezultat.

POVEZANO: Što je šifriranje i kako funkcionira?

Generatori slučajnih brojeva korisni su u razne svrhe. Osim očitih aplikacija poput generiranja slučajnih brojeva za potrebe kockanja ili stvaranja nepredvidivih rezultata u računalnoj igri, slučajnost je važna za kriptografiju.

Kriptografija zahtijeva brojeve koje napadači ne mogu pogoditi. Ne možemo se stalno služiti istim brojevima. Te brojeve želimo generirati na vrlo nepredvidljiv način kako ih napadači ne bi mogli pogoditi. Ti su slučajni brojevi neophodni za sigurno šifriranje, bez obzira šifrirate li vlastite datoteke ili samo upotrebljavate HTTPS web mjesto na Internetu.

Istiniti slučajni brojevi

Možda se pitate kako računalo zapravo može generirati slučajni broj. Odakle dolazi ova "slučajnost". Ako je to samo dio računalnog koda, nije li moguće da brojevi koje računalo generira mogu biti predvidljivi?

Općenito grupiramo slučajne brojeve koje računala generiraju u dvije vrste, ovisno o tome kako se generiraju: "Istiniti" slučajni brojevi i pseudo-slučajni brojevi.

Da bi generiralo "istinski" slučajni broj, računalo mjeri neku vrstu fizičkog fenomena koji se događa izvan računala. Na primjer, računalo je moglo izmjeriti radioaktivni raspad atoma. Prema kvantnoj teoriji, ne postoji način da se sa sigurnošću zna kada će se dogoditi radioaktivni raspad, pa je ovo u osnovi "čista slučajnost" iz svemira. Napadač ne bi mogao predvidjeti kada će se dogoditi radioaktivni raspad, pa ne bi znao slučajnu vrijednost.

Za svakodnevni primjer, računalo se može osloniti na atmosfersku buku ili jednostavno koristiti točno vrijeme pritiska tipki na tipkovnici kao izvor nepredvidivih podataka ili entropije. Na primjer, vaše bi računalo moglo primijetiti da ste pritisnuli tipku točno u 0,23423523 sekunde nakon 14 sati. Uhvatite dovoljno određenog vremena povezanog s tim pritiscima na tipke i imat ćete izvor entropije koji možete koristiti za generiranje "istinskog" slučajnog broja. Niste predvidiv stroj, pa napadač ne može pogoditi točan trenutak kada pritisnete ove tipke. Uređaj / dev / random na Linuxu, koji generira slučajne brojeve, "blokira" i ne vraća rezultat dok ne skupi dovoljno entropije za vraćanje uistinu slučajnog broja.

Pseudoslučajni brojevi

Pseudoslučajni brojevi su alternativa "istinskim" slučajnim brojevima. Računalo bi moglo koristiti početnu vrijednost i algoritam za generiranje brojeva koji se čine slučajnima, ali koji su zapravo predvidljivi. Računalo ne prikuplja slučajne podatke iz okoline.

To nije nužno loše u svakoj situaciji. Na primjer, ako igrate videoigru, zapravo nije važno jesu li događaji koji se događaju u toj igri uzrokovani "istinitim" slučajnim brojevima ili pseudoslučajnim brojevima. S druge strane, ako upotrebljavate šifriranje, ne želite koristiti pseudoslučajne brojeve koje bi napadač mogao pogoditi.

Na primjer, recimo da napadač zna algoritam i vrijednost sjemena koje koristi pseudo slučajni brojni generator. I recimo da algoritam šifriranja dobije pseudoslučajni broj iz ovog algoritma i koristi ga za generiranje ključa šifriranja bez dodavanja dodatnih slučajnosti. Ako napadač zna dovoljno, mogao bi raditi unatrag i odrediti pseudoslučajni broj koji je algoritam šifriranja u tom slučaju morao izabrati, prekidajući šifriranje.

NSA i Intelov hardverski generator slučajnih brojeva

Da bi programerima olakšali stvari i pomogli u generiranju sigurnih slučajnih brojeva, Intel čipovi uključuju hardverski generator slučajnih brojeva poznat kao RdRand. Ovaj čip koristi izvor entropije na procesoru i daje slučajne brojeve softveru kada ih softver zatraži.

Problem je ovdje što je generator slučajnih brojeva u osnovi crni okvir i ne znamo što se događa u njemu. Kad bi RdRand sadržavao NSA zaklon, vlada bi mogla razbiti ključeve za šifriranje koji su generirani samo s podacima dostavljenim od tog generatora slučajnih brojeva.

Ovo je ozbiljna briga. U prosincu 2013. programeri FreeBSD-a uklonili su podršku za upotrebu RdRanda izravno kao izvora slučajnosti, rekavši da mu ne mogu vjerovati. [Izvor] Izlaz RdRand uređaja unosit će se u drugi algoritam koji dodaje dodatnu entropiju, osiguravajući da bilo koja pozadina u generatoru slučajnih brojeva ne bi bila važna. Linux je već radio na ovaj način, dalje randomizirajući slučajne podatke koji dolaze iz RdRanda, tako da ne bi bili predvidljivi čak i da postoji backdoor. [Izvor] U nedavnom AMA-u („Pitajte me bilo što“) na Redditu, izvršni direktor Intela Brian Krzanich nije odgovorio na pitanja o tim problemima. [Izvor]

Naravno, ovo vjerojatno nije problem samo s Intelovim čipovima. Programeri FreeBSD-a poimence su prozvali i Via-ove čipove. Ova kontroverza pokazuje zašto je stvaranje slučajnih brojeva koji su uistinu slučajni i nisu predvidljivi toliko važno.

Da bi generirali "istinske" slučajne brojeve, generatori slučajnih brojeva prikupljaju "entropiju" ili naizgled slučajne podatke iz fizičkog svijeta oko sebe. Za slučajnih brojeva koji ne stvarno trebaju biti slučajni, oni mogu samo koristiti algoritam i vrijednost sjemena.

Zasluge za slike: rekre89 na Flickr-u, Lisa Brewster na Flickr-u, Ryan Somma na Flickr-u, huangjiahui na Flickr-u