Random Numbers

We think of random numbers as being somehow arbitrary and unknowable in advance. Mathematically, a given string of numbers is random if there is no shorter way to express the string than the string itself. Thus, any sequence of numbers produced by a calculation or a formula can't be truly random.



Another way to think of this is that a string is random if you can't compress it. This definition excludes pi (3.14 . . . ) because a computer can reproduce a few billion digits of pi by applying a very short formula: a circle's circumference divided by its diameter. Thus, you can compress a billion digits into a short, simple formula: C/d. Unfortunately, just because you can't find a program that can compress a given sequence doesn't mean that there isn't one that someone may discover next month.

Intuitively, we equate randomness with a lack of discernible patterns, but even this isn't enough, because random processes will sometimes produce short sequences that appear to be nonrandom.

We care about random numbers because they are very useful in statistical applications, in testing procedures and software, and most especially in cryptography.

The only truly unbeatable cryptographic system uses what's called a one-time pad: a string of random numbers or letters used as a key to encode a message through some kind of transformation. If the pad is used only once and is truly random, it can never be broken. Use the same pad twice, however, and it's no longer unbreakable - at least in theory.

How to Make a Random Number

During World War II, British code clerks created random numbers for one-time pads using a method akin to that used for drawing numbers for a bingo game or lottery today - by drawing them out of a hat or a machine that scrambles their order.

That method worked but was slow and labor-intensive. Today, we use software programs called pseudorandom number generators that take an input value and perform a series of transformations and procedures. The input value must be truly random and is normally based on some unpredictable real-world event.

Several physical processes can be used to create random numbers. One method uses radioactive decay, which current physical theory assumes to be random. HotBits, an Internet resource, generates random numbers by timing successive particle pairs in radioactive decay detected by a Geiger-Muller tube.

Since 1999, Intel Corp. has supplied a hardware-based random number generator for use with its 8xx series of CPU support chip sets. Implemented in the Intel 82802 Firmware Hub Device, the generator uses thermal noise from a resistor to produce a random, nondeterministic and nonrepeating stream of bits.

Perhaps the oddest source for random numbers is lava lamps - yes, lava lamps, those lit-from-below, tapered glass bulbs with colored blobs of moving liquid that were popular in the 1960s and 1970s. Their use for random numbers was devised by researchers Robert G. Mende Jr., Landon Curt Noll and Sanjeev Sisodiya at Silicon Graphics Inc. in Mountain View, Calif., and was dubbed "lavarand." Noll and his colleagues decided that the unpredictably rising and falling blobs in a lava lamp would make a convenient source of randomness. Their process for generating random numbers is as follows:

A digital camera periodically photographs a set of six lava lamps, adding its own electronic noise to the data. The 921,600 bytes of the original image are compressed and scrambled into a 140-byte packet, which then serves as the seed value for a software-based pseudorandom number generator. "While any good chaotic source could be used, we favor lava lamps, in part because they are cool," the researchers say.

The importance of genuinely random seeds is illustrated in "Generating a Truly Random Number" (http://cobolreport.com/columnists/leif/), a report by Leif Svalgaard. He notes that "as the World Wide Web was gaining broad public appeal, the need for secure transmittal of payment information (such as credit card numbers) became evident. Netscape Communications Corp.'s browser began to use the Secure Sockets Layer (SSL) for such transactions. Basically, SSL protects communications by encrypting messages with a secret key - a large, random number."

SSL security depends entirely on the unpredictability of that number, but in 1995, two researchers found that the Netscape browser was generating its random numbers using just the time of day and the identification numbers of the process and its parent process. They then cracked the code in less than a minute.

Read accompanying stories:

See additional Computerworld QuickStudies


Copyright © 2002 IDG Communications, Inc.

Bing’s AI chatbot came to work for me. I had to fire it.
Shop Tech Products at Amazon