Getting real randomness in computers is quite hard. Most randomness is pseudo-random using some algorithm to create predictable but random looking output. In the early days these could be simple linear-feedback shift register approaches such as those used in early 8-bit computer sound chips like the Texas Instruments SN76489 that I used on the Memotech MTX. Nowadays we use more complex approaches but without some real randomness they are still predictable. Linux, for example, uses an entropy pool which it uses to capture as much non-pseudo-random information from the “outside world” as it can get it’s hands on, for example from the timing of keystrokes, and network packets.
Random numbers are needed for many things. Much of computer security is based upon algorithms that require, as inputs, a lot of randomness for the generation of unique keys and tokens. There is also a whole field of simulation, called the Monte Carlo method which is used to solve many problems where no good or efficiently solvable equations exist. In essense, the method involves generating random solutions and testing how good they are.
So what is real randomness? According to our best understanding of physics there is only one real source of randomness and that is from quantum measurements. This happens because all quantum mechanical systems can only be described in a statistical way and their random behaviour is constrained only by probabilities (which are well defined and not random.) According to our best understandings of the universe the rest of the laws of physics are strictly deterministic. However like our pseudo-random number generators inside computers chaos theory shows how even simple systems can create truly complex and random looking outputs. They are however deterministic and predictable if the initial conditions are fully known and no quantum randomness enters the system.
The problem with quantum randomness is that it is quite hard to access it, and very hard to get a lot of it. Despite our whole universe being built on a quantum mechanical basis the fact that quantum events are usually very small and swamped by the sheer vastness of the scale of our everyday events. One easy way to get a little bit of randomness is with a radiation detector such as a geiger muller tube. The one I have detects roughly 20 events every minute from beta and gamma-rays from background radiation in the atmosphere. That’s not a lot. Obviously if I had a big lump of uranium i could get a lot events and hence randomness from it, but that isn’t really safe or practical! Another approach is the use of a beam splitter and the use of single photon emitters and detectors but again this isn’t practical for everyday use.
Luckily there is another source of quantum noise called shot-noise. This exists in all electronic systems to some degree due to the quantised nature of electrons. Noise generators have been built that combine shot-noise with the avalanche effect to create a large amount of noise and hence randomness that is of a quantum mechanical origin but multiplied by it’s interaction with the psuedo-random chaotic avalanche breakdown characteristics of diodes.
Once such implementation of this is the BG7TBL wideband noise source. This post describes my explorations using this board. I am also using the Particle Photon as I do in many of my projects.
Figure 1: BG7TBL Noise Source connected to Photon particle board
I connected the BG7TBL output to the photons analog input via a decoupling capacitor of about 20nF to provide lowpass filtering to remove the highest of the frequencies from the output. (The BG7TBL has a noise bandwidth of over 30Mhz - far more than the lowly photon could sample and process) The BG7TBL requires a 12v power supply that can supply at least 300mA. This is quite a lot of power and the board runs quite warm.
Below is the sketch for the Photon which creates an HTTP webserver with a single endpoint to return random data. It returns back a hexadecimal formatted text/plain response with 1024 characters. Each bit in the response comes from a single sample of the random noise which is compared to a rolling mean to determine if it is 1 or 0.
#include <WebServer.h>
STARTUP(WiFi.selectAntenna(ANT_EXTERNAL));
#define PREFIX ""
WebServer webserver(PREFIX, 80);
String lastData;
const int AVG_WINDOW=32;
int avgTable[AVG_WINDOW];
int avgIndex=0;
int avgTotal=0;
int updateAvg(int aNewValue)
{
int removeValue=avgTable[avgIndex];
avgTable[avgIndex]=aNewValue;
avgIndex=(avgIndex+1)%AVG_WINDOW;
avgTotal+=aNewValue-removeValue;
return avgTotal/AVG_WINDOW;
}
void helloCmd(WebServer &server, WebServer::ConnectionType type, char *, bool)
{
server.httpSuccess();
if (type != WebServer::HEAD)
{
const int bytes=1024;
char msg[bytes+1];
fillRandomString(msg,bytes);
msg[bytes]=0;
server.print(msg);
}
}
int getRandomBit()
{
analogRead(A0);
int v=analogRead(A0);
int avg=updateAvg(v);
return (v-avg)>0;
}
unsigned int getRandomInt()
{
unsigned int k=0;
unsigned int n=1;
for (int i=0; i<32; i++)
{
if (getRandomBit()) k+=n;
n=n+n;
}
return k;
}
void fillRandomString(char* chs, int len) {
int j=0;
for(int i=0; i<len; i+=8) {
unsigned int j=getRandomInt();
sprintf(chs+i,"%08X", j);
j+=8;
}
}
void generateSummary()
{
int v=analogRead(A0);
int avg=updateAvg(v);
char chs[80];
sprintf(chs,"v=\"%d\" avg=\"%d\" ", v,avg);
lastData=chs;
}
void setup() {
pinMode(A0, INPUT);
setADCSampleTime(ADC_SampleTime_3Cycles);
Particle.variable("data",lastData);
webserver.setDefaultCommand(&helloCmd);
webserver.begin();
}
void loop() {
char buff[128];
int len = 128;
webserver.processConnection(buff, &len);
generateSummary();
}Once I had exposed the raw data endpoint on the network I wrote a groovy script in Polestar to generate a bitmap from the data like this:
Figure 3: Noise represented as a 2d pixel map
The groovy script simply builds a raw image buffer and then requests enough random data to scan each pixel of the image and paint a black pixel where needed on a white background.
import org.netkernel.layer0.nkf.*;
import org.netkernel.mod.hds.*;
import org.netkernel.layer0.representation.ByteArrayRepresentation;
import java.awt.*;
import java.awt.image.*;
import javax.imageio.*;
int w=512;
int s=1;
BufferedImage tmp = new BufferedImage(w*s, w*s, BufferedImage.TYPE_INT_ARGB);
Graphics2D g2 = tmp.createGraphics();
g2.setColor(Color.WHITE);
g2.fillRect(0,0,w*s,w*s);
g2.setColor(Color.BLACK);
int x=0;
int y=0;
rs=new RandomState(context);
while (y<w)
{
b= rs.getNextRandom();
if (b)
{ g2.fillRect(x*s,y*s,s,s);
}
x++;
if (x>=w)
{ x=0;
y++;
}
}
g2.dispose();
ByteArrayOutputStream baos = new ByteArrayOutputStream(14000);
ImageIO.write(tmp, "png", baos);
rep=new ByteArrayRepresentation(baos);
resp=context.createResponseFrom(rep);
resp.setExpiry(INKFResponse.EXPIRY_ALWAYS);
resp.setMimeType("image/png");
class RandomState
{
public RandomState(INKFRequestContext aContext)
{ context=aContext;
}
INKFRequestContext context;
String s=null;
int si=0;
long ld;
int b=1;
public boolean getNextRandom()
{
if (s==null || si>=s.length())
{ //if (s==null)
s=this.getRandom();
si=0;
b=1;
}
int c= toHex((int)s.charAt(si));
boolean result=(c&b)!=0;
b=b+b;
if (b>=16)
{ b=1;
si++;
}
return result;
}
public static int toHex(int aChar)
{ int result;
if (aChar<='9' && aChar>='0')
{ result = aChar-48;
}
else if (aChar<='F' && aChar>='A')
{ result= aChar-(65-10);
}
else
{ throw new IllegalArgumentException();
}
return result;
}
String getRandom()
{
INKFRequest req=context.createRequest("active:httpGet");
req.addArgument("url","http://192.168.1.120");
req.setRepresentationClass(String.class);
String random=context.issueRequest(req);
return random;
}
}Analysis
The first analysis I did was to run a fast-fourier transform on the image to detect any periodic artifacts in the noise. Unfortunately there was a bit. It seems like there is a slight lack of lower frequencies and then fundamental frequency tone in the noise with many weaker overtones. I experimented a bit with altering the averaging window length in the photon code. I think the noise is possibly earth leakage between the output of the BG7TBL and photon. This is a common problem when running different parts on different power supplies as I did here with the photon running on a 5v USB supply and the BG7TBL running on 12v.
Figure 5: 2D Fast fourier transform of noise image
As a final test I tried to run the Dieharder suite of tests on the randomness. These tests perform exhaustive checks on all aspects of the randomness to look for weaknesses. Unfortunately they also require massive amounts of test data which I didn’t give it. So the results where pretty poor:
#=============================================================================#
# dieharder version 3.31.1 Copyright 2003 Robert G. Brown #
#=============================================================================#
rng_name | filename |rands/second|
file_input| random.txt| 2.33e+06 |
#=============================================================================#
test_name |ntup| tsamples |psamples| p-value |Assessment
#=============================================================================#
# The file file_input was rewound 15 times
diehard_birthdays| 0| 100| 100|0.46093044| PASSED
# The file file_input was rewound 123 times
diehard_operm5| 0| 1000000| 100|0.00000000| FAILED
# The file file_input was rewound 263 times
diehard_rank_32x32| 0| 40000| 100|0.14251199| PASSED
# The file file_input was rewound 328 times
diehard_rank_6x8| 0| 100000| 100|0.00000000| FAILED
# The file file_input was rewound 357 times
diehard_bitstream| 0| 2097152| 100|0.00000000| FAILED
# The file file_input was rewound 585 times
diehard_opso| 0| 2097152| 100|0.00000000| FAILED
# The file file_input was rewound 737 times
diehard_oqso| 0| 2097152| 100|0.00000000| FAILED
# The file file_input was rewound 809 times
diehard_dna| 0| 2097152| 100|0.00000000| FAILED
# The file file_input was rewound 816 times
diehard_count_1s_str| 0| 256000| 100|0.00000000| FAILED
# The file file_input was rewound 955 times
diehard_count_1s_byt| 0| 256000| 100|0.00000000| FAILED
# The file file_input was rewound 958 times
diehard_parking_lot| 0| 12000| 100|0.00000001| FAILED
# The file file_input was rewound 960 times
diehard_2dsphere| 2| 8000| 100|0.42405764| PASSED
# The file file_input was rewound 961 times
diehard_3dsphere| 3| 4000| 100|0.99487526| PASSED
# The file file_input was rewound 1199 times
diehard_squeeze| 0| 100000| 100|0.00000000| FAILED
# The file file_input was rewound 1199 times
diehard_sums| 0| 100| 100|0.00436357| WEAK
# The file file_input was rewound 1210 times
diehard_runs| 0| 100000| 100|0.03783552| PASSED
diehard_runs| 0| 100000| 100|0.28070255| PASSED
# The file file_input was rewound 1358 times
diehard_craps| 0| 200000| 100|0.00000000| FAILED
diehard_craps| 0| 200000| 100|0.03489181| PASSED
# The file file_input was rewound 3536 times
marsaglia_tsang_gcd| 0| 10000000| 100|0.00000000| FAILED
marsaglia_tsang_gcd| 0| 10000000| 100|0.00000000| FAILED
# The file file_input was rewound 3547 times
sts_monobit| 1| 100000| 100|0.00000000| FAILED
# The file file_input was rewound 3558 times
sts_runs| 2| 100000| 100|0.00000000| FAILED
# The file file_input was rewound 3568 times
sts_serial| 1| 100000| 100|0.00000000| FAILED
sts_serial| 2| 100000| 100|0.00000000| FAILED
sts_serial| 3| 100000| 100|0.00000000| FAILED
sts_serial| 3| 100000| 100|0.00000276| WEAK
sts_serial| 4| 100000| 100|0.00000000| FAILED
sts_serial| 4| 100000| 100|0.00000000| FAILED
sts_serial| 5| 100000| 100|0.00000000| FAILED
sts_serial| 5| 100000| 100|0.00000000| FAILED
sts_serial| 6| 100000| 100|0.00000000| FAILED
sts_serial| 6| 100000| 100|0.00000000| FAILED
sts_serial| 7| 100000| 100|0.00000000| FAILED
sts_serial| 7| 100000| 100|0.00000000| FAILED
sts_serial| 8| 100000| 100|0.00000000| FAILED
sts_serial| 8| 100000| 100|0.00000047| FAILED
sts_serial| 9| 100000| 100|0.00000000| FAILED
sts_serial| 9| 100000| 100|0.01859174| PASSED
sts_serial| 10| 100000| 100|0.00000000| FAILED
sts_serial| 10| 100000| 100|0.00000000| FAILED
sts_serial| 11| 100000| 100|0.00000000| FAILED
sts_serial| 11| 100000| 100|0.00000000| FAILED
sts_serial| 12| 100000| 100|0.00000000| FAILED
sts_serial| 12| 100000| 100|0.10447315| PASSED
sts_serial| 13| 100000| 100|0.00000000| FAILED
sts_serial| 13| 100000| 100|0.00000000| FAILED
sts_serial| 14| 100000| 100|0.00000000| FAILED
sts_serial| 14| 100000| 100|0.00364429| WEAK
sts_serial| 15| 100000| 100|0.00000000| FAILED
sts_serial| 15| 100000| 100|0.27214094| PASSED
sts_serial| 16| 100000| 100|0.00000000| FAILED
sts_serial| 16| 100000| 100|0.03165166| PASSED
# The file file_input was rewound 3590 times
rgb_bitdist| 1| 100000| 100|0.00000000| FAILED
# The file file_input was rewound 3634 times
rgb_bitdist| 2| 100000| 100|0.00000000| FAILED
# The file file_input was rewound 3699 times
rgb_bitdist| 3| 100000| 100|0.00000000| FAILED
# The file file_input was rewound 3786 times
rgb_bitdist| 4| 100000| 100|0.00000000| FAILED
# The file file_input was rewound 3895 times
rgb_bitdist| 5| 100000| 100|0.00000000| FAILED
# The file file_input was rewound 4026 times
rgb_bitdist| 6| 100000| 100|0.00000000| FAILED
# The file file_input was rewound 4178 times
rgb_bitdist| 7| 100000| 100|0.00000000| FAILED
# The file file_input was rewound 4353 times
rgb_bitdist| 8| 100000| 100|0.00000000| FAILED
# The file file_input was rewound 4549 times
rgb_bitdist| 9| 100000| 100|0.00000000| FAILED
# The file file_input was rewound 4766 times
rgb_bitdist| 10| 100000| 100|0.00000000| FAILED
# The file file_input was rewound 5006 times
rgb_bitdist| 11| 100000| 100|0.00000000| FAILED
# The file file_input was rewound 5267 times
rgb_bitdist| 12| 100000| 100|0.00000000| FAILED
# The file file_input was rewound 5289 times
rgb_minimum_distance| 2| 10000| 1000|0.11132511| PASSED
# The file file_input was rewound 5322 times
rgb_minimum_distance| 3| 10000| 1000|0.00010924| WEAK
# The file file_input was rewound 5365 times
rgb_minimum_distance| 4| 10000| 1000|0.03845742| PASSED
# The file file_input was rewound 5420 times
rgb_minimum_distance| 5| 10000| 1000|0.00000000| FAILED
# The file file_input was rewound 5442 times
rgb_permutations| 2| 100000| 100|0.07975155| PASSED
# The file file_input was rewound 5474 times
rgb_permutations| 3| 100000| 100|0.10238874| PASSED
# The file file_input was rewound 5518 times
rgb_permutations| 4| 100000| 100|0.00013190| WEAK
# The file file_input was rewound 5572 times
rgb_permutations| 5| 100000| 100|0.00000221| WEAK
# The file file_input was rewound 5681 times
rgb_lagged_sum| 0| 1000000| 100|0.00000000| FAILED
# The file file_input was rewound 5899 times
rgb_lagged_sum| 1| 1000000| 100|0.00000000| FAILED
# The file file_input was rewound 6226 times
rgb_lagged_sum| 2| 1000000| 100|0.00000000| FAILED
# The file file_input was rewound 6661 times
rgb_lagged_sum| 3| 1000000| 100|0.00000000| FAILED
# The file file_input was rewound 7206 times
rgb_lagged_sum| 4| 1000000| 100|0.00000000| FAILED
# The file file_input was rewound 7859 times
rgb_lagged_sum| 5| 1000000| 100|0.00000000| FAILED
# The file file_input was rewound 8622 times
rgb_lagged_sum| 6| 1000000| 100|0.00000000| FAILED
# The file file_input was rewound 9493 times
rgb_lagged_sum| 7| 1000000| 100|0.00000000| FAILED
# The file file_input was rewound 10473 times
rgb_lagged_sum| 8| 1000000| 100|0.00000000| FAILED
# The file file_input was rewound 11562 times
rgb_lagged_sum| 9| 1000000| 100|0.00000000| FAILED
# The file file_input was rewound 12760 times
rgb_lagged_sum| 10| 1000000| 100|0.00000000| FAILED If all this seems like hard work there are of course many commercially available hardware random number generators.