| Cryptographically Secure Pseudo-random Number Generator |
Website Links For Secure |
Information AboutCryptographically Secure Pseudo-random Number Generator |
| CATEGORIES ABOUT CRYPTOGRAPHICALLY SECURE PSEUDORANDOM NUMBER GENERATOR | |
| cryptographic algorithms | |
| pseudorandom number generators | |
| cryptographically secure pseudorandom number generators | |
| cryptographic primitives | |
|
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 Pad s, 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. 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 their statistical properties are good (passing 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.
:: 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 next-bit test and thus be statistically random, as π appears to be a random sequence. (This would be guaranteed if pi is a Normal Number , for example.) However, this algorithm is not cryptographically secure; an attacker who determines which bit of pi (ie 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 . SOME BACKGROUND Santha and Vazirani proved that several bit streams with weak randomness can be combined to produce a higher-quality quasi-random bit stream. Even earlier, John Von Neumann proved that a simple algorithm can remove a considerable amount of the bias in any bit stream DESIGNS In the discussion below, CSPRNG designs are divided into three classes: 1) those based on block ciphers, 2) those based upon 'hard' mathematical problems, and 3) special-purpose designs. Designs based on cryptographic primitives
One design in this class is included in the ANSI X9.17 standard (''Financial Institution Key Management (wholesale)''), and has been adopted as a FIPS standard as well. It works as follows:
each time a random number is required:
It has been suggested that this algorithm would be improved by using AES instead of DES (Young and Yung, op cit, sect 3.5.1) Number theoretic designs
Special designs There are a number of practical PRNGs that have been designed to be cryptographically secure, including
STANDARDS 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:
EXTERNAL LINKS
|
|
|