Lably
Skip to content

Blum Blum Shub

Pseudorandom number generator

  • 10 min read
  • 2 chapters

Related on Lably

Through Prime number, Parity bit and Congruence relation

Lab · Class 6–12AI & Python Builds (Medha AI)Lab · Class 7–9Congruence of TrianglesLabCongruence of TrianglesLab · Class 6–10Geometric Constructions

Blum Blum Shub takes the form

xn+1=xn2modM,

where M = pq is the product of two large primes p and q. At each step of the algorithm, some output is derived from xn+1; the output is commonly either the bit parity of xn+1 or one or more of the least significant bits of xn+1.

The seed x0 should be an integer that is co-prime to M (i.e. p and q are not factors of x0) and not 1 or 0.

The two primes, p and q, should both be congruent to 3 (mod 4) (this guarantees that each quadratic residue has one square root which is also a quadratic residue), and should be safe primes with a small gcd((p-3)/2, (q-3)/2) (this makes the cycle length large).

An interesting characteristic of the Blum Blum Shub generator is the possibility to calculate any xi value directly (via Euler's theorem):

xi=(x02imodλ(M))modM,

where λ is the Carmichael function. (Here we have λ(M)=λ(p⋅q)=lcm⁡(p−1,q−1)).

Security

There is a proof reducing its security to the computational difficulty of factoring. When the primes are chosen appropriately, and O(log log M) lower-order bits of each xn are output, then in the limit as M grows large, distinguishing the output bits from random should be at least as difficult as solving the quadratic residuosity problem modulo M.

The performance of the BBS random-number generator depends on the size of the modulus M and the number of bits per iteration j. While lowering M or increasing j makes the algorithm faster, doing so also reduces the security. A 2005 paper gives concrete, as opposed to asymptotic, security proof of BBS, for a given M and j. The result can also be used to guide choices of the two numbers by balancing expected security against computational cost.

Sign in to keep reading

One more chapter is free with a Lably account.

More in Computing and communication

ISBNUnique numeric book identifier since 1970X (social network)American social networking serviceWayback MachineDigital archive by the Internet ArchivePython (programming language)General-purpose programming languageMacOSOperating system for Apple computersUnicodeCharacter encoding standard