2015 IEEE 21st International Symposium for Design and Technology in Electronic Packaging (SIITME)

Into Generating True Random Numbers - a Practical

Approach using FPGA

Andrei Marghescu, Paul Svasta

“Politehnica” University of Bucharest, CETTI
Bucharest, Romania
andrei.marghescu@cetti.ro
paul.svasta@cetti.ro

Abstract— True Random Numbers represents a sensitive The noise generator is the black box used for generating
research area for cryptographic algorithms and applications. random sequences. It is based on different kind of physical
They are mostly used in generating non-reproducible and non- unpredictable phenomenon, like cosmic radiations, oscillators
deterministic patterns used in different cryptographic protocols. jitter, sound and light propagation throughout different
A True Random Number Generator basically consists of three environments, etc.
main components: a noise generator, that is based on a physical
incontrollable phenomenon, a randomness extractor (for The randomness extraction box is used to aid the generator
assuring that the generated bits are uniformly distributed), and a to uniformly distribute the 0 and 1 bits along the output. The
randomness testing battery. Over the last years, since the Randomness Testing block consists of a set of statistical tests,
hardware technologies evolved, the random number generation used for testing the randomness of the output. The last two
became (once more) an attractive research field, channeling a lot blocks are based on purely mathematical concepts.
of efforts from the research communities worldwide. As a
consequence, the True Random Number Generation process The paper is structured as follow: the second chapter will
became more detailed and was elaborated in international describe the most known and most reliable noise sources that
standards (for example the NIST -National Institute of Standards are used in generating random numbers.
and Technology- standard). This paper presents some novel
The third chapter presents the Randomness Extraction and
practical approaches on True Random Number Generation, and
some personal deviations of some classical approaches, using the
Randomness Testing blocks, describing how the raw data
most common noise generator, based on oscillators jitter, used in acquired from the noise generator are transformed into a true
different contexts and variations, implemented in FPGA logic. random sequence. The forth chapter presents mechanisms used
Moreover, the paper describes the whole generation process, for emphasizing the randomness within physical phenomenon.
presenting, in comparison, the testing results of the generators The fifth and the sixth chapter presents the personalized
shown in the paper. solution, its implementation and results.
Keywords— TRNG, cryptography, FPGA, jitter, security II. NOISE SOURCES
I. INTRODUCTION The pillar of the TRNG is the noise generator, which has to
be completely unpredictable. For this purpose, as a noise
It is well known that starting with a good mathematical
generator, the most common source is represented by the jitter
concept (like a LFSR), someone can build a random number
found in the ring oscillators [6] [7]. Over the last years, the
generator, called a Pseudo Random Number Generator
most discussed setup for a TRNG is presented by Sunar et al.
(PRNG), obtaining the same randomness test results as a good
in [1] (Fig. 2), where they are combining a large amount of ring
True Random Number Generator (TRNG). This generator is
oscillators, whose outputs are modulo 2 added, being sampled
basically a deterministic one since each output is a function of
at a frequency given by another ring oscillator.
the previous one. Although in some particular cases the
deterministic property is very useful, in most cases it can Another good approach of an oscillator based TRNG is
become the greatest vulnerability of the whole cryptographic called TERO and has been described in [2] [3] and Fig. 3. The
system. This is why a TRNG consists of three main advantage of this approaches is that they can be easily be
components as described in Fig. 1. implemented using a FPGA.
A. Oscillator’s Jitter
It is well known that each oscillator has a jitter [8]. This
jitter is influenced by different kind of factors, such as
operating temperature, the stability of the power supply,
Fig. 1 - TRNG fabrication imperfections for the components that make them to
be slightly different, ambient thermal noise or vibration, etc.

978-1-5090-0332-7/15/$31.00 ©2015 IEEE 319 22-25 Oct 2015, Brasov, Romania

 2015 IEEE 21st International Symposium for Design and Technology in Electronic Packaging (SIITME)
The most known oscillator that is used for its jitter is the B. TERO Generator
Schmitt Trigger oscillator (Fig. 2) and its jitter can be observed Another very good noise generator is describes in [2] by
in Fig. 3. Varchola, Michal, and Milos Drutarovsky. This generator got
the name of TERO and its scheme is described in Fig. 5.

Fig. 5 – TERO Generator [2]

Fig. 2 – Schmitt Trigger Oscillator Since TERO’s concept gain some terrain among random
number generators, Haddad, Patrick, et al presented, in [3], a
personalization of it, using a simpler scheme consisting of
logical gates: NOT and NAND (Fig. 6). The scheme consists of
an even number of invertors for each block.
Since the measurement of such signals implies a very
performant Oscilloscope, the waveform, presented by Haddad,
Patrick, et al in [3] is presented in Fig. 7.

Fig. 3 – Schmitt Trigger Oscillator’s Jitter [4]

