share: true
aliases:
- Náhodná čísla
- RNG
- testování náhodných generátorů
- statistické hypotézy

Náhodná čísla

Mnoho kryptografických aplikací vyžaduje náhodná čísla
Vyžadovaná "kvalita" náhodnosti se u různých aplikací liší
RNG - Random Number Generator
Od náhodných posloupností očekáváme dobré statistické vlastnosti:
- Rovnoměrné rozdělení - všechny hodnoty jsou generovány se stejnou pravděpodobností
- Jednotlivé generování hodnoty jsou nezávislé - není mezi nimi žádná korelace
Veličina Entropie popisuje míru náhodnosti - jak obtížné je hodnotu (náhodné číslo) uhodnout
Entropie generátoru je maximální, pokud se pro danou délku generují všechny možné posloupnosti, každá z nich se stejnou pravděpodobností

Generátor pseudonáhodných čísel

K ověření vlastností náhodných generátorů se používají statistické testy
Pouze posuzujeme, zda generátor prošel testy. Nelze ale prokázat, že je opravdu kvalitní
Založeno na testování statistických hypotéz na určité hladině významnosti
- Nulová hypotéza - testovaná posloupnost je náhodná
- Testy vrací -hodnotu - vyjadřuje sílu důkazu proti nulové hypotéze
- Pokud -hodnota překročí určitou mez, považujeme nulovou hypotézu za neplatnou
Testy bývají součástí obecně známých a používaných sad ("baterií") testů:
- Diehard - 12 různých testů, poměrně silných
- Dieharder - re-implementace Diehard, přidána řada dalších testů
- NIST (National Institute of Standards and Technology) - 16 testů
- Tyto sady byly vyvinuty převážně pro testování PRNG, při testování TRNG je potřeba důkladně analyzovat zdroj entropie

Frekvenční test
- Testuje, zda posloupnost bitů obsahuje přibližně stejný počet 0 a 1
- Testuje se jednak celá posloupnost, jednak dílčí podposloupnosti
"Runs" test
- Testuje, zda počet a délka řetězců po sobě jdoucích stejných bitů v rámci testované posloupnosti bitů odpovídá náhodné posloupnosti
- Opět celá i dílčí podposloupnosti
Test hodností matic
- Zaměřuje se na hodnosti disjunktních podmatic
- Cílem je odhalit lineární závislost podposloupností pevné délky
- Vezmu celý řetězec, rozkouskuji ho, převedu na matici a testuji
Spektrální test
- Diskrétní Fourierova transformace
- Snaží se odhalit periodicitu
- Na výstupu Fourierovy transformace by se správně neměla ukázat žádná dominantní frekvence
Maurerův univerzální statistický test
- Testuje, zda lze posloupnost výrazněji bezztrátově zkomprimovat
- Výrazně komprimovatelná sekvence neobsahuje dostatek entropie
- Pokud mám na výstupu menší soubor než na vstupu, tak tam komprimační algoritmus našel nějakou redundanci, a to je špatně

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25