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

x_i = (x_i-1)² 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^[1]
x₀ je inicializační hodnota (seed), splňující
- 0 < x₀ < M
- gcd(x₀, M) = 1
výstupem generátoru je bit získaný jako bitová parita čísla x_i^[2]

Výhodou generátoru je možnost přímo vypočítat x_i:

x_i = x2ⁱ mod λ(M)
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

↑ BLUM, L.; BLUM, M.; SHUB, M. A Simple Unpredictable Pseudo-Random Number Generator. S. 364–383. SIAM Journal on Computing [online]. 1986-05 [cit. 2021-06-30]. Roč. 15, čís. 2, s. 364–383. Dostupné online. DOI 10.1137/0215025. (anglicky)
↑ BLUM, Lenore; BLUM, Manuel; SHUB, Michael. Comparison of Two Pseudo-Random Number Generators. S. 61–78. Advances in Cryptology [online]. 1983 [cit. 2021-06-30]. S. 61–78. Dostupné online. DOI 10.1007/978-1-4757-0602-4_6. (anglicky)

Pahýl

Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.

[blum1986-1] BLUM, L.; BLUM, M.; SHUB, M. A Simple Unpredictable Pseudo-Random Number Generator. S. 364–383. SIAM Journal on Computing [online]. 1986-05 [cit. 2021-06-30]. Roč. 15, čís. 2, s. 364–383. Dostupné online. DOI 10.1137/0215025. (anglicky)

[blum1983-2] BLUM, Lenore; BLUM, Manuel; SHUB, Michael. Comparison of Two Pseudo-Random Number Generators. S. 61–78. Advances in Cryptology [online]. 1983 [cit. 2021-06-30]. S. 61–78. Dostupné online. DOI 10.1007/978-1-4757-0602-4_6. (anglicky)

[1]

[2]