A pseudorandom number generator (PRNG) is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. It is not truly random in that it is completely determined by a relatively small set of initial values, called the PRNG’s state. Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom numbers are important in practice for simulations (e.g., of physical systems with the Monte Carlo method), and are central in the practice of cryptography and procedural generation. Common classes of these algorithms are linear congruential generators, Lagged Fibonacci generators, linear feedback shift registers and generalised feedback shift registers. Recent instances of pseudorandom algorithms include Blum Blum Shub, Fortuna, and the Mersenne twister.
Careful mathematical analysis is required to have any confidence a PRNG generates numbers that are sufficiently “random” to suit the intended use. Robert R. Coveyou of Oak Ridge National Laboratory once titled an article, “The generation of random numbers is too important to be left to chance.” As John von Neumann joked, “Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.”
A PRNG can be started from an arbitrary starting state, using a seed state. It will always produce the same sequence thereafter when initialized with that state. The maximum length of the sequence before it begins to repeat is determined by the size of the state, measured in bits. However, since the length of the maximum period potentially doubles with each bit of ‘state’ added, it is easy to build PRNGs with periods long enough for many practical applications.
If a PRNG’s internal state contains n bits, its period can be no longer than 2n results. For some PRNGs the period length can be calculated without walking through the whole period. Linear Feedback Shift Registers (LFSRs) are usually chosen to have periods of exactly 2n−1. Linear congruential generators have periods that can be calculated by factoring. Mixes (no restrictions) have periods of about 2n/2 on average, usually after walking through a nonrepeating starting sequence. Mixes that are reversible (permutations) have periods of about 2n−1 on average, and the period will always include the original internal state. Although PRNGs will repeat their results after they reach the end of their period, a repeated result does not imply that the end of the period has been reached, since its internal state may be larger than its output; this is particularly obvious with PRNGs with a 1-bit output.
Most pseudorandom generator algorithms produce sequences which are uniformly distributed by any of several tests. It is an open question, and one central to the theory and practice of cryptography, whether there is any way to distinguish the output of a high-quality PRNG from a truly random sequence without knowing the algorithm(s) used and the state with which it was initialized. The security of most cryptographic algorithms and protocols using PRNGs is based on the assumption that it is infeasible to distinguish use of a suitable PRNG from use of a truly random sequence. The simplest examples of this dependency are stream ciphers, which (most often) work by exclusive or-ing the plaintext of a message with the output of a PRNG, producing ciphertext. The design of cryptographically adequate PRNGs is extremely difficult, because they must meet additional criteria. The size of its period is an important factor in the cryptographic suitability of a PRNG, but not the only one.
A PRNG suitable for cryptographic applications is called a cryptographically secure PRNG (CSPRNG). The difference between a PRNG and a CSPRNG is not simple: a CSPRNG must meet certain design principles and be resistant to known attacks. Years of review are required before such an algorithm can be certified and it is still possible attacks will be discovered in the future.
Some classes of CSPRNGs include the following:
- Stream ciphers
- block ciphers running in counter or output feedback mode.
- Special designs with a security proof. For example Blum Blum Shub has a strong security proof, although the proof is conditional and requires that some internal values remain secret from any attacker. Moreover, Blum Blum Shub is too slow for many applications.
- PRNGs that have been designed specifically to be cryptographically secure, such as Microsoft’s Cryptographic Application Programming Interface function CryptGenRandom, the Yarrow algorithm (incorporated in Mac OS X and FreeBSD), and Fortuna.
- Combination PRNGs which attempt to combine several PRNG primitive algorithms with the goal of removing any non-randomness.
A cryptographically secure pseudo-random number generator (CSPRNG) is a pseudo-random number generator (PRNG) with properties that make it suitable for use in cryptography.
Many aspects of cryptography require random numbers, for example:
- Key generation
- Nonces
- Salts in certain signature schemes, including ECDSA, RSASSA-PSS.
- One-time pads
The “quality” of the randomness required for these applications varies. For example creating a nonce in some protocols needs only uniqueness. On the other hand, generation of a master key requires a higher quality, such as more entropy. And in the case of one-time pads, the information-theoretic guarantee of perfect secrecy only holds if the key material is obtained from a true random source with high entropy.
Ideally, the generation of random numbers in CSPRNGs uses entropy obtained from a high quality source, which might be a hardware random number generator or perhaps unpredictable system processes — though unexpected correlations have been found in several such ostensibly independent processes. From an information theoretic point of view, the amount of randomness, the entropy that can be generated is equal to the entropy provided by the system. But sometimes, in practical situations, more random numbers are needed than there is entropy available. Also the processes to extract randomness from a running system are slow in actual practice. In such instances, a CSPRNG can sometimes be used. A CSPRNG can “stretch” the available entropy over more bits.
When all the entropy we have is available before algorithm execution begins, we really have a stream cipher. However some crypto system designs allow for the addition of entropy during execution, in which case it is not a stream cipher equivalent and cannot be used as one. Stream cipher and CSPRNG design is thus closely related.
While this certainly would have been and likely currently is of great interest to Ed Scheidt, the idea of trying to solve a PRNG augmented cipher seems to be far beyond what is possible with pencil and paper. At least far beyond quite a few people. I think I read something that said they’ve been known since around 1946 so conceivably it is possible they were considered for Kryptos. I will bow out and simply say that this is currently beyond my abilities so it will not be very possible for me to examine possible applications.
Kryptos - Beyond K4 
The article says that stream ciphers are CSPRNGs. This is wrong. CSPRNGs can be used as stream ciphers, but not all stream ciphers have CSPRNG properties. A CSPRNG must be backward secure, i.e. if the internal state is partly or fully compromised, it must not be possible to go “backwards” in the stream. This is however possible in some stream ciphers (Grain, SEAL, etc.)
Seriously? You actually believe he wrote every word in every post or page? And then you run him down while sounding like some expert. If you know so much then why not contribute a little something to the cause?
I don’t think I’d agree with your comment but to clarify: I intended to describe PRNGs, CSPRNGs, their possible applications etc. etc. At this point I was considering if an archetypal algorithm could have been employed that someone with the know-how would be able to detect and thereby unravel. I can’t do this but it presents an interesting explanation for how K4 has resisted being solved.
Sorry for the confusion for anyone else, I’m sure some stream ciphers do not use CSPRNGs but the post was about PRNGs and I’d like to know how one would make a true stream cipher without pseudorandom numbers.