Hardwarový generátor náhodných čísel aneb náhoda z atomů

Martin Malý 2. 12. 2010

Pořádný generátor náhodných čísel je pro dnešní využití výpočetní techniky zásadní. Například generování šifrovacích klíčů se bez hromady dostatečně kvalitní náhody vůbec neobejde. Většina aplikací se spokojí se softwarovými generátory pseudonáhodných čísel. Ale pokud to chcete pořádně, musíte na to jinak.

Šum bývá často spojován spíš se slovy „odstranit“ nebo „omezit“, my si jej spojíme se slovem „využít“. Dovolte mi začít drobnou literární citací.

Pohon založený na principu nekonečné nepravděpodobnosti je senzační nová metoda, jak překonávat obrovské mezihvězdné vzdálenosti za pouhou nictinu vteřiny a nemuset se přitom zbytečně plácat v hyperprostoru. Byl objeven šťastnou náhodou a poté dotažen v použitelnou formu pohonu výzkumným týmem Galaktické vlády na planetě Damogran. Což je stručná historie tohoto objevu.

Princip generování malých kvant konečné nepravděpodobnosti byl samozřejmě obecně znám. Stačí spojit logické obvody submezonového mozku Čmeláčisko 57 s atomovým vynašečem vektorů, umístěným v nějakém silném zdroji Brownova pohybu, dejme tomu v šálku horkého čaje. Generátory tohoto typu byly často užívány při večírcích k prolomení počátečního ostychu – v souladu s Teorií neurčitosti se vždycky nechaly všechny molekuly hostitelčina spodního prádla naráz odskočit asi o půl metru doleva. Mnozí uznávaní fyzici říkají, že tohle by se tedy rozhodně nemělo trpět. Částečně proto, že je to zlehčování vědy, ale především proto, že na takovéhle večírky je nikdy nikdo nezve.

Další věc, která je pěkně štvala, byla jejich věčná neschopnost sestrojit přístroj, jenž by mohl generovat pole nekonečné nepravděpodobnosti potřebné k bleskové přepravě kosmické lodi mezi nejvzdálenějšími hvězdami, na dálky, nad nimiž zůstává rozum stát. Nakonec mrzutě prohlásili, že takový přístroj sestrojit nelze.

A pak jednoho dne jakýsi studentík, kterého nechali uklízet laboratoř po jednom zvlášť nepovedeném večírku, začal uvažovat asi takhle: Jestliže je skutečně nemožné sestrojit takový přístroj, pak to logicky musí být konečná nepravděpodobnost. Takže stačí vypočítat přesně, jak je to nepravděpodobné, zadat výsledek generátoru konečné nepravděpodobnosti, nalít mu pořádný šálek horkého čaje a… zapnout ho!

Tak to také udělal, a udiveně zjistil, že se mu podařilo vyrobit onen dlouho hledaný zlatý generátor nekonečné nepravděpodobnosti jen tak z ničeho nic. A ještě víc ho udivilo, když hned poté, co získal Cenu Galaktického institutu za mimořádnou mazanost, byl zlynčován rozvášněným davem fyziků. Konečně jim došlo, že jediná věc, kterou doopravdy nemůžou vystát, je právě takovýhle chytrák.

(Douglas Adams, Stopařův průvodce po Galaxii, překlad Jana Hollanová)

Ti z čtenářů, kteří mají přístup k submezonovému mozku Čmeláčisko 57 a k atomovému vynašeči vektorů, mohou zkusit původní pokus, my ostatní se spokojíme místo Čmeláčiska s Arduinem. Ukážeme si, jak generovat náhodná čísla hardwarově a demonstrujeme si postup prakticky, s Arduinem.

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

Náhodná čísla jsou v programování a IT velmi často používaná – a nemusí jít jen o náhodu ve hrách. Náhodná čísla hrají svou roli v komunikaci, v kryptografii a ve spoustě dalších oblastí. Problém je ale s generováním takovýchto čísel, resp. s tím, aby „náhoda byla opravdu náhodná“. Pamatujete se na pokyn „pohybujte hodně myší“, který dávají některé programy pro generování šifrovacích klíčů?

Tohle asi nebude náhoda…

Softwarové generování náhody

Některé jednodušší systémy používají k vypočítání náhodného (lépe řečeno pseudonáhodného) čísla matematických postupů a řad, jejichž výsledky vypadají velmi náhodně. Problém je, že pro stejné počáteční číslo (seed) je i posloupnost výsledků stejná. Do výpočtu náhody se proto zavádějí další prvky, jako je třeba počítadlo milisekund strojového času, kterým se matematická posloupnost na počátku „znáhodní“ (randomize).

