Home
Eruption - What is LavaRnd?
Obsidian - FAQ
Lava - Demos
Lavaologists - About us
Strata - New and old stuff
Magma - Download
Bedrock - Developers

LavaRnd process in detail

LavaRnd turns real world physical chaotic events into random numbers in 3 stages:
Stage 1: Digitization of a chaotic source
Stage 2: Chaotic to Random Transformation
Stage 3: Presentation

Stage 1: Digitization of a chaotic source

The LavaRnd reference implementation's chaotic source is the LavaCantm:

Close up image of a LavaCan   LavaCan on an Titanium PowerBook G4
LavaRnd LavaCan   LavaCan and friends *
A detailed discussion on the construction of a LavaCan is available.

At the heart of the LavaCan is a chip called the CCD. A CCD is the same chip found in cameras and webcams and is the device which transforms a captured image into digital data (pixels). The captured image consists of 19,200 pixels. Our LavaCan outputs images in a form known as the YUV420P palette where pixels are represented by Y luminance and well as U and V pseudo-colors.

We maximize the entropy of the chaotic source by tuning its settings after the LavaCan has been attached to the computer. When we set our webcam according to the LavaRnd pwc730 settings, we maximize the chaotic noise it produces. By turning the gain up and enclosing the CCD within the LavaCan, the pixels it produces consist mainly of digitized data measuring the background noise energy levels in a space completely devoid of light.

In the dark LavaCan environment, the U and V pseudo-colors are not very chaotic, because there is very little color in darkness. The Y luminance value is chaotic noise we will use to generate random numbers.

We can get a feel for what luminance data looks like by forming two types of images. One is a Grey scale image where the larger the luminance value, the whiter the pixel. The other is a color image where brighter and lighter pixels corresponds to brighter luminance values:

Webcam luminance data (2x magnification)
raw frame   false color frame
raw webcam frame   false color raw webcam frame

The images above were record on Sat May 23 02:32:20 2003 UTC.

The Grey scale image is good at showing overall patterns. The color image is good at showing differences between adjacent pixels. You will likely observe that the luminance data has some faint stripes as well as a lot of noise. This is because the CCD produces both chaotic and non-chaotic signals.

Stage 2: Chaotic to Random Transformation

The chaotic to random data transformation is performed by the Digital Blendertm which destroys the non-chaotic data and thus allows the chaotic data to dominate. The Digital Blender then a shuffle on the pixels by means of a 17-way turn.

Once the 17-way turn is complete, the LavaRnd Digital Blender performs 17 different SHA-1 cryptographic hash operations, and 17 different xor-rotate and fold operations. When their outputs are xor-ed and concatenated, 340 octets of random numbers are produced:

LavaRnd random numbers in image form (2x magnification)
Grey scale frame   false color frame
LavaRnd random output   false color LavaRnd random output

You will notice at the same magnification, the LavaRnd random output is much smaller than the luminance input. At the default alpha value of 1.0 there are about 56 octets of luminance pixel data consumed per random number octet produced.

For ease of viewing, the previous random number images are magnified:

LavaRnd random numbers in image form (16x magnification)
Grey scale frame   false color frame
LavaRnd random output   false color LavaRnd random output
LavaRnd random number as a decimal value
           196833694500421532179382622473332219872640073910301263160783180782999970574196147
25264451919802024035033543541426007758457528752532619837292467889445372137763435110700700246
59594451411046085581766321015811705824406209035522158586755566448931988028871743753775124445
42573518077346756920128517676668392119535083031920134324028395829549159101810471129270573100
72061176649620880822176402863809198768149712312381731310589072093441965487728442508575825967
88976228513948889674073510246826538303970589650996973082925069532292701721250083325215102240
04996846111978433783994562309750742873188954539513722467847190777959352265343379306519410125
31013562120874401937281066624941270484460855118140848483792582072273847150885830100982866409
58428778801204872118541035635361775686048031871089669033141924569214440300791073611436706653

Stage 3: Presentation

So, that's a pretty large random number. It's actually 817 digits long. Of course, many applications requiring the use of random numbers don't need a number quite this large. More often, what's needed is one or more random numbers in some particular form, for example:

  • Sum of two integers between 1 and 6 inclusive (simulating the roll of 2 six-sided dice)
  • a floating point number between 0 and 1 inclusive (simulating network load percentage in a test where optimal routing is desired)
  • a true/false value (simulating the flip of a coin and coming up with heads or tails)
  • a block of random data (to test a device's ability to respond appropriately to any input conditions - including invalid data)

Often times, application programmers are forced to map a random number returned by a random number generator into a range that is desired. This usually occurs when the random number generator provides random numbers in only one form other than that which is needed. If a programmer is not careful with his mapping function, he may destroy the uniform distribution of the numbers. An example:

An application needs the random number generator to provide a set of numbers simulating rolls of a die (e.g. 1 through 6). The vendor supplied random number generator generates 16 bit random numbers (e.g. in the range of 0 - 65,535). The programmer in an attempt to meet the roll die requirement divides the random number by 6 and uses the remainder to select one of 6 die faces.

What's went wrong here? The programmer has demonstrated a lack of understanding of the importance of maintaining uniform distribution e.g. his code has biased the roll of the dice. How? If you divide all possible 65,536 values by 6 and count the number of each remainder you'll find that 4 of the remainders occur slightly more often that the other 2; that is to say, that four die faces will appear more often than the last 2. While the bias may be small, how would you react if you knew that the electronic slot machine you were using in a casino was programmed in such a fashion?

This lack of understanding the importance of maintaining uniform distribution of random numbers in programs is well documented. Indeed, any accredited college level Computer Science curriculum provides a course which addresses the manipulation of numbers of all kind in a computing device. The terms "Numerical" and "Analysis" often appear in the title of such courses.

Rather than depending upon a programmer remembering the lessons learned in such a course, LavaRnd presents a number of different ways to provide random numbers to meet the requirements of an application. Choosing the appropriate LavaRnd interface to obtain random numbers can alleviate the loss of distribution uniformity of the random numbers being obtained.

LavaRnd interfaces provide access to random numbers in the following forms:

Type Length in bits Useful Constraints
Integers 8, 16, 32, and 64 (unconstrained)
0 <= n < ceiling
floor <= n < ceiling
floor <= n <= ceiling
Floating
Point
64 and 128 0 <= n < 1
0 <= n <= 1
floor <= n < ceiling
floor <= n <= ceiling
true/false 1 (none)
buffer of data any number of octets (none)

What is next?

* - Shine your light over here!

SourceForge.net Logo
Home  |   LavaRnd?  |   FAQ  |   Demos  |   About us  |   New & Old  |   Download  |   Developers  |   Tour