The second most known oscillator for its jitter is the Ring Fig. 6 – TERO Generator Simplified
Oscillator, consisting of an odd number of invertor gates that
are connected in a ring structure (Fig. 4). This oscillator is
probably the most used one because of its simplicity in FPGA
implementation.

Fig. 4 – FPGA Schematic of a Ring Oscillator Fig. 7 – TERO Output [3]

The difficulty of this approach is in finding a good scenario TERO is basically a circuit that oscillates temporarily until
in which multiple oscillators that are oscillating at different it stabilizes at a value (0 or 1), having as input a selector
frequencies can generate a non-deterministic output. For this, (control) which tells it when to start and when to stop. The
Sunar et al. [1] proposed a solution based on a combination of number of oscillations is pure random.
a large amount of ring oscillators and demonstrated
mathematically that his solution is stable and reliable. III. RANDOMNESS EXTRACTION AND TESTING
Our previous work [5], presented Sunar’s solution, adapted Each Noise generator comes with a bias, meaning that it
and implemented in a Zybo ZYNQ System on Chip Platform generates one of the two states (0 and 1) with a higher
and the results obtained with his approach. That paper probability. In sensible applications this bias has to be the ideal
describes also a new approach, based on Sunnar’s one, with the value of 0. For this to become true, the Randomness Extractor
corresponding results. intervenes.

978-1-5090-0332-7/15/$31.00 ©2015 IEEE 320 22-25 Oct 2015, Brasov, Romania

 2015 IEEE 21st International Symposium for Design and Technology in Electronic Packaging (SIITME)
For the presented solutions, the Von Neumann randomness Manipulating this king of phenomenon can imply different
extractor was chosen, since it is the most common in the techniques for each source. For Ring Oscillators we can use the
cryptographic field. This function works with pairs of two following techniques [4]:
outputted bits, discarding every pair where the bits are the same
(00 and 11) and outputting the first bit of the other pairs. • Counter Technique (Fig. 8) – is based on the
measurement of the jitter’s period. Usually the least
It is a good practice for testing each embedded device [9] significant bit of the result is used as the output of the
that generates Random Sequences. The role of the Randomness generator.
Testing is to determine if the sequence that is to be tested has
some kind of mathematical pattern. Statistical test batteries are • Desynchronization Technique (Fig. 9) – is based on
applied to the output data of the Randomness Extractor and for running a large number of ring oscillators that run on
the presented solutions, the following tests were chosen: different frequencies. The output of the generator is the
mod 2 sum of each ring oscillator output. This method
• Frequency test – this test counts and analyzes the number of implies a sample clock frequency that decides when to
apparitions of 1 and 0 within the output; check the states of the oscillators.
• Block frequency test – this test works the same as the first
one, but it analyzes blocks of data;
• Cumulative sums test – this test is works with partial
sequences within the tested ones, calculating the sum of
them;
Fig. 8 - Counter Technique
• Runs test – this test identifies identical sequences of bits,
calculating the number of runs that the sequences occur;
• Longest run test – this test works as the previous one and
calculates the length of the longest run;
• Rank test – this test computes the rank of disjoint matrixes
that were create using the tested sequence; Fig. 9 - Desynchronization Technique
• Fast Fourier transform test – this test uses the Fast Fourier When using the TERO generator, a counter is used to count
Transform, calculating and interpreting the peak heights; the number of temporary oscillations. The resulting bit of the
• Non-overlapping test – this test uses some predefined generator is the least significant bit of the counter.
patterns, calculating the number of occurrences; V. PERSONALIZED SOLLUTION
• Overlapping test – the purpose of this test is the same as the Starting from our previous work [5], where the TRNG
Overlapping one but, instead, it uses different search based on a large amount of Ring Oscillators had been tested,
engines; this research was conducted over the personalized solution
described in Fig 10.
• Universal test – this test tries to compress the sequence. The
idea behind this test is that a true random number cannot be
efficiently compressed (the compress ratio being very
small);
• Approximate entropy test – this test calculates the
frequency of n-bit blocks and the frequency of n+1-bit
blocks and compares them;
• Serial test – this test counts all the occurrences of fixed
length patterns;
• Linear complexity test – this test generates the length of an
equivalent LFSR (Linear Feedback Shift Register) that
would generate this sequence [5].
IV. ENTROPY EXTRACTION TECHNIQUES
It is well known that random sources exist due to
fabrication imperfections, operating temperature, the stability
of the power supply, ambient thermal noise or vibration, etc.
The hardest thing is extracting it. Manipulating a phenomenon Fig 10 - Proposed True Random Number Generator
that lasts for 20 ns (as the jitter of an average ring oscillator) The proposed solution uses 115 free running Ring
isn’t that easy as it looks like. Oscillators that consists of 3, 5 and 7 invertor gates each. The
output of every RO is added mod 2 (XOR) and connected to a

