This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate? Excessive Violence Sexual Content Political / Social
Email Address:
Article Id: WHEBN0000182249 Reproduction Date:
A cryptographically secure pseudo-random number generator (CSPRNG) or cryptographic pseudo-random number generator (CPRNG)^{[1]} 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:
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 comes 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.
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.
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.
Santha and Vazirani proved that several bit streams with weak randomness can be combined to produce a higher-quality quasi-random bit stream.^{[3]} Even earlier, John von Neumann proved that a simple algorithm can remove a considerable amount of the bias in any bit stream^{[4]} which should be applied to each bit stream before using any variation of the Santha-Vazirani design. The field is termed entropy extraction and is the subject of active research (e.g., N Nisan, S Safra, R Shaltiel, A Ta-Shma, C Umans, D Zuckerman).
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) special-purpose 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.
There are a number of practical PRNGs that have been designed to be cryptographically secure, including
Several CSPRNGs have been standardized. For example,
A good reference is maintained by NIST.
There are also standards for statistical testing of new CSPRNG designs:
The Guardian and The New York Times have reported that the National Security Agency (NSA) inserted a PRNG into NIST SP 800-90A 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^{[11]}^{[12]} that, as independent security experts long suspected,^{[13]} the NSA has been introducing weaknesses into CSPRNG standard 800-90; 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.^{[14]} RSA Security received a $10 million payment from the NSA to do so.^{[15]}
World War II, Steganography, Espionage, Internet, Germany
Principal investigator, Isoelectric point, Parental investment, Paternity Index, Phosphatidylinositol
Google, Apple Inc., Samsung Electronics, Microsoft Office, Sony
Computer science, Cryptography, Statistics, Data compression, Mathematics
Dice, Chaos theory, Gambling, Cryptography, Cryptographically secure pseudorandom number generator
Linux, Hardware random number generator, NetBSD, Cryptographically secure pseudorandom number generator, FreeBSD
Cryptographically secure pseudorandom number generator, Blum Blum Shub, Blum–Micali algorithm, CryptGenRandom, Dual EC DRBG
Modular arithmetic, Cryptography, Caesar cipher, Python (programming language), Php