Pseudorandom number generators/cs

Úvod

Programátoři i lidé, využívající v počítačových technologiích náhodná čísla, se často domnívají, že jsou náhodná generovaná čísla opravdu zcela náhodná, anebo nad tím ani příliš nepřemýšlí a prostě se na náhodnost spoléhají. Nicméně v IT světě není nic zcela náhodného. Ať už jsou vstupy do systému jistým způsobem předpověditelné dle statistických údajů (například díky dlouhodobému měření), i u náhodnosti postupuje počítač dle nějakého algoritmu. Dokonce i člověk, pokud má dát nějaké zcela náhodné číslo, lze jeho číslo pomocí tzv. Benfordova zákona očekávat v určitém formátu. Bavíme se tedy ještě o světě náhodnosti nebo o propracovaných algoritmech, které se tak pouze tváří a které si v běžném životě ani neuvědomujeme?

Pseudonáhodná čísla

Vzhledem k tomu, že generovaná čísla skutečně nejsou naprosto náhodná, označují se tato čísla jako pseudonáhodná. Pokud bychom se chtěli opravdu více přiblížit náhodě, můžeme sáhnout po přírodních zákonech a nechat si pomoci. Své o tom ví i HotBits (viz Fyzikální generátory náhodných čísel).

Pseudonáhodná nebo náhodná čísla?

Může vyvstat otázka, zda je lepší sada čistě náhodných čísel nebo pseudonáhodných čísel. Náhodná čísla například generovaná člověkem nebo přírodou mohou být nevhodná vzhledem k tomu, že některá čísla se opakují vícekrát a jiné méněkrát. Náhodnost může být ovlivněna tím, že člověk X ve výčtu od 1 do 100 preferuje častěji spíše čísla pod 50 a čísla nad 50 se vyskytují méně. Je zde ovšem porušena 100% náhodnost neboť každé číslo z výběru nemá naprosto stejnou pravděpodobnost výběru jako ostatní čísla. Taktéž výběr nevhodného přírodního jevu může způsobit, že některá čísla se vyskytují méně. V potaz můžeme vzít například šum pozadí. Jenže i šum existuje v různých barvách a tudíž se opět dostávají ke slovu některé hodnoty více než jiné. V pseudonáhodných posloupnostech je hlídáno, aby bylo rozdělení náhodné veličiny opravdu pseudonáhodné s výskytem rovnoměrným dle vybrané pravděpodobnostní funkce. Generování poté už není zcela náhodné, ale rozdělení hodnot se tak tváří. Vybráním vhodné pravděpodobnostní funkce můžeme pravděpodobnost čísel ovlivnit, avšak o zbytek se stará už generátor. U skutečně náhodných čísel může být také problém v jejich pomalejším získávání, zatímco generátor pseudonáhodných čísel plní pouze funkce algoritmů a může tak dodat kvanta náhodných hodnot během malé chvíle. Tam, kde tedy nezáleží příliš na náhodnosti, kde je potřeba spousta náhodných čísel během chvilky a kde je potřeba občas danou posloupnost hodnot zopakovat, se může více hodit posloupnost pseudonáhodných čísel. V oblastech hazardu či kryptografie, kde je naopak nežádoucí opakování posloupností, je naopak spíše žádán generátor skutečně náhodných čísel generovaných různými fyzikálními jevy. Ku příkladu je jasné, že by lidé sázející ve sportce neměli důvěru v losovaná čísla, pokud by byla vylosována algoritmem. A problém by nevyvstal pouze v nedůvěře. Chytří lidé by si čísla zapisovali tak dlouho, dokud by nenašli řád mezi losovanými čísly a tím by mohli odhalit algoritmus, což si nepřeje ani sázková kancelář. Točení míčků je tedy sice také dáno algoritmem fyzikálním (tření, gravitace, spin, akce a reakce a další), ovšem počáteční seed je vždy náhodný, moment vytažení také, a tak je výsledek pokaždé jiný.

Fyzikální generátory náhodných čísel

Fyzikální generátory jsou založeny na fyzikálních jevech, produkující nějaký šum. Ať už se jedná o atmosférický šum či využití fotoelektrického jevu. V následujících podkapitolách si ukážeme praktické příklady generátorů náhodných čísel TRNG (True Random Number Generator – Pravý generátor náhodných čísel).

HotBits

