# AVR Random Number Generator

I've read an appnote from TI (slaa338) that describes a technique for generating "for real" (as opposed to "pseudo") random numbers. It exploits the somewhat exotic clock subsystem of the MSP430 to achieve this goal. Does anyone know of a technique that can be implemented on an AVR (I'm interested in the XMega's in particular) for generating "for real" random numbers?

-
psuedo random works for dice games. I think he wants cryptographically secure. – Kortuk Jul 21 '10 at 19:19
Can you give a hint as to the application and/or the degree of randomness that you require? If it's for cryptography, there are additional considerations besides just the seed quality. Some of the suggestions already made-- like sampling environmental inputs of various types may or may not be appropriate based on your requirements. – Windell Oskay Jul 22 '10 at 6:08

How bad do you to use the XMega? If the crypto and random number generation are a big part of your project, Atmel's SecureAVR series has a hardware random number built in, and is designed for cryptographic applications.

Regardless, I doubt that you'll find a random seed source that has a good distribution. You'll want to run it through a pseudo random number generator a few times As long as you start with a different seed every time, this will give you a nice set of random numbers. An LGC is a quick and easy pseudo random generator:

static unsigned long Seed;

/* Call before first use of NextVal */
unsigned long InitSeed()
{
//Your code for random seed here

// Correct distribution errors in seed
NextVal();
NextVal();
NextVal();
return NextVal();
}

/* Linear Congruential Generator
* Constants from
* "Numerical Recipes in C"
* by way of
* <http://en.wikipedia.org/wiki/Linear_congruential_generator#LCGs_in_common_use>
* Note: Secure implementations may want to get uncommon/new LCG values
*/
unsigned long NextVal()
{
Seed=Seed*1664525L+1013904223L;
return Seed;
}

-
 Thatis awesome, I didn't realize the SecureAVR line existed, thanks for the pointer! – vicatcu Jul 22 '10 at 15:12 BTW: If you REALLY need security, the simple, effective, and fast LCG method I presented isn't what you want: Many LCGs can be broken; just get 2-3 values in a row, and plug them into an LCG generator with a set of known constants - this would include everything on the Wikipedia page. A matching pattern will let the attacker predict what the next number will be. It's possible (but harder) to figure out what the constants are from nothing, as well. – Kevin Vermeer Jul 22 '10 at 15:41 @reemrevnivek FYI, Atmel is selling off their SecureAVR line... they recommend their ARM-based 32-bit processors if you want cryptographic stuff which is a whole different ballgame in terms of development environment from AVR. They do have a couple with True RNGs on them though, maybe I'll play with them some day. – vicatcu Aug 5 '10 at 21:24

Connect up the ADC to a hardware noise source and use software to "whiten" the random numbers as needed.

Here's an AVR based project that does this: Leon's Mini Portable Random Number Generator (mPRNG)

Depending on how cryptographically secure it needs to be, you could use the noise of a floating analog input or the "internal temperature sensor" as your randomness seed instead of external hardware.

-
Naming a (more or less true) RNG, "-PRNG" is unfortunate. – Nick T Dec 2 '10 at 0:54

Another trick for generating a random seed, is to count the number of clock cycles until an external event. For example if this is a device to be used by a person, count the number of clock cycles until he presses the 'go' button, and use that as the random seed.

-
This may not be very secure against side channel attacks as they can break in by securing control of one device, but as with all cryptography, application determines feasibility. – Kortuk Jul 21 '10 at 19:20

To be sure to not restart with the same sequence, I use somme byte in the eeprom :

#include <avr/eeprom.h>
#include <stdlib.h> // rand

u16  EEMEM randinit;

int main(void) {
eeprom_write_word(&randinit,rand());
[...]
}


This give quite good random, and does not cost much in programme/memory.

-
 This reads byte 0 every time. What evidence do you have that this byte is random? If it is, this is a great technique! – Kevin Vermeer Jul 23 '10 at 1:19 This word (byte 0 & 1 in fact) will be random, because at each startup I initialise the random generator with it's content. THEN I upload it with a new rand(). So the next init will look random from the current one... and so on... But if I reset randinit to ffff (or 0000?), I will have the same randinit sequence! So it's not perfect. I forgot a warning about the fuse who erase the eeprom when uploading the *.hex ;) – jojo l'abricot Jul 23 '10 at 19:57

Have you looked at using something like randomSeed()? - used in the Arduino IDE

You can use this function to sample a floating (free) analog pin on the atmel AVR, it then uses the value to create an arbitrary starting point for the pseudo random number function - random().

The value created by random() may be a pseudo random number - but the arbitrary starting point created by randomSeed() should be as real a random number/value as you can get.

-
Sampling things like the analog pins is close to random, but will not have an even distribution. Run the seed through random a couple times, however, and it will. – Kevin Vermeer Jul 22 '10 at 3:34
....through a pseudo random number generator a couple... <- How did that go missing? NTS: Engage brain first, then fingers. – Kevin Vermeer Jul 22 '10 at 10:06
Exactly - It's also not the most secure if using it for encryption / protection etc, but it will give you a nice random number for something like generative music or dice games. It's good and easy to implement too :) – Jim Jul 22 '10 at 10:17