DIY Random Number Generator

Compu486 writes "The guys over at Inventgeek have come up with a project and how artical on building a random number generator that is less than 100.00 utilizing radioactive decay. Using some Linux based open source apps and with a little ingenuity and some parts you probably have laying around your house you can build your own."

Typos

[fatwreckfan]

I think it should read:

and how to article on...

And I have to wonder...that is less than 100.00 what?

I did this in highschool

[Anonymous Coward]

I hooked up a geiger counter to an old school analog game port.

I had a simple C program that just spun between 0 and 255, and when a signal came across the game port it would record the current number.

run that through a hash function of your choice and it worked great.

dont cpus today have some noise generators built into them though?

Editors?

[AntsInMyPants]

I know the English may not be the submitter's first language, but it would be nice if the editors....um, you know....*edited* the piece so it made sense.

Michael (Who now sits back and waits for people to pounce on my spelling/grammatical mistakes)

Re:Here's the money graph

[Anonymous Coward]

Mersenne Twister plus any unknown piece of data as a seed is good enough at resisting everything our current understanding of mathematics

Isn't Blum-Blum-Shub still a better choice of algo for encryption?

I seem to remember

[npcompleat]

There was a study done that asked a group of people to come up with a string of random ones and zeros. Unsurprisingly, after statistical analysis, they weren't very good. But the fantastic bit was to ask another group to pair off and for each of them to try to outguess the other: let your opponent see your string of ones and zeros so far and then try to make the next bit the opposite to the one they are likely to pick. Amazingly, these random strings were impressively more random. Perhaps we've evolved special pseudo-random number generators to allow us to be sneaky.

[I know, a reference would have been nice, but age does terrible things to your internal bibtex database]

Another approach

[FlyByPC]

John Walker, of Autodesk fame, did a similar project [fourmilab.ch], although with a simpler count-the-clicks approach. I copied it using an off-the-shelf Geiger counter and a piece of Autunite; it works well.

Typically silly

[m.dillon]

Randomness exists in nature all over the place. In fact, in every single atom, simply because we are not living in a world that is anywhere near a temperature of absolute zero. A johnson noise generator costs a few cents. In analog electronics, keeping randomness *OUT* is actually the harder problem.

Frankly, you don't need all that much true randomness to generate random numbers. You just need to be able to continuously seed a CSPNG from a random source, and not even at a very high rate. A few bits a second is plenty.

Move along,

-Matt

We use /dev/urandom

[the_duke_of_hazzard]

It's good enough to have been passed by all the regulators and is used by our online gaming systems.

Re:More difficult Rnd() generator

[Anthem.uxp]

The Radioactive Boy Scout

http://www.dangerouslaboratories.org/radscout.html [dangerousl...tories.org]
http://en.wikipedia.org/wiki/David_Hahn [wikipedia.org]

Re:I did this in highschool

[MustardMan]

And if YOU knew a bit of just slightly more advanced physics, you'd realize that radiation obeys conservation of momentum, just like everything else. It's very very easy to demonstrate direct correlation between radiation spikes measured when the detectors are the same distance from a sample, but 180 degrees apart. I did this in a sophomore lab in college with some equipment that looked like it was older than I was.

Is radioactive decay really random?

[dpbsmith]

For the better part of a century, radioactive decay is what scientists always use when they want to invoke a natural process that is "random." But is radioactive decay really random... that is, are there, say, well-established quantum-mechanical equations that predict this? Or is it merely chaotic, or not known to be predictable... like the popping of kernels of popcorn in a microwave, or, for that matter, the spins of a roulette wheel?

Re:I did this in highschool

[Linker3000]

The Commodore 64 had an analogue white noise generator in the SID ship and its value could be read via a port. Simple.

A simple 1/ megabit/sec generator for cryptography

[smilindog2000]

