Hardware Random Number Generator

Aaron Logue May 2002

05/15/15 Update: Check out this variation, adding Von Neumann debiasing without a microcontroller plus an analog bias adjustment trimmer:
http://makezine.com/projects/really-really-random-number-generator/

This page describes my effort to construct a random number generator with as high a security-to-cost ratio as I can manage. I warn anyone who intends to use any of this for anything serious to engage in a rigorous study of the weaknesses inherent in this design.

The PN junction of Q1 is reverse biased to produce avalanche noise. The resultant signal is amplified for the purpose of driving a TTL-level Schmitt trigger to produce a squarewave; a series of rising and falling edges with unpredictable time intervals between edges.

I did a sanity check on the above circuit by feeding the squarewave output to the input clock of a 7493 counter chip and taking a look at the MSB output on an oscilloscope. Each rising edge of the MSB output count on pin 11 meant that the counter chip had received 16 falling edges on its clock input pin 14. This revealed that 16 squarewave cycles took about 10 microseconds on average, with the shortest visually perceptable values being about 5 microseconds for 16 cycles and the longest about 15.

The trace shown here is set at 5 microseconds per division. The scope is triggering on the rising edge of the wave, but the falling edge is fuzzy due to the varying length of time that the 7493's MSB is high. The next rising edge varies by yet more, the falling edge by even more, and so on until the approximate times at which the 7493's MSB line rise or fall are no longer distinguishable, which seemed to occur after about 80 microseconds. None of this was cryptographically meaningful, but it was reassuring in terms of being consistent with the theory of operation.

I then connected the circuit to an SX microcontroller so that I could sample the squarewave, unbias the random bits, and transmit the results to a PC's serial port.

To unbias the bits, I use the Von Neumann method, described in the Schneier red book (Applied Cryptography 2nd Ed.) on page 425. I sample two bits and discard them if they are equal. If they are not equal, then I accumulate one of the bits. When enough bits are accumulated, I output them.

I support four different output formats in the microcontroller firmware; ASCII binary (sending a stream of "0" and "1" characters), ASCII hex (sending bytes as two hex characters in the range of 0-9 and A-F), base64 (0-63 values represented by uppercase A-Z, lowercase a-z, numerals 0-9, and characters + and /) and 8-bit raw binary. Formats are changed by sending the microcontroller a "1", "4", "6" or "8" command, corresponding to the number of actual bits encoded in each byte transmitted.

If a "?" character is sent, the program will return a 1, 4, 6, or 8 to indicate what its current format is. This should be done only when the program is not streaming random data. The random data stream is turned on and off with ^Q and ^S characters (ASCII XON and XOFF, or ctrl-Q and ctrl-S). The device streams at 9600 baud, and could probably sample at a rate fast enough to support 19200 or 38400 at full entropy.

Sample output in ASCII binary, hex, and base64 output modes:

10111010010100101110100111101001000001000111010110100101101110010100100011001000
10001001011110100011101001000011000100011011100000111111100000000001111001010100
01010000011110101101110111100000000110010011001111010001100011000101000010101111
00100011110001100001111001001101011001000110101001101110000010010001000100100010
10001110110000100001011100101101000001100110100001010110001011001101001001100101
01101011001101111011101001011010001010110001100011001110000110010011011110010100
1DE1CF585D8D78A6EECDB57BECAAC4046A97C8361BFC20F67E61004039EE094191BFCE7696883598
3399AC6A6CA722C17542DDE5AC64925281D6B9DEFA6EAC3539C794E4EDF8FD032B085DD9C5A6BD85
692DD3A5981C75BBA9B02A09FEC7F7E3D68767FF523B77D5E52297AB75A5F7A920EC7CA6DC6B09CA
D48EDB6D9FFC0007C5E92C9C74FE6343F8A43B69BB06E97CF88364234F6B5FE529AB5A44CC5DB454
7CB5FA2872E31810A36CEE55C6158D90A0D6FDFC8C59BBA31A07850E883B97A7917CEF419C823AE0
CFB712D5F8683C66C7EC2602EFD574C9BC6CD558DF60FAE59D3480F1F671B697CD5C521D910396A8
um5MgxMf7nIhsv2aUAm0+sNfw98ViO/eZmT9tgCMVGilTLJJLpN0II5xyXK86hHNhe0TsvyblTe9+o1w
qE6y8vMSkig7CTOnohm6nvAVR8/aKHzdI2nFRNQOdr/6TD39uq86Zjdt6rA7R9ihjCv9Xa+wBEt5Yc5w
vFKsoSn3sSJw0tMPbXue/sq8CCdDyxzBVHVf9FjVO6P4L7lZwPCKsREmnTyGK8jJ6kf1wLDgxGUCx9eB
reHUgwFXQNC1kytrVm96sUYr6zsFlmZFhT9ln6z/4kNMQZGd07Pljhm1Xjlxu6tNW68eY0v1aRqcKBnJ
VJCjgJrV3k/bdVTYs1+g++5iLqQRZfyt0tdmILUUIm/ecBq0yl2eLOVt56LmcYAUW+KTayp95sBf0Smw
xBAeHNjdl1tA/24pKyNVtftN68lRAzDIGD9Tk7IEcCJsXkcRUCPgoPb5BKqe7MGQ9wY2ZWDDRR2XiJbg


I did it up in a little box with a 7-segment LED display and added a MAX232 chip for the serial interface and some code to grab a random number from zero to nine and display it twice a second. Even when it's not connected to a computer, it sits there displaying random numbers, looking cool and making me happy. Perhaps it's art. Source code for the box as shown below is rngbox.asm. I also wrote a program that I could call outta crontab to keep my system's /dev/random entropy pool stocked with sweet, sweet, randomness. Source code for that is read_rng.c.

I also put this circuit on an ISA card. This allowed me to generate numbers at a higher rate than 9600 baud, so I grabbed 10 megabytes worth of output and ran it through the Diehard tests. It looked good. The ISA card RNG project can be seen here.