Microcontrollers   PCs — Embedded Electronics





True Random Number Generation Using Comparators








 Projects Home

 Workspace Pictures

 ReAl Computer Projects

 ReAl Computer Architecture

 Site in German  









The experimental platform:

The block diagram of the experimental setup:
The bit patterns are sent to an attached personal computer executing the more complex configuration and evaluation software.

The experimental setup consists of four comparator-counter circuits. The counter contents are read out via an 8-bit data bus:

One of the  comparator-counter circuits (CT / AUX):
It comprises an 8-bit counter and an auxiliary 2-bit counter. The 8-bit counter ceases counting when 255 oscillations have been counted. If only there were a few oscillations, the entropy would be insufficient. 200 or more oscillations would not improve entropy but consume too much time. Besides, bursts of oscillations so long impede observing the comparator's behavior on the oscilloscope. The auxiliary counter contributes the two least significant bits independent of the number of oscillations.

How the input voltage is generated:
Each comparator has, depending on its reference voltage, a region of the input voltage in which oscillations will occur if traversed not too fast. This so-called VIN window is defined by a lower and an upper VIN limit. It is reached and traversed in steps.

1) In the 1st loop, the microcontroller emits coarse steps until the counter outputs begin to change.

2) Then, the region is traversed in fine steps until the counter ceases to count (2).

The VIN values at the points (1) and (2) are stored as the lower and the upper VIN limit, thus defining the VIN window.

How the basic parameters are found experimentally:
The most important parameter is the slew rate or, in other words, the dwell time in the VIN window. To secure sufficient entropy, a somewhat larger number of oscillations should be counted. On the other hand, it should not take too long to obtain a random bit. It was an intuitive decision to provide an 8-bit counter. The CNT_MIN and CNT_MAX values are parameters to be entered manually. As a starting point, we may, for example, stipulate more than 32 oscillations but no more than 128.

The Flowchart of the basic algorithm:
It can be implemented by a program or a state machine. Subtleties, like checking for errors, have been omitted.

It is an obvious procedure: try to reach the linear region fast and then traverse it within a dwell time that provides for a sufficient number of oscillations. The quality of randomness, the entropy, however, was disappointingly low. This led to further investigations of how the comparator behaves when oscillating. The result: the main source of entropy is not the number of oscillations but small variations of the pulses. When voltage, timing, and thermal parameters are nearly constant, entropy manifests itself in small variations of the comparator's output:

The entropy is extracted by sampling and evaluating count values. The process of sampling is called collaring because we do not want to reproduce the signal faithfully but to extract randomness.
This pulse diagram illustrates how oscillations are counted and counter values collared. a), b), c) show collaring pulses at different intervals.

Generate a random bit:
In a first loop, the software begins to emit somewhat coarse input voltage steps. In each step, the content of the counter is read. When its value has been changed, the linear region has been reached where the oscillations begin. Then the second loop will traverse the linear region in fine steps. The count values are collared. The second loop ends when the counter content changes no more.

The outcome depends on the distance of the collaring pulses:

How the collared values are eavluated:

Do it with hardware:
This block diagram illustrates the same algorithm. It is, however, implemented in hardware. The collared values, however, are not brought into a RAM but evaluated on the fly. This way, some or even many comparators could be operated in parallel.



MORE ...








November 22, 2020