Site Tools


random_numbers
no way to compare when less than two revisions

Differences

This shows you the differences between two versions of the page.


random_numbers [2007/02/17 18:33] (current) – created - external edit 127.0.0.1
Line 1: Line 1:
 +# $EPIC: random_numbers.txt,v 1.2 2007/02/17 18:33:25 jnelson Exp $
 +
 +======About pseudo-random numbers:======
 +Psuedo-random number generators (RNG) always have tension between three 
 +opposing forces:
 +  1) Entropy
 +  2) Coverage
 +  3) Repeatability
 +
 +=====Entropy:=====
 +Entropy is the tendancy of a RNG to avoid revealing what the next random
 +number is going to be.   Entropy can be roughly measured by asking this
 +question: If I see <N> numbers from the random number generator, can I guess
 +what the possible values of the <N+1>th value is?  As N grows increasingly
 +larger, does the possible values of N+1 grow increasingly smaller?
 +
 +High entropy can be imaged as deck of cards where you select a card, and
 +then re-shuffle the deck before you select the next card.  
 +
 +=====Coverage:=====
 +Coverage is the tendancy of an RNG to select each value approximately the
 +same number of times.  Coverage can be roughly measured by determining 
 +whether the selections-per-number is flat (more coverage) or bell shaped
 +(less coverage),
 +
 +High coverage can be imagined as a deck of cards where you select a card,
 +and then remove that card from the deck, until all the cards have been 
 +used, and then you re-shuffle.
 +
 +=====Repeatability:=====
 +Repeatability is the tendancy of an RNG to be able to generate the same 
 +values each time it is used.  Repeatability is determined by observation.
 +
 +Repeatability can be imagined as a deck of cards where the order is 
 +predetermined, and you select each card in order.
 +
 +=====Why are these forces in opposition?=====
 +Any psuedo-random number generator that uses an algorithm has to have a 
 +starting value ("seed").  Most RNGs are fully repeatable, given the same 
 +initial seed.  The quality of the entropy is therefore only as good as 
 +the secrecy of the seed. 
 +
 +Any psuedo-random number generator that uses a mathematical formula to
 +decide what the next value is, bases the next number in part on the previous
 +number.  The best
 +RNGs create values that are very very large (arc4random creates values 
 +[0..2^170]) and then give you only a few bits of that number.  This hides 
 +from the viewer what the number is, and hinders the calculation of the 
 +next number.
 +
 +Any psuedo-random number generator that uses an external data source does
 +not have to be seeded, but the quality of the entropy depends on the 
 +external source.
 +
 +======Enough blathering!  What about EPIC?======
 +The client has four random number generators:
 +
 +^ [[SET RANDOM_SOURCE]] ^ Type ^ Entropy ^ Coverage ^ Repeatability ^ Seeded ^
 +|  0  | /dev/urandom           | High    | Medium   | Low           | No     |
 +|  1  | Classic ircII RNG      | None    | High     | High          | Yes    |
 +|  2  | gettimeofday()         | Medium  | Low      | Low           | No     |
 +|  3  | Arc4random             | High    | Medium   | Low           | No     |
 +
 +=====Urandom:=====
 +The /dev/urandom RNG reads 32 bits from /dev/urandom and returns them to you.
 +This requires that the client hold open /dev/urandom, which will reduce the
 +number of file descriptors available.  If /dev/urandom is not available, 
 +this RNG falls back to the classic ircII RNG.  You cannot seed this RNG.
 +
 +=====Classic ircII:=====
 +This is the RNG used by all versions of ircII.  It is always available, and
 +it is fully portable across all ircII clients.  Based on a 32 bit seed, it
 +generates a 32 bit number and returns it.  Given one number, it is possible
 +to generate all the random numbers that succeed it.  This RNG must be seeded,
 +and is fully repeatable with the same seed.
 +
 +=====gettimeofday():=====
 +This is the RNG historically used by EPIC.  It is usually available on all
 +epic and bx clients.  It works by calling gettimeofday() twice in succession
 +and using the low 16 bits of each call to generate a 32 bit number.  Given
 +faster computers and faster syscalls these days than 10 years ago, this RNG
 +doesn't give very good coverage, but it's hard to predict the exact time.
 +You cannot seed this RNG.
 +
 +=====Arc4random:=====
 +This is the RNG currently recommended for all-purpose use.  This RNG generates
 +numbers between 0 and 2^170 and returns the lowest 32 bits.  Not knowing what
 +the high 138 bits are makes it unreasonably difficult to calculate the next
 +value, since it's understood that all 2^32 values are possible within the 
 +2^138 different paths.  The Arc4random RNG is auto-seeding from /dev/urandom
 +so it is not repeatable.
 +
 +======History:======
 +The classic ircII RNG first appeared in ircII.
 +The gettimeofday() RNG first appeared in EPIC3.
 +The /dev/urandom RNG first appeared in EPIC4pre2.001.
 +The arc4random RNG first appeared in EPIC4-1.1.8.
 +
  
random_numbers.txt · Last modified: 2007/02/17 18:33 by 127.0.0.1