Ako počítače generujú náhodné čísla

Počítače vytvárajú náhodné číslo pre všetko od kryptografie až po videohry a hazardné hry. Existujú dve kategórie náhodných čísel - "pravé" náhodné čísla a čísla pseudonáhodných čísel - a rozdiel je dôležitý pre bezpečnosť šifrovacích systémov.

Počítače môžu vytvárať skutočne náhodné čísla pozorovaním niektorých externých údajov, ako sú napríklad pohyby myši alebo šum fanúšikov, čo nie je predvídateľné a vytvárať údaje z neho. Toto je známe ako entropia. Inokedy generujú čísla "pseudorandom" pomocou algoritmu, takže výsledky sa objavujú náhodne, aj keď nie sú.

Táto téma sa v poslednej dobe stala kontroverznejšou a mnohí ľudia sa pýtali na to, či je vstavaný čip generátora integrovaného hardvéru Intel dôveryhodný. Aby ste pochopili, prečo to nemusí byť dôveryhodné, budete musieť pochopiť, ako sa na prvom mieste generujú náhodné čísla a na čo sa používajú.

Aké náhodné čísla sa používajú

Náhodné čísla sa používajú už mnoho tisíc rokov. Bez ohľadu na to, či ide o prehratie mince alebo o kockovanie, cieľom je ponechať konečný výsledok až po náhodnú náhodu. Generátory náhodných čísel v počítači sú podobné - ide o pokus o dosiahnutie nepredvídateľného náhodného výsledku.

Generátory náhodných čísel sú užitočné pre mnoho rôznych účelov. Okrem zjavných aplikácií, ako je vytváranie náhodných čísiel na účely hazardných hier alebo vytváranie nepredvídateľných výsledkov v počítačovej hre, je náhodnosť dôležitá pre kryptografiu.

Kryptografia vyžaduje čísla, ktoré útočníci nemôžu odhadnúť. Nemôžeme jednoducho používať rovnaké čísla znova a znova. Chceme vytvoriť tieto čísla veľmi nepredvídateľným spôsobom, takže útočníci ich nemôžu uhádnuť. Tieto náhodné čísla sú dôležité pre bezpečné šifrovanie, či už šifrujete svoje vlastné súbory alebo len pomocou webovej stránky HTTPS na internete.

Pravé náhodné čísla

Možno vás zaujíma, ako môže počítač skutočne generovať náhodné číslo. Odkiaľ pochádza táto "náhodnosť". Ak je to len kus počítačového kódu, nie je možné, že čísla, ktoré generuje počítač, by mohli byť predvídateľné?

Všeobecne zoskupujeme náhodné čísla počítačov, ktoré sa generujú do dvoch typov, v závislosti od toho, ako sú generované: "Pravé" náhodné čísla a pseudonáhodné čísla.

Ak chcete vytvoriť "pravé" náhodné číslo, počítač meria nejaký typ fyzického javu, ktorý sa odohráva mimo počítača. Napríklad počítač mohol merať rádioaktívny rozklad atómu. Podľa kvantovej teórie neexistuje žiadny spôsob, ako určiť, či nastane rádioaktívny rozpad, takže je to v podstate "čistá náhodnosť" z vesmíru. Útočník by nebol schopný predpovedať, kedy nastane rádioaktívny úpadok, takže by nevedeli náhodnú hodnotu.

Pri každodennom príklade by sa počítač mohol spoľahnúť na atmosférický šum alebo jednoducho použiť presný čas stlačenia klávesov na klávesnici ako zdroja nepredvídateľných údajov alebo entropie. Napríklad, váš počítač môže zistiť, že ste stlačili kľúč presne po 0.23423523 sekundách po 14:00 ... Zachyťte dostatok konkrétnych časov spojených s týmito tlačidlami a budete mať zdroj entropie, ktorý môžete použiť na generovanie "pravdivého" náhodného číslo. Nie ste predvídateľný stroj, takže útočník nemôže odhadnúť presný okamih, kedy stlačíte tieto klávesy. Zariadenie / dev / random v systéme Linux, ktoré generuje náhodné čísla, "blokuje" a nevracia výsledok, kým nezhromaždí dostatok entropie na vrátenie skutočne náhodného čísla.

