Introduction
Random numbers play a main role in many applications, whether it’s for ensuring system security or performing statistical simulations. If you want to start an embedded project that requires the use of random numbers and wish to avoid using the first library you have found, this article is for you.
You just need a basic knowledge of C/C++ to understand this article, even if the concepts are understandable by everyone. To understand everything, all you need is a basic knowledge of mathematics and an understanding of a few physical phenomena.
How do you generate a random number? How can you be certain that the generated number is truly random? Are there different methods for generating random numbers in the embedded domain? In this article, I will guide you and explain all the mysteries surrounding random number generation. I will begin by explaining the different methods: pseudorandom number generators (PRNG) and hardwarebased random number generators (HRNG). For both approaches, I will provide code examples in C/C++. Finally, I will show you how to test the quality of a random number sequence using tests.
1  PRNG (PseudoRandom Number Generators)
Pseudorandom number generators (PRNG) are algorithms that generate numbers in a deterministic manner but with the appearance of randomness. These algorithms produce numbers with an uniform distribution. I will explain you how these algorithms work.
1.1  How PRNG works
PRNGs operate by using an initial value called a “seed.” From this seed, the algorithm generates a sequence of numbers using mathematical operations. However, this sequence is finite and will repeat after a certain number of iterations. Therefore, the numbers are not truly random, but they are unpredictable enough for many applications.
Terminology :

Seed : The initial input value for PRNGs that will be transformed through a series of mathematical operations to make it a pseudorandom number.

Period : The number of iterations the PRNG can perform before generating the same sequence of numbers again. A larger period indicates a higherquality PRNG because it can produce many random numbers with the same seed.

Entropy : A measure of unpredictability in the data used to generate these numbers. The higher the entropy, the more unpredictable the generated random numbers are considered.
1.2  PRNG examples
In this section, we will see some examples of PRNG algorithms, from less used to more common ones:
MiddleSquare Method
Created by John von Neumann in 1946, this method involves taking a number, squaring it, and extracting the middle digits. The quality of this method depends on the initial number. Some numbers can give the same sequence (like 0).
Linear Congruential Generators (LCG)
These generators use a linear formula to produce a sequence of numbers:
$X_{n+1} = (aX_n + c) % m$
 $X_n$ is the pseudorandom number generated at iteration n.
 $a$ is the multiplier.
 $c$ is the increment.
 $m$ is the modulo, which is the maximum value $X_n$ can reach (determining the period).
The parameters a
, c
, and m
are very important in the quality and period of the generator. Here are explanations for each of these parameters:

The Multiplier (
a
): It influences the period and distribution of generated numbers. The choice ofa
is important for the quality of the LCG. A wellselecteda
can increase the period and result in a uniform distribution of generated numbers. 
The Increment (
c
): The incrementc
is added to the product $aX_n$ at each iteration. It shifts the sequence of generated numbers. A good choice ofc
improves the quality of the generated numbers. 
The Modulo (
m
): The choice of the modulusm
plays a crucial role in determining the period of the LCG. To achieve a maximum period, it’s commonly suggested that the modulo should be carefully selected, and it’s often advised to use a prime power. While a prime modulus is a typical recommendation, it’s important to note that a power of a prime can also offer similar mathematical properties.
The statement “The larger m is, the longer the period will be” can be misleading. While a largerm
has the potential to yield a longer period, it’s not always the case. The relationship between the parameters of the LCG, including the multiplier and increment, is equally important. This is why wellknown LCGs have specific sets of parameters that have been meticulously chosen to maximize the period length. Simply increasing the size ofm
without considering these parameters may not necessarily result in a longer period.
These algorithms are simple to implement, but their quality depends on the choice of parameters.
The standard values are:
 $a = 16807$
 $c = 0$
 m = $2^{31}  1$
If you want an explanation of why these parameters were chosen, you can read this:
https://www.cs.odu.edu/~cmo/classes/old/cs475sp05/leemisText/07_c21.pdf
Here is a code in C++ that implements it.
C++ :


