Kako računala generiraju slučajne brojeve

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

Računala mogu generirati doista slučajne brojeve promatranjem nekih vanjskih podataka, kao što su pokreti miša ili buka ventilatora, što nije predvidljivo, i stvara podatke iz njega. To je poznato kao entropija. U drugim slučajevima generiraju "pseudoslučajne" brojeve pomoću algoritma tako da se rezultati pojavljuju nasumično, iako nisu.

Ova je tema nedavno postala kontroverznija, a mnogi ljudi sumnjaju da li je Intelov ugrađeni čip generatora slučajnih brojeva pouzdan u povjerenju. Da biste razumjeli zašto to možda nije pouzdano, morate razumjeti kako su nasumični brojevi već napravljeni i za što se koriste.

Za koje se slučajne brojeve koristi

Slučajni brojevi korišteni su već tisućama godina. Bez obzira radi li se o novčiću ili kocki, cilj je ostaviti krajnji rezultat do slučajne šanse. Generatori slučajnih brojeva u računalu su slični - oni su pokušaj postizanja nepredvidivog, slučajnog rezultata.

Generatori slučajnih brojeva korisni su za mnoge različite svrhe. Osim očiglednih aplikacija kao što su generiranje slučajnih brojeva za kockanje ili stvaranje 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 uvijek koristiti iste brojeve. Želimo generirati te brojeve na vrlo nepredvidiv način tako da ih napadači ne mogu pogoditi. Ovi slučajni brojevi su neophodni za sigurnu enkripciju, neovisno o tome šifrirate li svoje datoteke ili samo koristite HTTPS web-lokaciju na Internetu..

Pravi slučajni brojevi

Možda se pitate kako računalo zapravo može generirati slučajni broj. Odakle dolazi ta "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 računala s nasumičnim brojevima u dvije vrste, ovisno o tome kako su generirani: "True" slučajni brojevi i pseudo-slučajni brojevi.

Da bi generirao "pravi" slučajni broj, računalo mjeri neku vrstu fizičkog fenomena koji se događa izvan računala. Na primjer, računalo bi moglo mjeriti radioaktivni raspad atoma. Prema kvantnoj teoriji, nema načina da se sa sigurnošću sazna kada će doći do radioaktivnog raspada, tako da je to u biti "čista slučajnost" iz svemira. Napadač ne bi mogao predvidjeti kada će doći do radioaktivnog raspada, kako ne bi znali slučajnu vrijednost.

Za svakodnevni primjer, računalo se može osloniti na atmosferski šum ili jednostavno koristiti točno vrijeme kada pritisnete tipke na tipkovnici kao izvor nepredvidivih podataka ili entropije. Na primjer, vaše računalo može primijetiti da ste pritisnuli tipku točno 0,23423523 sekundi nakon 14 sati ... Uzmite dovoljno vremena vezanih uz ove pritiske na tipke i imat ćete izvor entropije koju možete upotrijebiti za generiranje "prave" slučajne reprodukcije broj. Niste predvidljiv stroj, pa napadač ne može pogoditi točan trenutak kada pritisnete ove tipke. / Dev / random uređaj na Linuxu, koji generira slučajne brojeve, "blokove" i ne vraća rezultat dok ne prikupi dovoljno entropije da vrati doista slučajan broj.

Pseudoslučajni brojevi

Pseudoslučajni brojevi su alternativa "pravim" slučajnim brojevima. Računalo može koristiti vrijednost sjemena i algoritam za generiranje brojeva koji se čine slučajnim, ali koji su zapravo predvidljivi. Računalo ne prikuplja nikakve slučajne podatke iz okruženja.

To nije nužno loša stvar u svakoj situaciji. Na primjer, ako igrate videoigru, nije bitno jesu li događaji koji se dogode u toj igri popunjeni "pravim" slučajnim brojevima ili pseudoslučajnim brojevima. S druge strane, ako koristite enkripciju, ne želite koristiti pseudoslovne brojeve koje napadač može pogoditi.

Na primjer, recimo da napadač zna algoritam i vrijednost sjemena koji koristi generator pseudoslučajnih brojeva. Recimo da algoritam šifriranja dobiva pseudoslučajni broj iz ovog algoritma i koristi ga za generiranje ključa za šifriranje bez dodavanja bilo kakve dodatne slučajnosti. Ako napadač zna dovoljno, mogli bi raditi unatrag i odrediti pseudoslovni broj koji je algoritam za šifriranje odabrao u tom slučaju, razbijanje enkripcije.

NSA i Intelov generator slučajnih brojeva

Kako bi programerima olakšali izradu i pomogli u stvaranju sigurnih slučajnih brojeva, Intelovi čipovi uključuju generator slučajnih brojeva utemeljen na hardveru poznat kao RdRand. Ovaj čip koristi izvor entropije na procesoru i daje slučajne brojeve softveru kada ih softver zatraži.

Problem je u tome što je generator slučajnih brojeva u biti crna kutija i ne znamo što se događa unutar nje. Ako je RdRand sadržavao backdoor NSA, vlada bi mogla razbiti ključeve za šifriranje koji su generirani samo s podacima dobivenim od tog generatora slučajnih brojeva.

To je ozbiljna briga. U prosincu 2013., FreeBSD-ovi programeri su uklonili podršku za korištenje RdRanda izravno kao izvor slučajnosti, tvrdeći da ne mogu vjerovati. [Izvor] Izlaz uređaja RdRand bi se ubacivao u drugi algoritam koji dodaje dodatnu entropiju, osiguravajući da bilo koji backdoor u generatoru slučajnih brojeva ne bi bio važan. Linux je već radio na ovaj način, dodatno nasumično odabirajući nasumične podatke koji dolaze iz RdRand-a, tako da ne bi bilo predvidljivo čak i ako je postojao backdoor. [Izvor] U nedavnom AMA (“Pitaj me”) na Redditu, glavni izvršni direktor Intela Brian Krzanich nije odgovorio na pitanja o tim zabrinutostima. [Izvor]

Naravno, to vjerojatno nije samo problem s Intelovim čipovima. FreeBSD-ovi programeri su također nazvali Via čipove. Ova kontroverza pokazuje zašto je tako važno generirati slučajne brojeve koji su doista slučajni i nisu predvidivi.

Da bi generirali “istinite” slučajne brojeve, generatori slučajnih brojeva prikupljaju “entropiju”, ili naizgled slučajne podatke iz fizičkog svijeta oko njih. Za slučajne brojeve koji to ne čine stvarno moraju biti slučajni, mogu koristiti samo algoritam i vrijednost sjemena.

Kredit za slike: rekre89 na Flickr, Lisa Brewster na Flickru, Ryan Somma na Flickr, huangjiahui na Flickr