Jednou z firem, získávající data tímto způsobem je švýcarská HotBits jenž generuje posloupnost pseudonáhodných bajtů na základě generátoru, který se řídí radioaktivním rozpadem částic, detekovaných v Geiger-Müllerové trubici propojené s počítačem. V tomto případě byl tedy generátor pseudonáhodných čísel nahrazen přírodním algoritmem.

RADOM.ORG

Další online službou je RANDOM.ORG, která získává náhodná čísla díky atmosférickému šumu. Je ale zapotřebí si hlídat nežádoucí šum, jako například ventilátor z počítače, který šum může ovlivnit a zanášet do něj svůj šum. Problém je pochopitelně v tom, že ventilátor produkuje pravidelný šum, který může náhodnost šumu snížit. RANDOM.ORG samozřejmě využívá faktu, že nikdo nezná rozpoložení a pohyb všech molekul vzduchu na planetě, proto se ani generovaná čísla nedají odhadnout. Místy navíc může zuřit nevyzpytatelná bouřka, což může šum také ovlivnit.

Silicon Graphics

Jedná se o amerického výrobce počítačového hardwaru, který přišel s tzv. lavarand generátorem. Jeho principem je snímkování lávové lampy, v níž se volně a náhodně pohybuje materiál. Ten je snímkován jako vzor a z těchto snímků pak generátor vytváří posloupnosti náhodných dat. Protože pohyb materiálu je náhodný, jsou pak i čísla zcela náhodná.

Generátor na základě lidského vstupu

Existují také generátory, které generují náhodná čísla z pohybu PC myši či z intervalů mezi jednotlivými stisky kláves na klávesnici. Zde ovšem vyvstává problém v tom, že operační systém načítá rychlé stisky kláves do bufferu a odesílá po více znacích najednou. To samozřejmě ovlivňuje náhodnost dat.

Generování čísel míčky

Tento generátor se využívá konkrétně v Sazce. Protože se zde hraje o vysoké peněžní částky, je pochopitelné, že čísla nejsou generována generátorem pseudonáhodných čísel. Přestože můžeme říci, že jsou do procesu výběru zapojeny fyzikální algoritmy (přitažlivá síla na základě hmotnosti míčků, třecí síla, zákon akce a reakce při odrazech a další), je výsledek těchto algoritmů tak složitý, jako louskání některých klíčů či komunikace v oboru kryptografie. Generování probíhá tak, že je notářem vybrána jedena z osmi sad míčků. Míčky jsou následně zkontrolovány, zda není některý z nich poškozený, zda jsou všechny čisté a zda nejsou poškozeny štítky s čísly, které musí být 100% čitelné. Dále je provedena kontrola losování, aby bylo jisté, že vše funguje bezchybně a nenastane během losování žádná chyba. Teprve pak je spuštěno losování neboli generování náhodných čísel (u Sazky v rozmezí 1-80 včetně). Je zřejmé že v Sazce generátor určí, komu připadne obrovská suma peněz, proto je celý proces generování možná jedním z nejostřeji nejsledovanějších, ať už notáři, techniky, ale i veřejností.

Generátory pseudonáhodných čísel v praxi

Tyto generátory nachází své uplatnění v místech, kde jistá pravidelnost není na obtíž nebo kde je potřeba se k vygenerované sekvenci dostat vícekrát. Své uplatnění najdou například v přehrávačích hudby, kde je zapnuta funkce náhodného výběru další skladby. Dále pak také v simulacích či modelování.

Lineární kongruentní generátor

Lineární kongruentní generátor je jedním z nejstarších a dle také nejrozšířenější z generátorů pseudonáhodných čísel. Každý další prvek je spočítán pomocí funkce Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_{n+1}=(l\times x_n+m)\bmod{M}} , přičemž Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M} je horní mez velikosti prvků, která má funkci modulo neboli zbytek po dělení číslem Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M} . Pokud je například Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M=10} , pak nejvyšší náhodné číslo bude 9. Pokud kupříkladu zvolíme Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M} rovno 27, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle l} rovno 5, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m} rovno 9 a první prvek (seed) zvolíme 8, pak další čísla dle výše uvedeného vztahu budou 22, 11, 10, 5, 7, 17 atd. U 19. prvku ovšem dostáváme opět 8, 22, 11 a řada se celá opakuje. Nevhodnou volbou parametrů se může stát, že bude opakování častější. UNIXová funkce rand() (viz Generátory programovacích jazyků) používá tento generátor také a to s parametry Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle l=1103515245} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle m=12345} a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M=2^{32}} . Pro počítače IBM byl zase generátor Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_{n+1}=(65539\times x_n) \bmod{2^{31}}} .