Mersenne Twister
This PRNG is a linear congruential generator, as seen above. It uses a Mersenne prime number ($2^n  1$). It is known for its very long period and speed.
The most common parameters for Mersenne Twister are:
 $a = 2^{19937}1$
 $c = 0$
 $m = 2^{19937}1$
The Mersenne Twister PRNG is the most used in embedded systems.
Here is some code in C++ that uses the librarary random.
C++ :


1.3 PRGN advantages and limits
Avantages

Efficiency: They are generally faster and require fewer resources compared to hardwarebased generators (HRNG), which we will see later.

Reproducibility: By using the same seed, you can reproduce the exact same sequence of numbers, which can be useful in certain situations, such as for testing.
Limits

Predictability: Since the sequences are deterministic, they can be predicted if someone knows the seed. In fields like cryptography, this can create security vulnerabilities.

Entropy: The quality of generated numbers depends on the algorithm and the chosen parameters. Some PRNGs may not be suitable for applications requiring a high level of randomness.
1.4 Use in Embedded Systems
PRNGs are widely used in embedded systems because they are easy to use. There are many libraries that implement these algorithms, and they are resourceefficient.
2  HardwareBased Random Number Generators (HRNG)
Are you looking for a way to generate numbers with a higher entropy than those generated by PRNG? Welcome to the world of HRNG. These hardwarebased random number generators use physical processes to generate truly random numbers. We will see how they work, their advantages, limits, and applications.
2.1 How HRNG Work
HRNGs can be:
 Internal (integrated into the processor)
 External (module like TPM) https://learn.microsoft.com/enus/windows/security/hardwaresecurity/tpm/trustedplatformmoduleoverview
 Created from scratch by software.
HRNGs use natural processes like electronic noise and radioactive decay to create random numbers. These processes are unpredictable because they’re chaotic, sensitive to tiny changes, and lack a straightforward way to predict what will happen. HRNGs take advantage of this natural unpredictability to generate strong random numbers Here are some physical phenomena used for HRNGs.
Electronic Noise (Entropy Noise)
Electronic circuits produce electrical noise. This noise serves as entropy to create random numbers.
Radioactive Decay
Some HRNGs use the decay of radioactive particles, such as atomic nuclei, to generate random pulses.
Temperature Variation
Temperature changes in an electronic device can create variations over time that can be exploited to generate random numbers.
Funny example : lava lamps
Cloudflare uses lava lamps to enhance encryption by leveraging their inherent randomness. In the pursuit of truly random data for secure encryption keys, Cloudflare employs a hundred lava lamps positioned in their headquarters. A camera captures random patterns in the lava lamps, converting them into digital images represented by strings of unpredictable numbers. These images serve as a basis for creating highly secure SSL/TLS encryption keys, ensuring robust protection for the millions of internet properties relying on Cloudflare’s services.
2.2 Internal HRNG
Intel and AMD have integrated the RDRAND instruction (for “read random”), which is a feature of Intel processors that allows generating random numbers from a builtin hardware random number generator on some of their processors. This hardware random number generator is powered by an internal entropy source in the processor.
They have also added the RDSEED instruction, which is similar to RDRAND but offers lowerlevel access to the data generated by the hardware entropy. It is available on some Intel Broadwell and AMD Zen processors.
Here is some C code that uses the RDRAND instruction.
C :


2.3 External HRNG
If your processor does not have an internal HRNG, you can use an external HRNG. These HRNGs come in the form of modules, often USB sticks. Here is a list of many of these modules: https://github.com/atoponce/awesomehwrng
2.4 Build your own Random Number Generator
If you don’t have an internal HRNG and don’t have the budget to buy an external HRNG, there is still a solution:
create your random number generator using the physical properties that your board offers for the HRNG and combine it with PRNG.
I will show you how.
The first step is to select a source of entropy. You can use various physical characteristics of your board for this:

System Clock: Variations in the system clock, depending on factors like temperature or electrical noise, can be used as a source of entropy.

Sensors: Temperature, humidity, or acceleration sensors can provide constantly changing data to fuel your HRNG.

