Generating random numbers from white noise

Even though rand() may be a good enough random number generator for making a video game, the patterns of random bits it spits out may not be sufficient for applications requiring truly random data. [Giorgio] built his own random number generator, and after many statistical tests it ended up being random enough for a few very complex calculations.

Previously, we saw [Giorgio] generate random numbers with a Chua circuit, but for all the complexity of building an electronic strange attractor there’s actually a much simpler source of random data: a white noise generator.

[Giorgio]‘s random number generator for this project is just a pair of resistors, with an op-amp buffer, amplifier, and current switch to turn analog data into a digital output of random 1s and 0s. [Giorgio] sampled this data by plugging the digital out into one of the GPIO pins of a Raspberry Pi and recording the data with s small script.

To verify his sequence of bits was actually random, [Giorgio] performed a few tests on the data, some more reliable in determining randomness than others.

Because every project needs a few awesome visualizations, [Giorgio] plotted each sequence of bits as either a black or white pixel in a bitmap. The resulting image certainly looks like television static, so there are no obvious problems with the data.

[Giorgio] also performed an interesting Monte Carlo simulation with his megabytes of random data: By plotting points on a plane (with a range from 0,0 to 1,1), [Giorgio] can approximate the value of π by testing if a point is inside a circle with a radius of 1. The best approximation of pi using 10,000 points of random data came out to be 3.1436

Of course [Giorgio] put his random data through a few proper statistical tests such as rngtest and dieharder, passing all the tests of randomness with flying colors. An interesting build that shows a small glimpse of how hard generating really random numbers actually is.

Comments

  1. ZombieLinux says:

    That comes out to just about 2098baud for creating random bits. I have to wonder if you would be better off tuning a ham radio or just using an audio output from an old crystal radio tuned to the empty spectrum. Wouldn’t that create the same effect using the existing background radiation?

    • Mike says:

      a low bit rate true random number generator is normally paired with a pseudorandom number generator in what is called a “randomness extractor”,this combines the speed of the pseudorandom number generator with the randomness of a true random number generator.

      The simplest method of doing this is to just XOR the pseudo random number with the latest true random number. Even if the true random number does not change as often, the fact that it changes unpredictably means that normal methods of attacking PRNG are made extremely difficult.

    • WA says:

      An avalanche noise source such as this can be sampled at much higher speed than was done here. That was almost certainly a limitation of the A2D (and computer hardware) used.

      The upper limit in speed is dictated by the bandwidth of the noise source.

      I have easily obtained twice this generation rate (with considerably more in process whitening) on a simple arduino.

      Avalanche TRNG with AVR

  2. krylenko says:

    The problem with radio noise is it’s generally very far from random, even if it sounds like white noise – there are just too many human-generated events in the radio spectrum. You’d have to perform at least as much whitening as Giorgio did, which would slow down the output rate.

    Plus you’d have the significant downside of possibly having a radio signal drift into tune while tuned to an “empty” channel.

    For the article itself, it’s two DIODES that produce the initial white noise, not two resistors.

  3. B says:

    You can also just crank the gain up on your sound card…you don’t even need a microphone connected, probably. The electrical noise, especially in a busy server room, will provide plenty of randomness.

  4. Mike says:

    UAirLtd wrote a great post on the Hackaday forums a few weeks ago, detailing a lot of the stuff here: http://forums.hackaday.com/viewtopic.php?f=2&t=2428 including reference to Die Harder and visual representation of numbers.

    I wonder if Giorgio did his project after reading the Hackaday forum, if he did, it wouldn’t have been the first time that Hackaday forum shows itself to be a valuable resource.

  5. WA says:

    This blog really doesn’t pay much attention to details…

    This generator is not based upon thermal noise in resistors, but rather the avalanche noise in a p-n junction semiconductor…

  6. h_2_o says:

    I had a math professor write a theses on this subject. His conclusion was very different than what is being described here, he was able to show clearly that noise, is not random. I will try and dig up his paper because for this type of application it was a good read, otherwise it is good insomnia material.

    • WA says:

      Either you (or the professor) are mistaken or more likely you are simply misunderstanding his thesis.

      No all noise is truly random, indeed most noise sources are not random at all. However, avalanche noise (used here) and johnson noise have both been tested to verify that they can be random in the sense that there was no way to distiguish them from a theoretical perfect random source…

      Of course the physical implementations of even truly random sources (such as radioactive decay) can be faulty (biased) and hence fail randomness tests…

  7. wowme@wtf.com says:

    WHAT???

  8. d ottaway says:

    Simple question for someone here – how do you plot points on a two dimensional graph if your data is a single random number?

    • d ottaway says:

      edit for correction:

      How do you plot points on a two dimensional graph if your data is a collection of random numbers?

      • anonymous says:

        Say you have a data set {x_0, x_1, x_2, …, x_j}. To plot a data point x_i on the plane [0,1]x[0,1] use its index (i) divided by the # of points in your data set (j+1) as the first coordinate and its value as the second.

      • anonymous says:

        Cool project. 3.1436 is about as good as you’re ever going to get with only 10,000 points, because the Monte Carlo method converges pretty darn slowly no matter how random your random numbers are.

      • WA says:

        Both the method anonymous posted and the one I posted of treating the sequential numbers as coordinate pairs; (N1,N2),(N3,N4),(N5,N6),… are useful. The former can reveal repetative patterns, while the later can reveal correlation issues…

  9. Wa says:

    Take the sequence of numbers in pairs. first of the pair is x, second is y.

  10. Greg Marlow says:

    I just use the least significant bit of the PC audio AD converter with an open mice. I then string the least significant bits to get a random number of the size I want.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 93,803 other followers