random_numbers

# Differences

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

 — random_numbers [2007/02/17 18:33] (current) 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 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. +