When I cannot make progres on my “official” projects, I like to try new things, experiment new techniques with simple devices (some complete posts on my other projects will come soon).
After some talks on the Electrolab hackerspace Mailing list, I had the idea to try random number generators. I came across this idea after realizing that good “really random” numbers are of extreme importance for online security, as they are used in SSL, GPG, and lots of other security algorithms.
There are two random number generator categories:
- Deterministic or pseudo-random number generators
- Non-deterministic or true random number generators
Pseudo Random Number Generators (PRNG)
With a PRNG, one get new random numbers from algorithms, batch after batch, by applying a given cryptographic primitive to the previous generator output. These generators can rely on encryption (AES, DES) or hashing (SHA, MD5) or other methods. Another method does not use cryptograpy but simple linear congruence relations (usually introducting specific constant values, and a modulo operation with a prime number). What these generators achieve is “deep bit mixing”, and all the mixing operations are based on the initial value used in the algorithm, the seed.
For every seed entered in the algorithm, it will produce a (hopefully) different, but unique, mixed sequence. Using twice the same seed will produce twice the same sequence, hence the deterministic name. The current system time in milliseconds is a classical seeding mechanism, since it will be different at each call, difficult to predict, and never repeat.
With well-chosen algorithms, the numbers (or stream of bits) produced usually have good randomness characteristics. But it is sometimes difficult to prove that the random sequence will never repeat, and that the bits faithfully represents a random variable with correct statistical properties. And in all cases, the produced bits only depend on the seed, which is not often desirable, since an attacker may control this seed and gain the ability to repeat the “random” sequences.
True Random Number Generators (TRNG)
A TRNG relies on a physical phenomenon to produce random values. Some examples include:
- Voltage across a (high-value) resistor: this is thermal noise
- Analog to Digital converter noise – conversion uncertainty (this method is used in the FST-01 and the NeuG project)
- Avalanche and Tunneling noise in a PN juction (diode, transistor) in breakdown conduction mode
- Atmospheric noise produced in the ionosphere, can be acquired by an FM radio receiver tuned between stations (this is the method used by the random.org website, (which I don’t like it because it can be attacked by transmitting signals on the tested frequency, which has to be kept secret. Of course alterations in randomness will be detected, but this amounts to a denial of service attack)
These generators usually rely on an analog core. A Schmidt Trigger gate can be used to produce a digital data stream with randomly spaced edges. A simple microcontroller will then be able to sample this signal, and deal with it in software.
It is then necessary to:
- Cancel any generator bias with a “cleaning” algorithm such as the Von Neumann one, that will get raw random bits in pairs, and discard pairs where both bits are equal. This means that the data throughput of such a generator is not constant.
- Make sure that the random properties of the signal are enforced. Mean, variance, autocorrelation, stuck bits and repeated patterns have to be checked for in real time.
- Emit data in a usable format (usually a serial data stream)
Some conclusions can be drawn:
- One has to make sure of the quality of the noise to get sufficiently random numbers
- The random data throughput is not unlimited! But many RNG can be coupled to used to increase it.
A first device
To apply these concepts, I decided to start with a small basic project : a noise generator. Lots of designs are available on the web, I decided to use a P-N transistor juction, just like this one:
Yes, the collector is not connected! This isn’t a mistake! Only the B-E junction of this transistor is interesting. It is biased at 12V, which is over the maximum VBE voltage from the datasheet. This does not destroy the transistor, but produces avalanche and tunneling conduction, which amounts to noise. A simple diode could have been used, but it would have required a much higher voltage, since diodes are designed to sustain high reverse voltages.
Here is a picture of the build:
This is one of the simplest circuits I’ve ever built.
For the 2N2222A, the VBE max is 6V, so 12V are enough to produce noise from the BE junction. The generated noise has a 1V peat-to-peak amplitude, which is a correct value for injection into my PC sound card. When listening to that signal, one will hear the classic “psssshhhh” hum, just like the signal between 2 radio stations. Here is a spectrum diagram produced by Audacity:
All audio frequencies are present in this signal, which is a characteristic of “white” noise, just like white light contains all wavelengths. In the high frequencies, I’m suspecting a decrease of amplitude due to filters in my soundcard, and in the low frequencies, we see a lower amplitude, probably caused by interstage capacitors and the soundcard DC-block, however there are a few peaks. Here is the same spectrum with a log horizontal scale, which produces a zoom on the lowest frequencies:
All is not so good! All of these peaks are multiple of 50Hz, which is the mains frequency here. So I’m picking up noise from the power supply! The unconnected collector transistor lead may also be picking signals.
This is very bad for random signals, because this basically means that my random data is mixed with a few pure sinusoidal signals, which means that a part of the signal repeats itself every 20 ms. This repetition is easily noticed on an autocorrelation plot, which characterizes similarity of a signal with a delayed version of itself:
According to the autocorrelation plot, this signal is not random at all. This is just a very noisy sinusoidal signal!
Here is what I plan to do for the future of this project:
- Shielding the noise generation transistor so that the collector lead does not pick up ambient signals. Also, shielding the whole generator so that no part of the device picks up noise too.
- Use a battery to power the generator, and do more measures, to check that the 50Hz noise really comes from the power supply.
- Optimize inter stage capacitors to make sure the noise bandwidth is as wide as possible
- Add strong power supply filtering to cut off external influences. This will be a very,very low pass filter, with a series association of a low value resistor (in fact, as high as possible to avoid heat, provide sufficient voltage to the transistor, while keeping the filter cutoff frequency as low as possible) and a choke inductance, followed by several bypass capacitors to the ground, in a paralle association of multiple components from picofarads to hundred microfarads.
To conclude, this was a fun experiment. I feel that some simple optimizations will bring me a clean noise generator, that will be able to enter the construction of a reliable true random number generator. I have lots of ideas, but for the moment, 3D printing is calling me!
Update Sep 19, 2013:
Jon remarked that the sound card acquisition could be the cause of the 50Hz Signal, so I made a new recording with audacity, with the same noise generation device attached, unpowered. Here is the result:
Yes, that’s a very nice and strong 50 Hz hum The harmonics are generated by a combination of this signal with the noise generator. Time to drop this sound card if I want to continue serious measurements… Thank you, Jon!
Photo by Sebastien F4GRX