3.8. Random Numbers

So far we have met several situations where we needed random elements from a (finite) set, for example, the set (or ) or the set (or ) or the set of -rational points on an elliptic (or hyperelliptic) curve. By randomness, we here mean that each element is equally likely to get selected, that is, if #S = n, then each element of S is selected with probability 1/n. Since elements of a set S of cardinality n can be represented as bit strings of length ≤ ⌈lg(n + 1)⌉, the problem of selecting a random element of S essentially reduces to the problem of generating (finite) random sequences of bits. A random sequence of bits is one in which every bit has a probability of 1/2 of being either 0 or 1 (irrespective of the other bits in the sequence).

3.8.1. Pseudorandom Bit Generators

Generating a (truly) random sequence of bits seems to be an impossible task. Some natural phenomena, such as electronic noise from a specifically designed integrated circuit, can be used to generate random bit sequences. However, such systems are prone to malfunctioning, often influenced by observations and are, of course, costly. A software solution is definitely the more practical alternative. Phenomena, like the system clock, the work load or memory usage of a machine, that can be captured by programs may be used to generate random bit sequences. But this strategy also suffers from various drawbacks. First of all the sequences generated by these methods would not be (truly) random. Moreover they are vulnerable to attacks by adversaries (for example, if a random bit generator is based on the system clock and if the adversary knows the approximate time when a bit sequence is generated using that generator, she will have to try only a few possibilities to generate the same sequence).

In order to obviate these difficulties, pseudorandom bit generators (PRBG) are commonly used. A bit string a₀a₁a₂ . . . is generated by a PRBG following a specific strategy, which is more often that not a (mathematical) algorithm. The first bit a₀ is based on certain initial value, called a seed, whereas for i ≥ 1the bit a_i is generated as a predetermined function of some or all of the previous bits a₀, . . . , a_i–1. Since the resulting bit a_i is now functionally dependent on the previous bits, the sequence is not at all random (but deterministic), but we are happy if the sequence a₀a₁a₂ . . . looks or behaves random. A random behaviour of a sequence is often examined by certain well-known statistical tests. If a generator generates bit sequences passed by these tests, we call it a PRBG and sequences available from such a generator pseudorandom bit sequences. Various kinds of PRBGs are used for generating pseudorandom bit sequences. We won’t describe them here, but concentrate on a particular kind of generators that has a special significance in cryptography.

3.8.2. Cryptographically Strong Pseudorandom Bit Generators

A PRBG for which no polynomial time algorithms exist (provably or not) in order to predict with probability significantly larger than 1/2 a bit in a sequence generated by the PRBG from a knowledge of the previous bits (but without the knowledge of the seed) is called a cryptographically strong (or secure) pseudorandom bit generator or a CSPRBG in short. Usually, an intractable computational problem (see Section 4.2) is at the heart of the security of a CSPRBG. As an example, we now explain the Blum–Blum–Shub (or BBS) generator.

Algorithm 3.37. Blum–Blum–Shub pseudorandom bit generator

In Algorithm 3.37, we have used indices for the sequence x_i for the sake of clarity. In an actual implementation, all indices may be removed, that is, one may use a single variable x to store and update the sequence x_i. Furthermore, if there is no harm in altering the value of s, one might even use the same variable for s and x.

The cryptographic security of the BBS generator stems from the presumed intractability of factoring integers or of computing square roots modulo a composite integer (here n = pq) (see Exercise 3.43). Note that p, q and s have to be kept secret, whereas n can be made public. A knowledge of x_{m + 1} is also not expected to help an opponent and may too be made public. For achieving the desired level of secrecy, p and q should be of nearly equal size and the size of n should be sufficiently large (say, 768 bits or more). Generating each bit by the BBS generator involves a modular squaring and is, therefore, somewhat slow (compared to the traditional PRBGs which do not guarantee cryptographic security). However, the BBS generator can be used for moderately infrequent purposes, for example, for the generation of a session key. Moreover, a maximum of lg lg n (least significant) bits (instead of 1 as in the above snippet) can be extracted from each x_i without degrading the security of the generator.

It is evident that any (infinite) sequence a₀a₁ · · · generated by the BBS generator must be periodic. As an extreme example, if s = 1, then the BBS generator outputs a sequence of one-bits only. We are interested in rather short (sub)sequences (of such infinite sequences). Therefore, it suffices if the length of the period is reasonably large (for a random seed s). This is guaranteed if one uses strong primes (Definition 3.5)

3.8.3. Seeding Pseudorandom Bit Generators

The way we have defined PRBG (or CSPRBG) makes it evident that the unpredictability of a pseudorandom bit sequence essentially reduces to that of the seed. Care should, therefore, be taken in order to choose the values of the seed. The seed need not be randomly or pseudorandomly generated, but should have a high degree of unpredictability, so that it is infeasible for an adversary to have a reasonably quick guess of it. As an example, assume that we intend to generate a suitable seed s for the BBS generator with a 1024-bit modulus n. If we employ for that purpose a specific algorithm (known to the opponent) using only the built-in random number generator of a standard compiler and if this built-in generator has a 32-bit seed σ, then there are only 2³² possibilities for s, even when s itself is 1024 bits long. Thus an adversary has to try at most 2³² (2³¹ on an average) values of σ in order to guess the correct value of s. So we must add further unpredictability to the resulting seed value s. This can be done by setting the bits of s depending on several factors, like the system clock, the system load, the memory usage, keyboard inputs from a human user and so on. Each of such factors might not be individually completely unpredictable, but their combined effect should preclude the feasibility of an exhaustive search by the opponent. After all, we have 1024 bits of s to fill up and even if the total search space of possible values of s is as low as 2¹⁶⁰, it would be impossible for the opponent to guess s in a reasonable span of time. Note that more often than not the values of the seed need not be remembered: that is, need not be regenerated afterwards. As a result, there is no harm in introducing unpredictability in s caused by certain factors that we would not ourselves be able to reproduce in future.

Exercise Set 3.8