Cryptographically secure random number generator

from Wikipedia, the free encyclopedia

A cryptographically secure random number generator (even cryptographically suitable random number generator, or English cryptographically secure pseudo-random number generator ( CSPRNG )) is a the cryptology suitable generator for pseudo-random numbers . Such random numbers are required in many areas of cryptology, such as:

The quality requirements for the randomness of such numbers are very different. For nonces it is sufficient to guarantee the uniqueness of the number in a random experiment, for the creation of a master key or even a one-time pad the requirements for the number are much higher. For example, a one-time pad is in theory only unbreakable when natural random numbers was created.

Basically, the same prerequisites are necessary for a CSPRNG as for a normal pseudo-random number generator, only that a few additional conditions must be met for security. On the one hand, the sequence of numbers it generates must not be distinguishable from a real random number sequence. On the other hand, it must not be possible to infer its internal state from the generator output, even if the exact functionality is known.

The BSI specifies requirements for random number generators for use in federal government projects in the technical guideline BSI TR-03116. Functional classes are differentiated and named there. The designations used (PTG.1, PTG2,… DRG.1, DRG.2,…, NTG.1) are listed in the mathematical-technical appendix. Essentially, physical RNG (PTG.) Are differentiated from deterministic RNG (DRG), with further subdivision according to error detection and stochastic post-processing and thus belong to the hybrid RNGs that do not represent any named classes in this definition.

Nondeterministic CSRNG

In the ideal case, the generation of random numbers is fed by a non- deterministic entropy source. This can be, for example, a hardware-based random generator or a hybrid generator . For cryptological applications, non-deterministic generators should be used, because only with these can it be guaranteed that they are neither reproducible nor predictable.

Deterministic CS (P) RNG

As a rule, the use of a nondeterministic generator is not possible or too slow. In this case, a deterministic, cryptologically secure pseudo-random number generator is used. Cryptologically secure pseudo random number generators are either based on a cryptographic primitive such as block or stream encryption or a secure hash function , or on mathematically hard problems.

Generators based on cryptographic primitives

An encryption or hash function can be operated in the so-called counter or output feedback mode . It is important here that it should not be possible to find out the initial state of the generator. Determining the internal state of the generator is then equivalent to breaking the encryption itself.

The number generated here is cryptologically secure and pseudo-random (as long as it guarantees the function used). Generators based on proven functions such as B.  AES or SHA-1 based, there are all common statistical tests for randomness.

Generators based on number theory problems

The security of the Blum-Blum-Shub generator is based on the assumption that the prime factorization of integers is a difficult problem that cannot be solved in polynomial time.

Random tests

This article or section needs to be revised. Details should be given on the talk page. Please help to improve it , and then remove this flag.

FIPS 140

A test suite for CSPRNG is listed in this standard. For this purpose, 20,000 output bits are subjected to various statistical tests:

Mason's Universal Test

The idea behind this test is that it shouldn't be possible to significantly compress a sequence of random numbers .

Marsaglia's Diehard test suite

Extensive test suite, u. a .:

Birthday Spacings Test
chooses random points on an interval. These should be Poisson distributed . The principle of the test is related to the birthday paradox .
Overlapping Permutations
examines five consecutive (integer) numbers for uniform distribution. These can have 5! = 120 different arrangements that are equally likely.
Binary Rank Test
creates random matrices from the bits of the sequence to be tested, calculates their ranks . A chi-square test is then applied.
Bitstream test (bit sequence test)
regards the sequence of numbers to be tested as bit sequences of 20-bit "words" that overlap. There are 2 21 overlapping 20-bit words and 2 20 possible 20-bit words. The test counts the missing 20-bit words. These should be approximately normally distributed .
Count-The-1s Test (Count the ones)
examines byte sequences. It counts the "1" bits in the byte sequences and compares the received values ​​with the statistically expected values.
Parking Lot Test
randomly places unit circles in a 100 × 100 square. A circle is considered successfully parked if there is no overlap with an already successfully parked circle. The number of successfully parked circles after n = 12000 attempts should be approximately normally distributed .
Minimum Distance Test
places n = 8000 points in a 10000 × 10000 point square. Then the smallest distance between the pairs of points is determined. The square of these distances should be exponentially distributed .
3D Spheres Test (3D Sphere Test)
places n = 4000 points in a cube with an edge length of 1000. Then a sphere is formed around each point. The radius of these spheres is the distance between the center and the closest point. The resulting spherical volumes should follow an exponential distribution .
Runs test
takes n balls from an urn with two different types of balls . Balls drawn one after the other of the same color are combined to form a run ("run"). The number of remaining moves should correspond to that of a real random drawing of the given length n.
Craps test
applies a test statistic to 200,000 craps games

Standards

Many designs of CSPRNGs have been standardized and are documented in:

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

See also

literature

  • Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: Handbook of Applied Cryptography. CRC Press, Boca Raton FL et al. a. 1997, ISBN 0-8493-8523-7 ( CRC Press Series on Discrete Mathematics and its Applications ), Chapter 5.

Web links

Individual evidence

  1. ^ Wolfgang Killmann, Werner Schindler: A proposal for: Functionality classes for random number generators. Version 2.0 Federal Office for Information Security (BSI), 2011. ( online )
  2. ↑ NIST 800-20 (PDF; 3.1 MB)
  3. ↑ Pierre L'Ecuyer, Richard Simard: TestU01 Paper
  4. ↑ National Institute of Standards and Technology (Ed.): Digital Signature Standard (DSS) (=  Federal Information Processing Standards . No. 186-2 ). 2000, Appendix 3. Random Number Generation for the DSA ( csrc.nist.gov ( Memento from May 18, 2009 in the Internet Archive ) [PDF]). Digital Signature Standard (DSS) ( Memento from May 18, 2009 in the Internet Archive )