Cryptographically secure pseudorandom number generator
A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG)^{[1]} is a pseudorandom 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
 onetime pads
 salts in certain signature schemes, including ECDSA, RSASSAPSS
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 onetime pads, the informationtheoretic guarantee of perfect secrecy only holds if the key material comes from a true random source with high entropy.
Ideally, the generation of random numbers in CSPRNGs uses entropy obtained from a highquality source, generally the operating system's randomness API. However, unexpected correlations have been found in several such ostensibly independent processes. From an informationtheoretic 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.
Contents
Requirements
The requirements of an ordinary PRNG are also satisfied by a cryptographically secure PRNG, but the reverse is not true. CSPRNG requirements fall into two groups: first, that they pass statistical randomness tests; and secondly, that they hold up well under serious attack, even when part of their initial or running state becomes available to an attacker.^{[citation needed]}
 Every CSPRNG should satisfy the nextbit test. That is, given the first k bits of a random sequence, there is no polynomialtime algorithm that can predict the (k+1)th bit with probability of success better than 50%. Andrew Yao proved in 1982 that a generator passing the nextbit test will pass all other polynomialtime statistical tests for randomness.^{[2]}
 Every CSPRNG should withstand "state compromise extensions". In the event that part or all of its state has been revealed (or guessed correctly), it should be impossible to reconstruct the stream of random numbers prior to the revelation. Additionally, if there is an entropy input while running, it should be infeasible to use knowledge of the input's state to predict future conditions of the CSPRNG state.

 Example: If the CSPRNG under consideration produces output by computing bits of π in sequence, starting from some unknown point in the binary expansion, it may well satisfy the nextbit test and thus be statistically random, as π appears to be a random sequence. (This would be guaranteed if π is a normal number, for example.) However, this algorithm is not cryptographically secure; an attacker who determines which bit of pi (i.e. the state of the algorithm) is currently in use will be able to calculate all preceding bits as well.
Most PRNGs are not suitable for use as CSPRNGs and will fail on both counts. First, while most PRNGs outputs appear random to assorted statistical tests, they do not resist determined reverse engineering. Specialized statistical tests may be found specially tuned to such a PRNG that shows the random numbers not to be truly random. Second, for most PRNGs, when their state has been revealed, all past random numbers can be retrodicted, allowing an attacker to read all past messages, as well as future ones.
CSPRNGs are designed explicitly to resist this type of cryptanalysis.
Definitions
In the asymptotic setting, a family of deterministic polynomial time computable functions G_{k} : {0, 1}^{k} → {0, 1}^{p(k)} for some polynomial p, is a pseudorandom number generator (PRG), if it stretches the length of its input (p(k) > k for any k), and if its output is computationally indistinguishable from true randomess, i.e. for any probabilistic polynomial time algorithm A, which outputs 1 or 0 as a distinguisher,
 Pr[x ← {0, 1}^{k}, A(G(x))=1]  Pr[r ← {0, 1}^{p(k)}, A(r)=1] < μ(k) for some negligible function μ.^{[3]} (The notation x ← X means that x is chosen uniformly at random from the set X.)
There is an equivalent characterization: For any function family G_{k} : {0, 1}^{k} → {0, 1}^{p(k)}, G is a PRG if and only if the next output bit of G cannot be predicted by a polynomial time algorithm.^{[4]}
A PRG G_{k} : {0, 1}^{k} → {0, 1}^{k} × {0, 1}^{t(k)} with block length t(k) is a polynomial time computable function, where the input string s_{i} with length k is the current state at period i, and the output (s_{i+1}, y_{i}) consists of the next state s_{i+1} and the pseudorandom output block y_{i} of period i. Such a PRG is called forward secure if it withstands state compromise extensions in the following sense. If the initial state s_{1} is chosen at uniformly random from {0, 1}^{k}, for any i, (y_{1}y_{2}···y_{i}, s_{i+1}) must be computationally indistinguishable from (r_{i·t(k)}, s_{i+1}), in which r_{i·t(k)} is chosen at uniformly random from {0, 1}^{i·t(k)}. ^{[5]}
Any PRG G : {0, 1}^{k} → {0, 1}^{p(k)} can be turned into a forward secure PRG with block length p(k)  k by splitting its output into the next state and the actual output. This is done by setting G(s) = (G_{0}(s), G_{1}(s)), in which G_{0}(s) = s = k and G_{1}(s) = p(k)  k; then G is a forward secure PRG with G_{0} as the next state and G_{1} as the pseudorandom output block of the current period.
Entropy extraction
Santha and Vazirani proved that several bit streams with weak randomness can be combined to produce a higherquality quasirandom bit stream.^{[6]} Even earlier, John von Neumann proved that a simple algorithm can remove a considerable amount of the bias in any bit stream^{[7]} which should be applied to each bit stream before using any variation of the SanthaVazirani design.
Designs
In the discussion below, CSPRNG designs are divided into three classes: 1) those based on cryptographic primitives such as ciphers and cryptographic hashes, 2) those based upon mathematical problems thought to be hard, and 3) specialpurpose designs. The last often introduce additional entropy when available and, strictly speaking, are not "pure" pseudorandom number generators, as their output is not completely determined by their initial state. This addition can prevent attacks even if the initial state is compromised.
Designs based on cryptographic primitives
 A secure block cipher can be converted into a CSPRNG by running it in counter mode. This is done by choosing a random key and encrypting a 0, then encrypting a 1, then encrypting a 2, etc. The counter can also be started at an arbitrary number other than zero. Assuming an nbit block cipher the output can be distinguished from random data after around 2^{n/2} blocks since, following the birthday problem, colliding blocks should become likely at that point, whereas a block cipher in CTR mode will never output identical blocks. For 64 bit block ciphers this limits the safe output size to a few gigabytes, with 128 bit blocks the limitation is large enough not to impact typical applications.
 A cryptographically secure hash of a counter might also act as a good CSPRNG in some cases. In this case, it is also necessary that the initial value of this counter is random and secret. However, there has been little study of these algorithms for use in this manner, and at least some authors warn against this use.^{[vague]}^{[8]}
 Most stream ciphers work by generating a pseudorandom stream of bits that are combined (almost always XORed) with the plaintext; running the cipher on a counter will return a new pseudorandom stream, possibly with a longer period. The cipher can only be secure if the original stream is a good CSPRNG, although this is not necessarily the case (see the RC4 cipher). Again, the initial state must be kept secret.
