Cryptography Reference
In-Depth Information
Regardless of the underlying technique used, there are two problems with
non-deterministic generators:
1. They tend to be expensive to implement.
2. It is, essentially, impossible to produce two identical strings of true randomness
in two different places (indeed, this is the very point of using physical
phenomena as a randomness source).
For these reasons, in most cryptographic applications deterministic sources of
randomness tend to be preferred.
8.1.4
Deterministic generators
The idea of a
deterministic
random generator may sound like an oxymoron,
since anything that can be determined cannot be truly random. The term
pseudorandom
(which we introduced in Section 4.2.1) is often used to describe
both a deterministic generator and its output.
BASIC MODEL OF A DETERMINISTIC GENERATOR
A
deterministic generator
is an algorithm that outputs a pseudorandom bit
string, in other words a bit string that has no apparent structure. However,
as we just hinted, the output of a deterministic generator is certainly not
randomly generated. In fact, anyone who knows the information that is input
to the deterministic generator can completely predict the output. Each time the
algorithm is run using the same input, the same output will be produced. Such
predictability is, in at least one sense, the opposite of randomness.
However, if we use a
secret
input into the deterministic generator then, with
careful design of the generation process, we might be able to generate output
that will have no apparent structure. It will thus
appear
to have been randomly
generated to anyone who does not know the secret input. This is precisely the idea
behind a deterministic generator. The basic model of a deterministic generator is
shown in Figure 8.1.
Seed
Generator
11001011010100100011101001….
Figure 8.1.
Basic model of a deterministic generator
