DataTerminology.comNEW
Also known as: BBS
A number-theoretic CSPRNG defined by squaring modulo a composite M=p·q, with security tied to factoring hardness.
DESCRIPTION
Blum Blum Shub (BBS) produces bits via x_{n+1} = x_n^2 mod M, where M is a product of two large primes congruent to 3 mod 4. Security is based on the difficulty of factoring M and predicting quadratic residues, making BBS provably secure under widely believed assumptions. It is relatively slow and mainly of theoretical and niche practical interest. Bit extraction (usually least significant bits) must follow guidance to preserve security. While historically important, modern systems often favor DRBGs based on hashes, HMAC, or block ciphers for performance.
ALTERNATIVE DEFINITIONS
Wikipedia
In cryptography, the Blum Blum Shub (BBS) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub.
States origin, classifies as PRNG, and situates in cryptography.
Schneier and Kelsey
The Blum-Blum-Shub generator is defined by x_{i+1} = x_i^2 mod M, where M is the product of two primes p and q congruent to 3 modulo 4.
Gives the precise recurrence and constraints on modulus.
RELATED TERMS
Cryptographically Secure Pseudorandom Number Generator Quadratic Residues Modular Arithmetic Seed NIST SP 800-90A Entropy Source Bit Extraction Number Theory
COMPETING TERMS
RELATIONS
KNOWLEDGE AREAS
Mathematics Data Security Testing & Validation
TARGET AUDIENCE
Cybersecurity Engineer Security Architect Software Developer Chief Information Security Officer
EXTERNAL SOURCES
- Wikipedia - Blum Blum Shub
- Schneier.com - Context on CSPRNG designs
- Handbook of Applied Cryptography - Chapter on random bit generation
TOP QUESTIONS
Why is Blum Blum Shub considered secure?
Its security reduces to the hardness of factoring and predicting quadratic residues, offering provable guarantees under standard assumptions.
Category: Concept
Why is Blum Blum Shub not widely used in practice?
It is relatively slow compared to DRBGs based on hashes or block ciphers, which are more practical at scale.
Category: Relevancy
How should bits be extracted from Blum Blum Shub?
Typically only the least significant bit or a few bits per iteration are used to maintain security.
Category: BestPractice
What parameters are required for Blum Blum Shub?
Select large primes p and q with p≡q≡3 (mod 4), compute M=p·q, and choose a seed co-prime to M.
Category: Requirements
Is Blum Blum Shub suitable for seeding other PRNGs?
Yes, it can provide high-quality bits to seed faster PRNGs, though this adds complexity.
Category: Opinion
Can Blum Blum Shub be parallelized?
It’s difficult due to sequential dependence; parallel streams require independent moduli and careful design.
Category: BestPractice
What is a practical alternative to Blum Blum Shub?
NIST SP 800-90A DRBGs (Hash_DRBG, HMAC_DRBG, CTR_DRBG) offer strong security and performance.
Category: Alternatives
Does Blum Blum Shub pass standard randomness tests?
Yes, when used correctly, but tests alone do not establish cryptographic security.
Category: Testing
What happens if p or q are poorly chosen?
Security degrades; factoring becomes easier and outputs may be more predictable.
Category: Risk