Randomising diode

Question

I've been watching Minder DVDs and one of the extras from Series 6 is a Premium Bonds ad from 1986 which explains that their super-duper ERNIE 2 machine uses diodes (I think) that emit pulses at random intervals in order to generate random numbers for the prize draw. Unfortunately, I wasn't able to find the film on Youtube to link to! They were saying that the use of a physical randomising device makes predicting the results of the machine impossible but obviously it was an ad so they were selling a product! How good are these diodes in fact? How inexpensive would they (or similar hardware) be to add to a computer to generate random numbers instead of an algorithm? Would they produce "randomer" numbers than a time-seeded algorithm? I.e. would it be worth the cost of an extra component or are algorithms random enough for most uses?

Answer 1

There is a reasonably good article on Hardware random number generator at wikipedia.

Yes, you may want to add a 'True Random Number Generator' (TRNG) to a computer, and manufacturers do. In some applications, a TRNG is worth a premium price.

For example Sun Microsystems had a hardware random number generator board available as an extra cost option for some of their products, used for example in banking or e-commerce. It was worth paying the extra to generate a large number of truly random numbers at a high rate.

It is described at Sun Microsystems Sun Crypto Accelerator 6000

Software based random numbers use sources of entropy in the system to 'seed' their behaviour (say hard-disk head seek time). However those techniques require reasonable amounts of entropy to give them a good source of randomness. At very high rates of random number generation their isn't enough time to for the systems underlying sources of randomness to provide that. Hence the randomness may be inadequate.

Generating high quality random numbers isn't a problem restricted to web sites and the net. For example ST Micro implement a 'True Random Number Generator' on their STM32F2 and STM32F4 Cortex-M3 and Cortex-M4 Microcontrollers. Those devices are embedded devices, and so are intended to be used to implement cryptographically secure applications.

It is described in an application note called "AN4230 Application note: STM32F2xx, STM32F4xx random number generation validation using NIST statistical test suite"

It says

The True random number generator peripheral implemented on STM32 ..., and it is based on an analog circuit. This circuit generates a continuous analog noise that feed a Linear Feedback Shift Register (LFSR) in order to produce a 32-bit random number.

The analog circuit is made of several ring oscillators whose outputs are XORed."

Answer 2

You've asked several sub questions so I'll just address a couple. The whole topic of hardware random number generation is a huge multi disciplinary subject so'll I'll also further restrict this to diodes(*) and the concept of entropy.

Entropy is unpredictability, or surprisal. It comes from chaotic systems and quantum mechanics. You can think of it as rolling a die where the single spot is actually a piece of lead rather than paint. It will fall single spot down most of the time. But occasionally it will land otherwise. This is an entropy source with considerable bias as it mainly reads a "6". Most entropy sources in nature are either biased or have non uniform probability distributions. The entropy then gets converted to a uniformly distributed set of numbers via post processing and you have your true random number generator (TRNG). Like ERNIE.

The randomising diode is perfect for amateur and professional low rate random number generation. It's junction breaks down when reverse biased and creates totally unpredictable electrical noise. You can then process this entropy to extract random numbers. Maxim have a good application circuit based around a 1N759 Zener diode. Here's an extract:-

They've measured noise out to 100 MHz. If this were to be sampled at say 4 bits via a flash ADC, you might expect random numbers in the order of 100 Mbits /s. This is very much an upper limit as I've never seen a commercial diode based TRNG anywhere this speed. I'm quite chuffed to achieve 100 kbits /s.

ERNIE 1 used a similar diode like device called a thermionic valve typically used for voltage stabilisation.

You could make the point that a TRNG produces randomer random numbers than a pseudo random number generator (PRNG) but this is somewhat a semantic /philosophical argument. Some say that a TRNG is effectively the same as a PRNG as their respective outputs will be computationally indistinguishable from random. However, a PRNG is seeded with a start point and then manipulates this initial value algebraically to produce output. It you know the seed, you can totally predict the output. A TRNG has no seed. The seed is the physical diode itself and our current level of understanding means we cannot predict it's entropic output. John von Neumann famously said that "Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin."

TRNGs sound sexy. The current ERNIE (5) is extremely slow yet is marketed as a wonderful truly unpredictable system drawing upon decades of nostalgia and anthropomorphism.

*Note: Some say that the emitter base junction in a transistor is a diode which can be used for similar randomness purposes. I would draw your attention to this question why you shouldn't.