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. A pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers, the elements of which are approximately independent of each other. ... The German Lorenz cipher machine, used in World War II for encryption of high-level messages. ...

Many aspects of cryptography require random numbers, for example: // About Bees This article is about completely random and illogical things. ...

• 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 perfect secrecy only holds if the key material is obtained from a true random source with high entropy. Key generation is the process of generating keys for cryptography. ... Nonce means for the present time or for a single occasion or purpose, although the word is not often found in general use. ... In data encryption, salt is an initialization vector of a block cipher. ... Elliptic Curve DSA (EC-DSA) is a variant of the Digital Signature Algorithm which operates on elliptic curve groups. ... Excerpt from a one-time pad. ... Look up Protocol in Wiktionary, the free dictionary Protocol is a set of guidelines for use in various circumstances. ... A key is a piece of information that controls the operation of a cryptography algorithm. ... Entropy of a Bernoulli trial as a function of success probability. ... Excerpt from a one-time pad. ... To meet Wikipedias quality standards, this article or section may require cleanup. ...

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 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. In computing, a hardware random number generator is an apparatus that generates random numbers from a physical process. ...

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. The operation of A5/1, a LFSR-based stream cipher used to encrypt mobile phone conversations. ... A cryptosystem (or cryptographic system) is the package of all procedures, protocols, cryptographic algorithms and instructions used for encoding and decoding messages using cryptography. ...

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 (eg, passing statistical randomness tests), second, that they hold up well under serious attack, even when (part of) their state (initial or running) becomes available to an attacker.

• Every CSPRNG should satisfy the "next-bit test". The next-bit test is the following: Given the first k bits of a random sequence there is no polynomial-time algorithm that can predict the (k+1)th bit with probability of success higher than 1/2. Andrew Yao proved in 1982 that a generator passing the next-bit test will pass all other polynomial-time statistical tests for randomness.

• Every CSPRNG should withstand 'state compromise extensions'. That is, in the unfortunate case 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. Also, if there is an entropy input while running, it should be infeasible (ie, very very hard) to use knowledge of the state to predict future conditions of the CSPRNG state.

Example: If the CSPRNG under consideration produces output by computing some function of the next digit of π, it may well be random, as π appears to be a random sequence (at least no patterns of any kind have been found). However, this does not satisfy the next-bit test, and thus is not cryptographically secure. There exist algorithms that will predict the next bit; examples include looking up digits or computing them ad hoc.

Most PRNGs are not suitable for use as CSPRNGs and will fail on both counts. First, whilst they appear random to assorted statistical tests, they do not resist determined reverse engineering. That is a specialized statistical test 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 future random numbers can be predicted. Andrew Chi-Chih Yao (Chinese: 姚期智; Hanyu Pinyin: ) (born December 24, 1946) is a prominent computer scientist. ... 1982 (MCMLXXXII) was a common year starting on Friday of the Gregorian calendar. ... Lower-case π (the lower case letter is usually used for the constant) The mathematical constant π is an irrational number, approximately equal to 3. ...

CSPRNGs are designed explicitly to resist this type of cryptanalysis, and if well done, actually do so. Cryptanalysis (from the Greek kryptós, hidden, and analýein, to loosen or to untie) is the study of methods for obtaining the meaning of encrypted information, without access to the secret information which is normally required to do so. ...

Some background

Santha and Vazirani (M Santha and UV Vazirani, Generating quasi-random sequences from slightly-random sources, Proc 25th IEEE Symp on foundations of Comp Sci, 434-440, IEEE, 1984) 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 (J v Neumann, Various techniques for use in connection with random digits, Collected Works, vol 5, pg 768-770, Pergamon, 1963) 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 (eg, N Nisan, S Safra, R Shaltiel, A Ta-Shma, C Umans, D Zuckerman). John von Neumann in the 1940s. ...

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

• 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 zero, then encrypting a 1, then encrypting a 2, etc. The counter can also be started at an arbitrary number other than zero. Obviously, the period will be 2ⁿ for an n-bit block cipher; equally obviously, the initial values (ie, key and "plaintext") must not become known to an attacker lest, however good this CSPRNG construction might be otherwise, all security be lost.

• A cryptographically secure hash of a counter might also act as a good CSPRNG in some cases. In this case, it is necessary that the initial value of this counter is random and secret. If the counter is a bignum, then the CSPRNG could have an infinite period. However, there has been little study of these algorithms for use in this manner, and at least some authors warn against this use (Young and Yung, Malicious Cryptography, Wiley, 2004, sect 3.2).

