Random number form the basis for the security of many cryptographic primitives.

RNG:
  Generate bits (R_n) where
  P(R_n = 0) = .5
  and
  P(R_n = 0 | R_0, R_1, ... R_n-1) = .5

This condition is required to have a full bit of information entropy per output bit:
H(X) = - Summ(1 to n)(p_i * lg(p_i)
with no mutual information:
 I(R_n ; R_0... R_n-1) = H(R_n) - H(R_n | R_0, R_1... R_n-1) = 0

 Based on sampling some physical source of true randomness.  (none approved, but NIST has said they might, eventually)

Random vs Statistically Random vs Cryptographically random

several requirements for 'success':
  An attacker can't distinguish between an RNG stream and the PRNG stream (generally or in poly time)

  An attacker can't guess the future output, even given previous output.

PRNG (DRNG):
  Purpose:  To look like a RNG (have the same properties), but without the randomness.

 F(staten) = Rn
staten+1 = G(state_n, Rn)

How does this work from the information theory point of view?

Pitfalls:
 If attacker can guess state, they can get all future (and sometimes past) values.
     Cryptographic primitives are used to form one way functions to make this hard
 If state hits previous value, it loop:
   see birthday attack...

 OK, so how do we fix these problems?  Add more information: 
  seed the generator while running, using non-guessable info.  (hmmmm... RNG?)

Helps with both problems:
  Loops are short lived.  (depending on re-seeding interval)
  Attacker can't get past values, and must guess seeding info.

Engineering problems:
  How to estimate the seeded entropy?  (and how to get it)
  Seed keys compromised
  Attack on the cryptographic primitives
  Side channel analysis could leak state
  Chosen input to a PRNG

Once failure occurs, what happens?
  If no reseeding, the failure is permanent.
  Attacker may be able to attempt to forward guess re-seeds, if they are low entropy.  (consequence: reseed with large entropy chunks)
  With some generators, some parts of the state are invariant, and are therefore permanently compromised.

X9.17
(see diagram)

Note that a normal implementation does not allow for user seeding: entropy is gathered from a clock.

Note that it is unclear how often the PRNG is seeded from the clock.

Note that this generator's state does not change completely:
 Key (static): 112 bits to 168 bits
 Other state: 64 bits.

Could possibly seed by XORing clock with random seed or XORing past state with current state.  Note: User input should be processed (hashed / DES encrypted) to prevent an attacker from having too much control over the internal state.

FIPS 186-2 (revised)
(see diagram)

Allows for user input.  This seeds the generator.

If the attacker can dictate the user supplied seed, they can cause the PRNG to output the same value continuously.

Notes:
State size varies from 160 to 512 bits (for SHA based G function).  Use a larger state size for greater security.

Seed in large (unguessable) entropy blocks.
Hash the seed to prevent an attacker from causing the generator to repeat.

All state information is influenced by past state and user-provided entropy.

Note that sha based G function requires 1 SHA (like) operation, whereas DES based G function requires 5 DES operations.