Jak počítače generují náhodné čísla

Počítače generují náhodné číslo pro vše od kryptografie až po videohry a hazardní hry. Existují dvě kategorie náhodných čísel - "pravé" náhodná čísla a čísla pseudonáhodných čísel - a rozdíl je důležitý pro zabezpečení šifrovacích systémů.

Počítače mohou vytvářet opravdu náhodné číslice tím, že pozorují některé vnější data, jako jsou pohyby myší nebo hluk fanoušků, což není předvídatelné a vytváří z nich data. Toto je známé jako entropie. Jinak generují čísla "pseudorandom" pomocí algoritmu, takže výsledky se objeví náhodně, i když nejsou.

Toto téma se v poslední době stalo kontroverznějším a mnoho lidí se ptá, zda je vestavěný integrovaný čip generátoru náhodných čísel Intel důvěryhodný. Chcete-li pochopit, proč to nemusí být důvěryhodné, musíte pochopit, jak jsou náhodná čísla původně generována a na co se používají.

Co náhodná čísla jsou používána

Náhodné číslice byly používány po mnoho tisíc let. Ať už jde o minci nebo o kolečkách, cílem je nechat konečný výsledek až náhodnou náhodou. Generátory náhodných čísel v počítači jsou podobné - jde o pokus dosáhnout nepředvídatelného a náhodného výsledku.

Generátory náhodných čísel jsou užitečné pro mnoho různých účelů. Kromě zjevných aplikací, jako je generování náhodných čísel pro účely hazardních her nebo vytváření nepředvídatelných výsledků v počítačové hře, je pro kryptografii důležitá náhoda.

Kryptografie vyžaduje čísla, která útočníci nemohou odhadnout. Nemůžeme jen používat stejná čísla znovu a znovu. Chceme generovat tato čísla velice nepředvídatelným způsobem, takže útočníci je nemohou hádat. Tato náhodná čísla jsou nezbytná pro bezpečné šifrování, ať už šifrujete své vlastní soubory, nebo právě používáte webovou stránku HTTPS na Internetu.

Pravé náhodné čísla

Možná se ptáte, jak může počítač skutečně vygenerovat náhodné číslo. Odkud pochází tato "náhodnost". Je-li to jen kus kódu počítače, není možné, aby čísla, která počítač generuje, byly předvídatelné?

Obecně seskupujeme náhodná čísla, která počítače vygenerují do dvou typů, v závislosti na tom, jak jsou generovány: "Pravda" náhodná čísla a pseudonáhodná čísla.

Chcete-li vygenerovat "pravé" náhodné číslo, počítač měří nějaký typ fyzického jevu, který se děje mimo počítač. Například počítač mohl měřit radioaktivní rozklad atomu. Podle kvantové teorie neexistuje žádný způsob, jak vědět jistě, kdy nastane radioaktivní rozpad, takže je to v podstatě "čistá náhodnost" z vesmíru. Útočník by nebyl schopen předpovědět, kdy nastane radioaktivní rozpad, a tak by nevěděli náhodnou hodnotu.

Pro více každodenní příklad by se počítač mohl spoléhat na atmosférický šum nebo jednoduše použít přesný čas, kdy stisknete klávesy na klávesnici jako zdroj nepředvídatelných dat nebo entropie. Například váš počítač si může všimnout, že jste stiskli klávesu přesně po 0.23423523 sekundách po 14 hodin ... Chyť dostatečně specifické časy spojené s těmito tlačítky a budete mít zdroj entropie, který můžete použít k vytvoření "pravdivého" náhodného číslo. Nejste předvídatelný stroj, takže útočník nemůže odhadnout přesný okamžik, kdy stisknete tyto klávesy. / Dev / náhodná zařízení v systému Linux, která generuje náhodné čísla, "blokuje" a nevrací výsledek, dokud nenajde dostatek entropie k návratu skutečně náhodného čísla.

Pseudonáhodná čísla

Pseudonáhodná čísla jsou alternativou k "pravdivým" náhodným číslům. Počítač mohl použít hodnotu počátku a algoritmus pro generování čísel, které se zdají být náhodné, ale které jsou ve skutečnosti předvídatelné. Počítač neshromažďuje žádná náhodná data z prostředí.

To není nutně špatná věc v každé situaci. Pokud například hrajete videohru, nezáleží na tom, zda se události, které se vyskytují v této hře, skryjí "pravdivými" náhodnými čísly nebo pseudonáhodnými čísly. Na druhou stranu, pokud používáte šifrování, nechcete používat pseudonáhodná čísla, která by útočník mohl odhadnout.

Řekněme například, že útočník zná algoritmus a hodnotu počátku, který používá generátor pseudonáhodných čísel. A řekněme, že šifrovací algoritmus získá z tohoto algoritmu číslo pseudonáhodného čísla a používá ho k vytvoření šifrovacího klíče bez přidání jakékoliv další náhodnosti. Pokud by útočník věděl dost, mohli by pracovat zpět a určit pseudonáhodné číslo, které šifrovací algoritmus musel v takovém případě zvolit, aby porušil šifrování.

NSA a Generátor náhodných čísel hardwaru společnosti Intel

Pro usnadnění vývojářů a pomoc při generování zabezpečených náhodných čísel obsahuje čipy Intel hardwarové generátory náhodných čísel známé jako RdRand. Tento čip využívá zdroj entropie na procesoru a poskytuje softwarová čísla, pokud je požaduje software.

Problém je, že generátor náhodných čísel je v podstatě černá skříňka a nevíme, co se děje uvnitř. Pokud by RdRand obsahovala backdoor NSA, vláda by mohla přerušit šifrovací klíče, které byly generovány pouze s údaji dodanými tímto generátorem náhodných čísel.

To je vážné znepokojení. V prosinci roku 2013 vývojáři FreeBSD odstranili podporu pro použití RdRand přímo jako zdroj náhodnosti, říkat, že nemohou věřit. [Zdroj] Výstup zařízení RdRand by byl přiváděn do jiného algoritmu, který přidá další entropii, což by zajistilo, že jakékoli zadní vrátky v generátoru náhodných čísel by neměly na mysli. Linux již pracoval tímto způsobem, dále randomizoval náhodná data pocházející z RdRandu, takže by to nebylo možné předvídat, i když tam byla backdoor. [Zdroj] V nedávné AMA ("Ask Me Anything") na Redditu CEO společnosti Intel Brian Krzanich neodpověděl na otázky týkající se těchto obav. [Zdroj]

Samozřejmě, to pravděpodobně není jen problém s čipy Intel. Vývojáři FreeBSDu také volali Via čipy. Tato kontroverze ukazuje, proč je generování náhodných čísel, které jsou skutečně náhodné a nejsou předvídatelné, tak důležité.

K generování "pravdivých" náhodných čísel generátory náhodných čísel shromáždí "entropii" nebo zdánlivě náhodná data z fyzického světa kolem nich. U náhodných čísel, která ne opravdu musí být náhodná, mohou používat pouze algoritmus a hodnotu počátku.

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