Now, first of all what is random?
It turns out that there are
an awful lot of definitions of random.
And there are two major ones that are very widely used.
The first one is statistical randomness.
If you look at a sequence of bits, zeros and ones.
With statistical randomness, the rule is that there'll be
an equal probability that
the next bits you get will be zero or one.
So in other words, it's equally likely
to be zero as it is to one.
And then it has to pass
certain statistical tests for randomness.
But once you've done that,
you've got a good statistically random sequence
of bits that you can use a simulation search.
The problem is these bits are often generated by
algorithms and as such are predictable.
This takes us to another type of cryptography,
another type of randomness called kolmogorov
randomness or cryptographic randomness.
That adds the requirement that,
given perfect knowledge of every bit that
has been generated in the sequence so far,
you cannot predict what the next bit will be.
And the difference between it and
statistical randomness is given
a perfect knowledge of every bit that
has been generated in the past for
the sequence with
statistical randomness, there's an algorithm.
And so you can figure out the algorithm
and then just figure out whether
the next bit is zero or one.
It's equally likely to be both,
but there is an algorithm that allows you to predict it.
With cryptographic randomness, you can't have that.
And the reason that's important is
because for example in generating cryptographic keys,
if you know what one key is
and you can predict the next few bits,
you can reduce the space the number of
keys you have to search to get the next key,
or eliminate it entirely and just know what it is.
Both cryptographic randomness you can't do this.
Now, here's an interesting and amusing comic
that illustrates this point.
It's from Scott Adams Dilbert.
And the comic is, Dogbert asked to generate
a sequence of random numbers, integers.
Dogbert says, okay 9, 9, 9,
9, 9, 9, 9,
9, 9 and so forth.
Dilbert expresses incredulity and
says, are those really random?
Now the question is, could this actually occur
with a real random number generator?
Surprisingly the answer is yes.
Because given a sequence of numbers in the past,
it would be equally likely to be any one
of the digits, zero to nine.
And it could be nine,
this is called the rand.
And if you look for example at
the decimal representation of the number pi.
In pi, there are a number of
rands of nines and other numbers too,
yet pi is transcendental and
the numbers in the digits in
its representation are often treated as random.
By the way they're not really random,
they're pseudorandom because once you
figure out that it's the digits in pi,
you can predict the next one quite easily.
So, the distinction between random and pseudorandom.
If it's statistically random,
then it's pseudorandom for
the purposes for which we're using the term.
Pseudorandom means it's produced by an algorithm that
generates a series of bits that appear unpredictable,
but in fact are computed from an algorithm.
The pseudorandom number generators
typically maintain what's called internal state,
which tells them how to generate the next number.
Every time something is output,
every time you output a bit, the state changes.
And what the pseudorandom number generates,
you have to start somewhere.
So you have an initial state.
This is called the seed.
Sometimes you just get a little short stringing
you generate the initial actual initial state from it.
But the point is wherever you start, that's the seed.
If I can guess the seed,
I can generate the entire sequence.
On the other hand, a random sequence of bits is
something that's not generated
by a deterministic algorithm.
It's usually some physical phenomena.
For example certain aspects of hardware.
Rand did a very famous collection of
numbers by measuring output,
rather by measuring changes in radiation level
from the nuclear testing in the fifties.
And even there they had to touch it up a little
bit to make it usable.
But the point is the atomic background is random.
White noise is another very good way to generate it.
White noise is simply what you hear when there's nothing,
when you don't hear sounds.
How discs do seeks or rather
the variance and times is often random as well.
So there are a number of ways to get it from hardware.
And once you've generated them bits,
there may be a deterministic algorithm applied to
add some more uncertainty, that's fine.
But the point is, the algorithm
doesn't start from a seed. It's not predictable.
It starts from a set of random numbers or random bits.
And so, you don't know what's going to come out
even if you know everything previously.
A good way to look at this is if you're going to
test something that uses random numbers,
you want pseudorandom numbers
because that way you can repeat
the same sequence over and over
just by using the same seed.
On the other hand when it rolls into production,
you're going to want real random
numbers and that's when you use
a real random number generator
rather than a pseudorandom number generator.
Because if you can repeat it, it's pseudorandom.
It is not random.