Cryptography Reference
In-Depth Information
reseeded periodically. This may be modeled by having a function
f
that takes into
account additional sources of randomness (this possibility is not illustrated in Figure
12.1). In this case, however, the distinction between a random bit generator and a
PRBG gets fuzzy.
There are many security requirements for PRBGs. For example, an obvious
(minimal) security requirement is that the length of the seed (i.e.,
) must be suffi-
ciently large so that a search over all 2
|s
0
|
elements of the space of all possible seeds
is computationally infeasible for the adversary. Furthermore, the bit sequence gen-
erated by a PRBG must pass all relevant statistical randomness tests (as mentioned
in Section 9.3). Note, however, that passing statistical randomness tests is only a
necessary but usually not sufficient condition for a PRBG to be secure in a cryp-
tographically strong sense. For example, the following PRBGs pass most statistical
randomness tests but are still not sufficiently secure for cryptographic purposes:
|
s
0
|
1. PRBGs that employ LFSRs as introduced and briefly discussed in Section
10.3;
2. PRBGs that employ the binary expansion of algebraic numbers, such as
√
3
or
√
5;
3. Linear congruential generators that take as input a seed
x
0
=
s
0
and three
integer parameters
a
,
b
,and
n
, and that use the linear recurrence
x
i
=
ax
i−
1
+
b
(mod
n
)
to recursively generate an output sequence (
x
i
)
i≥
1
.
LFSRs have well-known shortcomings and weaknesses when used as PRBGs.
The same is true for the binary expansion of algebraic numbers. Last but not
least, linear congruential generators are frequently used for simulation purposes
and probabilistic algorithms (see, for example, Chapter 3 of [1]), but they are
predictable—that is, it is possible to infer the parameters
a
,
b
,and
n
given just a few
output values
x
i
(e.g., [2, 3]). This makes them particularly useless for cryptographic
applications.
Contrary to these examples, there are PRBGs that can be used for crypto-
graphic purposes. For example, if we have a one-way function
f
, then we can always
construct a conceptually simple PRBG by selecting a seed
s
0
and applying
f
to the
sequence of values
s
1
=
s
0
+1