Fibonacciho generátor

Fibonacciho generátor se odvíjí od Fibonacciho posloupnosti, kde každý další prvek je součtem předchozích dvou. Posloupnost začíná při počátku v 1 jako 1, 2, 3, 5, 8, 13, 21 atd. Pokud přidáme jako u předchozího generátoru opět Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \bmod{M}} , omezíme získaná čísla zase na celočíselné zbytky po dělení Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle M} a tím stanovíme horní mez pro získané hodnoty. Podobně založen byl Millerův a Prenticův generátor, který byl definován vzorcem Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle x_{n+1}=(x_{n-2}+x_{n-3})\bmod{3137}} , jenž má periodu po 9843907 prvcích.

Mersenne Twister

Algoritmus Mersenne Twister (také jako MT19937) je nejen velmi rychlý, ale má i velkou periodu (počet čísel, po které se začne řada opakovat) Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2^{19937}-1} . Je dokonce rychlejší než lineárně kongruentní generátor, ovšem je mnohem náročnější na paměť. Díky své rychlosti a velké periodicitě se výborně hodí pro různé simulace. Stojí za zmínku, že tento algoritmus je mimo jiné také využit ke generování náhodných čísel pro funkci RAND (česky NÁHČÍSLO), a to konkrétně v Officech 2010 , a pak je také tento generátor využit v Simulačním softwaru NetLogo, kde je také použit ke generování ve funkci random . MT19937 je využit v mnohých softwarech od MS Office až po různé simulační programy a v neposlední řadě také v mnoha programovacích jazycích.

Complimentary-multiply-with-carry

Jedná se o alternativu k algoritmu Mersenne Twister, který má ještě větší periodu Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2^{131086}} a je ještě rychlejší, ale opět paměťově ještě náročnější.

MS Excel generátor pseudonáhodných čísel

Náhled možností generátoru v MS Excel

File:RovnomerneRozdeleni.PNG

První graf rovnoměrného rozdělení hodnot od 1 do 100

File:RovnomerneRozdeleni.PNG

Druhý graf rovnoměrného rozdělení hodnot od 1 do 100

File:RovnomerneRozdeleni.PNG

Třetí graf rovnoměrného rozdělení hodnot od 1 do 100

MS Excel obsahuje v sobě zabudovaný též generátor pseudonáhodných čísel. Jak bylo zmíněno výše (viz Mersenne Twister), pracuje na principu MT19937, což znamená, že jeho periodicita je po Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle 2^{19937}-1} prvcích. Najdeme jej pod kartou Data a následně Analýza dat. Jedná se o doplněk, který musí být dodatečně dodán. Po kliknutí vybereme Generátor pseudonáhodných čísel. Následné okno je přizpůsobeno podle volby Typu rozložení. Co je ale společné, je počet proměnných (udává počet generovaných sloupců) a počet náhodných čísel (počet generovaných řádků). Pokud se pokusíme o rovnoměrné rozdělení, můžeme se podívat, jak tyto generátory fungují. Pro názornost byly vybrány 3 sloupce po 1000 čísel od 1 do 1000. Obrázky na pravé straně zachycují histogram z určitých intervalů. Můžeme vidět, že se algoritmus opravdu snaží o rovnoměrné rozmístění náhodných čísel. Jen tak pro zajímavost, směrodatné odchylky jsou pro první graf 28.72, pro druhý 28.08 a pro třetí 28.94. Vidíme tedy že algoritmus se opravdu držel nízké odchylky, přičemž ve druhé posloupnosti se mu to dařilo nejlépe a v poslední nejhůře. U třetího totiž upřednostňoval více čísla z inervalu 1-11. Pokud vyzkoušíme generátor například Normálního rozdělení, algoritmus opět hlídá rovnoměrnost dle nastavených parametrů. Opět ale každá řada vychází jinak. Narážíme zde na zmíněnou výhodu a nevýhodu zároveň, a sice opakovatelnost pseudonáhodných posloupností. Ať se mohou vygenerovaná čísla jevit jakkoliv náhodná, byla vypočítána algoritmem. Klíčové políčko je v nastavení generátoru Základ generátoru (neboli seed). Pokud vygenerujeme posloupnost např. 1000 čísel od 1 do 100 a zadáme základ například 3, při každém dalším pokusu se stejnými parametry a hlavně základem dostáváme opět tutéž samou posloupnost čísel. To je v různých oborech žádoucí a v jiných nikoliv.

Kryptografie

