Blum Blum Shub

Blum Blum Shub (BBS) je jednoduchý generátor pseudonáhodných čísel z třídy kryptograficky bezpečný generátor pseudonáhodných čísel (CSPRNG). Název je odvozen od autorů, kteří popsali v roce 1986 (resp. 1982) jeho vlastnosti. Těmi jsou Lenore Blum, Manuel Blum a Michael Shub.

BBS používá rekurzivní formuli

:xi = (xi-1)2 mod M

kde * M je součin dvou velkých (tajných) prvočísel p a q, pro ta by mělo platit, že jsou ** kongruentní 3 modulo 4 ** stejné délky * x0 je inicializační hodnota (seed), splňující ** 0 0 0, M) = 1 * výstupem generátoru je bit získaný jako bitová parita čísla xi

Výhodou generátoru je možnost přímo vypočítat xi: : xi = xb=0|p=2i mod λ(M)|s=0 mod M kde λ je Carmichaelova funkce.

Blum Blum Shub je zajímavý spíše z teoretického hlediska a v praxi se příliš nepoužívá, kvůli malé rychlosti a nutnosti utajení p a q.

Odkazy

Reference

Kategorie:Generátory pseudonáhodných čísel