Random Number Generation


RANDOM (UNPREDICTABLE) NUMBERS

Random numbers are important in a number of cryptographic applications, and by random I mean unpredictable in a very strict sense. The following describes a random number generator based on an unpredictable physical phenomenon.

cartoon

One method of generating unpredictable numbers is to measure the time intervals between decay events of a radioactive substance.

IONIZING SMOKE DETECTOR

smoke detector photo 1 One common and inexpensive radioactive substance is Americium 241, found in household ionizing smoke detectors.

Americium 241 is a relatively soft radioactive metal with a half-life of 432.6 years. An average consumer smoke detector contains about 0.3 micrograms of Americium 241 in the form of americium dioxide. It decays to Neptunium-237 by emitting an alpha particle, with a by-product (about one percent of the emitted energy) of gamma rays. This decay is unpredicable, so if we have a way of counting and measuring this decay we can convert those data into random numbers.

In my set-up I use a First Alert model SA301B battery-operated smoke detector, basically because it was handy. Please use a detector that is not needed to protect a dwelling. They're pretty cheap and no-name brands are available at Home Depot or other home improvement stores for well under $10.

Note that the ionizing smoke detector contains radioactive material, not the photoelectric ones (unless they are the expensive dual-method detectors). The radioactive ones are easy to spot because they have unusual warnings on the label, as seen here.

smoke detector label

DISASSEMBLING THE SMOKE DETECTOR

First of all, it should go without saying that if you decide to actually attempt any of these actions that it is entirely at your own risk. I cannot be responsible in any way for any problems or injuries you may experience. If your house goes up in smoke and you glow in the dark for the rest of your short life, it's not my fault. I am simply describing what I have done -- I am not encouraging anyone to do anything. I disclaim everything.

The first step in getting at the radioactive material is to remove the plastic housing. The SA301 has a plastic lid covering the innards, connected to the base plate by way of plastic snap-in clips. Inserting a screwdriver or other thin flat tool will help in releasing the clips. A simpler option is to break or otherwise destroy the housing, since it's not needed for this application.

Removing the housing reveals a circuit board and three large assemblies. The top part appears to be some kind of filter, and is easily removed. The disk on the right is the piezoelectric buzzer (the alarm noisemaker) and the metal can on the left is what we're after.

The circuit board is held to the base plate by another set of plastic clips, which can either be pried or broken to free the board.

disassembly 1

The metal can is held in place by a security Torx screw, in this case a T10H, the head of which can be seen to the right of the can. The "radioactive material" stamp and the security screw should give the experimenter a little pause to at least be careful. First Alert probably frowns on people disassembling their detectors, and is likely trying to protect themselves from liability due to overly curious individuals.

Americium 241 is an alpha emitter, and alpha particles are the least penetrating type of radiation. Because of the low penetration of alpha radiation, Americium 241 only poses a health risk when ingested or inhaled.

It's important that the pellet containing the Americium 241 remains intact, so it would be wise not to break it, grind it, or otherwise disturb it. Problems can arise if the pellet, or parts of it, become airborne and are inhaled or otherwise ingested.

disassembly 2

Removing the lid reveals the ionization chamber where the smoke particles would be detected. Basically the Americium 241 decay induces a current flow between the two charged metal disks. If a smoke particle enters the chamber between the two plates, that current is interrupted and the smoke detector goes off. A somewhat more detailed explanation can be found here. disassembly 3

The chamber is attached to the circuit board in four places: three metal "legs" and one integrated circuit (IC) pin. Clipping or unsoldering the legs and clipping the IC pin will release the chamber from the circuit board. disassembly 4

The chamber may be split apart into upper and lower halves. The lower half (the disk on the right) contains the Americium 241. disassembly 5

This is as far as I went in disassembling the radioactive source. The disk and "legs" make an adequate base for mounting (see below). disassembly 6

MEASURING THE RADIOACTIVITY

RM60 Now that we have a source of radiation, we need something to measure it with. I use a model RM-60 Micro Roentgen Radiation Monitor from Aware Electronics. This unit is powered via a serial interface and uses four pins on a DB9 connector:
  • Pin 4: Data Terminal Ready (DTR)
  • Pin 5: Signal Ground (GND)
  • Pin 7: Request to Send (RTS)
  • Pin 9: Ring (RI)

To start taking measurements, raise DTR to power the RM-60. After a five-second charging period, the RM-60 will toggle the Ring (RI) indicator pin each time it detects a particle.

MOUNTING THE PIECES

mounting 1 mounting 2 The most expedient method of mounting for me was to use an empty cardboard box, just large enough to hold the RM-60. The chamber mounting legs are sharp enough to dig into the cardboard and hold it vertically. The sensor can be aligned so that the port will be just a few centimeters away from the radioactive source.

The distance between the sensor and the source doesn't have to be exact. It needs to be close enough to receive particles fairly frequently yet not so close that the activity rate exceeds the timing ability of the computer.

I adjusted the distance to get a fairly rapid (about 5 to 10 clicks per second) activity result from the sensor.

PROCESSING THE MEASUREMENTS

I have my RM-60 connected to the serial port of an old 486 PC running DOS. I wrote a C program to raise DTR, monitor RI and report the number of milliseconds between each detection. I use a timer source driven from the PC's 8259A Programmable Interrupt Controller rather than the standard DOS clock() to get better resolution (the DOS clock ticks about 18.2 times per second, which masks a lot of the entropy we're trying to measure).

The result of these measurements is a stream of time intervals between detections. Click here to see an example file that contains an hour's worth of raw timer intervals.

The least significant bit of the time interval is considered the "random bit." An easy way to think about this is that the absolute value of the timing measurement is not important -- the only characteristic we care about is whether the interval value is even or odd.

It is possible that the timing measurement has a bias. Said another way, it's possible that the intervals may have many more odd numbers than even, or vice versa, due to some internal behavior of the hardware or software. So, rather than using the least significant bit directly, we take a pair of bits from two adjacent values and de-skew them by taking the result according to this table:

Bit 1Bit 2Result
0 0 Discarded, no output
0 1 Output a 0 bit
1 0 Output a 1 bit
1 1 Discarded, no output

What this essentially says is that if one time interval and the next time interval are both even or both odd, both intervals are thrown out. If the first interval is even and the second interval is odd, a '0' is output as the random bit. If the first interval is odd and the second interval is even, a '1' is output as the random bit.

Eight bits from the output of the de-skewing process are placed in a byte and written to an output file. With the current setup I'm averaging about 10 bytes (80 bits) per minute into this file, or about 14 kilobytes of random data per day. Click here to see an example file that contains an hour's worth of de-skewed bits derived from the earlier interval examples.

A separate program takes batches of 2048 bits (256 bytes) from that file and passes them into the Secure Hash Algorithm (SHA-1), resulting in an output block of 160 bits (20 bytes). Click here to see an example file that contains the output from the SHA-1 algorithm using the previous example de-skewed bits.

These bytes are then used as keying material for cryptographic operations.


Please send comments to Dan Veeneman
Click here for the home page.
Updated November 12, 2002