How does one find random numbers for keys ?

Question Posted / guest

1 Answers
3154 Views
TCS, I also Faced
E-Mail Answers

How does one find random numbers for keys ?..

Answer / ramkumar

Whether using a secret-key cryptosystem or a public-key
cryptosystem, one needs a good source of random numbers for
key generation. The main features of a good source are that
it produces numbers that are unknown and unpredictable by
potential adversaries. Random numbers obtained from a
physical process are in principle the best, since many
physical processes appear truly random. 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 inter-key stroke timings measured in
microseconds. Techniques using the spinning of disks to
generate random data are not truly random, as the movement
of the disk platter cannot be considered 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
unpredictable. By whichever method they are generated, the
random numbers may still contain some correlation, thus
preventing sufficient statistical randomness. Therefore, it
is best to run them through a good hash function (see
Question 2.1.6) before actually using them [ECS94].

Another approach is to use a pseudo-random number generator
fed by a random seed. The primary difference between random
and pseudo-random numbers is that pseudo-random numbers are
necessarily periodic whereas truly random numbers are not.
Since pseudo-random number generators are deterministic
algorithms, it is important to find one that is
cryptographically secure and also to use a good random
seed; the generator effectively acts as an "expander" from
the seed to a larger amount of pseudo-random data. The seed
must be sufficiently variable to deter attacks based on
trying all possible seeds.

It is not sufficient for a pseudo-random 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 2.3.7). Other
generators perhaps based on DES (see Section 3.2) or a hash
function (see Question 2.1.6) can also be considered to
satisfy this definition, under reasonable assumptions.

A summary of methods for generating random numbers in
software can be found in [Mat96].

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