Appendix B: Pseudorandom Number Generation - Codes: The Guide to Secrecy from Ancient to Modern Times - page 507

Properties of Blum Integers
If n is a Blum integer, then each of the following hold, where the symbol

b is the Jacobi symbol (see Appendix A, especially page 482).
1. − p = − q =

−

1.

and n = 1, then one of 2. If x ∈ Z /n Z ± x is a quadratic residue modulo n .

3. If x 2

≡ y (mod n ), then the four square roots of y are given by

upy ( q +1) / 4 + vqy ( p +1) / 4 , and x = upy ( q +1) / 4

vqy ( p +1) / 4 ,

x = ± ± −

where

up + vq =1 .

x 2 (mod n ), then exactly one (least quadratic residue of a) square

4. If y ≡

root x of y , with n = 1 satisfies x

≤ n/ 2.

Now we are ready for the next generator.

B.2 The Blum-Blum-Shub-(BBS) PRNG

be a seed quadratic residue where n is a Blum integer. This
initializes the BBS-PRNG (also known as the quadratic residue generator ). The
random bit sequence is generated as follows.
1. For j =1 , 2 ,... , compute x j ≡

Let x 0 ∈ Z /n Z

x j − 1 (mod n ).
2. Let b j be the least significant bit of x j .
Then the output pseudorandom bit sequence is b 1 ,b 2 ,... .

It can be shown that if x 0 is kept secret, then for a cryptanalyst to predict the
least significant bits in the above output sequence is computationally equivalent
to factoring n (see [110]). (Compare with the RSA conjecture on page 175.)
The BBS-PRNG is considered to be a cryptographically secure pseudoran-
dom bit generator (CSPRBG) (see page 151). This takes us into the formal
area of semantic security , which means that the ciphertext does not reveal any
information about the plaintext to a cryptanalyst (whose computational power
is polynomially bounded). The reader interested in pursuing this formal theory
may consult the pioneering work of Goldwasser and Micali in [109], as well as
Blum and Micali in [31], and the much more recent [184].
One drawback to the BBS-PRNG is that it may be very slow in application.
To improve speed, one may select the m least significant bits of x j , and if

≤

log 2 (log 2 ( n )) ,
then the scheme is cryptographically secure (see[30]).

m