Hardwarové generování náhody

Tam, kde je potřeba „opravdová náhoda“ nebo kde podmínky umožňují použití samostatného zařízení, tam se používá hardwarový generátor náhodných čísel. Jeho princip bývá založen na měření určitého jevu, který nastává náhodně (např. rozpad radioaktivních látek). Tam, kde není vhodné použít radioaktivní materiál, lze jako zdroj náhodného signálu použít šum.

Šum

Šum je, zjednodušeně řečeno, náhodný signál. V telekomunikaci se rozeznává několik různých druhů šumů, podle jejich charakteristik. Nejznámější je pravděpodobně bílý šum, který má konstantní výkonovou spektrální hustotu, což znamená, že stejně široká frekvenční pásma mají stejnou energii. Název je analogií s bílým světlem, které obsahuje rovnoměrně zastoupené všechny frekvence – i v bílém šumu jsou (teoreticky) zastoupeny rovnoměrně všechny frekvence. V literární ukázce zmíněnému Brownovu pohybu odpovídá červený (nebo též hnědý) šum – ten obsahuje více nižších frekvencí.

Není nad pěkný šum…

Šum získáme poměrně snadno – stačí vzít staré rádio a naladit ho na frekvenci, kde nevysílá žádná rozhlasová stanice. Výstup takového rádia můžeme připojit přes kondenzátor na analogový vstup Arduina. Pokud jej budeme v pravidelných intervalech vzorkovat, dostaneme náhodná čísla.

Další možnost, jak získat šum, je využít faktu, že polovodičový P-N přechod šumí. Nejčastěji se používá Zenerova dioda v závěrném směru či přechod emitor-báze u bipolárního tranzistoru. Při dostatečně nízkém proudu, který nezničí přechod průrazem, vzniká na P-N přechodu šum, jehož spektrum se velmi blíží bílému šumu.

I další možnost počítá se šumem polovodičových přechodů. Pokud totiž nastavíte A/D převodník na vyšší citlivost a necháte vstup „ve vzduchu“, tj nepřivedete na něj žádný signál, bude převodník měřit šum, co na vstupu vzniká jako výsledek rušení od zbytku čipu, od vnějších obvodů, od statické elektřiny, bude zkrátka přijímat veškerý elektromagnetic­ký smog…

Pokud budete používat jako zdroj šumu nějakou externí součástku, můžete využít faktu, že se šum zvyšuje s rostoucí teplotou. Zenerova dioda, vhodně ohřátá (nalijte jí třeba pořádný šálek horkého čaje…) bude produkovat šum mnohem líp.

Zpracování šumu v Arduinu

Zpracování je velmi jednoduché:

 void setup() {
  Serial.begin(9600);
  //analogReference(INTERNAL);
 }
 
 void loop() {
  int val=0;
  for (int i=0;i<8;i++){
   int analogValue = analogRead(0);
   val = val << 1;
   val += (analogValue & 1);
  }
  
   Serial.println(val);
   analogRead(0);
 }

V části setup pouze nastavíme sériový přenos. Pokud necháme vstup „viset ve vzduchu“, můžeme zkusit přepnout na vnitřní zdroj referenčního napětí, které je 1.1V (u starších modelů s procesorem ATMega8 je to 2.56V), získáme tak vyšší přesnost (a tedy i silnější šum).

Ve smyčce pak vzorkujeme hodnotu na analogovém vstupu a používáme z ní vždy ten nejnižší bit. Osm takto získaných bitů složíme do jednoho bajtu, a ten odešleme po sériové lince. Analogový vstup je pak přečten ještě jednou naprázdno.

Získáme tak zdroj náhodných čísel, které nám jdou po sériovém rozhraní, oddělené znakem nový řádek. Využití je už na konkrétní aplikaci.

Ukázková aplikace

Opět jsme sáhli k jednoduchému vizualizačnímu nástroji Processing. Čteme čísla ze sériového vstupu a kreslíme histogram.

import processing.serial.*;
Serial myPort;
int[] num = new int[256];
void setup () {
  size(256, 400);       
  println(Serial.list());
  myPort = new Serial(this, Serial.list()[2], 9600);
  myPort.bufferUntil('\n');
  for (int i=0;i<256;i++) {num[i]=0;}
}
void draw () {
  //zase nic
}
void serialEvent (Serial myPort) {
  String inString = myPort.readStringUntil('\n');
  if (inString != null) {
   
    //zpracování teploty - modrý graf
    inString = trim(inString);
    float inByte = float(inString);
    int n = floor(inByte);
    num[n]++;
    stroke(127,34,255);
    line(n, 400, n, 400-num[n]);
   
  }
}

