Cryptography Reference
In-Depth Information
Unfortunately, these questions don't make a lot of sense unless they are considered
in a specific context.
In theory, there exists a measure of randomness for a finite sequence of values.
In fact, the
Kolmogorov complexity
measures the minimal length of a program
for a Turing machine
1
that is able to generate the sequence. Unfortunately, the
Kolmogorov complexity is inherently noncomputable (i.e., it is not known how to
compute the Kolmogorov complexity for a given sequence of values), and hence
it is not particularly useful. If we know that a (pseudorandom) bit sequence was
generated with a
linear feedback shift register
(LFSR), then we could use the
linear
complexity
to measure its randomness. In fact, the linear complexity measures the
size (i.e., number of bits) of the shortest LFSR that can produce the sequence. The
measure therefore speaks to the difficulty of generating—and perhaps analyzing—
the bit sequence. There is an algorithm due to Berlekamp and Massey [1] that can
be used to compute the linear complexity. Note, however, that the linear complexity
(and hence also the Berlekamp-Massey algorithm) assumes that the (pseudorandom)
bit sequence is generated with an LFSR. Consequently, it is possible that a bit
sequence has a large linear complexity but can still be generated easily with some
other means.
Without arguing about the existence of randomness and without trying to
measure the randomness of a given sequence of values (e.g., bits or numbers), we
elaborate on the question of how random bits can be generated in the rest of this
chapter. According to Definition 2.5, a random bit generator is a device or algorithm
that outputs a sequence of statistically independent and unbiased bits. This basically
means that the bits occur with the same probability (i.e., Pr[0] = Pr[1] = 1
/
2), and
that all 2
k
possible
k
-tuples occur approximately equally often (i.e., with probability
1
/
2
k
for all
k
).
If we can generate random bits, then we can also generate (uniformly distrib-
uted) random numbers of any size. If, for example, we want to construct an
n
-bit
random number
a
,thenweset
b
1
=1, use the random bit generator to generate
n
∈
N
−
1 random bits
b
2
,...,b
n
,andset
n
b
i
2
n−i
.
a
=
(9.1)
i
=1
Similarly, if we want to construct a number that is randomly selected from the
interval [0
,m
] for
m
∈
N
,thenweset
n
to the length of
m
(i.e.,
n
=
log
m
+1)and
use the random bit generator to generate
n
random bits
b
1
,...,b
n
.If
a
constructed
according to (9.1) is smaller or equal to
m
, then we use it. If, however,
a
is bigger
1
Refer to Section 6.5 for an introduction to Turing machines.
