Slashdot Mirror
LavaRnd: A Open Source Project for Truly Random Numbers
Phil Windley writes "Truly random numbers are crucial to good encryption.
Most people have heard of Silicon Graphic's use of Lava Lamps to generate random numbers. There were some problems: it required special SGI hardware and software along with six lava lamps, and the solution wasn't portable. But the biggest drawback was that SGI patented the idea so it wasn't freely available. Now, some of the scientists behind the SGI random number system have create LavaRnd, an open source project for creating truly random numbers using inexpensive cameras, open source code, and inexpensive hardware. The system uses a saturated CCD in a light-tight can as a chaotic source to produce the seed. Software processes the result into truly random numbers in a variety of formats. The result is a random number that is crytographically sound, ranking at the top of its class in the NIST 800-22 Billion bit test. Its even portable, so the truly paranoid can take it with them when they travel."
Site's already /.'ed.
You can nab the code off sourceforge though:
http://sourceforge.net/projects/lavarnd
Unless the random-number generator is built outside of our Universe, it can't generate truly random numbers. Only pseudo-random ones. As it stands, there will always be something influencing the result. Fortunately for us, pseudo-random numbers are impossible to differentiate from random ones and are random enough to serve our purposes anyway.
Support the First Amendment. Read at -1
The Apple ][ computers used the pause between keystrokes, measured much more precisely than necessary and disregarding all but the last 8 bits, as an attempt at an analog random number seed for their psuedorandom number generator. Very simple and effective and I haven't seen many implementations of better systems around. One side effect was that if you had a program which ran off the boot disk with no keystrokes, it would do the same thing every time, no matter how improbable that was...
It's psychosomatic. You need a lobotomy. I'll get a saw.
You are correct that white noise can produce appropriately random numbers.
The problem is that for encryption purposes you may need some huge random numbers. If you want to do that from an analog solution you'll have to take your samples closer and closer together, until the numbers become less random. If you start sampling sound 1 million times a second, any two values next to each other my be really close and actually predictable.
t
Because sound is not random at all. White noise is, but how often do you hear that? Not often. Voices, cars driving by, phones ringing, all of these are patterns. Patterns lead to cracks in the numbers that can be culled for weaknesses in the algorithm. This in turn leads to knowledge of what algorithm is being used, which in turn leads to a directed cryptanalysis of the data, exactly what true random numbers are meant to avoid.
Even using mouse clicks, keystroke times, etc. is not random. Thats why its called "pseudo-random". Processing normal everyday sound through a PRNG (pseudo random number generator) is still only pseudo, not real.
People have been working on this problem for decades. Trust me, what you are asking about has not only been tried, but been used and even attacked.
Where to begin... For starters, the double slit experiment, to see the neat effects of single electron interference, must be done in a vacuum. The electorns must not be influenced by anything else at all, like air/gas molecules. Also, it must be done at temperatures near absolute zero, where the thermal bath of the environment doesn't wash out the quantum effect you are talking about... Just not possible on a portable system...
The original motivation for random number generators was simulation. One of the early mainframes, and I am afraid I forget which one, included a true random number generator. It was an unexpected disaster, totally unusable for simulation and other then-state-of-the-art users of random numbers. They were "too random".
It turns out that for an experiment to be useful it need to be repeatable. Thus, it was critical that users be able to repeat the sequence of "random" numbers. Thus the reason why all random number mechanisms permit you to set the seed... otherwise they could just use a sufficiently random seed and life would be good.
Another aspect of random number is that they must not only be "random", but they need to have a well defined distribution over the range of possible values. You might assume it is desirable to have a linear distribution, which IS useful in some settings, but other distributions ("bell curve", and exponential come to mind) are also extremely useful.
IF one has a real need for truly random numbers, the source for those number does need to perform to a certain distribution over the range of possible values. And it can not be used to the exclusion of the existing techniques which have been extremely useful in their intended problem domains. This is really just another case of a good solution in one problem domain being used in another without its underlying foundation being examined for applicability to that new problem domain.
You don't understand what is meant by "uniformly distributed." Say you have a uniform random variable taking on the values 1..10. A "uniform random variable" means that each possible outcome has an equal probability of occurring. It doesn't mean that there must necessarily be equal numbers of 1,2,3,4, etc. in the output.
Imagine the previous random source generating two sequences. The first is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. The second sequence is [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]. How much less likely is it to generate the second sequence than the first one? The answer is, it is no less likely. Both sequences are equally likely. This is the meaning of a "uniform source." It certainly doesn't mean that sequences such as [1, 1, 1, ...] cannot occur!
9 out of 10 people would probably say all 0's or all 1's isn't a random result, even when it comes from a random source.
They probably would say that, but they'd be wrong. People have major misconceptions about randomness. If a random source generates the sequence [1, 6, 3, 3, 8, 2] people will say "Ho hum." If the same source outputs [1, 2, 3, 4, 5, 6] people all of a sudden get interested and say "I wonder what's going on." There's nothing going on. The random source doesn't care whether your brain wants to ascribe some special meaning to the sequence [1, 2, 3, 4, 5, 6]; it generated it mindlessly, and your human tendency to pick out patterns has kicked in. You are imposing your own order on it, when no real order exists.
> What always bothers me is when people want uniformly distributed random numbers. I know why its valuable but if you make sure that your numbers are uniformly distributed they aren't really random anymore.
Sure they are. There's a difference between "randomness" and "distribution". You could have random numbers with a uniform distribution, a gaussian distribution, an exponential distribution, some bimodal distribution, etc., and they would still be random.
But it's really convenient to have a RNG with a uniform distribution, since you can easily transform numbers drawn from that distribution to some other arbitrary distribution by taking f(x) with the desired f() and an x drawn from the uniform distribution.
BTW, "uniform distribution" doesn't mean that you get the same number of occurences of each number in the range; it only means they have the same probability of occuring. (OK, that distinction gets a bit tricky when you're talking about pseudo-random numbers, but let's pretend we're talking about genuinely random numbers.)
> Its just as likely to get all 0's or all 1's as it is to get any other single random number and yet 9 out of 10 people would probably say all 0's or all 1's isn't a random result, even when it comes from a random source.
Yeah, but that's because we intellectually identify those numbers as "special", when they aren't really. For instance, people would probably think the numeric representation of their birthdate was special, though someone else might think it a perfectly random number. Strictly speaking, randomness has nothing to do with the importance humans assign to the result.
> I guess the big misunderstanding is that once you have a number, its not random, you know what it is.
Yes, the a posteriori probability of an event, given that the even happened, is always one. Pseudoscientists are fond of constructing probability arguments that they think should be convincing, not realizing that they are just painting a bull's-eye around wherever the arrow happened to strike.
> A random pattern is probably better defined as one you can't predict, and once you have it, recreating it with the same process is not likely.
For most uses we would want to say that "you can't predict" means that all possible patterns are equally likely, i.e. that betting on one has the same expected pay-off as betting on any other, at least if we're talking about a uniform distribution. And as for re-creation, we usually want sequentially generated patterns to be independent, i.e. that knowing what has been produced in the past does not help you predict what's coming up next. In particular, if your generator produced pattern z last time, the probability of producing z next time is still the same as the probability of producing any other pattern.
Any time there is a preferred way to bet, whether considering the past or not, it means that your generator is biased in ways that you probably don't want for a basic RNG. If you want biases, introduce them by filtering the number produced by a RNG with a uniform distribution.
Sheesh, evil *and* a jerk. -- Jade
> audio circuits often use diode junctions in reverse-breakdown mode as a source of "white noise". couldn't we computer folks do the same? seems a similar idea to the the dark CCD technique.
I think there are already a lot of solid-state solutions out there that use thermal noise to generate random bits. The lava-lamp solution and its derivatives sound like a lot of fun geeky fooling-around, but ultimately seem to be a solution in search of a niche.
Sheesh, evil *and* a jerk. -- Jade