I've long had an interest in random number generation. In fact, a very early PCB I designed and built was exactly for this purpose: Arduino Random Number Generator.
That project used a property of transistors called "avalanche noise". Inconveniently, it required a supply of +-10V to work properly. Avalanche noise is sometimes explained as being a "quantum effect" and thus is supposed to be a source of true randomness.
There are other types of physical randomness. One actually exists inside the RP2040 chip already: It has a Ring Oscillator peripheral built in. However, this project shows how to build a Ring Oscillator from a simple "78*14" chip and process it into an infinite unguessable string of bytes using CircuitPython.
I built this project with a QT Py RP2040. It's very simple; the only other required parts are the 74*14 chip, a breadboard, and some wire.
This is not a truly robust RNG and you shouldn't use it for anything serious. For example, someone could tamper with it and just remove the connection between the RP2040 and the ring oscillator; the code wouldn't notice, but its outputs would be exactly the same each time it was powered on. Real RNG products will have part of the software that verifies that the random source is behaving like a random source and is not fixed at a single value, or otherwise trivially predictable.
Ring Oscillator Theory
A Ring Oscillator is based on a ring of an odd number of Schmitt-trigger XOR gates. This project uses three gates in its ring.
The output of gate 1 is tied to the input of gate 2; the output of gate 2 is tied to the input of gate 3, and the output of gate 3 is tied to the input of gate 1.
Suppose you want to know the value that will appear at the output of each gate. Well, let's suppose the input to gate 1 is HIGH. Then we must have:
- Gate 1 input: HIGH output: LOW
- Gate 2 input: LOW output: HIGH
- Gate 3 input: HIGH output: LOW
Notice how we concluded that if the gate 1 input is HIGH, then the gate 1 input is LOW. In philosophy class, you'd call this a logical contradiction and just decide that such a thing cannot exist. But in a physical system, what happens is: Each gate takes some length of time to "drive" its output from HIGH to LOW or vice versa; and each gate has some specific input voltage to determine whether it wants to drive its output HIGH or LOW. And in fact these properties vary unpredictably from moment to moment.
The exact period of a ring oscillator like this varies from moment to moment, depending on many physical details. A lot of ink can be spilled by electronic engineers & physicists about exactly "how random" this is, but a screenshot from a scope shows clearly that over even a short period of time the crests and troughs of the output of the ring oscillator "smear out" across all possibilities:
Here, an oscilloscope is capturing the output of one of the ring oscillator gates. The overall rate of the output wave (which looks rather like a sine wave) is about 53MHz. The trigger point is at the left (marked with an orange "T") and hundreds of different captures of the data are overlaid on each other. At the right, the sine waves are smeared horizontally because the period of each individual wave varies unpredictably, even over as short a time as a few hundred nanoseconds. For our purposes we will assume that this variation contains some small fraction of "true randomness".
Using PIO to capture samples at high speed
The first step is to capture a large amount of raw data: The RP2040 has its own crystal oscillator, which is internally converted to a clock of approximately 125MHz. We can program the PIO peripheral to sample the output of the ring oscillator every cycle of that clock, or every 8 nanoseconds! This data is likely to have runs of 0s and 1s, but when you look at a larger distance (say, 100 bits or 800 nanoseconds apart) they're going to be uncorrelated because of the variation, just like the sine waves above are smeared out after a few hundred nanoseconds.
The following code creates a PIO peripheral that samples at the maximum rate. The ring oscillator output is connected to pin A3:
program = adafruit_pioasm.Program("""
in pins, 1
""")
sm = rp2pio.StateMachine(program.assembled,
frequency=125_000_000,
jmp_pin = board.A3,
first_in_pin = board.A3,
in_pin_count = 1,
auto_push=True,
push_threshold=32,
**program.pio_kwargs,
)
Using a cryptographic hash to mix random data
The code continues on, grabbing 10240 bits of ring oscillator data (320 units of 32 bits each) and sending it to the SHA1 cryptographic hash function. This produces a 40-byte (160 bit) value, which is sent to the connected host computer for further processing:
h = hashlib.new('sha1')
buf = array.array('L', [320])
while True:
sm.readinto(buf)
h.update(buf)
d = h.digest()
usb_cdc.data.write(d)
Notice how a large amount of data (10240 bits) has been mixed into a small output (160 bits) using a strong cryptographic algorithm. If we assume the cryptographic strength of the SHA1 algorithm, then it should require an infeasible amount of computational power to find out anything about the input data from the output data. And if even a single bit of the input changes, approximately half the bits of the output have to change, on average. That is, the output data has to appear to be 'perfectly random' and any little variation in the inputs leads to a huge change in the outputs.
Put another way, as long as there's "at least some" randomness in the input, it doesn't matter if there are also a lot of correlations in the input: the SHA1 process will produce random, unguessable numbers.
You also need to install the adafruit_pioasm library from the Adafruit CircuitPython bundle.
import usb_cdc
import binascii
import hashlib
import array
import board
import rp2pio
import adafruit_pioasm
program = adafruit_pioasm.Program("""
in pins, 1
""")
sm = rp2pio.StateMachine(program.assembled,
frequency=125_000_000,
jmp_pin = board.A3,
first_in_pin = board.A3,
in_pin_count = 1,
auto_push=True,
push_threshold=32,
**program.pio_kwargs,
)
usb_cdc.data.write_timeout = None
h = hashlib.new('sha1')
buf = array.array('L', [320])
while True:
sm.readinto(buf)
h.update(buf)
d = h.digest()
usb_cdc.data.write(d)
Full boot.py
The following file is required in order to enable the 2nd CDC data port. Use the reset button on your board after updating boot.py for the changes to take effect.
import usb_cdc usb_cdc.enable(data=True)
Grabbing the random numbers on a Linux PC
Here's the full code of a program to grab the random numbers and print them on standard output. You can test the quality of the random numbers with a program like rngtest:
$ python rr.py | rngtest -c 20
[...]
rngtest: bits received from input: 400032
rngtest: FIPS 140-2 successes: 20
rngtest: input channel speed: (min=395.730; avg=402.633; max=431.849)Kibits/s
rngtest: FIPS tests speed: (min=87.094; avg=113.634; max=200.774)Mibits/s
rngtest: Program run time: 987867 microseconds
# 48.86KiB @ 50.14KiB/s
#!/usr/bin/python3
import serial
import sys
import time
import os
K = 1024.0
M = K * K
G = K * K * K
def human(x):
if x >= G:
return "%.2fGiB" % (x / G)
if x >= M:
return "%.2fMiB" % (x / M)
if x >= K:
return "%.2fKiB" % (x / K)
return "%dB" % x
def main():
global c0
s = serial.serial_for_url(
"/dev/serial/by-id/usb-Adafruit_QT_Py_RP2040_DF609072DB5C3F28-if02"
)
s.timeout = None
c = -1
if len(sys.argv) > 1:
c = int(sys.argv[1])
t0 = time.time()
c0 = c
b = 0
while c:
if c == -1:
a = 4096
else:
a = min(c, 4096)
r = os.read(s.fileno(), a)
a = len(r)
if c != -1:
c -= a
b += a
try:
sys.stdout.buffer.write(r)
except BrokenPipeError:
break
t1 = time.time()
sp = "%s/s" % human(b / (t1 - t0))
if c == -1:
sys.stderr.write("# %10s @ %s\r" % (human(b), sp))
else:
sys.stderr.write("# %10s/%10s @ %s %d\r" % (human(b), human(c0), sp, a))
sys.stdout.flush()
if a < c:
time.sleep(0.01)
if __name__ == "__main__":
try:
main()
except (KeyboardInterrupt, IOError):
sys.stderr.write("\n")
if c0 != -1:
raise
This page (CircuitPython "Ring Oscillator" RNG with SN74AHCT14) was last updated on December 23, 2024.
Text editor powered by tinymce.