Generování náhodných čísel

DEFINICE Náhodné číslo nelze předpovědět. Můžeme se tedy bavit o jeho definici, ale nikoliv o číslu samotném. Ná...


DEFINICE
Náhodné číslo nelze předpovědět. Můžeme se tedy bavit o jeho definici, ale
nikoliv o číslu samotném. Náhodná čísla se mohou tvořit na základě fyzických
procesů, jako je např. házení kostkami či mincí nebo počítání intervalů mezi
radioaktivními rozpady jednotlivých atomů. Software sám nedokáže generovat
skutečná náhodná čísla; místo toho vytváří tzv. pseudonáhodná čísla, odvozená
od prvního skutečně náhodného.
Myslíme si, že náhodná čísla jsou libovolná a dopředu nepředpověditelná.
Matematicky řečeno daný řetězec čísel je náhodný, pokud neexistuje kratší
způsob vyjádření řetězce než právě řetězec samotný. Proto žádná souslednost
čísel vzniklá na základě výpočtu nemůže být skutečně náhodná.
Na náhodná čísla můžeme také pohlížet jako na čísla, která se nedají
komprimovat. Tato definice vylučuje i číslice, ze kterých je složeno číslo pí
(3,14...), protože počítač je schopný vytvořit několik miliard desetinných míst
pí použitím pouze velmi krátkého vzorečku: podělí obvod kruhu jeho průměrem.
Můžete tedy komprimovat miliardu číslic do jednoduchého tvaru C/d. Když ale
zrovna nemůžete najít program, který dokáže danou sekvenci komprimovat,
neznamená to ještě, že ho za měsíc někdo neobjeví.
Intuitivně bychom za náhodná považovali čísla, která na první pohled postrádají
mezi sebou postřehnutelnou souvislost, ale ani to není tak jednoduché. Náhodné
procesy mohou také občas produkovat krátké sledy čísel, které se budou zdát
nenáhodné.

K čemu vlastně
Proč nás vlastně zajímají náhodná čísla? Protože jsou velmi užitečná ve
statistice, při testování procedur a softwaru a především v šifrování.
Jediný nepřekonatelný šifrovací systém používá to, čemu se říká one-time pad
(dále OTP, česky "jednorázová výplň"). Jedná se o řetězec náhodných čísel nebo
písmen, který lze po určité transformaci použít jako klíč k zašifrování zprávy.
Pokud je tato výplň použitá pouze jednou a je skutečně náhodná, nikdy nemůže
být odhalena. Pokud ji však použijete dvakrát, už je teoreticky možné ji
odhalit.
Vznik náhodného čísla
Během druhé světové války tvořili britští šifrovací odborníci náhodná čísla pro
OTP podobnou metodou, jako při losování čísel v bingu nebo v loterii. Tahali
čísla z klobouku nebo ze stroje, který míchal jejich pořadím.
Taková metoda fungovala, ale byla pomalá a pracná. Dnes používáme software,
generátory pseudonáhodných čísel. Vezmou si určité vstupní číslo a provedou s
ním sérii transformací a procedur. Toto vstupní číslo musí být opravdu náhodné
a je obvykle založeno na nějaké nepředvídatelné události z reálného světa. V
nejjednodušším případě například z čítače reálného času v hodinách počítače
přesně v okamžiku spuštění programu.
K vytvoření náhodného čísla může být využito různých fyzikálních procesů. Jedna
metoda používá radioaktivní rozpad, který je podle fyzikální teorie považován
za náhodný. Internetový zdroj HotBits generuje náhodná čísla sledováním
časového průběhu radioaktivního rozpadu částic, jak je zaznamenáván
Geiger-Müllerovou trubicí.
Od roku 1999 dodává společnost Intel harwarový generátor náhodných čísel, který
se používá s jejich procesorovými čipsety sérií 8xx. K vytváření náhodného,
nedeterministického a neopakujícího se proudu bitů využívá tepelného šumu
připojeného rezistoru.
Asi nejpodivnějším zdrojem náhodných čísel jsou lávové lampy. Ano, ty lávové
lampy, které byly populární v 60. a 70. letech. Připomínají zespoda osvětlenou
zúženou žárovku, ve které probublávají barevné kuličky kapaliny. Jejich použití
pro generování náhodných čísel navrhli vědci Robert G. Mende Jr., Landon Curt
Noll a Sanjeev Sisodiya z kalifornské společnosti Silicon Graphics. Nalezenému
procesu se začalo říkat "lavarand". Noll a jeho kolegové zjistili, že
nepředvídatelné vznášení a klesání kapek v lávové lampě by mohlo sloužit jako
vhodný zdroj náhodnosti. Jejich postup při generování náhodných čísel je
následující:
- Digitální kamera periodicky fotografuje soustavu šesti lávových lamp, přičemž
k datům přidává ještě svůj vlastní elektronický šum. l921 600 bajtů původního
obrázku je komprimováno a zakódováno do 140bajtového souboru. Uvedená data pak
slouží jako první číselná hodnota softwarovému generátoru pseudonáhodných
čísel. "Protože se mohl použít jakýkoliv dobrý zdroj chaotických dějů, rozhodli
jsme se pro lávové lampy. Částečně také proto, že se nám prostě tak líbí...,"
prohlašovali zmínění vědci.

Na internetu
Důležitost vytváření ryze náhodných čísel vysvětluje Leif Svalgaard ve své
studii Generování skutečně náhodných čísel (cobolreport.com/columnists/leif/).
Poznamenává, že "jakmile začal internet získávat sympatie široké veřejnosti,
stala se aktuální i otázka bezpečného přenosu finančních dat (jako například
čísel kreditních karet). Prohlížeč od Netscape Communications začal pro tyto
účely používat Secure Socket Layer (SSL). Stručně řečeno SSL chrání komunikaci
na síti tím, že zprávy šifruje tajným klíčem velkým náhodným číslem."
Bezpečnost SSL zcela závisí na náhodnosti zmíněného čísla. V roce 1995 ale dva
vědci odhalili, že internetový prohlížeč generoval svá náhodná čísla pouze na
základě aktuálního času a identifikačních čísel tohoto procesu a jeho
parentálního procesu. K rozluštění kódu jim pak stačila ani ne minuta.









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.