978-1-5090-0332-7/15/$31.00 ©2015 IEEE 321 22-25 Oct 2015, Brasov, Romania

 2015 IEEE 21st International Symposium for Design and Technology in Electronic Packaging (SIITME)
D Flip Flop. The clock of the D Flip Flop is connected to one The results of all the solutions presented within this paper
TERO Generator. The scheme works as follow: can be found in Chapter VI, and in our previous researches [4]
and [5].
• The Ring Oscillators runs freely;
This work can be viewed as a hands-on tutorial on how to
• The output of each oscillator is connected to a create a True Random Number Generator. It describes in detail
XOR gate implying permanently output of data; how to build a generator that is based on the most known noise
• The data from the XOR gate is sampled when the generators and describes how they work. Moreover, it proposes
TERO generator output is high (1). In other words, a personalized solution that was implemented and tested, and
when the TERO generator output is 1 the XOR the results recommend it to be used as a True Random Number
gate is “consulted”. Generator.

VI. IMPLEMENTATION AND RESULTS ACKNOWLEDGMENT

The presented solution was implemented and tested using a The authors would like to express their gratitude to AFCEA
Zybo ZYNQ System on Chip development board, powering an International for the financial support. This paper was
ARM Cortex Microprocessor and an ARTIX 7 Equivalent published under the frame of the “Partnerships in priority
FPGA, developed by Xilinx. areas” (PN II) Romanian Research program, developed and
supported by MEN-UEFISCDI, BLCPL project, PN-II-PT-
Von Neumann randomness extractor was chosen for this PCCA-2013-4-1546, no. 58/2014.
solution and the results of the NIST randomness test batteries
applied to 100MB of data are described in Table 1.
REFERENCES
Test Passed/Total Result
Frequency 2/2 passed
[1] Sunar, B.; Martin, W.J.; Stinson, D.R., "A Provably Secure True
Block Frequency 2/2 passed Random Number Generator with Built-In Tolerance to Active Attacks,"
in Computers, IEEE Transactions on , vol.56, no.1, pp.109-119, Jan.
Cumulative Sums 4/4 passed 2007;
[2] Varchola, Michal, and Milos Drutarovsky. "New high entropy element
Runs 2/2 passed
for FPGA based true random number generators." Cryptographic
Longest Run 2/2 passed Hardware and Embedded Systems, CHES 2010. Springer Berlin
Heidelberg, 2010. 351-365;
Rank 2/2 passed [3] Haddad, Patrick, et al. "A Physical Approach for Stochastic Modeling of
FFT 2/2 passed TERO-based TRNG." Workshop on Cryptographic Hardware and
Embedded Systems, CHES 2015. 2015;
Non Overlapping 294/296 passed [4] Andrei Marghescu, Paul Svasta, and Emil Simion. " Randomness
Extraction Techniques for Jittery Oscillators" Electronics Technology
Overlapping 2/2 passed (ISSE), Proceedings of the 2015 38th International Spring Seminar on.
Universal 2/2 passed IEEE, 2015;
[5] Marghescu, Andrei, et al. "Adapting a ring oscillator-based true random
Approximate Entropy 2/2 passed number generator for Zynq system on chip embedded platform." Design
and Technology in Electronic Packaging (SIITME), 2014 IEEE 20th
Random Excursions 16/16 passed International Symposium for. IEEE, 2014;
Random Excursions Variant 36/36 passed [6] Wold, Knut, and Chik How Tan. "Analysis and enhancement of random
number generator in FPGA based on oscillator rings." International
Serial 4/4 passed Journal of Reconfigurable Computing 2009 (2009): 4.
Linear Complexity 2/2 passed [7] Bochard, Nathalie, Florent Bernard, Viktor Fischer, and Boyan
Table 1 – Results Table Valtchanov. "True-randomness and pseudo-randomness in ring
oscillator-based true random number generators." International Journal
of Reconfigurable Computing 2010 (2011).
VII. CONCLUSIONS
[8] Andrei Drumea, Robert Dobre, “Clicks counting methods for a scope
This paper analyzed and described some methods on how knob”, “HIDRAULICA” Magazine of Hydraulics,Pneumatics,
one can generate True Random Numbers using a FPGA. It Tribology, Ecology, Sensorics, Mechatronics, No. 4/2013, ISSN 1453 –
described the need for a stable noise generator and presented 7303, pp. 79-84;
some tested solutions that can be used for this purpose. [9] Andrei Drumea, Robert Alexandru Dobre, "Modelling, simulation and
testing of an autonomous embedded system supplied by a photovoltaic
panel", 20th International Symposium for Design and Technology in
Electronic Packaging, SIITME2014, October 2014, pp.309-312

978-1-5090-0332-7/15/$31.00 ©2015 IEEE 322 22-25 Oct 2015, Brasov, Romania