Most toolchains for embedded system include support for random number generation. But if you’ve read the manual you’ll know that this is really just pseudo random number generation (PRNG). When calling this function the same numbers will always return in the same order unless a different random number seed is supplied in advance. [Gardner] put together a simple and cheap solution for deriving better random number seeds. He reads a voltage from a 555 timer using the ADC on the microcontroller. At first glance it may not seem like a great source of randomness, but he performed some testing and the results look quite promising.
The project is aimed at Arduino-based circuits, but any chip with an ADC will work. The 555 timer is used as a free running oscillator. We know that this not be very stable when compared to even the worst of crystal oscillators, but that’s what makes it work so well as a random seed source. Add to this the low parts count and small size of the additional circuitry and you’ve got a winning combination. So keep this in mind when you need a random number but don’t necessarily need rock solid entropy.
[via Reddit and Freetronics]
In before all the random number elitists
3.
/chosen by fair die roll
On PSoC devices, a nasty trick is to use an ADC input connected to a collumn that isn’t being driven by the analog mux.
You get noise that’s random enough, but you still get the clock and other stuff superimposed.
Not sure of you could do something similar on AVR chips though.
I think I did this inadvertently on a PIC, and got only zeros from the ADC. I’ll have to try again under more controlled circumstances, as it would be quite useful if it works.
If anyone else has interesting tricks for random seed generation, I’d love to hear them.
Sampling a floating pin with the ADC is the cheap standard way to seed the random number generator with the Arduino. Much easier than sampling atmospheric noise, though much less random.
Methinks you did not read da article.
Interesting, my little idea… why not also using characteristic changing devices, such as a photo-resistor (in series/parallel with your resistor) and/or a photo-diode (in parallel with the capacitor) to also change the frequency. I can imagine playing with temperature as well, or any other interesting ambient elements (sound?), to affect the signal.
If your looking for nice near random noise slightly lift one side of a cheep optical mouse off the table. It will be slightly bias in one corner of the screen but if you get it just right you leave the cursor dancing around. The bias can quite easily be equalized out using the generated seqence it’s self.
Although I suspect it wouldn’t be too hard to grab individual pixels. It is certainly a cheep, quick and dirty option to read a ps2/usb connector.
The basic statistical tests he did are a good start, but one of the standard tests for random numbers is to group them in sets of N and plot the results as points in an N-dimensional space.
The 2D test, for instance, would would collect the sequence {27, 182, 818, 2, 845, 90} into the points (27, 182), (818, 2), (845, 90) then plot them on a rectangular grid. The 3D test would plot the points (27, 182, 818), (2, 845, 90), and plot them in a cube.
If there’s a relationship between sequential numbers, the points tend to cluster in noticable patterns. The numbers from LCRNGs (the easiest ones to write) tend to make diagonal lines. If the numbers are independent of each other, the points fill the space randomly.
I’d be interested to see how the numbers from this plot out. It’s probably not cryptographically strong, but I agree with the OP that you don’t need crypto-level randomness most of the time.
Even if this doesn’t turn out to be all that great a source of randomness on its own, it would probably be great for randomly clocking a deterministic RNG. With that technique, you just read and discard a value every so often, ideally using a pattern with no relationship to the RNG itself. The occasional skips in the sequence apparently play hell with attempts to analyze the RNG’s output.
@mstone
The “plot k-tuples in k-space” is a traditional test, but it is mostly relevant for certain types of psuedo-random generators, especially simple linear congruential generators.
An auto-correlation or FFT would be a better approach here, as it would reveal how much of the underlying sine wave remains after sampling. Even just plotting sequential points in the time domain would be good — he is undersampling by a factor of 13:1, but unless you have 10% clock drift cycle-to-cycle the next point will be largely predictable even if over long times the function takes on all values with the right probability.
But these techniques would be hard to do in the internal memory of the arduino.
Found an interesting article at:
http://n1.taur.dk/avrfreaks/engather.pdf
A short summary by the author:
“The 328p can interrupt on watchdog timer. The watchdog uses its own RC oscillator, and has phase noise relative to the main clocksource.
Set up a timer so it counts every clock. An 8 bit timer is plenty. In the watchdog interrupt read the timer, and hash the value. I usually do so for ~4s before claiming to have 128 bits of entropy to drive cryptographic functions.”
So it appears to be doing the same thing as this project, except it uses a built-in RC oscillator. Sounds a little trickier to implement, but could be worthwhile if you wish to avoid extra hardware.
It also makes me wonder if you could extract useful phase noise from other things. An external crystal oscillator not related to the main clock? A simple RC circuit alternately driven and read by a single pin of the Arduino itself?
Dual oscillator RNGs are relatively common, Intel chips also use a dual oscillator random number generator: http://www.cryptography.com/public/pdf/IntelRNG.pdf except they go one better and use a voltage controlled oscillator fed by amplified noise from a resistor.
I have implemented an Arduino library that uses the jitter associated with the WDT interrupt to generate random numbers. Statistical testing indicates that this method produces cryptographically secure uniform random numbers.
Library at Arduino Entropy Library
I dont see this being any better than a floating adc pin. while the RC clock of the 555 isn’t exactly stable, it is far more regular than a floating pin! yes you get 60Hz but he’s making the assumption that 1. that is all the noise that is there. actually there is alot of random non-periodic noise out there. Every time someone nearby flips a light switch, CFLs starting up, lamp dimmers, gas stove /furnace ignitors, lightning, combustion engine ignition, etc etc…and 2. that once you are in nature, the noise goes away. You would have to be wayyyyyy far away from anything not to get the occasional blurp of noise from something. and you don’t have to use diode connected transistors. low voltage zeners will work, you just need higher gain with them. or a max232 as a charge pump like he mentions. I get low parts count, but saying this is better than a floating ADC pin isn’t computing here…
I just used a floating ADC input pin. To get a random byte I read the ADC pin 8 times in a certain time distance, and after every reading I ommit the 7 MSB bits. The LSB of a floating ADC pin gives very good random values.
Maybe I do a data acquisition of this one day if I have time to see how good values it gets me.