Linear Congruential Generators
By far, the most widely used technique for pseudorandom number
generation is an algorithm first proposed by Lehmer [LEHM51], which is known as the linear congruential method. The
algorithm is parameterized with four numbers, as follows:
|
m
|
the modulus
|
m > 0
|
|
a
|
the multiplier
|
0 < a < m
|
|
c
|
the increment
|
0
|
|
X0
|
the starting value, or seed
|
0
|
The sequence of random numbers {Xn} is obtained via the following iterative
equation:
Xn+1 = (aXn + c) mod
m
If m, a, c, and X0 are integers, then this technique will
produce a sequence of integers with each integer in the range 0 ![]()
Xn
< m.
The selection of values for a,
c, and m is critical in developing a good
random number generator. For example, consider a,
= c = 1. The sequence produced is obviously not
satisfactory. Now consider the values a = 7,
c = 0, m = 32, and
X0 = 1. This generates the sequence
{7, 17, 23, 1, 7, etc.}, which is also clearly unsatisfactory. Of the 32
possible values, only 4 are used; thus, the sequence is said to have a period of
4. If, instead, we change the value of a to 5,
then the sequence is {5, 25, 29, 17, 21, 9, 13, 1, 5, etc.}, which increases the
period to 8.
We would like m to be very
large, so that there is the potential for producing a long series of distinct
random numbers. A common criterion is that m be
nearly equal to the maximum representable nonnegative integer for a given
computer. Thus, a value of m near to or equal to
231 is typically chosen.
[PARK88] proposes three tests to be
used in evaluating a random number generator:
T1: The function should be a full-period generating function. That is, the function should generate all the numbers between 0 and m before repeating.T2: The generated sequence should appear random. Because it is generated deterministically, the sequence is not random. There is a variety of statistical tests that can be used to assess the degree to which a sequence exhibits randomness.T3: The function should implement efficiently with 32-bit arithmetic.
With appropriate values of a, c,
and m, these three tests can be passed. With
respect to T1 it can be shown that if m is prime and c = 0,
then for certain values of a, the period of the
generating function is m 1, with only the value 0
missing. For 32-bit arithmetic, a convenient prime value of m is 231 1. Thus, the generating function
becomes
Xn+1 = (aXn) mod(231 1)
Of the more than 2 billion possible choices for a, only a handful of multipliers pass all three tests.
One such value is a = 75 = 16807,
which was originally designed for use in the IBM 360 family of computers [LEWI69]. This generator
is widely used and has been subjected to a more thorough testing than any other
PRNG. It is frequently recommended for statistical and simulation work (e.g.,
[JAIN91], [SAUE81]).
The strength of the linear congruential algorithm is that if
the multiplier and modulus are properly chosen, the resulting sequence of
numbers will be statistically indistinguishable from a sequence drawn at random
(but without replacement) from the set 1, 2,...,m
1. But there is nothing random at all about the algorithm, apart from the choice
of the initial value X0. Once that
value is chosen, the remaining numbers in the sequence follow deterministically.
This has implications for cryptanalysis.
If an opponent knows that the linear congruential algorithm is
being used and if the parameters are known (e.g., a =75, c = 0,
m = 231 1), then once a single number
is discovered, all subsequent numbers are known. Even if the opponent knows only
that a linear congruential algorithm is being used, knowledge of a small part of
the sequence is sufficient to determine the parameters of the algorithm. Suppose
that the opponent is able to determine values for X0, X1, X2 and X3 Then
X1 = (aX0 + c) mod
m
X2 = (aX1 + c) mod
m
X3 = (aX2 + c) mod
m
These equations can be solved for a,
c, and m.
Thus, although it is nice to be able to use a good PRNG, it
is desirable to make the actual sequence used nonreproducible, so that knowledge
of part of the sequence on the part of an opponent is insufficient to determine
future elements of the sequence. This goal can be achieved in a number of ways.
For example, [BRIG79] suggests using an internal
system clock to modify the random number stream. One way to use the clock would
be to restart the sequence after every N numbers
using the current clock value (mod m) as the new
seed. Another way would be simply to add the current clock value to each random
number (mod m).
Cryptographically Generated Random Numbers
For cryptographic applications, it makes some sense to take
advantage of the encryption logic available to produce random numbers. A number
of means have been used, and in this subsection we look at three representative
examples.
Cyclic Encryption
Figure 7.13 illustrates
an approach suggested in [MEYE82]. In this case, the procedure
is used to generate session keys from a master key. A counter with period N provides input to the encryption logic. For example,
if 56-bit DES keys are to be produced, then a counter with period 256
can be used. After each key is produced, the counter is incremented by one.
Thus, the pseudorandom numbers produced by this scheme cycle through a full
period: Each of the outputs X0, X1,... XN1 is based
on a different counter value and therefore X0 ![]()
X1 ![]()
... ![]()
XN1. Because
the master key is protected, it is not computationally feasible to deduce any of
the session keys (random numbers) through knowledge of one or more earlier
session keys.
No comments:
Post a Comment