Block Ciphers - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 115

wind, flipping style, and the relative weight of the two sides of the coin. For example, if a coin is flipped 100
times, it may turn out that on average, we can expect heads to occur about 49 times but tails to occur 51 times
(with probabilities 0.49 and 0.51, respectively).
This is an example of bias : the characteristic of a process to favor one outcome more often than others, even
if that process is truly random.
There are ways to reduce bias, typically by combining several bits to produce one bit, or by combining sever-
al sources of randomness with each other. For example, we can simply XOR several bits from different random
sources to obtain a new random bit. With the coin example, we will assume that tails is a 0, and heads is a 1. If
we take two coin flips, we get a 0 if we have two tails in a row, or two heads in a row, giving us a probability of
The probability of a 1 is therefore 1 − 0.5002 = 0.4998. Both probabilities are much closer to 1/2, giving us a
bit that has much less bias in its output (since a purely random coin flip would have a probability of 1/2 for both
heads and tails).
4.13.2 Linear Congruential Random Number Generator
Of all of the various types of pseudorandom number generators out there, a decent and popular choice is the
linear congruential random number generator [6]. This is a random number generator that gives a sequence
of numbers from numbers of the form
This gives a sequence of numbers dependent on integers a, c, m, and the seed , which is the initial value ( X 0 ) of
the series.
This series is called “linear congruential” because it is based on the fact that the next number is linearly re-
lated to the next, modulo m.
Knuth [6] gives some guidance to reduce predictability and bias in this series:
1. The seed can be chosen arbitrarily. Three common ways to get a seed include saving it between ses-
sions, generating it from the current date and time, or having the user input it. With all of the other vari-
ables the same, using the same seed each time allows experiments with a pseudorandom source to be run
with repeatable results.
2. The modulus m should be large, greater than 2 30 . The word size of the computer, such as 32 or 64 bits,
is acceptable, especially with speed concerns. But there must be no roundoff errors possible (meaning
integer, and not floating point, arithmetic must be used).
3. If m is the computer word size, such as 2 32 for a 32-bit computer, then ensure that a ≡ 5 (mod 8).
Otherwise, there will be cycles in the output, and certain values will never be hit (because of algebraic
properties of linear congruences).
4. Set a to be in the range m /100 to 99 m /100, and not have a simple digit pattern (like 12121...). Further-
more, a should be put through several statistical tests to guarantee that the numbers are acceptable.
5. Choose c so that it shares no common factors with m, essentially, although its choice is far less import-
ant than a. Preferably, do not choose c = 0.
6. The most significant bits (on the left) are more random than the least significant bits (on the right), and
thus these should play a greater role. It's better to use the bits to represent a binary number between 0 and
1, that is, by letting the bits be on the right side after the decimal point (or, better, the “binary point”).