Náhodná čísla se uplatňují také v oboru kryptografie, ať už se jedná o elektronické podpisy nebo šifrování dat. Ku příkladu můžeme uvést RSA generátor, který je používán pro generování bezpečné RSA šifry. Pro RSA šifru je potřeba vygenerovat dle předepsaného algoritmu klíč veřejný a privátní. Zjištění privátního klíče není nemožné, ovšem zabere tolik času, že jsou data již neaktuální. Posuneme-li se dále, bude nás zajímat, co vše musí generátor pseudonáhodných čísel v kryptografii splňovat. Je zřejmé, že kryptografie je citlivý obor, kde budou kladeny vyšší nároky na generátor pseudonáhodných čísel.

• Čísla musí být pseudonáhodná, což znamená, že nelze v relativně blízké době s pravděpodobností větší než 50 % zjistit další číslo.
• I za předpokladu, že uniknou data o stavu generátoru nesmí být snadné opět zjistit již vygenerovanou sekvenci. Této podmínce říkáme dopředná bezpečnost.
• Pokud se útočník dostane k datům generátoru a zná tak jeho současný stav, i přesto by neměl být schopen generovat stejná čísla jako generátor. Této podmínce se říká zpětná bezpečnost a můžeme jí docílit například pravidelným přidáváním entropie do současného stavu.

Generátory programovacích jazyků

C

Pro linuxový jazyk C je pro práci s pseudonáhodnými čísly použita funkce rand() a srand() ze standardní funkce <stdlib.h>. Funkce rand() vrací náhodné číslo od 0 do RAND_MAX, funkce srand čísla nevrací, ale poskytuje možnost zadání seed neboli počátku (pro případ, že budeme chtít posloupnost zopakovat) pro funkci rand(). Bohužel se tyto funkce ukázaly jako špatná volba pro dostatečnou náhodnost generovaných čísel. Proto nejsou vhodné k použití, kde je potřeba dobrá náhoda čísel, jako například v kryptografii.

C#

Ve světě C# existuje třída pro práci s pseudonáhodnými čísly System.Random. Tato třída se inicializuje formou semínka seed (pokud není zadáno, použije se aktuální datum a čas). Dále pak obsahuje funkce Next(), která vrátí další pseudonáhodné číslo, Next(Int32), vracející pseudonáhodná čísla menší než zadaný parametr a nakonec Next(Int32,Int32) vracející čísla větší než první argument a menší než druhý argument. Generátor v jazyce C# se zdá být mnohem lepší než pro jazyk C. Pracuje pomocí algoritmu, který založil Donald E. Knuth. Problém nastává ve chvíli, kdy ve stejném cyklu pokaždé inicializujeme Random a následně vygenerujeme další číslo. Protože cykly probíhají standardně velmi rychle, je semínko většinu cyklů stejné, a tak se může stát, že dostaneme více stejných čísel. Tomu se pochopitelně můžeme vyhnout tím, že Random inicializujeme pouze jednou. Další problém nastává, pokud používáme více vláken Thread. Zde se doporučuje, aby si každé vlákno inicializovalo svou instanci Random.

Java

Pro jazyk Java lze využít hned dvě různé funkce Random(), každá z jiné knihovny. První je z knihovny java.lang.Math a druhá z java.util.Random. Při použití Math.random() dostáváme hodnoty v rozsahu 0 až 1. Můžeme tedy dostat číslo například 0.42589632565639872. Pochopitelně zapojením této funkce s dalším upravujícím kódem lze funkci přizpůsobit, aby vracela čísla v jiném rozsahu. Třída Random jakožto druhá varianta pak umí vracet více typů jako float, double, long či boolean. Tato třída generuje náhodná čísla pomocí lineárního kongruentního generátoru (viz kapitola Lineární kongruentní generátor). Generování je tedy velmi rychlé, ale nelze využít na jiné bezpečnostní či identifikační účely.

Závěr

Generátory pseudonáhodných čísel jsou nepostradatelnou součástí programovacích jazyků, simulačních prostředí a dalších softwarů. Oproti generátorům skutečně náhodných čísel mají své výhody jako rychlost a opakovatelnost v místech, kde si to přejeme, ale na druhou stranu trpí nedostatkem náhodnosti, protože posloupnost získávaných čísel se může v jistém bodě znovu opakovat. Proto se nehodí pro bezpečnost či hazard. Vždy bychom si proto měli být vědomi, který typ generátoru používáme, jak rychle potřebujeme čísla dostávat a jak moc nám záleží na nevyzpytatelnosti generovaných čísel.