Algoritmus, jehož výstupem je posloupnost, která sice ve skutečnosti není náhodná, ale která se zdá být náhodná, pokud útočníkovi nejsou známy některé parametry generátoru
Snadno realizovatelné
Rychlé
Výstup je ale předvídatelný
Lineární kongruenční generátor
Není kryptograficky bezpečný
! Rovnice:
= posloupnost pseudonáhodných čísel
= modul (často mocnina 2)
= násobitel
= inkrement
= počáteční hodnota (seed)
Požadavky na kryptograficky bezpečné PRNG
Next-bit test
! Je-li známo prvních bitů náhodné posloupnosti, neexistuje žádný algoritmus s polynomiální složitostí, který by dokázal předpovědět další, tedy . bit s pravděpodobností úspěchu
Tedy nejsem schopen z předchozích bitů vygenerovat další bit s pravděpodobností větší než 50%
State compromise
! I když je zjištěn vnitřní stav generátoru (konečného automatu), ať už celý nebo jen z části, nelze zpětně zrekonstruovat dosavadní vygenerovanou náhodnou posloupnost
Navíc, pokud do generátoru za běhu vstupuje další entropie, nemělo by být možné předpovědět vnitřní stav v následujících iteracích