On Random Number Generation

There are a lot of good ways to generate random numbers. Generally, what you want to do, is start with a good random (or at least secret) seed, and then pass it through some cryptographic function. That will get you fast and good pseudorandom numbers. This is a good solution and a solved problem!

On embedded systems though, often you can't do that -- there's not enough storage, memory, or time to run decent cryptography. Some MCUs provide a way to generate decent random numbers using their Wi-Fi chip or an internal temperature sensor. Even without that, you can generally sample the least significant bit of a free ADC pin or the microsecond timing variations of user input.

These solutions work well enough, although not all of them are secure, and most are not random. In a true random system, the next bit cannot be predicted with better than 50% accuracy, given infinite computing power, infinite time, and perfect knowledge of the system.

We can imagine how some of the systems above would fail this test:

  1. Perfect knowledge -- if you know the cryptographic key and algorithm, you can predict the next bit with 100% accuracy. Same if you know the precise temperature, user input timings, or ADC voltage.
  2. Infinite compute / infinite time -- Given enough compute and time, you can work out the encryption key and algorithm.
  3. No bias -- sampling real temperature, input timings, and voltages tends to introduce subtle bias or correlation between bits. Even if you can't predict the outcome with certainty, you can guess at better than 50% odds.

Basic Operating Principle

A common entropy source for good random number generation is the humble zener diode. Unlike normal diodes that can be damaged when you apply enough reverse voltage for them to cause avalanche breakdown, zener diodes keep working -- they are designed for this.

But what actually happens when this breakdown occurs? It's called an avalanche breakdown for a reason! When one electron pushes thought the PN junction, it knocks other electrons loose, which knock more loose, and so on. This is like a snowflake initiating an avalanche.

The exact amount of current that pushes bast the PN barrier is governed by quantum effects. So a common method would be to just measure ADC noise on a zener diode, then use some simple match to normalize the data (e.g. remove bias). This is the basis of a very good and very cheap quantum true random number generator.

What if we Used Timing Instead?

So one day, I was thinking -- the exact time an avalanche occurs should also be governed by quantum effects, right? That first electron has to tunnel through the barrier to make all the rest get moving!

So, could we design a quantum true random number generator that uses event detection, instead of measuring the avalanche amplitude? This turns out to have a few challenges.

Speed

To time things accurately, the speed of your measurement system needs to be much faster than what you're timing. If I want 8 bits of time resolution, then my sampling system must be running 256 times faster than the time between events. When dealing with quantum events this is annoying -- they have unpredictable timing, which is the whole point.

Amplification

It's not called "quantum physics" because you're dealing with a lot of atoms. Quantity = 1. So even when we are talking about avalanche events that inherently amplify the signal many times... it's still a small signal. Usually this means op-amps, and that could certainly be done, but I don't feel like using up my fancy op-amps for this. They are a few dollars each and I'm a cheapskate.

Device Selection

It turns out the avalanche events happen at a pretty high frequency for a zener. It would be a pain to measure them with a microcontroller, they occur pretty fast. I considered using a silicon photomultiplier, but of course those are even faster, around 1 nanoseccond and at very high rates. So I needed something that was slower.

Spicy Solutions

I experimented with a lot of devices. What I found was that I could use transistors (in a funny / cursed configuration) instead of zener diodes. This makes sense because of course transistors also have junctions. Eventually I found that the 2N5551 reverse biased with 12-14V produced avalanche events at a good rate. The downside is that transistors are very (very, very) not designed to handle this. They can degrade and the device can fail silently -- I left one running for about a year and no such thing happened, but your experience maybe different. I may update the design to reduce the chance of this happening.

For amplification, I recalled an old trick where you can use any inverter as an inverting amplifier -- and boy do I have a lot of hex inverters. So this can be solved for 0$ in additional parts, which appealed to me very much. There's a downside of course: hex inverters are designed to work at logic levels, and so are super inefficient as amplifiers. They actually get hot and I recommend a heat sink. It's works OK though. OK-ish. OK adjacent. It hasn't caught on fire yet anyway.

The signal looks pretty cool since the scope can't quite track it.

The Von Neumann Extractor

Finally for speed issues -- enter the Von Neumann Extractor. This is an algorithm that extracts randomness from high-entropy events. You no longer need to precisely time events. You just need to be able to measure 2 times between 3 events and decide which of the two times is longer. If the first one is, output 0. If the second one is, output 1. If they are equal, don't output and start over.

This algorithm means even I don't need very high speed to extract random numbers from my entropy source. I wrote it up in assembly on an Attiny261A, which outputs bytes to a Pi Pico W (ESP8266 / ESP32 also fine). Then I push it out MQTT so that all my devices can use it.

Statistical Analysis

I still need to perform a statistical analysis of the results. Good analyses exist for zener and transistor based entropy sources, but I'm using avalanche event timing instead of measuring with the ADC. There might be some bugs to work out.

Superficially, it looks OK though. It's producing ~8kb of entropy per second, which is quite OK! It can't push all that out MQTT right now. Sending 1 message per byte is inefficient, I should accumulate more bytes before sending.

Kindly ignore the bodge wire on the power supply.

Other Devices Based on this Design

I made two other devices based on this design. First, an I-Ching divination device (a divinator? divinatrix?). This required converting the entire Book of Changes into JSON. A J-Ching, if you will (please don't). This was running as a bot for a while on various social media platforms that I don't use. You could message it and receive a divination. I'll probably port it to this website at some point.

Then, there's the Schrödinger Trigger. This basically fires one of two outputs logic HIGH when it receives logic HIGH on an input. It acts as a sort of "illogical gate". I designed it for integration into a coffee machine, so you could prepare de/caffeinated coffee that exists in a superposition of states until you drink it. It also looks pretty cool:

A dramatic -- and helpfully labelled -- design.