Náhodná čísla a jejich generování
V článku budu mluvit o generování posloupnosti nějakých náhodných bitů (nuly a jedničky) - z nich se potom generují náhodná čísla, písmena atd.
Náhodná čísla potřebujeme v IT skoro v každodenní práci. Generujeme si nějaké kryptografické klíče, hesla, v šifrování atd. Jak ale docílit, že číslo je opravdu náhodné? V počítači má vše nějaký řád, chová se nějak predikovatelně, tak jak získat nějakou posloupnost náhodných nul a jedniček?
Taková náhodná posloupnost se vyznačuje tím, že je nepředvídatelná a její výsledek nejde zreprodukovat. Očekáváme od ní rovnoměrné rozdělení a nezávislost mezi vygenerovanými hodnotami.
Počítače sami o sobě neumí vygenerovat přímo náhodnou posloupnost. Generují nějakou pseudo-náhodnou poslopnost. Takovýmto generátorům se říká PRNG (Pseudo Random Number Generator). To je vesměs algoritmus, který má na výstupu "náhodnou" posloupnost, která ve skutečnosti není náhodná. Pokud uživatel zná parametry generování, tak dokáže chování tohoto generátoru nasimulovat. Jejich výhody jsou v tom, že jsou snadno realizovatelné a rychlé.
Příklady:
Lineární kongruenční generátor: je jeden z nejstarších, nejznámějších, ale není kryptograficky bezpečný. Vše závisí na seedu, což je nultá hodnota v posloupnosti náhodných čísel, od které se odvozují další hodnoty posloupnosti podle předpisu.
Blum-blub-shub: funguje na podobném principu, ale je kryptograficky bezpečný. Na vstupu bere seed, ale dělá s ním jiné operace. Je pomalejší než LKG a lze spočítat i-tý prvek posloupnosti.
Aby byl generátor kryptograficky bezpečný, musí splňovat tyto test: Next-bit-test a state-compromise test.
Předchozí generátory vyžadují nějaký počáteční vstup - seed. Všechna jejich náhodnost se pak odvíjí od něj. Jak ale tedy získat tento seed, který má být náhodný?
Na to slouží generátory skutečně náhodných čísel/posloupností (TRNG - True random number generator). Ty používají nedeterministické události jako například: radioaktivní rozpad, atmosférický šum, teplotní šum nebo chování uživatele (psaní na klávesnici, pohyb myší). Tyto generátory jsou složitější na implementaci, protože požadují často nějaký hardware navíc. Vygenerovaná čísla se následně ještě zpracovávají, aby se třeba vyvážil počet jedniček a nul kvůli statistickým vlastnostem např. John von Neumann dekorelátor. Ten vezme vždy dvojici bitů. Pokud to je 00 nebo 11, tak vstup zahodí. Pokud to je 01 dosadí místo toho nulu, a pokud 10, dosadí jedničku.
Jak si ověřím, že daný generátor, který jsem navrhl není kvalitní (spíš se testuje nekvalita než kvalita)?
Na to slouží testy náhodnosti. Mezi ně se řadí např.:
- Frekvenční test: obsah přibližně stejného počtu jedniček a nul v posloupnosti i podposloupnostech
- Runs test: testuje délku po sobě jdoucích jedniček a nul
- Spektrální test: odhaluje periodicitu
Zdroj: ČVUT FIT - Bezpečnost
