3. Optoelektronický generátor náhodných čísel Fyzikální generátor náhodných čísel může být založen na nejrůznějších fyzikálních procesech. Jde přitom o to, aby proces samotný byl náhodný ve smyslu nepředpověditelnosti výsledku jeho individuální realizace a vzájemné nekorelovanosti takovýchto individuálních realizací. Tato náhodnost může být • praktická, kdy systém je sice po teoretické stránce považován za deterministický, ale je popsán mnoha (často neúplně známými) parametry a obvykle není přesně znám jeho počáteční stav (nebo je technicky obtížné připravit systém opakovaně ve stejném počátečním stavu, příkladem takového generátoru náhodných čísel je třeba ruleta), Na tomto principu fungují generátory založené na sledování šumu (např. elektrický šum na Zenerově diodě). • fundamentální, kdy náhodnost je zahrnuta přímo ve fyzikální podstatě jevu a jev je jako náhodný popsán i fyzikálními zákony. V oblasti kvantové fyziky existuje celá řada jevů, které jsou náhodné ze své samotné podstaty. Zákony kvantové mechaniky popisují chování souborů kvantových objektů, nejsou ale, vyjma speciálních případů, schopny předpovědět s určitostí chování individuálního kvantového objektu; předpovídají pouze pravděpodobnosti, s jakými nastane ten či onen konkrétní jev. Důvodem přitom není, jak dnes dotvrzuje velké množství experimentálních dat, momentální neznalost jakýchsi ”skrytých” proměnných - jde o skutečně fundamentální vlastnost mikrosvěta, kterou nelze nijak obejít! To poskytuje velmi dobrý prostor pro konstrukci generátoru náhodných čísel splňujícího nejpřísnější kritéria vyžadovaná např. kryptologickými aplikacemi. Vybereme-li nějaký elementární kvantový proces, který jsme schopni dobře teoreticky analyzovat, tj. určit pravděpodobnosti všech jeho možných výsledků, a jsme-li schopni takový proces opakovaně za dobře definovaných podmínek experimentálně realizovat, můžeme jej použít jako základ pro generaci náhodných čísel. 3.1. Zvolený fyzikální proces − dělení světla na děliči svazku Jedním z elementárních kvantových procesů je dopad světelného kvanta-fotonu na tzv. dělič svazku. Jedná se o zařízení, které se v klasické optice používá k rozdělení jednoho svazku světla na dva. Může jít např. o tzv. polopropustné zrcadlo, existuje však i celá řada jiných konkrétních realizací tohoto prvku. V našem případě jsme zvolili vláknovou implementaci v podobě vláknového děliče. Zajímavé pro nás je, že snižujeme-li intenzitu světla, začne se projevovat jeho kvantový charakter. Světelná energie se totiž šíří v malých nedělitelných dávkách-fotonech. Dopadne-li jediný foton na dělič svazku, nemůže se rozpůlit; může prostě jen ”zvolit” jednu ze dvou možných cest. To kterou se vydá, je náhodný jev v nejryzejším smyslu. Popis generátoru Generátor má tři části • Optická část • Řídící elektronika • Napěťový zdroj Rozměry: 33×33×14 cm3 Vstupní napětí: 230 V AC Přípojka na PC: paralelní port
1
3.2. Optická část
>>
>>
Obrázek 1: Schéma optické části. • • • •
Celá optická část je složená z vláknových komponent. Zdroj: Pigtailovaná (navázaná přímo do vlákna) laserová dioda Optické pulzy jsou zeslabeny pomocí dvou atenuátorů (hrubý, jemný) Pravděpodobnost detekce jednotlivého optického pulzu na každém detektoru je nastavena na ∼ 40%.
3.3. Řídící elektronika
Obrázek 2: Schéma elektrického zapojení. Obrázek 3 odpovídá dvěma cyklům délky 200 ns. Detektor zaznamenal foton v prvním cyklu, v druhém ne. Do desky ADSP byla tedy odeslána sekvence bitů ’10’. • Časový bod 0: klopné obvody D jsou vynulovány, generuje se laserový pulz. ≈ Časový bod 3: TTL pulz z detektoru (pokud zaznamenal foton) dorazí k D. • Časový bod 7: stavy obou detektorů jsou načteny do paměti desky ADSP přes sériové porty.
2
Obrázek 3: Časování jednotlivých elektrických signálů. 3.4. Falešné detekční události Detekce fotonů, které nejsou z laserové diody: ⇒ Jsou potlačeny díky vláknovým komponentám a uzavřením zařízení v boxu. Temné pulzy: Jsou způsobené termálními excitacemi nosičů v detektoru. ⇒ Jsou minimalizovány termoelektrickým chlazením lavinové fotodiody na −25 ◦ C. Mrtvá doba: Po detekci fotonu se spustí lavinový průraz. Průrazné napětí je odpojeno z p-n přechodu a lavina se zastaví. Během doby, kdy je průrazné napětí odpojeno detektor nemůže detekovat další fotony (nespustí se lavina). After-pulzy: Pokud se některý nosič z laviny zachytí na nějakém centru. Může se po opětném připojení průrazného napětí uvolnit a spustit falešnou lavinu. ⇒ Zanedbatelné díky nastavení dlouhé mrtvé doby 150 ns. Celkový počet falešných detekcí je ≈ 150 za sekundu. Poměr falešných pulzů vůči chtěným detekcím fotonů z laserové diody je ≈ 1 × 10−4 . Tabulka 1: Detekční pravděpodobnosti optických pulzů diody na oboou detektorech. Detektor 0
Detektor 1
po ’0’
po ’1’
nepodmíněná
po ’0’
po ’1’
nepodmíněná
hned po startu
49.50%
43.04%
46.50%
46.86%
46.77%
46.82%
15 min temperování
42.64%
41.81%
42.27%
48.09%
48.05%
48.06%
Detekční pravděpodobnost detektoru 0 je závislá na výsledku v předešlém cyklu. Pokud došlo k detekci, je v dalším cyklu detekční účinnost nižší o 6.5%. Naštěstí se tento jev po ustálení teplotní rovnováhy v generátoru (15-20 minutes). ⇒ Proto je třeba generátor před započetím generování dobrých náhodných dat temperovat, t.j. generovaná data se testují a teprve po té, co splňují kritérium na kvalitu, se přejde k záznamu dat.
3
3.5. Provoz generátoru náhodných čísel Generátor se z řídícího PC může přepínat mezi 4 mody. Mod 0: stavy klopných obvodů D jsou v každém cyklu zaznamenány a odeslány do PC v bloku (13 kByte). ⇒ pro ověření bezchybné funkce. Mod 1: Do PC se přenáší pouze součty bitů ’1’s v 13 kBytových blocích (pro každý detektor). ⇒ slouží k nastavení detekční pravděpodobnosti na obou detektorech. Mod 2: Do PC se přenáší 8 kBytové bloky hrubých dat. Tabulka 2: Generace hrubých dat ze stavu detektorů v jednom cyklu. Stavy detektorů D1 a D0
’00’
’01’
’10’
’11’
Vygenerovaný hrubý Bit
”
’0’
’1’
”
− Vyváženost ’0’ a ’1’ kolísá v čase (Obr. 4). Mod 3: Do PC se posílají 2 kBytové bloky vyvážených dat. + k vyvážení se používá nejjednodušší procedura navržená von Neumannem + vyvážení ’0’ a ’1’ je vynikající 50:50 (Obr. 5) − efektivita je pouze 25%. Tabulka 3: Generace vyvážených dat z hrubých dat. pár Bitů hrubých dat vygenerovaný vyvážený Bit
’00’
’01’
’10’
’11’
”
’0’
’1’
”
Tabulka 4: Časy a rychlost generace v jednotlivých modech. Mod
záznam
zpracování
přenos
blok
čas
rychlost
#
ms
ms
ms
kByte
ms
kByte/s
0
21
1
69
26
70
373
1
21
24
1
-
45
-
2
25
45
21
8
70
114
3
25
47
5
2
72
28
4
Obrázek 4: Rovnováha ’0’s a ’1’s v souboru hrubých dat.
Obrázek 5: Rovnováha ’0’s a ’1’s v souboru vyvážených dat.
. . .
. .. . . . . . . . . . . . . . . .. ... ... . . . ..... ... . .. . ...... . .. . .. ....... .. . ... ... . .... . ........ . . . ....... ... . .. .. . ............ .. .. .. ........... . . . . . . .... .... ....... . ... . . ....... .. . . .. ... ... ... . . ........ ... . . . . .. .. ..... ...... . .. .. . . .... . . .... . .. . ... ... .. ... ..... ... . .. . .. . . . .. . . . . . . . . . ... . . . . . . .. . . . . .
5
3.6. Testy dat • • • • •
Testy náhodných dat ověřují některé statistické vlastnosti dat. Výsledné hodnoty se porovnají s teoretickou hodnotou očekávanou pro ideální náhodná data. Pokud je výsledek konzistentní s teoretickou předpovědí, pak se říká, že generátor testem ”prošel”. T.z. tento test nenašel rozdíl mezi skutečně náhodnými daty a testovanými daty. Čím více různými testy data projdou, tím je možné datům více věřit.
3.6.1. Diehard • 15 statistických testů navržených G. Marsagliem, WWW: http://stat.fsu.edu/∼ geo/diehard.html.
Tabulka 5: Soupis výsledků 15 testů Diehard. ◦ − prošel, × − neprošel Test #
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
hrubá data
◦
◦
◦
×
×
×
×
×
×
◦
◦
×
◦
◦
×
vyvážená
◦
◦
◦
◦
◦
◦
◦
◦
◦
◦
◦
◦
◦
◦
◦
Vyvážená data generovaná v modu 3 projdou všemy 15 testy. 3.6.2. Autokorelace mezi bity ve vzdálenosti m N 1 X Γ(m) = xi ⊕ xi+m . N i=1
m = 1, . . . , 10, pro N = 223 . Výsledné Γ leží v intervalu od 0.49953 do 0.50009, t.j. neexistuje žádná korelace mezi sousedními bity vygenerované vyvážené posloupnosti. 3.6.3. Monte Carlo odhad π Vygenerovali jsme osm souborů vyvážených dat o velikosti 10 MByte, spočítáme π z každého souboru a z nich potom průměr a standardní odchylku: π = (3.1430 ± 0.0012) Tento test namapuje 8Bytu na souřadnice bodu ve čtverci. Z toho, že výsledek je dobrý lze říci, že vygenerované body jsou v ploše rovnoměrně rozmístěny. 3.7. Závěr • • • • • • •
Předvedli jsme funkční prototyp generátoru náhodných čísel. Je založen na fundamentální náhodnosti dané kvantovou mechanikou. Zařízení se skládá z běžně dostupných komponent. Lze ho připojit k libovolnému PC s paralelním portem. Stabilní generaci garantuje vláknové provedení a umístění v ochranném boxu. Vygenerovaná vyvážená data splňují všechna studovaná kritéria náhodnosti. Rychlost generace vyvážených dat je 28 kByte/s.
6
