Jak počítač generuje náhodná čísla

Jak počítač generuje náhodná čísla

Generování náhodných čísel je potřebné snad všude od kryptografie přes videohry až k hazardu. Zřejmě to nevíte, ale existují dvě kategorie náhodných čísel – „pravá“ náhodná čísla a pseudonáhodná čísla. Rozdíl mezi nimi je důležitý pro bezpečnost šifrovacích systémů. Takže pojďme se na to podívat.

Toto téma je v současné době celkem aktuální. Mnoho lidí si totiž klade otázku, zda je vestavěný hardwarový čip od Intelu generující náhodná čísla důvěryhodný. Abychom pochopili, že aspoň v Linuxu vlastně důvěryhodný vůbec být nemusí, budeme muset pochopit, jak jsou náhodná čísla generována.

K čemu se náhodná čísla využívají

Náhodná čísla jsou používána po tisíce let. Ať už házíte mincí nebo kostkou, cílem je nechat výsledek náhodě. Generátory náhodných čísel v počítači jsou podobné – je to pokus o dosažení nepředvídatelných výsledků.

Jsou užitečné pro mnoho různých účelů. Kromě aplikací, kde je jejich využití zjevné, jako například generování náhodných čísel pro hazardní hry nebo vytváření neočekávatelných závěrů v počítačové hře, je náhodnost důležitá i pro kryptografii.

Kryptografie vyžaduje čísla, která nemohou případní útočníci uhodnout. Nemůžeme jen tak používat stejná čísla znovu a znovu. Potřebujeme je generovat nepředvídatelným způsobem. A to ať už šifrujeme vlastní sobory nebo jen webové stránky na internetu pomocí HTTPS protokolu.

gambling

Pravá náhodná čísla

Možná se divíte, jak může počítač generovat skutečně náhodná čísla. Odkud asi pochází ta „náhodnost“? Pokud je to jen kus kódu, není možné generovaná čísla předvídat?

Náhodná čísla obecně dělíme do dvou typů v závislosti na tom, jak jsou generována: „pravá“ a pseudonáhodná.

K vygenerování „pravého“ náhodného čísla počítač měří nějaký fyzikální jev, který se odehrává mimo počítač. Například by mohl měřit radioaktivní rozpad atomu. Podle kvantové teorie totiž neexistuje žádný způsob, jak s jistotou zjistit, kdy k němu dojde, takže se v podstatě jedná o čistou náhodnost. Útočník by nebyl schopen předvídat, kdy dojde k rozpadu, takže by nikdy nepřišel na náhodné hodnoty.

Když se přesuneme více do naší každodenní reality, mohl by se počítač spoléhat i na atmosférický šum, nebo jednoduše používat jako zdroj nepředvídatelných dat přesný čas stisku klávesy. Váš počítač je totiž schopný zpozorovat, že jste stiskli klávesu „A“ přesně 0,2343523 sekundy po druhé hodině odpolední. Když zaznamená dostatek takových konkrétních časových údajů, bude mít dobrý zdroj pro vytvoření „pravého“ náhodného čísla. Lidé nejsou předvídatelné stroje, takže útočník nemůže odhadnout, kdy přesně zmáčknou klávesu.

Například generátor čísel v Linuxu dev/random vám není schopen navrátit výsledek, dokud neshromáždí dostatek materiálu, aby mohl vygenerovat skutečně náhodné číslo. Jeho protiklad dev/urandom při nedostatku dat vrátí „méně náhodné číslo“.

linux-generate-random-data

Pseudonáhodná čísla

Pseudonáhodná čísla jsou alternativou k „pravým“ náhodným číslům. Počítač k nim může používat algoritmus, který se zdá náhodný, ale ve skutečnosti je předvídatelný. Neshromažďují se v něm totiž žádná náhodná data z okolního prostředí.

Možná si říkáte, proč se vůbec taková možnost využívá, když ji lze předvídat. Kdyby útočník znal algoritmus generátoru náhodných čísel, který je v šifrování používán, mohl by šifru snadno rozluštit. Ano, takže v kryptografii je to skutečně k ničemu. Ale například u videoher na tom vůbec nezáleží. A proto je tam tato metoda často využívána, protože je mnohem méně náročná než sběr dat z okolního prostředí.

lottery_1838360b

NSA a hardwarový generátor Intelu

Aby bylo pro vývojáře jednodušší vytvářet bezpečná náhodná čísla, obsahují čipy Intelu hardwarový generátor známý jako RdRand. Tento čip poskytuje náhodná čísla softwaru, pokud je software požaduje.

Problém se týká toho, že tenhle čip je pro nás vlastně takovou černou skříňkou. My vůbec nevíme, co se v něm děje. Objevily se i zvěsti o tom, že možná obsahuje nějaké špehovací zařízení NSA, takže je veškeré šifrovací klíče vytvořené pomocí RdRand možné prolomit.

A to je závažný problém. Ale co se týká například Linuxu, tak Linus Torvalds na to zareagoval, že jeho uživatelé jsou v bezpečí. I kdyby nad RdRand měla nějakou kontrolu NSA, tak Linux se nemusí bát, protože tenhle čip používá jen jako jeden z mnoha vstupů pro náhodné generování čísel.

Generální ředitel Intelu Brian Krzanich se k této otázce nevyjádřil, takže nic není potvrzené. Ale ani vyvrácené.

Intel--621x414

Na konec si to pojďme ještě jednou zopakovat. Chcete-li vytvořit skutečně naprosto náhodná čísla, musíte se řídit podle něčeho z okolního prostředí, co nelze předvídat. V opačném případě vám prostě stačí použít nějaký „náhodný“ algoritmus.

Zdroje: How to geek, Root, obrázky: Dncomputer, Telegraph, Lottery, Livemint

Komentáře

Nahoru