Na výsledku můžeme snadno vidět, jak moc je naše náhoda náhodná. Pokud budou sloupečky vyrovnané, získali jsme opravdu náhodný generátor.

Vypadá to, že náhoda je opravdu náhodná

Můžete si vyzkoušet, co se stane, když diodu odstíníte (např. umístěním do kovové klece), co se stane, když se jí dotknete rukou, když ji zchladíte nebo naopak ohřejete… experimentování se meze nekladou.

widgety

Náhodnost…?

Tématem měření náhodnosti náhodných čísel se zabýval článek o programu Ent zde na Rootu. Předložili jsme mu soubor cca 50 kB dat, získaných ze šumu Zenerovy diody a se zvýšenou citlivostí A/D převodníku. Výsledek byl následující:

Entropy = 7.990824 bits per byte.
Optimum compression would reduce the size
of this 53943 byte file by 0 percent.
Chi square distribution for 53943 samples is 476.42, and randomly
would exceed this value less than 0.01 percent of the times.
Arithmetic mean value of data bytes is 126.8738 (127.5 = random).
Monte Carlo value for Pi is 3.183092325 (error 1.32 percent).
Serial correlation coefficient is -0.000661 (totally uncorrelated = 0.0).

Je tedy vidět, že se jedná opravdu o náhodná čísla. Pro porovnání – výsledky pro data ze zdroje /dev/random, který je považován za poměrně kvalitní a dává výsledky jen ve chvíli, kdy pro ně má dostatek dat:

Entropy = 7.866459 bits per byte.
Optimum compression would reduce the size
of this 1664 byte file by 1 percent.
Chi square distribution for 1664 samples is 291.69, and randomly
would exceed this value 10.00 percent of the times.
Arithmetic mean value of data bytes is 124.9910 (127.5 = random).
Monte Carlo value for Pi is 3.220216606 (error 2.50 percent).
Serial correlation coefficient is 0.008519 (totally uncorrelated = 0.0).

Desky Arduino Uno a Arduino Mega 2560 k redakci zapůjčil obchod HW Kitchen, Arduino a Ethernet Shield obchod Czechduino. Děkujeme za laskavé zapůjčení.

Našli jste v článku chybu?
Lupa.cz: Patička e-mailu závazná jako vlastnoruční podpis?

Patička e-mailu závazná jako vlastnoruční podpis?

Vitalia.cz: 5 pravidel proti infekci močových cest

5 pravidel proti infekci močových cest

DigiZone.cz: Parlamentní listy: kde končí PR...

Parlamentní listy: kde končí PR...

Vitalia.cz: Voda z Vltavy před a po úpravě na pitnou

Voda z Vltavy před a po úpravě na pitnou

Lupa.cz: Jak levné procesory změnily svět?

Jak levné procesory změnily svět?

Vitalia.cz: dTest odhalil ten nejlepší kečup

dTest odhalil ten nejlepší kečup

Vitalia.cz: Tesco nabízí desítky tun jídla zdarma

Tesco nabízí desítky tun jídla zdarma

120na80.cz: Pálení žáhy: která jídla ne a co nás uzdraví?

Pálení žáhy: která jídla ne a co nás uzdraví?

Vitalia.cz: Tahák, jak vyzrát nad zápachem z úst

Tahák, jak vyzrát nad zápachem z úst

DigiZone.cz: Nova opět stahuje „milionáře“

Nova opět stahuje „milionáře“

Vitalia.cz: Jsou vegani a vyrábějí nemléko

Jsou vegani a vyrábějí nemléko

Lupa.cz: Adblock Plus začal prodávat reklamy

Adblock Plus začal prodávat reklamy

120na80.cz: Co je padesátkrát sladší než cukr?

Co je padesátkrát sladší než cukr?

Vitalia.cz: Jak Ondra o astma přišel

Jak Ondra o astma přišel

Podnikatel.cz: Nemá dluhy? Zjistíte to na poště

Nemá dluhy? Zjistíte to na poště

Vitalia.cz: Antibakteriální mýdla nepomáhají, spíš škodí

Antibakteriální mýdla nepomáhají, spíš škodí

DigiZone.cz: Budoucnost TV vysílání ve Visegrádu

Budoucnost TV vysílání ve Visegrádu

Podnikatel.cz: Rohlik.cz testoval roboty pro rozvážku

Rohlik.cz testoval roboty pro rozvážku

120na80.cz: Galerie: Čínští policisté testují českou minerálku

Galerie: Čínští policisté testují českou minerálku

Podnikatel.cz: Letáky? Lidi zuří, ale ony stále fungují

Letáky? Lidi zuří, ale ony stále fungují