True Random Numbers
Let’s begin by looking at something that mostly works.
Assume a TRNG based on radioactive decay. As long as we are only talking
hypothetically, we can hypothesize a radioactive source that provides 60,000
counts per minute. (Number picked because it was 1000 per second.) A real source
that hot would be a hazard to electronic circuitry to say nothing to the danger
to living creatures.
We will generate random bits by counting the number of disintegrations for one
second. We then take the low bit of this count as a random bit. It takes 8
seconds to get a byte, but lets not worry about speed. Is this a good algorithm?
Given the 1000 counts per second this method works at least well enough. But to
see a problem pull a lead curtain between our source and our detector. Look at
what happens when the count rate drops to 15 counts per minute. We will have
three times as many zeros as ones. It’s actually a little worse than that
because in any given minute there is a significant chance of two disintegrations
in a single second. This then looks like no counts for that second. Thus we only
collect about 13 1 bits during an average minute.
WITH A LITTLE MORE COMPLEXITY
The method can be repaired at no loss of data rate as long as we have an average
of many counts per second. Change the accumulation time to 0.25 second. Then if
the low order bits of successive count pairs are different then collect the low
order bit from the first count. (Or take from the second count. But don’t switch
around.) If the bits are the same do not collect any bit for these two counts.
At 15 counts per minute this procedure produces just under 15 bits per minute.
(Is this called von Neumann elimination?)
ADDITIONAL COMPLEXITY HELPS MUCH
Let’s change our electronic hardware. Add a 4MHz counter and use it to measure
the time between disintegrations. The average value will be 4000 (4MHz /
1000 counts per second.) But now we have 2 problems. (1) How much randomness do
we have here and (2) how the !@#$% do we produce uniformly distributed bits and
bytes from these counts. Unless my math has failed me (and lately I would not
trust it) we have log2(4000) bits per disintegration. I.e. just under 12 bits
per disintegration. (Remember, log2(4096) is 12.)
Just to be safe let’s assume 10 bits of randomness per disintegration. Thus this
method gives 10,000 bits per second – 5 orders of magnitude more than our
original method. Not bad for a little electronic complexity.
Resolving our second point requires some thought. What I do is spread the raw
data values into a mixing table and run the mixing process.
But first little background...
Hardware types should understand the LFSR, Linear Feedback Shift Register.
Software types should think of a long shift register. The register is shifted
left on each clock. The bit that is shifted out the top of the register XOR’d
with one or more bits in the register to make the bit shifted in at the low end.
By selecting xor taps correctly (tables exist for this purpose) any given bit
position is nicely random with a period of one less than 2^(number of bits in
the register.) The degenerate all zero state is the “one less” of the previous
sentence.
Software types should understand the lagged Fibonacci
generator (LFG). It is no fluke that the low bits of LFG words exactly
follow the bit sequence of the LFSR with the same parameters. With proper
parameters, a LFG has a period only a little less than 2^(number of bits in the
table.)
Using a LFSR...
Now that we have the background let’s look at using an LSFR to produce uniformly
distributed bits and bytes from our counts derived from radioactive decay. I
would complement a bit in the LSFR every time I see a disintegration. (I suspect
that the easiest place to do so would be in the xor feeding the new low-order
bit. But anyplace would work just as well.)
Then assuming that we are getting 1000 disintegrations per second I would output
one bit every 400 clocks. Lower disintegration rates should, of course, output
bits at a lower rate.
Using a LFG...
Being a software type I favor the lagged Fibonacci generator as a bit mixing
device. Given 10 bits of randomness per sample I would output 32 bits every
third sample. See link for a suitable method
of seeding. My name for seeding as we use the generator is “Continuous Seeding.”
Side Notes
For the LFSR it might be a little better to use a variable sample rate. After
outputting a bit collect the next 5 bits, add 385 and use that as the number of
clocks before the next sample. Simple hardware interaction to make this work
could operate like this:
Hardware has several registers accessible by the microcontroller. After the
sample delay count is reached the hardware saves the next 8 bits in the sample
register and zeros its delay count register. Software output one of the bits in
the sample register and adds 385 to the low 5 bits in the sample register. The
sum is posted to the “sample when delay count reaches this value” register.
For the LFG one could simply output word zero of the table. But several simple
things can be done that might be better. Use the low 5 bits of last word of the
table as an index. Fetch the indexed word and the next 3 words. Xor them
together after shifting the next 3 words 8, 16 and 24 bits. Given a 32-bit
processor this operation will add only a trivial amount of overhead. As nearly
as your author can tell this added bit of nonsense will have no negative
consequences and might help a little.
Now let’s be practical
Radioactive decay is both dangerous and its detectors are expensive. By
expensive I mean that they would cost over US$5. Several choices for random
hardware are both safe and cheep. Here I would discuss the use of reverse biased
diode noise. Except I am not a hardware engineer.
With almost any noise source the thing should be setup to produce a randomly varying analog voltage in some reasonable
range. We will be using a microcontroller with an analog input. We will sample
the voltage at 30KHz. Each sample will run a seed and mash much like the
seedFIB function.
Next Topic - An inexpensive TRNG
Previous Topic
Return to Index