I put together a simple random number generator in the late '90s using avalanche noise from the reverse break-down of a cheap transistor's emitter/base junction. I amplified it with a simple supply noise insensitive 4-transistor amplifier, and pushed it through an 8-bit 40 megabit/sec Analog Devices A/D converter. I xor-ed 80 samples together, while rotating bits in between samples. I used a $3 Lattice PLD to interface the board to an old PCs ISA bus.

I generated a CD full of random data, which anyone is willing to have if they want it. I've tested it against the "Die Hard" tests, and almost all the 10-meg files pass. There is one test that failed now and then, so I contacted the statistics professor who wrote it. I showed him that his own random number generator, thought to be nearly foolproof, failed the same test with the same probability. It seems I found a bug in his program!

Total cost for components is $10. Anyone who is interested can have schematics for free. Contact me at [e-mail].

The theory behind it is simple... who cares if the bits from the source are completely random? It turns out you just need a LITTLE true randomness from the source. By xoring bits together that have some randomness, you quickly approach truly random. By my estimate, only God would ever know the difference for the data I generated from perfectly random data, since the board could generate data for billions of years before accumulating even one bit of non-random data in it's output.

Mathematical proof:

Two semi-random bits b1 and b2 each contain small amounts of
non-random noise which we can call d1 and d2. Note that d1 and d2 can
be correlated, and usually are. The notation P(expression) means the
probability that the expression will be 1.

I define P(b1) and P(b2) as:

P(b1) = 0.5 + d1
P(b2) = 0.5 + d2

Both d1 and d2 have a range of -0.5 to 0.5. Xoring b1 and b2 together gives:

P(b1 ^ b2) = P(b1 & !b2) + P(!b1 & b2) = P(b1)*P(!b2) + P(!b1)*P(b2)
= (0.5 + d1)*(0.5 - d2) + (0.5 - d1)*(0.5 + d2)
= 0.25 - 0.5*d2 + 0.5*d1 - d1*d2 + 0.25 + 0.5*d2 - 0.5*d1 - d1*d2
= 0.5 - 2*d1*d2

Squaring a small number makes it very small indeed. If d1 and d2 are
already 0.01, then xoring b1 and b2 together results in a random bit
noise level 0.0002. This leads to the following equation for the
amount of non-random noise defined as n(bits) given the number of bits
in the xor sum:

n(1) = d
n(2) = 2*n(1)^2 = 2*d^2
n(4) = 2*n(2)^2 = 2*(2*d^2)^2 = 2^3*d^4
n(8) = 2*n(4)^2 = 2*(2^3*d^4)^2 = 2^7*d^8 ...
n(i) = 2^(i-1)*d^i = .5*2^i*d^i = .5*(2*d)^i

Here's how you can use this equation. Lets say you believe you have
non-random noise levels of no more than d. You want the noise level
to be less than N. We want to compute the number of bits needed, i:

N = n(i) = .5*(2*d)^i
2*N = (2*d)^i
log(2*N) = i*log(2*d)
i = log(2*N)/log(2*d)

So, for example, if you feel your non-randomness per bit is less than 10%,
but you need less than 1 part per billion, we compute the number of bits
needed in the xor-sum:

i = log(2*10^-9)/log(2*.1) = 12.5

In other words, just xor together at least 13 bits.

Re:I did this in highschool

[VanessaE]

The "random" generator in the C64, at least the one you refer to, was an all-digital shift-and-drop-bits algorithm used by the SID chip's three noise generators, and is accessed by reading the "voice 3 oscillator" register while voice 3 is set to produce noise (the audio from this voice can be silenced if desired, without affecting the algorithm). The algorithm cycles periodically and, if memory serves, can be reset manually if desired. There is no analog component to the noise generator algorithm.

A good way to get a nice random number is to take advantage of the inherent randomness of the user - initialize your noise generator to run continuously at a high iteration rate, wait for a keyboard, joystick, or mouse event, and then take as many samples from the noise generator as you need. The amount of time the noise generator was left actively running before the key/joy/mouse event will vary with the user's attention and reaction time, and will essentially randomize the values you get.