|Previous||Table of Contents||Next|
Random-number generators are not random because they dont have to be. Most simple applications, like computer games, need so few random numbers that they hardly notice. However, cryptography is extremely sensitive to the properties of random-number generators. Use a poor random-number generator and you start getting weird correlations and strange results [1231,1238]. If you are depending on your random-number generator for security, weird correlations and strange results are the last things you want.
The problem is that a random-number generator doesnt produce a random sequence. It probably doesnt produce anything that looks even remotely like a random sequence. Of course, it is impossible to produce something truly random on a computer. Donald Knuth quotes John von Neumann as saying: Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin . Computers are deterministic beasts: Stuff goes in one end, completely predictable operations occur inside, and different stuff comes out the other end. Put the same stuff in on two separate occasions and the same stuff comes out both times. Put the same stuff into two identical computers, and the same stuff comes out of both of them. A computer can only be in a finite number of states (a large finite number, but a finite number nonetheless), and the stuff that comes out will always be a deterministic function of the stuff that went in and the computers current state. That means that any random-number generator on a computer (at least, on a finite-state machine) is, by definition, periodic. Anything that is periodic is, by definition, predictable. And if something is predictable, it cant be random. A true random-number generator requires some random input; a computer cant provide that.
The best a computer can produce is a pseudo-random-sequence generator. Whats that? Many people have taken a stab at defining this formally, but Ill hand-wave here. A pseudo-random sequence is one that looks random. The sequences period should be long enough so that a finite sequence of reasonable lengththat is, one that is actually usedis not periodic. If you need a billion random bits, dont choose a sequence generator that repeats after only sixteen thousand bits. These relatively short nonperiodic subsequences should be as indistinguishable as possible from random sequences. For example, they should have about the same number of ones and zeros, about half the runs (sequences of the same bit) should be of length one, one quarter of length two, one eighth of length three, and so on. They should not be compressible. The distribution of run lengths for zeros and ones should be the same [643,863,99,1357]. These properties can be empirically measured and then compared to statistical expectations using a chi-square test.
For our purposes, a sequence generator is pseudo-random if it has this property:
A lot of effort has gone into producing good pseudo-random sequences on computer. Discussions of generators abound in the academic literature, along with various tests of randomness. All of these generators are periodic (theres no escaping that); but with potential periods of 2256 bits and higher, they can be used for the largest applications.
The problem is still those weird correlations and strange results. Every pseudo-random-sequence generator is going to produce them if you use them in a certain way. And thats what a cryptanalyst will use to attack the system.
Cryptographically Secure Pseudo-Random Sequences
Cryptographic applications demand much more of a pseudo-random-sequence generator than do most other applications. Cryptographic randomness doesnt mean just statistical randomness, although thats part of it. For a sequence to be cryptographically secure pseudo-random, it must also have this property:
Cryptographically secure pseudo-random sequences should not be compressible...unless you know the key. The key is generally the seed used to set the initial state of the generator.
Like any cryptographic algorithm, cryptographically secure pseudo-random-sequence generators are subject to attack. Just as it is possible to break an encryption algorithm, it is possible to break a cryptographically secure pseudo-random-sequence generator. Making generators resistant to attack is what cryptography is all about.
Real Random Sequences
Now were drifting into the domain of philosophers. Is there such a thing as randomness? What is a random sequence? How do you know if a sequence is random? Is 101110100 more random than 101010101? Quantum mechanics tells us that there is honest-to-goodness randomness in the real world. But can we preserve that randomness in the deterministic world of computer chips and finite-state machines?
Philosophy aside, from our point of view a sequence generator is real random if it has this additional third property:
The output of a generator satisfying these three properties will be good enough for a one-time pad, key generation, and any other cryptographic applications that require a truly random sequence generator. The difficulty is in determining whether a sequence is really random. If I repeatedly encrypt a string with DES and a given key, I will get a nice, random-looking output; you wont be able to tell that its nonrandom unless you rent time on the NSAs DES cracker.
|Previous||Table of Contents||Next|