June 12, 2001
Connoisseurs of Chaos Offer a Valuable Product: Randomness
By GEORGE JOHNSON
n
an age when most people seem obsessed with bringing order to their
lives — with Day- Timers, Palm Pilots, and even professional
anticlutter specialists to wrestle their closets and junk drawers into
line — a Web site in Switzerland has been offering a very different
service: providing the world with randomness.
Pay a visit to the home page of this purveyor of unpredictability, called Hotbits, and you will hear what sounds like the erratic clicking of a Geiger counter.
It is the sound of neutrons in a radioactive substance spewing out electrons and gamma rays as they decay. This decay is random, as guaranteed by laws of quantum mechanics, so by training a Geiger counter on a sample of krypton 85 and feeding the signal to a computer, Hotbits (www.fourmilab.ch /hotbits) generates a constant stream of random digits. Just fill out an electronic form, saying how many bits you want and they will be dispatched immediately over the Internet.
Or you may turn to one of Hotbits's rivals. Random.org generates
unpredictable sequences of data using a radio tuned between stations,
harvesting the atmospheric noise. Another operation, Lavarand (on the
Web at lavarand.sgi.com), produces random numbers by training digital
cameras on burbling lava lamps.
Perverse as all this may sound,
the connoisseurs of chaos are offering a valuable commodity. For
cryptography, game-playing, sociological surveys and various scientific
calculations, people often need series of numbers that are devoid of
pattern. And that is a tall order. Generating true randomness is one of
computer science's most difficult challenges.
"Computers are designed to be predictable," said Landon Curt Noll, a mathematician and cryptographer for SystemExperts, a computer security consulting firm. "If they do something we don't expect, we say they are broken."
After expending so much effort to squeeze whimsy and caprice from the circuitry, computer scientists must find ways to trick the electronic clockworks into simulating erratic behavior.
People might need
to generate secret passwords or lottery numbers, scramble sensitive
messages to protect them from eavesdroppers, or mimic the roll of dice
or the dealing of a poker hand.
Or they might need to perform
a scientific experiment. A sociologist or a statistician surveying a
random sample of the public, a biologist analyzing the mercurial spread
of a disease or the growth of a population, a psychologist studying
whether an avowed clairvoyant can guess the identities of hidden cards
with a success rate better than chance — all need random numbers to
calculate the uncertain outcomes of pro- cesses that can only be
described using probability.
"The world consists of the tension between order and chaos," said Gregory Chaitin, a mathematician at the I.B.M.
Before high-speed
digital computers were invented, mathematicians compiled tables of
random numbers by blindly flipping through phone books, casting dice,
spinning spinners or drawing cards from a hat. As automation came of
age, the RAND Corporation used a kind of electronic roulette wheel to
generate a classic work, published in 1955, called "A Million Random
Digits With 100,000 Normal Deviates." The seemingly oxymoronic term
"normal deviates" (random numbers whose occurrence can be plotted on a
bell-shaped curve) inspired the New York Public Library to shelve the
book in the psychology section.
RAND's herculean task took
years. After the wheel had spun off the numbers, at the rate of one per
second, they had to be sifted to expel some maddening regularities and
then stored on 20,000 I.B.M. punch cards (50 numbers per card). But
further scrutiny showed that some order still lingered. Certain digits
tended to appear more often than others. And so the numbers were
further scrambled (using a process called modular arithmetic) and then
printed out using a machine called a Cardatype.
"Because of the
very nature of the tables," the authors noted in the introduction, "it
did not seem necessary to proofread every page of the final manuscript
in order to catch random errors of the Cardatype."
But as
science's demand for random numbers continued to grow, even the longest
tables were quickly exhausted. A way was needed to produce torrents of
random numbers on the fly, and nothing could spit out digits faster
than a digital computer.
Therein lay the paradox: how to use order to generate disorder. The best that could be hoped for, it seemed, was pseudorandomness — numbers that, though produced by a completely deterministic and repeatable process, appear to be patternless.
The mathematician John Von Neumann suggested one of the first rather imperfect pseudorandom number generators — a simple procedure, or algorithm, called the middle square method. Arbitrarily pick a number — your cat's birthday, the license plate of the next car that drives by — and use it as a "seed." Square it and take the middle digits. Write down that number and then use it as the seed for the next round. Suppose you start with 357. That number squared is 127,449 and the middle digits are 2,744. Square that and extract the middle digits: 295. Repeat the process again and again: 702, 9280, 1184. So far, so good. But the next number that appears is 18, then 324, then 2, and there is nowhere to go from there.
Mathematicians have come up with far more reliable pseudorandom generators. The digits that come stuttering forth appear to be as patternless as raindrops on pavement or snow on a television set tuned to an empty channel. But even the best algorithms share the same weakness: the numbers are not really unpredictable. If you run the process long enough, the cycle of digits will eventually repeat — a pattern appears. Even worse, anyone with the same seed and algorithm can reproduce the sequence.
Often this
doesn't matter, but for applications like cryptography true randomness
can be crucial. An eavesdropper who can guess the seed of the "random"
number used to encode a message can break the cipher. To get a computer
to produce a genuinely unpredictable outcome, it must be opened up to
the outside world — buffeted by a stream of the randomness that courses
all around.
To build his Hotbits generator, John Walker, who founded the software company Autodesk
Near Zurich he maintains a kind of personal
computer-science exploratorium he calls Fourmilab. (The name means "ant
laboratory" in French, an allusion to Mr. Walker's interest in
artificial life, computer programs that strive to mimic living
creatures.) His Hotbits service receives about 300 requests a day for
its radioactively produced random numbers. Many are used in
parapsychology experiments, conducted in another corner of the
Fourmilab Web site, in which people try to use their mental powers to
alter the outcome of random events.
At Random.org, Mads Haahr,
a Ph.D. student in computer science at Trinity College in Dublin, has
been using radio static to generate random numbers since 1998 —
"23,383,506,944 random bits served so far!" the site recently boasted,
a tally updated by the hour. Clients include a Danish television
station that runs a computerized backgammon game on the Internet, an
Australian radio station that holds drawings to award prizes, and a
University of Florida anthropologist who picks random samplings of
informants for surveys.
Faced with a difficult decision, anyone
can go to the site and consult the automated coin-flipping program,
choosing between a Colombian 500-peso piece, an East Caribbean dollar,
a Luxembourgian Euro, or 18 other coins.
Hotbits and Random.org
exist mostly as educational diversions. They don't pour out random
numbers fast enough for such voracious demands as ultra high-security
cryptography. Several years ago, Mr. Noll and some colleagues at the
Silicon Graphics
A lava lamp is a chaotic
system, meaning that it is ruled by a phenomenon called "sensitive
dependence on initial conditions." The slightest variations in the
temperature, the distribution of the "lava," and many other variables
lead to wildly divergent patterns in the slow, burbling ballet.
Throwing in even more wild cards, Mr. Noll and his cohorts used six
lava lamps, each of a different color. The result was called Lavarand.
Every second a digital camera snapped an image of the fluctuating scene
converting the array of pixels into a string of bits.
This
stream of ones and zeroes still contained an undesirable amount of
predictability. The lava, after all, had to stay within the confines of
the six stationery lamps — it couldn't go jumping from one to another.
A red lava lamp couldn't randomly turn yellow or blue.
To weed
out the pockets of order, the scientists sent the signal through an
automatic number mangler called a hash function — a kind of distiller
of randomness. A tiny fluctuation in the algorithm's input — a subtle
variation in the brightness or hue of a single pixel — would cause the
output to wildly fluctuate. The result was a smaller, messier bit
string — call it Essence of Chaos. Finally these digits were used to
seed a heavy-duty pseudorandom generator called a Blum Blum Shub (after
its inventors, the computer scientists Lenore Blum, Manuel Blum and
Mike Shub.)
The ultimate outcome, the scientists confidently declared, was a truly irreproducible number. In case there was any doubt, they noted that there were yet other sources of unpredictability in the system: Tiny quantum fluctuations from the movement of subatomic particles would affect the behavior of the lava lamps, and the camera itself injected a silent roar of visual static.
In fact Mr. Noll and another Silicon Graphics researcher, Simon Cooper, discovered one day that, pretty as they were, the lava lamps were irrelevant. The system worked even better if they put a cap on the camera lens and simply fed the computer a stream of blind electronic noise. Using this as their source, Mr. Cooper and Mr. Noll are now working on an improved system called LavaRnd. (In the spirit of minimalism the final "a" was dropped from the name, allowing it, Mr. Noll said, to fit on a license plate.)
And so the quality of science's manufactured chaos
continues to improve, bringing its own kind of order. Mr. Haahr, the
keeper of Random .org, said that when he started his enterprise, he was
struck by the irony of deliberately dispensing randomness. "It was a
bit like selling sand in the desert," he said. "But it's not quite like
that because the noise you're getting from Random.org is pure in a way;
it's different from the hustling-bustling cacophony of the information
age. Producing anything that's pure, even noise, takes effort."
