Generating random numbers.

[NatureTM 100]

I was looking for example code for RF2500 last night and came across some TI code for using the ADC as a random number generator. The function was in assembly, so I rewrote it in C:

 

bool getRandomBit(){
ADC10CTL1 |= INCH_5;
ADC10CTL0 |= SREF_1 + ADC10SHT_1 + REFON + ADC10ON;
ADC10CTL0 |= ENC + ADC10SC;
while(ADC10CTL1 & ADC10BUSY);
return ADC10MEM & 0x01;
}

 

Pin 1.5 is floating unconnected, and is measured by the adc. The LSB is used as the random bit. There's a twist though. Pin 1.4 is also floating unconnected, and is used as Vref+, so the top end of the range is floating as well. I thought that was pretty clever. Nice, TI!

 

I wrote a few console programs to help me visualize the randomness. It turned out the generator was biased toward producing 0's. This function used with the previous function seemed to remove the bias:

 

bool get0BiasRandomBit(){
if(getRandomBit()){
	if(getRandomBit())
		return 0;
	else
		return 1;
}
else{
	if(getRandomBit())
		return 1;
	else
		return 0;
}
}

 

To test for bias, I displayed a meandering line in a serial console. If I get more 0's than 1's, the line should slowly skew to the left or right:

 

#include "msp430g2231.h"
#include "config.h"
#include "softserial.h"
#include 

#define CONSOLE_WIDTH					80

bool getRandomBit();
bool get0BiasRandomBit();

void main(){
int linePositon = CONSOLE_WIDTH / 2;
char cursorPosition;


DCOCTL = CALDCO_16MHZ;
BCSCTL1 = CALBC1_16MHZ;

WDTCTL = WDTPW + WDTHOLD;					// Stop WDT

SoftSerial_init();
_enable_interrupts();

while(1){
	for(cursorPosition = 0; cursorPosition < linePositon; cursorPosition++)
		SoftSerial_xmit('8');

	SoftSerial_xmit(' ');
	cursorPosition++;
	while(cursorPosition < CONSOLE_WIDTH){
		SoftSerial_xmit('8');
		cursorPosition++;
	}

	if(get0BiasRandomBit())
		linePositon++;
	else
		linePositon--;

	if(linePositon < 0)
		linePositon = CONSOLE_WIDTH + linePositon;
	else if(linePositon >= CONSOLE_WIDTH - 1)
		linePositon = linePositon - CONSOLE_WIDTH;
}
}

bool get0BiasRandomBit(){
if(getRandomBit()){
	if(getRandomBit())
		return 0;
	else
		return 1;
}
else{
	if(getRandomBit())
		return 1;
	else
		return 0;
}
}

bool getRandomBit(){
ADC10CTL1 |= INCH_5;
ADC10CTL0 |= SREF_1 + ADC10SHT_1 + REFON + ADC10ON;
ADC10CTL0 |= ENC + ADC10SC;
while(ADC10CTL1 & ADC10BUSY);
return ADC10MEM & 0x01;
}

 

and some example output from this code:

 

This sends a comma-separated list of random ints to the console:

#include "msp430g2231.h"
#include "config.h"
#include "softserial.h"
#include 
#include 

int adcGenRand16();
void reverse(char s[]);
void itoa(int n, char s[]);
void txString(char string[]);
bool getRandomBit();
bool get0BiasRandomBit();

void main(){
int random;
char string[7];

DCOCTL = CALDCO_16MHZ;
BCSCTL1 = CALBC1_16MHZ;

WDTCTL = WDTPW + WDTHOLD;					// Stop WDT

SoftSerial_init();
_enable_interrupts();

while(1){
	random = adcGenRand16();
	itoa(random, string);
	txString(string);
}
}

void txString(char string[]){
int iString = 0;
while(string[iString] != 0){
	SoftSerial_xmit(string[iString]);
	iString++;
}
SoftSerial_xmit(',');
SoftSerial_xmit(' ');
}

bool get0BiasRandomBit(){
if(getRandomBit()){
	if(getRandomBit())
		return 0;
	else
		return 1;
}
else{
	if(getRandomBit())
		return 1;
	else
		return 0;
}
}

bool getRandomBit(){
ADC10CTL1 |= INCH_5;
ADC10CTL0 |= SREF_1 + ADC10SHT_1 + REFON + ADC10ON;
ADC10CTL0 |= ENC + ADC10SC;
while(ADC10CTL1 & ADC10BUSY);
return ADC10MEM & 0x01;
}

int adcGenRand16(){
char bit;
unsigned int random;

for(bit = 0; bit < 16; bit++){
	random <<= 1;
	random |= get0BiasRandomBit();
}
return random;
}

/* itoa:  convert n to characters in s */
void itoa(int n, char s[])
{
    int i, sign;

    if ((sign = n) < 0)  /* record sign */
        n = -n;          /* make n positive */
    i = 0;
    do {       /* generate digits in reverse order */
        s[i++] = n % 10 + '0';   /* get next digit */
    } while ((n /= 10) > 0);     /* delete it */
    if (sign < 0)
        s[i++] = '-';
    s[i] = '\0';
    reverse(s);
}

/* reverse:  reverse string s in place */
void reverse(char s[])
{
    int i, j;
    char c;

    for (i = 0, j = strlen(s)-1; i         c = s[i];
        s[i] = s[j];
        s[j] = c;
    }
}

 

 

I guess I got a little sidetracked from my original purpose of getting started with the RF2500, but I had fun.

[bluehash 1,581]

Had the same idea to use the ADC as a seed, but using the Vref+ too is clever.

Love the visualization.

[NatureTM 100]

I ran my ADC-based random number generator's output through the DIEHARD battery of tests for randomness quality and it failed miserably. I tried different pins for the ADC and a few different things in the code and all the results were terrible. That should probably have been expected, but a little part of me was still hopeful. I guess we shouldn't use it for any kind of cryptography.

 

I also took a closer look at how I was removing the bias. I think I just pulled that code out of my booty, because the fact that it led to low bias output seems to just have been luck. It works when the chances of getting a 1 (or 0, I forgot) are around 30%. DIEHARD thought either method had too much bias anyway.

 

The good news is that I wrote a tiny bit of java to take the serial output and put it into a binary file for consumption by DIEHARD, along with a little MSP430 prog to send the data. 9600 is way too slow, so I run it through an FTDI. My point is, if anyone feels like playing around with randomness and has a function they want tested, I'd gladly run it through my setup, saving you the hassle.