Hard Drive Activity: The movement of the read/write arm and speed fluctuations of a hard drive can be exploited to generate entropy.

Network Data: Network packets, their timing, and arrival order can be used to obtain entropy.
Once you have chosen your source of entropy, you can sample it at regular intervals and mix it to increase entropy.
Here is some C code that uses the system clock for entropy. This code also mixes the entropy generated for greater randomness.
C :


This C++ code uses std::random_device which creates a random integer distribution from a hardware source but it is not specified which one.
C++ :


2.5 HRNG advantages and limits
Hardwarebased random number generators (HRNG) have a number of advantages and limits in the context of embedded systems:
Avantages

High Entropy: HRNG generally offer high entropy, meaning they produce random numbers with high unpredictability.

Reliability: HRNs are less susceptible to correlations bias compared to some PRNG. This is important for enhancing security.
Limits

Complexity: HRNG require an understanding of the exploited physical phenomena, which can make their development more complex.

Limited speed: HRNG based on physical phenomena such as electronic noise may have limited speed compared to software PRNG. This can limit random number generation in realtime applications.
3  How to test the RNG
It is crucial to test the quality of a random number generator to ensure its reliability. There are different types of tests:
 Statistical Tests
 Pattern Tests
 Correlation Tests
3.1 Different Types of Tests
Statistical Tests
Statistical tests are used to check the distribution of randomly generated numbers compared to the expected distribution. I will introduce the chisquare test here.
The chisquare test is a statistical method used to determine if significant differences exist between observed and expected frequencies in a data set. It evaluates whether the variations between these frequencies are significant enough to be considered more than caused by the luck.
Formula : χ2 = ∑(Oi – Ei)2/Ei
Oi: Observed value Ei: Expected value
Pattern Tests
Pattern tests are used to check for the presence of patterns in randomly generated numbers. The principle involves converting the number to binary and detecting the repetition of sequences of 0 and 1. The more repeated sequences there are, the less random the number is considered.
Correlation Tests
Correlation tests are used to check whether the sequence of generated numbers is correlated. The lower the correlation, the more randomly the numbers are generated.
This test involves multiplying the values of elements shifted by a distance ‘k’ and summing these products. Finally, this sum is divided by the product of the total number of elements in the sequence and the total number of offset pairs.
Here is a C++ code that implements a correlation code.
C++ :


3.2 Various Standards
Standard  Description 

SP 80090A  Recommendation for Random Number Generation Using Deterministic Methods (PRNG) 
SP 80090B  Recommendation for the Entropy Sources Used for Random Number Generation and the Testing of Entropy Sources 
SP 80090C  Recommendation for Random Number Generator Constructions 
SP 80090  Validation through the Cryptographic Algorithm Validation Program (CAVP) and the Cryptographic Module Validation Program (CMVP) of NIST 
SP 80022  A set of Statistical Tests for Random and Pseudorandom Number Generators for Cryptographic Use 
Conclusion
To conclude, there are several methods for generating random numbers in embedded systems. Not all of these methods are equal in terms of quality, complexity and cost, and the choice of generator you use depends on the quality of the random number you want.
To resume, here are the main differences between the different types of random number generator:
Method  Description 

Pseudorandom number generator (PRNG)  Easy to implement, many libraries available. Suitable for solutions that are not critical for reliability. 
Hardware random number generator (HRNG)  Considered the best method for a highly reliable random number generator that is difficult to crack. Can be implemented using a module on your card or by purchasing an external module. 
Mix of PRNG and HRNG  A commonly used method. If a dedicated HRNG is not available, you can leverage the random characteristics of your card and combine this entropy with a PRNG to create a robust random number generator. 
Sources
https://www.sciencedirect.com/topics/computerscience/mersennetwister
https://medium.com/unitychain/provablerandomnesshowtotestrngs55ac6726c5a3
https://rosettacode.org/wiki/Linear_congruential_generator
https://fr.wikipedia.org/wiki/G%C3%A9n%C3%A9rateur_de_nombres_pseudoal%C3%A9atoires