Map Index Random Help Topics

## Topic: random number generation

topics > Group: mathematics

Group:
security

Topic:
encryption
Topic:
kinds of numbers
Topic:
randomness
Topic:
probabilistic and randomized algorithms
Topic:
sequence generators
Topic:
simulation
Topic:
statistics

#### Summary

Computers need random numbers for encryption, simulation, randomized algorithms, and identification.

True random numbers are difficult to generate. The basic approach is to build a pool of physically random data, and then manipulate that pool to remove biases and unanticapated correlations.

Pseudorandom numbers are generated. Given the random number seed, you can recreate the sequence. A random salt is a random number added to the input data. It increases the randomness of the input. Linear congruent generators are well understood. Generators may be combined. (cbb 6/06)

Subtopic: unique permanent IDs

 Quote: in a distributed environment need unique, permanent ids (128 bits) for all data [»giffDK7_1985, OK]

Subtopic: true random numbers

 Quote: for true random numbers on heavily used workstations, repeatedly set an alarm and increment until the interrupt occurs. [»lacyJB10_1993] Quote: how to extract random bits from an unknown, biased source [»mitzM4_2002] Quote: generate random data from the MD5 hash of an entry pool of timing measurements Quote: the Ferranti Mark I included a hardware random number generator; e.g., random walk probability [»turiA3_1951]

Subtopic: random sample and permutation generation

 Quote: optimal algorithm for generating random samples and permutations [»bentJ9_1987]

Subtopic: pseduorandom number generation

 Quote: efficient multiply-with-carry random number generators with maximal period; analyzed with b-adic numbers [»goreM10_2003] Quote: generates pseudorandom functions from a one-way function and a random string; indistinguishable from random functions in polynomial-time [»goldO10_1986] Quote: squaring mod a Blum-integer is a cryptographically strong pseudorandom bit generator [»goldO10_1986] Quote: a random number generator should allow multiple streams of random numbers; e.g., the minimal standard [»parkSK7_1993] Quote: describes a set of software tools for generating multiple sequences of random numbers; needed for simulation [»lecuP3_1991] Quote: combined Tausworthe random number generators can have a period of 10^18 [»tezuS4_1991] Quote: ISAAC is a fast pseudorandom number generator with very long cycle lengths, opaque internal state, and no detectable bias [»jenkRJ2_1996] Quote: software generation of secure, practically strong random numbers; no specialized hardware or privileged system calls [»gutmP1_1998]

Subtopic: problems with random number generators

 Quote: random number generators may be insecure; e.g. using current time and process ID as the seed [»gutmP1_1998] Quote: a random number generator should never leak its internal state; e.g., input or output data, system swap file, unreviewed code [»gutmP1_1998] Quote: 30 bit random numbers are repeated too quickly; multiple recursive generators give longer periods and good statistics [»lecuP10_1990]

Subtopic: linear congruent generators

 Quote: 48271 is a better multiplier for the minimal standard Lehmer random number generator [»parkSK7_1993] Quote: a = 16807 and m = 2^31-1 defines a good random number generator; exhaustively tested and well understood; also 48271 and 69621 [»parkSK10_1988] Quote: easy to compute the next number in a linear congruential sequence from preceding numbers; so not truly random [»goldO10_1986] Quote: exhaustive search for optimal multiplicative congruential random number generators with modulus 2^31-1 [»fishGS1_1986] Quote: implement multiplicative congruential generators with multipliers +- 2^a +- 2^b [»wuPC6_1997]

Subtopic: randoms in a programming language

 Quote: write a random number generator in SL5 as an environment that is resumed for each value [»hansDR5_1978] QuoteRef: simscrip_1971 ;;169 can specify attribute as producing random numbers

Subtopic: random seed

 Quote: for replicated trials, should reseed with the last random number; otherwise Lehmer generators may fail, especially for small seeds [»parkSK7_1993] Quote: prompt user for initial seed; for reproducibility, e.g., social security number [»parkSK10_1988]

Subtopic: random salt

 Quote: generate 128-bit salt from arc4random seeded from the kernel's entropy pool of current time and timing data [»provN6_1999] Quote: UNIX uses encrypted passwords that include a random number assigned by the system to the user [»morrR11_1979, OK] Quote: a Helix server provides 96-bit capabilities which encrypt access rights to an object with 40 bits padding [»fridM5_1985]

Related Topics

Group: security   (23 topics, 874 quotes)

Topic: encryption (45 items)
Topic: kinds of numbers (24 items)
Topic: randomness (20 items)
Topic: probabilistic and randomized algorithms (11 items)
Topic: sequence generators (16 items)
Topic: simulation (35 items)
Topic: statistics
(12 items)

Updated barberCB 3/06