Number theoretic designs
 The Blum Blum Shub algorithm has a security proof based on the difficulty of the Quadratic residuosity problem. Since the only known way to solve that problem is to factor the modulus, it is generally regarded that the difficulty of integer factorization provides a conditional security proof for the Blum Blum Shub algorithm. However the algorithm is very inefficient and therefore impractical unless extreme security is needed.
 The BlumMicali algorithm has an unconditional security proof based on the difficulty of the discrete logarithm problem but is also very inefficient.
 Daniel Brown of Certicom has written a 2006 security proof for Dual_EC_DRBG, based on the assumed hardness of the Decisional Diffie–Hellman assumption, the xlogarithm problem, and the truncated point problem. The 2006 proof explicitly assumes a lower outlen than in the Dual_EC_DRBG standard, and that the P and Q in the Dual_EC_DRBG standard (which were revealed in 2013 to be probably backdoored by NSA) are replaced with nonbackdoored values.
Special designs
There are a number of practical PRNGs that have been designed to be cryptographically secure, including
 the Yarrow algorithm which attempts to evaluate the entropic quality of its inputs. Yarrow is used in FreeBSD, OpenBSD and Mac OS X (also as /dev/random).
 the Fortuna algorithm, the successor to Yarrow, which does not attempt to evaluate the entropic quality of its inputs.
 the function CryptGenRandom provided in Microsoft's Cryptographic Application Programming Interface
 ISAAC based on a variant of the RC4 cipher
 Evolutionary algorithm based on NIST Statistical Test Suite.^{[9]}^{[10]}
 arc4random
 AESCTR DRBG is often used as a random number generator in systems that use AES encryption.^{[11]}^{[12]}
 ANSI X9.17 standard (Financial Institution Key Management (wholesale)), which has been adopted as a FIPS standard as well. It takes as input a TDEA (keying option 2) key bundle k and (the initial value of) a 64 bit random seed s.^{[13]} Each time a random number is required it:
 Obtains the current date/time D to the maximum resolution possible.
 Computes a temporary value t = TDEA_{k}(D)
 Computes the random value x = TDEA_{k}(s ⊕ t), where ⊕ denotes bitwise exclusive or.
 Updates the seed s = TDEA_{k}(x ⊕ t)
 Obviously, the technique is easily generalized to any block cipher; AES has been suggested (Young and Yung, op cit, sect 3.5.1).
Standards
Several CSPRNGs have been standardized. For example,
 FIPS 1862
 NIST SP 80090A: This standard has three uncontroversial CSPRNGs named Hash_DRBG, HMAC_DRBG, and CTR_DRBG; and a PRNG named Dual_EC_DRBG which has been shown to not be cryptographically secure and probably has a kleptographic NSA backdoor.
 ANSI X9.171985 Appendix C
 ANSI X9.311998 Appendix A.2.4
 ANSI X9.621998 Annex A.4, obsoleted by ANSI X9.622005, Annex D (HMAC_DRBG)
A good reference is maintained by NIST.
There are also standards for statistical testing of new CSPRNG designs:
 A Statistical Test Suite for Random and Pseudorandom Number Generators, NIST Special Publication 80022.