• Most stream ciphers work by generating a pseudorandom stream of bits that are combined (almost always XORed) with the plaintext; this stream can sometimes be used as a good CSPRNG (though not always: see RC4 cipher).

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: Encryption Decryption In cryptography, a block cipher is a symmetric key cipher which operates on fixed-length groups of bits, termed blocks, with an unvarying transformation. ... In cryptography, a block cipher operates on blocks of fixed length, often 64 or 128 bits. ... // About Bees This article is about completely random and illogical things. ... A key is a piece of information that controls the operation of a cryptography algorithm. ... The plain text term has a different meaning. ... In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make it suitable for use as a primitive in various information security applications, such as authentication and message integrity. ... A bignum package in a computer or program allows internal representation of very large integers, rational numbers, decimal numbers, or floating-point numbers (limitted only by available memory), and provides a set of arithmetic operations on such numbers. ... The operation of A5/1, a LFSR-based stream cipher used to encrypt mobile phone conversations. ... The plain text term has a different meaning. ... For the Vietnam road named RC4, see Route Coloniale 4. ... The American National Standards Institute (ANSI) is a private, non-profit standards organization that produces industrial standards in the United States. ... FIPS could mean Federal Information Processing Standard, publicly announced standards developed by the U.S. Federal government. ...

• input: Date/time information D (in the maximum resolution available), a 64 bit random seed s, and a DES EDE key k.
• compute: I = DES_k (D)
• output: Each time a random number is required, output x=DES_k(I xor s), and update the seed s to DES_k(x xor I)

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) AES is a three-letter abbreviation with multiple meanings, as described below: Aeromedical Evacuation Squadron, a unit in the U.S. Air Force tasked with transporting injured military members by means of fixed-wing aircraft. ... Look up Des and des in Wiktionary, the free dictionary. ...

Number theoretic designs

• Blum Blum Shub has a strong, though conditional, security proof, based on the difficulty of integer factorization. However, implementations are slow compared to some other designs.

Blum Blum Shub (BBS) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et al, 1986). ... In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ...

Special designs

There are PRNGs that have been designed to be cryptographically secure.

• the Yarrow algorithm which attempts to evaluate the entropic quality of its inputs, and an updated version, Fortuna, which does not
• ISAAC based on a variant of the RC4 cipher
• Microsoft's Cryptographic Application Programming Interface function CryptGenRandom; all Microsoft-provided cryptography, though, shares the same PRNG implementation, an internal function called RtlGenRandom. RtlGenRandom, which is documented as follows:

[RtlGenRandom] generates as specified in FIPS 186-2 appendix 3.1 with SHA-1 as the G function. And with entropy from: The Yarrow algorithm is a cryptographically secure pseudo-random number generator. ... Fortuna is a cryptographically secure pseudo-random number generator (PRNG) devised by Bruce Schneier and Niels Ferguson. ... ISAAC is a pseudorandom number generator designed by Bob Jenkins (1996) to be cryptographically secure. ... For the Vietnam road named RC4, see Route Coloniale 4. ... Microsoft Corporation (NASDAQ: MSFT, HKSE: 4338) is an international computer technology corporation with 2005 global annual sales of US$39. ... Also known as the Microsoft CAPI... It is the Microsoft standard interface for use by Microsoft operating systems and the software running on them to complete cryptographic operations. ...

• The current process ID (GetCurrentProcessID).
• The current thread ID (GetCurrentThreadID).
• The tick count since boot time (GetTickCount).
• The current time (GetLocalTime).
• Various high-precision performance counters (QueryPerformanceCounter).
• An MD4 hash of the user's environment block, which includes username, computer name, and search path. MD4 is a hashing algorithm that creates a 128-bit message digest from input data to verify data integrity.
• High-precision internal CPU counters, such as RDTSC, RDMSR, RDPMC [omitted: long lists of low-level system information fields and performance counters]

Source: Writing Secure Code, Second Edition. ISBN 0-7356-1722-8.

There are some difficulties with the Microsoft design in that MD4 has been broken (H Dobbertin, Alf Swindles Ann, CryptoBytes(3)1, Fall 1995), and there is very little work supporting SHA-1 as an adequate entropy extraction algorithm. In addition, several of the entropy values used can be found by examining operating system state (eg, by a virus or Trojan) and some can be determined externally (eg, duration since boot), thus reducing the actual entropy used by the function. MD4 is a message digest algorithm (the fourth in a series) designed by Professor Ronald Rivest of MIT in 1990. ... Orders A virus is a submicroscopic particle that can infect the cells of a biological organism. ...

Standards

Several CSPRNGs have been standardized. For example,

• FIPS 186-2
• ANSI X9.17-1985 Appendix C
• ANSI X9.31-1998 Appendix A.2.4
• ANSI X9.62-1998 Annex A.4

A good reference is maintained by NIST. As a non-regulatory agency of the United States Department of Commerce’s Technology Administration, the National Institute of Standards (NIST) develops and promotes measurement, standards, and technology to enhance productivity, facilitate trade, and improve the quality of life. ...

There are also standards for statistical testing of new CSPRNG designs:

• A Statistical Test Suite for Random and Pseudorandom Number Generators, NIST Special Publication 800-22.

Wikibooks has more about this subject:

Cryptography:Random number generation

Image File history File links Wikibooks-logo-en. ...

External links

• Java "entropy pool" for cryptographically-secure unpredictable random numbers.
• Cryptographically Secure Random number on Windows without using CryptoAPI