How Does One Find Random Numbers for Keys?

One needs a good source of random numbers to generate keys, both for secret-key algorithms and public-key algorithms. Random numbers obtained from a physical process are in principle the best. One could use a hardware device, such as a noisy diode; some are sold commercially on computer add-in boards for this purpose. Another idea is to use physical movements of the computer user, such as keystroke timings measured in microseconds. However, it was recently proved that techniques that used the spinning of disks to generate random data are not truly random, as the movement of the disk platter is not truly random. A negligible-cost alternative is available. Davis et al. designed a random number generator based on the variation of a disk drive motor's speed [DIP94]. This variation is caused by air turbulence, which has been shown to be unpredicatable. By whichever method they are generated, the random numbers may still contain some correlations, thus preventing sufficient statistical randomness. Therefore, it is best to run them through a good hash function (see Question 94) before actually using them [ECS94].

Another approach is to use a pseudorandom number generator fed by a random seed. Since these are deterministic algorithms, it is important to find one that is cryptographically secure and also to use a truly random seed; the generator effectively acts as an "expander" from the seed to a larger amount of pseudorandom data. The seed must be sufficiently variable to deter attacks based on trying all possible seeds.

It is not sufficient for a pseudorandom number generator just to pass a variety of statistical tests, as described in Knuth [Knu81] and elsewhere, because the output of such generators may still be predictable. Rather, it must be computationally infeasible for an attacker to determine any bit of the output sequence, even if all the others are known, with probability better than 1/2. Blum and Micali's generator based on the discrete logarithm problem [BM84] satisfies this stronger definition, assuming that computing discrete logarithm is difficult(see Question 52). Other generators, perhaps based on DES (see Question 64) or a hash function (see Question 94), can also be considered to satisfy this definition, under reasonable assumptions.

Note that one does not need random numbers to determine the public and private exponents in RSA (see Question 8), after generating the primes and hence the modulus. One can simply choose an arbitrary value for the public exponent, which then determines the private exponent.

| Question 113 |