Tato počítačová karta SSL Accelerator používá hardwarový generátor náhodných čísel pro generování kryptografických klíčů pro šifrování dat odesílaných přes počítačové sítě.
Hardwarový generátor náhodných čísel je ve výpočetní technice přístroj, který generuje náhodná čísla z fyzikálního procesu, nikoli z počítačového programu. Taková zařízení jsou často založena na mikroskopických jevech, které generují nízkoúrovňový, statisticky náhodný „šumový“ signál, jako je tepelný šum nebo fotoelektrický efekt nebo jiné kvantové jevy. Tyto procesy jsou teoreticky zcela nepředvídatelné a tvrzení teorie o nepředvídatelnosti jsou podrobena experimentálnímu testu. Hardwarový generátor náhodných čísel se obvykle skládá z převodníku, který převede některé aspekty fyzikálních jevů na elektrický signál, zesilovače a dalších elektronických obvodů, které zvýší amplitudu náhodných fluktuací na makroskopickou úroveň, a nějakého typu analogového na digitální převodník, který převede výstup na digitální číslo, často jednoduchou binární číslici 0 nebo 1. Opakovaným vzorkováním náhodně se měnícího signálu se získá řada náhodných čísel.
Generátory náhodných čísel lze také sestavit z „náhodných“ makroskopických procesů pomocí zařízení, jako je hod mincí, kostky, ruleta a loterijní stroje. Přítomnost nepředvídatelnosti v těchto jevech lze odůvodnit teorií nestabilních dynamických systémů a teorií chaosu. I když jsou makroskopické procesy deterministické podle newtonovské mechaniky, výstup dobře navrženého zařízení, jako je ruleta, nelze v praxi předvídat, protože závisí na citlivých mikrodetailech počátečních podmínek každého použití.
Ačkoli kostky byly většinou používány v hazardních hrách a v novější době jako „náhodné“ prvky ve hrách (např. role playing games), viktoriánský vědec Francis Galton popsal způsob, jak používat kostky k explicitnímu generování náhodných čísel pro vědecké účely v roce 1890.
Hardwarové generátory náhodných čísel jsou často relativně pomalé, to znamená, že produkují omezený počet náhodných bitů za sekundu. Aby se zvýšila rychlost dat, často se používají ke generování „semínka“ pro rychlejší kryptografický PRNG, který pak generuje pseudonáhodnou výstupní sekvenci.
Nepředvídatelná náhodná čísla byla nejprve zkoumána v souvislosti s hazardními hrami a mnoho náhodných zařízení, jako jsou kostky, míchání hracích karet a ruleta, bylo poprvé vyvinuto pro takové použití. Spravedlivě produkovaná náhodná čísla jsou životně důležitá pro elektronické hazardní hry a způsoby jejich vytváření jsou někdy regulovány vládními herními komisemi.
Náhodná čísla jsou také používána pro nehazardní účely, a to jak tam, kde je jejich použití matematicky důležité, jako je výběr vzorků pro průzkumy veřejného mínění, tak v situacích, kdy je spravedlnost aproximována randomizací, jako je výběr porotců a vojenských loterií.
Hlavní využití hardwarových generátorů náhodných čísel je v oblasti šifrování dat, například pro vytváření náhodných kryptografických klíčů pro šifrování dat. Jsou bezpečnější alternativou k pseudogenerátorům náhodných čísel (PRNG), softwarovým programům běžně používaným v počítačích pro generování „náhodných“ čísel. PRNG používají deterministický algoritmus pro vytváření číselných sekvencí. Ačkoli tyto pseudonáhodné sekvence projdou statistickými vzorovými testy náhodnosti, díky znalosti algoritmu a podmínek použitých k jeho inicializaci, nazývaných „seed“, lze výstup předpovědět. Protože sekvence čísel produkovaná PRNG je předvídatelná, data šifrovaná pseudonáhodnými čísly jsou potenciálně zranitelná vůči kryptoanalýze. Hardwarové generátory náhodných čísel produkují sekvence čísel, které nejsou předvídatelné, a proto poskytují největší zabezpečení, když se používají k šifrování dat.
Jedním z prvních způsobů výroby náhodných čísel byla variace stejných strojů, které se používaly při hře keno nebo výběru loterijních čísel. V podstatě tyto smíšené očíslované ping-pongové míčky s foukaným vzduchem, možná v kombinaci s mechanickým mícháním, a používají nějakou metodu pro výběr míčků ze směšovací komory (4786056 U.S. Patent 4,786,0564786056
). Tato metoda dává v některých smyslech rozumné výsledky, ale náhodná čísla generovaná tímto způsobem jsou drahá. Metoda je ve své podstatě pomalá a ve většině automatizovaných situací (tj. s počítači) je nepoužitelná.
Milion náhodných číslic se 100 000 normálních odchylek
Fyzikální jevy s kvantově-náhodnými vlastnostmi
Fyzikální jevy bez kvantově-náhodných vlastností
Dalším variabilním fyzikálním jevem, který lze snadno změřit, je posun hodin.
Tento poslední přístup musí být implementován opatrně a může být napaden, pokud tomu tak není. Například dopředná bezpečnost generátoru v Linuxu 2.6.10 by mohla být prolomena s 264 nebo 296 časovou složitostí. Generátor náhodných čísel použitý pro kryptografické účely v rané verzi prohlížeče Netscape byl jistě zranitelný (a byl okamžitě změněn).
Všechny mikroprocesory VIA C3 obsahují od roku 2003 na procesorovém čipu hardwarovou RNG. Namísto použití tepelného šumu jsou surové bity generovány pomocí čtyř volně běžících oscilátorů, které jsou navrženy tak, aby běžely různou rychlostí. Výstup dvou je XORed pro řízení zkreslení na třetím oscilátoru, jehož výstup časuje výstup čtvrtého oscilátoru pro výrobu surového bitu. Drobné rozdíly v teplotě, vlastnostech křemíku a lokálních elektrických podmínkách způsobují pokračující kolísání rychlosti oscilátoru a tím vytvářejí entropii surových bitů. Pro další zajištění náhodnosti jsou na každém čipu vlastně dvě takové RNG, každá umístěná v jiném prostředí a otočená na křemíku. Konečný výstup je kombinací těchto dvou generátorů. Rychlost surového výstupu je desítky až stovky megabitů za sekundu a rychlost bělení je několik megabitů za sekundu. Uživatelský software může přistupovat k generovanému náhodnému bitovému proudu pomocí nových neprivilegovaných instrukcí strojového jazyka.
Softwarová implementace souvisejícího nápadu na běžném hardwaru je obsažena v CryptoLibu, knihovně kryptografických rutin. Algoritmus se nazývá truerand. Většina moderních počítačů má dva krystalové oscilátory, jeden pro hodiny reálného času a jeden pro primární hodiny CPU; truerand této skutečnosti využívá. Používá službu operačního systému, která nastaví budík, běžící mimo hodiny reálného času. Jeden podprogram nastaví, že se budík spustí za jedno tiknutí hodin (obvykle 1/60 sekundy). Další pak vstoupí do cyklu while a čeká, až se budík spustí. Protože se budík nespustí vždy přesně za jedno tiknutí, nejméně významné bity počtu iterací smyčky mezi nastavením budíku a jeho spouštěním se budou náhodně lišit, což může pro některé účely stačit. Truerand nevyžaduje dodatečný hardware, ale v systému s více úlohami je třeba dbát na to, aby nedocházelo k nerandomizujícím interferencím jiných procesů (např. v pozastavení procesu počítání smyčky, kdy plánovač operačního systému spouští a zastavuje různé procesy).
Bitový proud z takových systémů je náchylný ke zkreslení, přičemž převažují buď jedničky, nebo nuly. Existují dva přístupy, jak se vypořádat se zkreslením a dalšími artefakty. Prvním je navrhnout RNG tak, aby se minimalizovalo zkreslení, které je vlastní provozu generátoru. Jedna metoda, jak toto opravit, vrací zpět generovaný bitový proud, filtrovaný low-pass filtrem, aby se upravilo zkreslení generátoru. Podle centrální limitní věty bude mít zpětnovazební smyčka tendenci být dobře nastavená ‚téměř po celou dobu‘. Ultra-vysoké rychlosti generátorů náhodných čísel často používají tuto metodu. I pak jsou generovaná čísla obvykle poněkud zkreslená.
Omezení: Toto zkreslení je pozorováno pouze v případě jednotného typu generátoru náhodných čísel. Existují i jiné typy metody generování náhodných čísel a nejběžnějším způsobem je exponenciální rozdělení. Toto rozdělení bylo prokázáno v diskusi o kostkách vržených. Jakmile lze změřit počet kostek vržených mezi stejným číslem kostky, jedná se o exponenciální rozdělení: P(x)= (1/6)*(5/6)^x
V takovém případě je vygenerované náhodné číslo bez problému zkreslení.
Druhým přístupem ke zvládnutí zkreslení je jeho redukce po generování (v softwaru nebo hardwaru). I když byly podniknuty výše uvedené kroky ke snížení hardwarového zkreslení, stále by se mělo předpokládat, že bitový proud obsahuje zkreslení a korelaci. Existuje několik technik pro redukci zkreslení a korelace, často nazývaných „bělící“ algoritmy, analogicky se souvisejícím problémem generování bílého šumu z korelovaného signálu.
Existuje jiný způsob, dynamicko-statický test, který provádí statickou kontrolu náhodnosti v každém bloku náhodných čísel dynamicky. To lze provést použitelně v krátkém čase, 1 gigabyte za sekundu nebo více.
Při této metodě, pokud má být jeden blok určen jako pochybný, je blok ignorován a zrušen.
Tato metoda je požadována v návrhu ANSI(X9F1).
John von Neumann vynalezl jednoduchý algoritmus pro opravu jednoduchého zkreslení a snížení korelace. Uvažuje bity po dvou, přičemž provádí jednu ze tří akcí: když jsou dva po sobě jdoucí bity stejné, jsou zahozeny; posloupnost 1,0 se stává 1; a posloupnost 0,1 se stává nulou. Představuje tedy klesající hranu s 1 a stoupající hranu s 0. To eliminuje jednoduché zkreslení a je snadno implementovatelné jako počítačový program nebo v digitální logice. Tato technika funguje bez ohledu na to, jak byly bity generovány. Nemůže však zajistit náhodnost ve svém výstupu. Co umí (s významným počtem zahozených bitů) je transformovat zkreslený náhodný bitový proud na nezaujatý.
Další technikou pro vylepšení téměř náhodného bitového proudu je exkluzivní nebo bitový proud s výstupem vysoce kvalitního kryptograficky zabezpečeného generátoru pseudonáhodných čísel, jako je Blum Blum Shub nebo silná proudová šifra. To může zlepšit dekódování a zkreslení číslic za nízkou cenu; může to být provedeno hardwarem, jako je FPGA, což je rychlejší než to udělat softwarem.
Související metoda, která snižuje zkreslení v téměř náhodném bitovém proudu, je vzít dva nebo více nekorelovaných v blízkosti náhodných bitových proudů, a exkluzivní nebo je dohromady. Nechť pravděpodobnost bitového proudu produkujícího 0 je 1/2 + e, kde -1/2 ≤ e ≤ 1/2. Pak e je zkreslení bitového proudu. Jestliže dva nekorelované bitové proudy se zkreslením e jsou exkluzivní nebo-ed dohromady, pak zkreslení výsledku bude 2e². To se může opakovat s více bitovými proudy (viz také lemma Piling-up).
Některé návrhy aplikují kryptografické hašovací funkce jako MD5, SHA-1 nebo RIPEMD-160 nebo dokonce CRC funkci na celý nebo část bitového proudu a pak používají výstup jako náhodný bitový proud. To je atraktivní, částečně proto, že je to relativně rychlé ve srovnání s některými jinými metodami, ale zcela závisí na vlastnostech v hašovacím výstupu, pro které může být jen malý teoretický základ.
PRNG s periodicky aktualizovanou náhodnou klávesou
Jiné návrhy používají to, co jsou považovány za pravé náhodné bity jako klíč pro vysoce kvalitní blokový šifrovací algoritmus, přičemž šifrovaný výstup je brán jako náhodný bitový proud. V těchto případech je však třeba dávat pozor na výběr vhodného blokového režimu. V některých implementacích je PRNG spuštěn pro omezený počet číslic, zatímco hardwarové generátorové zařízení produkuje nové osivo.
Softwaroví inženýři bez generátorů skutečných náhodných čísel se je často snaží vyvinout měřením fyzických událostí, které má software k dispozici. Příkladem je měření času mezi stisky kláves uživatelem a pak se bere nejméně významný bit (nebo dva nebo tři) počítání jako náhodná číslice. Podobný přístup měří plánování úkolů, zásahy do sítě, časy vyhledávání hlaviček disku a další interní události. Jeden návrh Microsoftu obsahuje velmi dlouhý seznam takových interních hodnot (viz článek CSPRNG).
Metoda je riskantní, pokud používá počítačem řízené události, protože chytrý, škodlivý útočník by mohl být schopen předpovědět kryptografický klíč ovládáním externích událostí. Je také riskantní, protože předpokládanou událost generovanou uživatelem (např. stisky kláves) může dostatečně důmyslný útočník zmanipulovat a umožnit tak kontrolu „náhodných hodnot“ používaných kryptografií.
Je velmi snadné si špatně vyložit hardware nebo softwarová zařízení, která se pokoušejí generovat náhodná čísla. Většina se také „rozbije“ tiše a při jejich degradaci často produkuje stále méně náhodných čísel. Fyzickým příkladem může být rapidně klesající radioaktivita kouřových detektorů zmíněných výše. Režimů poruch v takových zařízeních je mnoho a jsou komplikované, pomalé a obtížně odhalitelné.
Stejně jako u jiných součástí kryptografického systému by měl být softwarový generátor náhodných čísel navržen tak, aby odolával určitým útokům. Obrana proti těmto útokům je obtížná.
Hardwarové generátory náhodných čísel by měly být neustále monitorovány kvůli správnému provozu. RFC 4086, FIPS Pub 140-2 a NIST Special Publication 800-90b obsahují testy, které mohou být k tomuto použity. Viz také dokumentace pro novozélandskou kryptografickou softwarovou knihovnu cryptlib.