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:

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:


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.