A True Random Number Generator in Arduino (AVR ATmega in that case)

The Problem

I was working on a system where I had to initialize each microcontroller-based device on a communication bus with unique addresses. Since the addressed are supposed to be unique while the devices were identical, the trick was to use randomization to attain different behaviour from controllers that have identical controllers, code and PCBs. This way, when we request two devices on the same address to switch to a new address with a coin flip, the probability of only one device jumping was 50%, meaning, in a short time, we can assign unique addresses to all the devices previously having the same address.

We used the standard randomizers and even ADCs to include real-world non-linearities, this system proved to be perfectly linear. No matter how much time it would take, since all the devices were powered up at the same time and had the exact same code, would always like to jump an address when requested. Remember Marty from the movie Madagascar?

And the only way we could find was to use hardware components like adjustable potential dividers to make each circuit have at least something unique that it could sense. Even this technique failed because it was an added component in the circuit and the fabrication process plus the probability of having a unique seed was just 1/1024 (because the sensor, the ADC, was just 10 bits wide). We needed a better randomizer with a truly random seed.

I must mention one other article here that presents two more methods of random number generation. I couldn't use either of them because one of them is dependent on dedicated hardware and the other was memory intensive. The method presented in this article is so light that it actually saves 300 bytes on the flash to replace the existing arduino rand(). The other article can still be found here.

A Little Background

ADCs have already been used to generate true random numbers in microcontrollers. There come some limitations when either we cannot spare any analog input pin for this randomization or the ADC saturates in presence of EMFs and ESFs in the circuit nearby. I have used Atmega328p to demonstrate a way to overcome both of these limitations. Instead of trying to read a floating (and supposedly random) input signal, we create an internal signal and exploit the limitation of the hardware that cannot synthesize the signal exactly as it is supposed to do. This opens up an opportunity to randomize some bits.

So the ADC of ATMega (other AVRs and most other controllers with internal ADC) uses a programmable multiplexer to route different pins to the main converter. In addition to attaching it to input pins of the controller, it can also be attached to some internal predefined voltages, which in case of Atmega328p are 0V and 1.1V bandgap voltage. The reference can also be changed but we do not use the effects of changing it in this method. Using these two voltages, we synthesize a pulsating square pulse of amplitude 1.1V on our ADC. The ADC should read a "0" for the low pulse and "1023" for the high but this is true when our assumption of having a square pulse is true which is not. Changing the voltage level takes some time due to the internal capacitance of the controller circuitry and lucky us, that this time is in the exact range the ADC takes for each conversion. So, in a perfectly linear microcontroller circuit, we have formed a sub-system that is highly nonlinear due to multiple factors like the supply voltage, temperatures, and most importantly, the oscillations which tend to exploit very interesting dynamics of the system when we are playing in the range of natural frequencies of other components.

Now the measured values are random yet may contain some sort of pattern because they are coming from a non-chaotic physical phenomenon. To reduce this effect, we use some coding techniques. Like having a "seed", using bit shifting, and randomly changing the synthesized signal frequency. The first is done by using the result of the previous conversion as the starting point, (just like we do in pseudo-random numbers); the bit shifting is done using the processor's standard shifting instructions; and the last one is done by changing the clock frequency of the ADC after each conversion.

Using the Code

Here is sample code written to generate an 8 bit random number. Wider numbers can be attained by increasing the bits depth or using multiple randomizers.

int N = 20;
// 20 works really fine for uint8, can be increased to reduce patterns.
// Each cicle takes around 80us on 16Mhz main clock
// which give a random number almost every 1.5ms.
for (int i = 0; i < N; i++)
{
  // Synthesize a voltage on the input
  if (i % 2 == 0)
    ADMUX = 0b01001110; // [A] // High (1.1V). // See Datasheet Table 23-3 and 23-4
                               // for Atmega328p
  else
    ADMUX = 0b01001111; // [A] //  Low (0V)
  ADCSRA |= 1 << ADSC;  // Start a conversion. See Datasheet for Atmega328p Page 207
  uint8_t low, high;
  // ADSC is cleared when the conversion finishes
  while ((ADCSRA >> ADSC) % 2); // wait for the conversion to complete
  low  = ADCL;          // do not swap this sequence. Low has to be fetched first.
  high = ADCH;          // the value is always between 0-3
  V ^= low;
  V ^= high;

  // Let's shift rotate the number;

  uint8_t last = V % 2;
  V >>= 1;
  V |= last << 7;        // "7" will need to change to K-1 to use a K bits wide datatype
  // Disable the ADC
  ADCSRA = 0;

  // Enable the ADC with a randomly selected clock Prescaler between 2 and 128.
  // Since each conversion takes 13 ADC cycles, at 16Mhz system clock,
  // the ADC will now take something in between 1.6us and 104us
  // for each conversion (75us on the average).
  ADCSRA = 0b10000000 | ((V % 4) << 1); // See Datasheet Table 23-5 for Atmega328p
}

Sample Output With N = 20

Sample Output With N = 50

Improvement Margin

• While measuring the signal, we can increase non-linearity by changing the reference voltage as well. This will have to be embedded in point [A] of the above code.
• The final number can be complemented by adding a pseudo-random number generator taking the real numbers as a seed.
• To make the ADC reading more random, we can either make the signal more erratic (e.g., using variable clock rates) or by making the signal move very fast. The uncertainty of the ADC will increase while reading a very fast signal. This can be done by moving the oscillating system more towards a point of resonance. This means that only one of the possible frequencies of the ADC clock will give the maximum rise and fall times for the signal, and thus more erratic ADC readings.
• The Bit width of the random number can be increased.

Applications

• Security
• Communication

History

• 23^rd August, 2021: Initial version