Editing Pseudorandom number generator (section)

=={{Anchor|Cryptographically secure pseudorandom number generators}}Cryptographic PRNGs==
{{Main article|Cryptographically secure pseudorandom number generator}}
A PRNG suitable for [[cryptography|cryptographic]] applications is called a ''cryptographically-secure PRNG'' (CSPRNG). A requirement for a CSPRNG is that an adversary not knowing the seed has only [[negligible function|negligible]] [[advantage (cryptography)|advantage]] in distinguishing the generator's output sequence from a random sequence. In other words, while a PRNG is only required to pass certain statistical tests, a CSPRNG must pass all statistical tests that are restricted to [[polynomial time]] in the size of the seed. Though a proof of this property is beyond the current state of the art of [[computational complexity theory]], strong evidence may be provided by [[reduction (complexity)|reducing]] to the CSPRNG from a [[mathematical problem|problem]] that is assumed to be [[computational hardness assumption|hard]], such as [[integer factorization]].<ref>{{Cite book|title=Cryptanalytic Attacks on RSA|author=Song Y. Yan|date=7 December 2007 |publisher=Springer, 2007|page=73|isbn=978-0-387-48741-0}}</ref> In general, years of review may be required before an algorithm can be certified as a CSPRNG.

Some classes of CSPRNGs include the following:

* [[stream cipher]]s
* [[block cipher]]s running in [[counter mode|counter]]<ref>{{cite web|url=https://www.schneier.com/fortuna.pdf|title=Cryptography Engineering: Design Principles and Practical Applications, Chapter 9.4: The Generator|author1=[[Niels Ferguson]] |author2=[[Bruce Schneier]] |author3=Tadayoshi Kohno|year=2010}}</ref> or [[output feedback]] mode
* 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 (PRNG)|Fortuna]]
* combination PRNGs which attempt to combine several PRNG primitive algorithms with the goal of removing any detectable non-randomness
* special designs based on mathematical hardness assumptions: examples include the ''Micali–Schnorr generator'',<ref>{{cite web |url=https://www.staff.uni-mainz.de/pommeren/Cryptology/Bitstream/4_Perfect/ |title=IV.4 Perfect Random Generators |work=Cryptology |author=Klaus Pommerening |publisher=[[Johannes Gutenberg University of Mainz|uni-mainz.de]] |year=2016 |access-date=2017-11-12 }}</ref> [[Naor-Reingold Pseudorandom Function|Naor-Reingold pseudorandom function]] and the [[Blum Blum Shub]] algorithm, which provide a strong security proof (such algorithms are rather slow compared to traditional constructions, and impractical for many applications)
* generic PRNGs: while it has been shown that a (cryptographically) secure PRNG can be constructed generically from any [[one-way function]],<ref name="GoldreichLevinNotes">{{cite web | url=http://www.cs.cornell.edu/courses/cs687/2006fa/lectures/lecture11.pdf | title=Lecture 11: The Goldreich-Levin Theorem | work=COM S 687 Introduction to Cryptography | access-date=20 July 2016 | author=Pass, Rafael}}</ref> this generic construction is extremely slow in practice, so is mainly of theoretical interest.

It has been shown to be likely that the [[National Security Agency|NSA]] has inserted an asymmetric <!--[[kleptographic]]--> [[backdoor (computing)|backdoor]] into the [[NIST]]-certified pseudorandom number generator [[Dual_EC_DRBG]].<ref>{{cite web|url=http://blog.cryptographyengineering.com/2013/09/the-many-flaws-of-dualecdrbg.html|title=The Many Flaws of Dual_EC_DRBG|author=[[Matthew D. Green|Matthew Green]]|date=18 September 2013 }}</ref>

Most PRNG algorithms produce sequences that are [[uniform distribution (discrete)|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. In this setting, the distinguisher knows that either the known PRNG algorithm was used (but not the state with which it was initialized) or a truly random algorithm was used, and has to distinguish between the two.<ref>{{Cite book|last1=Katz|first1=Jonathan|last2=Yehuda|first2=Lindell|title=Introduction to modern cryptography|publisher=CRC press|date=2014|page=70}}</ref> 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 cipher]]s, 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.