Pseudorandomness
|
|
Pseudorandomness is the state of being, while statistically seemingly random, generated at least in part by a definite computational process.
Almost random
A pseudo-random variable is a variable which is created by a deterministic procedure (often a computer program or subroutine) which (generally) takes random bits as input. The pseudo-random string will typically be longer than the original random string, but less random (less entropy in the information theory sense). This can be useful for randomized algorithms.
Pseudorandom number generators are widely used in such applications as computer modeling (e.g., Markov chains), statistics, experimental design, etc. Some of them are 'sufficiently' random to be useful in these applications. Many are not, and considerable sophistication is required to correctly determine the difference for any particular purpose. Incautious use of readily available random number generators has caused considerable, and long sustained, damage to the worth of large numbers of research projects for many years. The RANDU generator routine available on many large mainframe computers for decades had considerable, widely unappreciated, faults.
Consider a warning from an unusually capable observer: "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin." - John von Neumann (1951)
Cryptography
For such applications as cryptography, the use of pseudorandom number generators (whether hardware or software or some combination) is insecure. When random values are required in cryptography, the context is making an opponent's cryptanalytic life maximally difficult, so that message security will be maximized. Only a random, and furthermore, unpredictable value (or a great many of them) can provide this. Note that truly random sequences may be in fact nevertheless predictable and so entirely useless for cryptographic purposes (consider the digits of π, e, or φ, for instance).
There are many examples in cryptographic history of cyphers, otherwise excellent, in which random choices were not random enough and security was lost in direct consequence. The World War II Japanese Purple cypher machine used for diplomatic communications is a good example. It was consistently broken throughout WWII, and indeed from somewhat before the United States entered that war, mostly because the 'key values' used were insufficiently random. They had patterns, and those patterns made any intercepted traffic readily decryptable. Had keys (ie, the initial settings of the stepping switches in the machine) been made unpredictably (ie, randomly), that traffic would have been much much harder to break, and perhaps even secure in practice (as the Purple machine was actually a pretty good design, for its time).
Users and designers of cryptography are strongly cautioned to treat their randomness needs with the utmost care. Absolutely nothing has changed with the era of computerized cryptography, except that patterns in pseudo random data are easier to discover than ever before. Randomness is, if anything, more important than ever.