Pseudorandom numbers and sequences

Random number generation is an important primitive in many cryptographic mechanisms. For example, keys for encryption transformations need to be generated in a manner which is unpredictable to an adversary. Generating a random key typically involves the selection of random numbers or bit sequences. Random number generation presents challenging issues. A brief introduction is given here with details left to Chapter 5.

Often in cryptographic applications, one of the following steps must be performed:

  • (i) From a finite set of n elements (e.g., {1,2,... , n}), select an element at random.
  • (ii) From the set of all sequences (strings) of length m over some finite alphabet A of n symbols, select a sequence at random.
  • (iii) Generate a random sequence (string) of symbols of length m over a set of n symbols. It is not clear what exactly it means to select at random or generate at random. Calling a number random without a context makes little sense. Is the number 23 a random number? No, but if 49 identical balls labeled with a number from 1 to 49 are in a container, and this container mixes the balls uniformly, drops one ball out, and this ball happens to be labeled with the number 23, then one would say that 23 was generated randomly from a uniform distribution. The probability that 23 drops out is 1 in 49 or

If the number on the ball which was dropped from the container is recorded and the ball is placed back in the container and the process repeated 6 times, then a random sequence of length 6 defined on the alphabet A = {1,2,... , 49} will have been generated. What is the chance that the sequence 17,45,1,7,23,35 occurs? Since each element in the sequence has probability ^ of occuring, the probability of the sequence 17,45,1,7,23,35 occurring is

There are precisely 13841287201 sequences of length 6 over the alphabet A. If each of these sequences is written on one of 13841287201 balls and they are placed in the container (first removing the original 49 balls) then the chance that the sequence given above drops out is the same as if it were generated one ball at a time. Hence, (ii) and (iii) above are essentially the same statements.

Finding good methods to generate random sequences is difficult.

1.67 Example (random sequence generator) To generate a random sequence of 0’s and l’s, a

coin could be tossed with a head landing up recorded as a 1 and a tail as a 0. It is assumed that the coin is unbiased, which means that the probability of a 1 on a given toss is exactly |. This will depend on how well the coin is made and how the toss is performed. This method would be of little value in a system where random sequences must be generated quickly and often. It has no practical value other than to serve as an example of the idea of random number generation. □

1.68 Example (random sequence generator) A noise diode may be used to produce random

binary sequences. This is reasonable if one has some way to be convinced that the probability that a 1 will be produced on any given trial is i. Should this assumption be false, the sequence generated would not have been selected from a uniform distribution and so not all sequences of a given length would be equally likely. The only way to get some feeling for the reliability of this type of random source is to carry out statistical tests on its output. These are considered in Chapter 5. If the diode is a source of a uniform distribution on the set of all binary sequences of a given length, it provides an effective way to generate random sequences. □

Since most true sources of random sequences (if there is such a thing) come from physical means, they tend to be either costly or slow in their generation. To overcome these problems, methods have been devised to construct pseudorandom sequences in a deterministic manner from a shorter random sequence called a seed. The pseudorandom sequences appear to be generated by a truly random source to anyone not knowing the method of generation. Often the generation algorithm is known to all, but the seed is unknown except by the entity generating the sequence. A plethora of algorithms has been developed to generate pseudorandom bit sequences of various types. Many of these are completely unsuitable for cryptographic purposes and one must be cautious of claims by creators of such algorithms as to the random nature of the output.

< Prev   CONTENTS   Source   Next >