Pseudonáhodné čísla

Pseudonáhodné čísla sú alternatívou k "pravdivým" náhodným číslam. Počítač by mohol použiť hodnotu začiatku a algoritmus na generovanie čísel, ktoré sa javia ako náhodné, ale predvídateľné. Počítač nezhromažďuje žiadne náhodné údaje z prostredia.

To nie je nevyhnutne zlá vec v každej situácii. Napríklad, ak hráte videohru, nezáleží na tom, či udalosti, ktoré sa vyskytujú v tejto hre, sú pokryté "pravými" náhodnými číslami alebo pseudonáhodnými číslami. Na druhej strane, ak používate šifrovanie, nechcete používať pseudonáhodné čísla, ktoré by útočník mohol uhádnuť.

Povedzme napríklad, že útočník pozná algoritmus a hodnotu začiatku, ktorú používa generátor pseudonáhodných čísel. Povedzme, že šifrovací algoritmus získa od tohto algoritmu číslo pseudonáhodného čísla a používa ho na generovanie šifrovacieho kľúča bez pridania akéhokoľvek ďalšieho náhodného výberu. Ak by útočník vedel dostatočne, mohli by pracovať späť a určiť číslo pseudonáhodného čísla, ktoré sa v takomto prípade musel šifrovací algoritmus vybrať, čím porušil šifrovanie.

NSA a generátor počítačových náhodných čísel spoločnosti Intel

S cieľom uľahčiť vývojárom a pomôcť generovať zabezpečené náhodné čísla obsahujú čipy Intel hardvérový generátor náhodných čísel známy ako RdRand. Tento čip využíva zdroj entropie na procesore a poskytuje softvérové ​​náhodné čísla, keď ich softvér požaduje.

Problém je, že generátor náhodných čísel je v podstate čierny box a nevieme, čo sa v ňom deje. Ak by RdRand obsahoval backdoor NSA, vláda by mohla zlomiť šifrovacie kľúče, ktoré boli vytvorené len s údajmi dodanými týmto generátorom náhodných čísel.

To je vážny problém. V decembri 2013 vývojári FreeBSD odstránili podporu používania RdRand priamo ako zdroj náhodnosti, a povedali, že nemôžu tomu dôverovať. [Zdroj] Výstup zariadenia RdRand by bol privádzaný do iného algoritmu, ktorý pridáva dodatočnú entropiu, čím sa zabezpečí, že akékoľvek zadné vrátky v generátore náhodných čísel nezáleží. Linux už pracoval týmto spôsobom, ďalej randomizoval náhodné dáta prichádzajúce z RdRand, takže by nebolo predvídateľné, aj keď tam bola backdoor. [Zdroj] V nedávnom AMA ("Opýtajte sa čokoľvek") na spoločnosť Reddit generálny riaditeľ spoločnosti Intel Brian Krzanich neodpovedal na otázky týkajúce sa týchto problémov. [Zdroj]

Samozrejme, pravdepodobne to nie je len problém s čipmi Intel. Vývojári vo FreeBSD vytočili Via svoje čipy aj podľa názvu. Táto kontroverzia ukazuje, že generovanie náhodných čísel, ktoré sú naozaj náhodné a nie sú predvídateľné, je tak dôležité.

Ak chcete generovať "pravé" náhodné čísla, generátory náhodných čísel zhromažďujú "entropiu" alebo zdanlivo náhodné údaje z fyzického sveta okolo nich. Pre náhodné čísla, ktoré nie naozaj musia byť náhodné, môžu použiť iba algoritmus a hodnotu osiva.

Image Credit: rekre89 na Flickr, Lisa Brewster na Flickr, Ryan Somma na Flickr, huangjiahui na Flickr