# Cryptographically secure pseudorandom bit generation

Two cryptographically secure pseudorandom bit generators (CSPRBG - see Definition 5.8) are presented in this section. The security of each generator relies on the presumed intractability of an underlying number-theoretic problem. The modular multiplications that these generators use make them relatively slow compared to the (ad-hoc) pseudorandom bit generators of §5.3. Nevertheless they may be useful in some circumstances, for example, generating pseudorandom bits on hardware devices which already have the circuitry for performing modular multiplications. Efficient techniques for implementing modular multiplication are presented in §14.3.

## RSA pseudorandom bit generator

The RSA pseudorandom bit generator is a CSPRBG under the assumption that the RSA problem is intractable (§3.3; see also §3.9.2).

5.35 Algorithm RSA pseudorandom bit generator

SUMMARY: a pseudorandom bit sequence z,Z2,... ,zi of length / is generated.

1. Setup. Generate two secret RSA-like primes p and q (cf. Note 8.8), and compute n = pq and ф = (p - l)(g -1). Select a random integer e, 1 < e < ф, such that

gcd(e, ф) = 1.

• 2. Select a random integer ;c0 (the seed) in the interval [1, n — 1].
• 3. For i from 1 to / do the following:
• 3.1 Xi mod n.
• 3.2 Zi<— the least significant bit of хг.
• 4. The output sequence is z, Z2, . . . ,zp
• 5.36 Note (efficiency of the RSA PRBG) If e = 3 is chosen (cf. Note 8.9(ii)), then generating each pseudorandom bit г, requires one modular multiplication and one modular squaring. The efficiency of the generator can be improved by extracting the j least significant bits of Xi in step 3.2, where j = clglgn and c is a constant. Provided that n is sufficiently large, this modified generator is also cryptographically secure (cf. Fact 3.87). For a modulus n of a fixed bitlength (e.g., 1024 bits), an explicit range of values of c for which the resulting generator remains cryptographically secure (cf. Remark 5.9) under the intractability assumption of the RSA problem has not been determined.

The following modification improves the efficiency of the RSA PRBG.

5.37 Algorithm Micali-Schnorr pseudorandom bit generator

SUMMARY: a pseudorandom bit sequence is generated.

1. Setup. Generate two secret RS А-like primes p and q (cf. Note 8.8), and compute n = pq and о = (p - 1)(г/ -1). Let N = |_lg nj +1 (the bitlength of n). Select an integer

e, 1 < e < ф, such that gcd(e, ф) = 1 and 80e < N. Let к = |_ЛГ(1 - §)J and r = N — k. '

• 2. Select a random sequence x0 (the seed) of bitlength r.
• 3. Generate a pseudorandom sequence of length k-l. For i from 1 to / do the following:
• 3.1 yi<— ж®_1 mod n.
• 3.2 Xi<- the r most significant bits of щ.
• 3.3 zp— the к least significant bits of y,.
• 4. The output sequence is z || 22 || • • • || zu where || denotes concatenation.
• 5.38 Note (efficiency of the Micali-Schnorr PRBG) Algorithm 5.37 is more efficient than the RSA PRBG since [N( 1 - |)J bits are generated per exponentiation by e. For example, if e = 3 and N = 1024, then к = 341 bits are generated per exponentiation. Moreover, each exponentiation requires only one modular squaring of an r = 683-bit number, and one modular multiplication.
• 5.39 Note (security of the Micali-Schnorr PRBG) Algorithm 5.37 is cryptographically secure under the assumption that the following is true: the distribution xe mod n for random /--bit sequences x is indistinguishable by all polynomial-time statistical tests from the uniform distribution of integers in the interval [0, n — 1]. This assumption is stronger than requiring that the RSA problem be intractable.

## Blum-Blum-Shub pseudorandom bit generator

The Blum-Blum-Shub pseudorandom bit generator (also known as the x[1] [2] [3] [4] [5] mod n generator or the BBS generator) is a CSPRBG under the assumption that integer factorization is intractable (§3.2). It forms the basis for the Blum-Goldwasser probabilistic public-key encryption scheme (Algorithm 8.56).

5.40 Algorithm Blum-Blum-Shub pseudorandom bit generator

5.41 Note (efficiency of the Blum-Blum-Shub PRBG) Generating each pseudorandom bit requires one modular squaring. The efficiency of the generator can be improved by extracting the j least significant bits of x, in step 3.2, where j = c lg lg n and c is a constant. Provided that n is sufficiently large, this modified generator is also cryptographically secure. For a modulus n of a fixed bitlength (eg. 1024 bits), an explicit range of values of c for which the resulting generator is cryptographically secure (cf. Remark 5.9) under the intractability assumption of the integer factorization problem has not been determined.

• [1] SUMMARY: a pseudorandom bit sequence z, Z2,... ,zi of length l is generated.
• [2] Setup. Generate two large secret random (and distinct) primes p and q (cf. Note 8.8),each congruent to 3 modulo 4, and compute n = pq.
• [3] Select a random integer .s (the seed) in the interval [1, ?г - 1] such that gcd(s, n) = 1,and compute x0-^s3 mod n.
• [4] For i from 1 to / do the following: 3.1 Xi<— mod n. 3.2 zp.— the least significant bit of ж,.
• [5] The output sequence is z, Z2, ■ ■ ■ ,zp