AVR Random Number Generator

Question

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?

Answer 1

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;
} 

Answer 2

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.

Answer 3

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.

Answer 4

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) {
        srand(eeprom_read_word(&randinit));
        eeprom_write_word(&randinit,rand());
        [...]
 }

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

Answer 5

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.