Generování Náhodných Čísel Flashcards
Kryptografické generátory, požadavky, použití, princip, testování generátorů.
RNG - Požadavky
Entropie: Míra nejistoty nebo náhodnosti. Vysoká entropie znamená větší obtížnost předpovídání.
Nepředvídatelnost: Všechna čísla v sekvenci by měla být statisticky neodlišitelná od skutečné náhody.
Jedinečnost: Každý generátor by měl produkovat unikátní sekvence (zejména v kryptografii, aby nedocházelo k opakování klíčů nebo nonce).
Distribuce: Čísla musí být rovnoměrně rozložena, aby nedocházelo k žádným biasům.
RNG - Typy generování
Pravé Náhodné Generátory - Využívají fyzikální jevy (např. šum v elektronických obvodech, radioaktivní rozpad) k produkci skutečně náhodných čísel. Generování je založeno na nepredikovatelných procesech v přírodě. Výhodou je vysoká entropie a nepredikovatelnost. Nevýhodou je pomalejší generování čísel a větší nároky na hardware.
Pseudonáhodné Generátory - Generují čísla na základě deterministických algoritmů. Využívají počáteční hodnotu zvanou seed. Pokud je stejný seed použit opakovaně, generátor produkuje stejnou sekvenci čísel. Jsou rychlé a snadno implementovatelné, ale kvalita náhodnosti závisí na kvalitě algoritmu a entropii seedu.
Kryptograficky Bezpečné Pseudonáhodné Generátory -
Použití RNG v kryptografii
Generování klíčů - Kryptografické klíče musí být nepředvídatelné a unikátní, aby odolaly brute-force útokům.
Inicializační vektory a Nonce - Nonce (čísla použité jednorázově) a IV musí být jedinečné a náhodné, aby nedocházelo ke zranitelnostem, jako je například odhalení vztahu mezi dvěma šifrovanými zprávami.
Solení hesel: Přidáním náhodného saltingu k heslům před jejich hashováním se zamezí efektivnímu použití rainbow tabulek.
Generování podpisů a autentizačních tokenů - Digitální podpisy a autentizační schémata často využívají náhodná čísla k zajištění bezpečnosti.
RNG - Typy Generátorů
Fyzikální - Teoreticky jsou nedeterministické, nejsou ale známy přesné parametry, kterými by se daly
popsat a modelovat. Zaručují maximální bezpečnost a neopakovatelnost. Nevýhodou je
pomalé generování či problematická technická realizace. Příklady: radioaktivní rozpad,
tepelný šum, kvantové generátory.
Algoritmické generátory -Posloupnost náhodná není, pokud útočníkovi jsou známy některé parametry generátoru.
Výhodami je rychlost, nízká odchylka od poměru 1:1 nebo snadná realizace. Nevýhodami jsou bezpečnost či periodicita.
Příklady: čas, teplota HW komponent, šum na low-level sběrnicích (USB, pohyb myši), pohyb HDD.
Smíšené generátory - TRNG z fyzikálního generátoru se spojí s PRNG výstupem pomocí XOR.
Příklady PRNG
Bloková šifra v režimu čítače: náhodně se zvolí klíč a počáteční hodnota 𝑖; zvoleným klíčem se šifrují hodnoty 𝑖, 𝑖 + 1, . . . – perioda u 𝑛-bitové šifry je 2^n
Hashovací funkce aplikovaná na čítač: hashuje se 𝑖, 𝑖 + 1, . . . .
Proudové šifry
Blum-Blum-Shub PRNG - založený na těžkosti faktorizace velkých čísel. Velmi pomalý
Yarrow/Fortuna - Shromažďují náhodná data z různých zdrojů (např. pohyb myši, síťový provoz), využívají hashovací funkce a blokové šifry. Používají se v operačních systémech jako základ náhodnosti.
Bloková šifra v režimu čítače - Bezpečnost je založena na síle šifry (např. AES). Používá se v kryptografických knihovnách jako OpenSSL
Hashovací funkce SHA -2 nebo HMAC. Bezpečné a snadno implementovatelné
Testování PRNG
Statistická náhodnost – výstup by měl být nerozeznatelný od skutečně náhodného.
Nepředvídatelnost – žádný algoritmus by neměl být schopen předvídat další výstup.
Dlouhá perioda – výstup by se neměl opakovat v krátkém čase.
Bezpečnost vůči útokům – pro kryptografické účely musí být výstup odolný vůči zpětné analýze.
Typy testů:
Frequency (Monobit) test – Obsahuje testovaná posloupnost bitů přibližně stejný počet nul a jedniček?
Runs test – Je počet a délka řetězců po sobě jdoucích stejných bitů na úrovni náhodné posloupnosti?
Serial test – sleduje výskyt podřetězců, např. 00, 01, 10, 11
Approximate entropy test – měří opakovatelnost vzorů