NSA backdoor in the Dual_EC_DRBG PRNG
The Guardian and The New York Times have reported that the National Security Agency (NSA) inserted a PRNG into NIST SP 80090A that had a backdoor which allows the NSA to readily decrypt material that was encrypted with the aid of Dual_EC_DRBG. Both papers report^{[14]}^{[15]} that, as independent security experts long suspected,^{[16]} the NSA has been introducing weaknesses into CSPRNG standard 80090; this being confirmed for the first time by one of the top secret documents leaked to the Guardian by Edward Snowden. The NSA worked covertly to get its own version of the NIST draft security standard approved for worldwide use in 2006. The leaked document states that "eventually, NSA became the sole editor." In spite of the known potential for a backdoor and other known significant deficiencies with Dual_EC_DRBG, several companies such as RSA Security continued using Dual_EC_DRBG until the backdoor was confirmed in 2013.^{[17]} RSA Security received a $10 million payment from the NSA to do so.^{[18]}
References
 ↑ Huang, Andrew (2003). Hacking the Xbox: An Introduction to Reverse Engineering. No Starch Press Series. No Starch Press. p. 111. ISBN 9781593270292. Retrieved 20131024.
[...] the keystream generator [...] can be thought of as a cryptographic pseudorandom number generator (CPRNG).
 ↑ Andrew ChiChih Yao. Theory and applications of trapdoor functions. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982.
 ↑ Goldreich, Oded (2001), Foundations of cryptography I: Basic Tools, Cambridge: Cambridge University Press, ISBN 9780511546891, def 3.3.1.
 ↑ Goldreich, Oded (2001), Foundations of cryptography I: Basic Tools, Cambridge: Cambridge University Press, ISBN 9780511546891, Theorem 3.3.7.
 ↑ Dodis, Yevgeniy, Lecture 5 Notes of Introduction to Cryptography (PDF), retrieved 3 January 2016, def 4.
 ↑ Miklos Santha, Umesh V. Vazirani (19841024). "Generating quasirandom sequences from slightlyrandom sources" (PDF). Proceedings of the 25th IEEE Symposium on Foundations of Computer Science. University of California. pp. 434–440. ISBN 081860591X. Retrieved 20061129.
 ↑ John von Neumann (19630301). "Various techniques for use in connection with random digits". The Collected Works of John von Neumann. Pergamon Press. pp. 768–770. ISBN 0080095666.
 ↑ Adam Young, Moti Yung (20040201). Malicious Cryptography: Exposing Cryptovirology. sect 3.2: John Wiley & Sons. p. 416. ISBN 9780764549755.
 ↑ NIST. "A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications". NIST, Special Publication April 2010
 ↑ A. Poorghanad, A. Sadr, A. Kashanipour" Generating High Quality Pseudo Random Number Using Evolutionary Methods", IEEE Congress on Computational Intelligence and Security, vol. 9, pp. 331335 , May,2008 [1]
 ↑ David Kleidermacher, Mike Kleidermacher. "Embedded Systems Security: Practical Methods for Safe and Secure Software and Systems Development". Elsevier, 2012. p. 256.
 ↑ George Cox, Charles Dike, and DJ Johnston. "Intel’s Digital Random Number Generator (DRNG)". 2011.
 ↑ Handbook of Applied Cryptography, Alfred Menezes, Paul van Oorschot, and Scott Vanstone, CRC Press, 1996, Chapter 5 Pseudorandom Bits and Sequences (PDF)
 ↑ James Borger; Glenn Greenwald (6 September 2013). "Revealed: how US and UK spy agencies defeat internet privacy and security". The Guardian. The Guardian. Retrieved 7 September 2013.
 ↑ Nicole Perlroth (5 September 2013). "N.S.A. Able to Foil Basic Safeguards of Privacy on Web". The New York Times. Retrieved 7 September 2013.
 ↑ Bruce Schneier (15 November 2007). "Did NSA Put a Secret Backdoor in New Encryption Standard?". Wired. Retrieved 7 September 2013.
 ↑ Matthew Green. "RSA warns developers not to use RSA products".
 ↑ Joseph Menn (20 December 2013). "Exclusive: Secret contract tied NSA and security industry pioneer". Reuters.
External links
The Wikibook Cryptography has a page on the topic of: Random number generation 
 RFC 4086, Randomness Requirements for Security
 Java "entropy pool" for cryptographically secure unpredictable random numbers.
 Java standard class providing a cryptographically strong pseudorandom number generator (PRNG).
 Cryptographically Secure Random number on Windows without using CryptoAPI
 Conjectured Security of the ANSINIST Elliptic Curve RNG, Daniel R. L. Brown, IACR ePrint 2006/117.
 A Security Analysis of the NIST SP 80090 Elliptic Curve Random Number Generator, Daniel R. L. Brown and Kristian Gjosteen, IACR ePrint 2007/048. To appear in CRYPTO 2007.
 Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator, Berry Schoenmakers and Andrey Sidorenko, IACR ePrint 2006/190.
 Efficient Pseudorandom Generators Based on the DDH Assumption, Reza Rezaeian Farashahi and Berry Schoenmakers and Andrey Sidorenko, IACR ePrint 2006/321.
 Analysis of the Linux Random Number Generator, Zvi Gutterman and Benny Pinkas and Tzachy Reinman.