next topic »

[Reply #45 on:]

I have tried using each of the oscillators on several boards (with great thanks to three partners) as a means to generate "true random numbers".  My conclusion is that Atmel makes really good processors that are getting better.

[Reply #46 on:]

Unlike the Arduino, where there are 10 bits of measurement and then the rest are all 0 and the value is exactly the same every time you read it, no matter what internal source and reference you use.   

The 6 high bits. If those started giving other than zero the ADC would be useless.

Sometimes the random can be found in the time between events. A loop in Arduino can measure finer than micros() resolution allows. Perhaps the loops between noise making that low bit change....

[Reply #47 on:]

Sometimes the random can be found in the time between events. A loop in Arduino can measure finer than micros() resolution allows. Perhaps the loops between noise making that low bit change....

Yeah, I tried to measure the time each ADC conversion takes, which seemed to vary more than the ADC reading itself, but it was the same pattern every time I ran it:

Code:

32, 39, 38, 43, 238, 36, 22, 238, 37, 22, 38, 25, 22, 38, 25, 38, 22, 41, 42, 41, 41, 41, 41, 41, 25, 25
32, 39, 38, 43, 238, 36, 22, 238, 37, 22, 38, 25, 22, 38, 25, 38, 22, 41, 42, 41, 41, 41, 41, 41, 25, 25
32, 39, 38, 43, 238, 36, 22, 238, 37, 22, 38, 25, 22, 38, 25, 38, 22, 41, 42, 41, 41, 41, 41, 41, 25, 25

[Reply #48 on:]

Not time between each A/D conversion. Time between high points or low points or crossing a value, and yeah it still needs an irregular varying data source.

Have you tried ADC on an unterminated pin? Or better yet, switch back and forth between 2 unterminated analog pins since fast switching between ADC pins is documented to give bad readings, for a good read after fast switch you need to measure twice and use the second.

IMO the silicon itself is too regular, random needs external influences. That's why I suggested radio noise or radioactive decay, the latter is as random as it gets plus you don't need a Geiger counter to detect ions but rather an amplifier.

Back in the 80's with PC's I used to time user keystrokes and buffer those up for random keys, and that was measuring 18 per second "ticks". Use the user!

PS: Oh wait, I didn't go by "ticks". I loop-counted.

[Reply #49 on:]

Yeah, I tried to measure the time each ADC conversion takes

There is a "long" conversion and a "short" conversion but otherwise no variation.  Atmel documents the conversion time...

A normal conversion takes 13 ADC clock cycles. The first conversion after the ADC is switched on (ADEN in ADCSRA is set) takes 25 ADC clock cycles in order to initialize the analog circuitry.

The variations in your measurements are strictly a function of the phasing difference between loop, timer 0, and the ADC clock.  In other words, there is no randomness in the values.  The maximum values (238) are the result of the timer 0 interrupt service routine running in the middle interfering with the measurement.

[Reply #50 on:]

Ok, here's my attempt using the watchdog timer jitter.  It's slow (64 bit/s) and I can't prove that it's truly random, but it doesn't require external components or timers, seems to test well, and is at least more random looking than TrueRandom:

https://gist.github.com/2568571

https://secure.flickr.com/photos/56868697@N00/sets/72157629934367149/

Tested only on my Duemilanove.

[Reply #51 on:]

I have been experimenting with true random number generators for the last couple of months and thought I would share my thoughts (and some code),

The request that started this thread indicated that the author didn't want repeats; however, repeated sequences are a strong indicator of true randomness.  Indeed, one of the easiest ways to determine if a stream of randomness is true or human generated is the number and frequency of repeated sequences.  Typically when a human tries to create a random sequence, they don't create more than one or two (up to three) repeats while a truely random sequence of 100 coin flips is almost certain to have at least one sequence of 5 consecutive heads or tails...  In short what looks random, usually isn't.

All methods I have tried, including radioactive decay (geiger counters) have exhibited significant bias in the raw data stream.  All of the references I have found indicate that some degree of whitening is needed to create an unbiased random stream.  A good web source of information and specifically a simple piece of software that performs a test for randomness is available from the Hotbits web site.

His sample code, ported to an Arduino, works very well and takes the radioactive decay sourced bit stream with a couple of whitening techniques and produces a good (but fairly slow stream) of entropy.  My installation using a Arduino Mega with Ethernet Shield and an external geiger counter sampling a small piece of uranium ore is producing about 50,000 bytes of entropy per day.

The avalanche noise based random number generator as implemented by Rob Seward (http://robseward.com/misc/RNG2) did not produce a unbiased random stream.  I tested both the Von Neuman and the XOR bias removal sub-routines he provided and neither produced anything close to an unbiased stream for me (I implemented four different variations of the circuit).  However, when I used his Von Neuman subroutine to produce a byte from the bit stream and then XOR'ed two consecutive bytes, I got a very unbiased stream of bytes.

I did end up making some modifications to the circuit Seward used.  First I used a dc-dc step up regulator to produce between 13-15v dc (I varied it slightly for each of my implementations).  It is important to note that this circuit needs more than 5 volts, I have used it down to 9 volts, but performance wasn't as good. This was needed to produce a maximum output voltage of nearly 2.5V.  I then added an external 2.5V voltage reference to AREF to make use of the maximum resolution of the ADC.  The latter made a huge improvement in the performance of the entropy stream since it spread out the values read from just a couple of values to hundreds...  The circuit is very dependent upon the specific characteristics of the transistors involved and needs tweaking to get good performance for each circuit.  The speed of generation I have been getting from these circuits is approximately 11,000,000 bytes per day.

The circuit and the code have been tested on an old Arduino NG, Duemella, Uno, and Mega...

[Reply #52 on:]

Code:

// TRNG_USB
//
// True Random Number Generator - Generates a stream of random bits based upon the avalanche noise obtained from a reverse biased
// NPN transistor
//
// This code, created by Walter Anderson and is based upon an arduino sketch created by Robert Seward (http://robseward.com/misc/RNG2)
// The noise circuit and concept for using it as a random number source was originally conceived by Will Ware and posted to the usenet
//  (sci.crypt) a copy of this post is available at http://web.jfet.org/hw-rng.html
//
#include <stdio.h>

const int BINS_SIZE=256;
const int CALIBRATION_SIZE=50000;
const int MODE_READY=0;
const int MODE_ASCII_DECIMAL=1;
const int MODE_ASCII_HEX=2;
const int MODE_ASCII_BINARY=3;
const int MODE_BINARY=4;
const int MODE_PASSWORD=5;
const int MODE_MAC=6;
const int MODE_DICE=7;
const int baud_rate = 19200;
const int adc_pin = 0;

unsigned int bins[BINS_SIZE];
byte threshold;
byte OP_MODE;
byte PASSWORD[6];
boolean DEBUG = false;

void showBins(void)
{
  int i;
  char tmp[8];

  Serial.println("Data used to calibrate Random noise generator");
  Serial.print(" ");
  for (i=0; i<BINS_SIZE; i++)
  {
    sprintf(tmp, "%05u", bins[i]);
    if (((i+1) % 8)==0)
      Serial.println(tmp);
    else
      Serial.print(tmp);
    Serial.print(" ");
  }
  Serial.print("Median = ");
  Serial.println(threshold,DEC);
}

// I repackaged Robert Seward's calibration code into a single subroutine.  This will allow for the calibration to be performed
// both at initialization as well as ultimately be called for by the host device when needed.
// The concept of calibrating the median value is intriguing, it will be interesting to see if this becomes nescessary as the device
// ages
void calibrate(void){
  unsigned long half;
  unsigned long total = 0;
  unsigned int calibration_counter = 0;
  int adc_value;
  int i;
  byte adc_byte;
 
  for (i=0; i < BINS_SIZE; i++){
    bins[i] = 0;
  } 
  while (calibration_counter < CALIBRATION_SIZE)
  {
    adc_value = analogRead(adc_pin);
    adc_byte = adc_value >> 2;
    bins[adc_byte]++; 
    calibration_counter++;
  }
  for(i=0; i < BINS_SIZE; i++)
  {
    total += bins[i];
  }
  half = total >> 1;
  total = 0;
  for(i=0; i < BINS_SIZE; i++)
  {
    total += bins[i];
    if(total > half)
    {
      break;
    }
  }
  threshold = i;
  // In debugging mode (which may be turned on by the host) display the histogram data and median value calculated
  if (DEBUG)
    showBins();
}


void recalibrate(boolean show)
{
  if (show)
    DEBUG=true;
  Serial.println("Starting Calibration");
  calibrate();
  Serial.println("Finishing Calibration");
  if (show)
    DEBUG=false; 
}


// This routine will convert a 6 bit value (0-63) to an acceptible password character
char mapChar(byte parm)
{
  char retval;
  if (parm < 10)           // map 0..9 to ascii 0..9
    retval = char(48 + parm);
  else if (parm < 11)      // map 10 to -
    retval = '-';
  else if (parm < 12)      // map 11 to +
    retval = '.';
  else if (parm < 38)      // map 12 to 37 to ascii A..Z
    retval = char(53 + parm);
  else if (parm < 64)      // map 38 to 63 to ascii a..z
    retval = char(59
    + parm);
  else
    retval = 0;            // if parm is invalid return null 
  return(retval);
}

// This routine accumulates 6 bytes of data and then returns to the host an 8 character password
void getPassword(byte data)
{
  static byte cnt=0;
  byte a, b, c;
  char pw[9];
 
  PASSWORD[cnt] = data;
  cnt++;
  if (cnt>=6)
  {
    // Transfer sequencially six bits of data to a value to be converted to an ASCII character
    a = (PASSWORD[0] & B11111100) >> 2;
    pw[0] = mapChar(a);
    a = ((PASSWORD[0] & B00000011) << 4) + ((PASSWORD[1] & B11110000) >> 4);
    pw[1] = mapChar(a);
    a = ((PASSWORD[1] & B00001111) << 2) + ((PASSWORD[2] & B11000000) >> 6);
    pw[2] = mapChar(a);
    a = (PASSWORD[2] & B00111111);
    pw[3] = mapChar(a);
    a = (PASSWORD[3] & B11111100) >> 2;
    pw[4] = mapChar(a);
    a = ((PASSWORD[3] & B00000011) << 4) + ((PASSWORD[4] & B11110000) >> 4);
    pw[5] = mapChar(a);
    a = ((PASSWORD[4] & B00001111) << 2) + ((PASSWORD[5] & B11000000) >> 6);
    pw[6] = mapChar(a);
    a = (PASSWORD[5] & B00111111);
    pw[7] = mapChar(a);
    pw[8]=0;
    cnt = 0;
    Serial.println(pw);
    OP_MODE = MODE_READY;
  }
}

// This routine processes the adc byte value and uses the calibrated median value to convert it to
// a bit value (1 | 0) and then passes that to an algorithm for beginning to remove the bias
// inherrent in the hardware
void processInput(byte adc_byte, byte threshold)
{
  boolean input_bool;
  input_bool = (adc_byte < threshold) ? 1 : 0;
  vonNeumann(input_bool);
}

// This routine implements the von Neumann algorithm for removing bias from a bit stream
void vonNeumann(byte input)
{
  static int count = 1;
  static boolean previous = 0;
  static boolean flip_flop = 0;
 
  flip_flop = !flip_flop;

  if(flip_flop)
  {
    if(input == 1 && previous == 0)
    {
      buildByte(0);
    } else if (input == 0 && previous == 1) {
      buildByte(1);
    }
  }
  previous = input;
}

// This routine takes the bit stream from the first phase of bias removal and then
// adds a second stage of bias removal by xor'ng two consequetive bytes. 
// Depending upon the current operating mode, will dictate how the resulting byte
// is processed
void buildByte(boolean input)
{
  static int byte_counter = 0;
  static byte out = 0;
  static byte first;
  static boolean second=false;

  if (input == 1)
  {
    out = (out << 1) | 0x01;
  } else {
    out = (out << 1);
  }
  byte_counter++;
  byte_counter %= 8;
  if(byte_counter == 0)
  {
    if (second)
    {
      out = out ^ first;
      switch (OP_MODE)
      {
        case MODE_ASCII_DECIMAL :  Serial.println(out, DEC);
                                   break;
        case MODE_ASCII_HEX :      Serial.println(out, HEX);
                                   break;
        case MODE_ASCII_BINARY :   Serial.println(out, BIN);
                                   break;
        case MODE_BINARY :         Serial.write(out);
                                   break;
        case MODE_PASSWORD :       getPassword(out);
                                   break;
      }
      second = false;
      out = 0; 
    } else {
      first = out;
      out = 0;
      second = true;
    }
  }
}

void reset(void)
{
  OP_MODE = MODE_READY;
  Serial.println("Ready");
} 

// Standard arduino setup procedure
void setup(){
  analogReference(EXTERNAL); 
  Serial.begin(baud_rate);
  if (DEBUG)
  {
    Serial.write(34);
    Serial.print("values");
    Serial.write(34);
    Serial.println(" ");
  } else {
    Serial.println("Avalanche Noise Random Number Generator");
    Serial.println("version 1.0");
    Serial.println("by Walter Anderson");
    Serial.println(" ");
    Serial.println("Starting Calibration");
  }
  calibrate();
  if (DEBUG == false)
  {
    Serial.println("Finishing Calibration");
    Serial.println("Ready");
  }
}

// Main processing loop
void loop(){
  int adc_value;
  char recv;
  byte adc_byte;
 
  // We only obtain noise from the adc when we are in a mode that requires it
  if (OP_MODE != MODE_READY)
  {
    adc_value = analogRead(adc_pin);
    adc_byte = adc_value >> 2;
    processInput(adc_byte, threshold);
  }
 
  // Check if command information is being sent by the host
  if (Serial.available())
  {
    recv = Serial.read();
    switch (recv)
    {
      case '2' : OP_MODE = MODE_ASCII_BINARY;
                 break;
      case 'A' :
      case 'a' : OP_MODE = MODE_ASCII_DECIMAL;
                 break;
      case 'B' :
      case 'b' : OP_MODE = MODE_BINARY;
                 break;
      case 'C' :
      case 'c' : OP_MODE = MODE_READY;
                 break;
      case 'D' :
      case 'd' : OP_MODE = MODE_DICE;
                 break;
      case 'H' :
      case 'h' : OP_MODE = MODE_ASCII_HEX;
                 break;
      case 'M' :
      case 'm' : OP_MODE = MODE_MAC;
                 break;
      case 'P' :
      case 'p' : OP_MODE = MODE_PASSWORD;
                 break;
      case 'r' : reset();
                 break;
      case 'S' :
      case 's' : showBins();
                 break;               
      case 'X' : recalibrate(true);
                 break;
      case 'x' : recalibrate(false);
                 break;
    }
  }
}

[Reply #53 on:]

Ok, here's my attempt using the watchdog timer jitter.  ... Tested only on my Duemilanove.

Try a few boards with SMD processors.

[Reply #54 on:]

Try a few boards with SMD processors.

I don't have any, or I would.  Do you think those behave differently?

[Reply #55 on:]

I know they do.

[Reply #56 on:]

I know they do.

Terse much?

[Reply #57 on:]

I just thought of measuring the internal voltage reference vs. supply voltage. Right now I have not to much time to try this but this should pick up quite a lot of noise in the LSBs. But it might be biased though.

[Reply #58 on:]

I have been experimenting with true random number generators for the last couple of months and thought I would share my thoughts (and some code),

Thank you.

The avalanche noise based random number generator as implemented by Rob Seward (http://robseward.com/misc/RNG2)

I've read that the output changes over time (something about a junction in the transistors changing).  Have you noticed that happening?  Does the code account for that possibility?

Have you applied the usual statistical tests?

[Reply #59 on:]

I've read that the output changes over time (something about a junction in the transistors changing).  Have you noticed that happening?  Does the code account for that possibility?

I have read this as well, and considering that the four separate versions I have built so far have all had significant differences in output at a fixed supply voltage, I fully expect that to be the case.  I have only been running these particular circuits for a couple of weeks and so far I haven't noticed any changes in performance, but since they seem so sensitive to the transistors parameters (probably beta in this case) I expect to see such change.  That is one nice thing about Sewards code concept.  His code computes a median value of a sample of the readings and uses that median to transform the readings into bits.  That should take the inherent changes in the transistors out of the equation...which seems to have been confirmed by the fact the all four of my sample circuits seem to be producing equally random streams.

Have you applied the usual statistical tests?

So far only rudimentary ones.  I am waiting until I accumulate several gigabytes of data before I apply the more stringent tests.  This should take a couple of months, which should also let me test the performance over time...

I am attaching a couple of files with a histogram and some of the basic stats on the first five data files (10,000,000 bytes each) that the circuit has produced.