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: pseudo-random number generators (PRNG) and hardware-based 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 (Pseudo-Random Number Generators)

Pseudo-random 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 pseudo-random number.

• Period : The number of iterations the PRNG can perform before generating the same sequence of numbers again. A larger period indicates a higher-quality 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:

Middle-Square 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 pseudo-random 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:

1. The Multiplier (a): It influences the period and distribution of generated numbers. The choice of a is important for the quality of the LCG. A well-selected a can increase the period and result in a uniform distribution of generated numbers.

2. The Increment (c): The increment c is added to the product $aX_n$ at each iteration. It shifts the sequence of generated numbers. A good choice of c improves the quality of the generated numbers.

3. The Modulo (m): The choice of the modulus m 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 larger m 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 well-known LCGs have specific sets of parameters that have been meticulously chosen to maximize the period length. Simply increasing the size of m 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++ :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <iostream>
#include <random>

int main() {
    // a = 16807, c = 0, m = 2147483647
    std::linear_congruential_engine<std::uint_fast32_t, 16807, 0, 2147483647> rng;

    // each time rng() is called, it will perform an iteration of LCG
    for (int i = 0; i < 10; i++) {
        std::cout << rng() << std::endl;
    }

    return 0;
}

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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <iostream>
#include <random>

int main() {
    //  Mersenne Twister (PRNG) with random seed
    std::mt19937 rng(std::random_device{}());

    // Create a uniform distribution of integers between 1 and 10000 inclusive
    std::uniform_int_distribution<int> distribution(1, 10000);

    int random_number = distribution(rng);

    std::cout << "Random number : " << random_number << std::endl;
    
    return 0;
}

1.3 PRGN advantages and limits

Avantages

• Efficiency: They are generally faster and require fewer resources compared to hardware-based 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 resource-efficient.

2 - Hardware-Based 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 hardware-based 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/en-us/windows/security/hardware-security/tpm/trusted-platform-module-overview
• 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 built-in 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 lower-level 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 :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <immintrin.h>
#include <stdio.h>

int generateRandomNumber() {
   unsigned int randomValue;
   
   // Use the RDRAND instruction to generate a random number
   if (_rdrand32_step(&randomValue)) {
       return (int)randomValue;
   } else {
       // If RDRAND fails (may occur if the processor does not support it)
       return -1;
   }
}

int main() {
   int randomNumber = generateRandomNumber();
   if (randomNumber != -1) {
       printf("Random number : %d\n", randomNumber);
   } else {
       printf("Random geration failed.\n");
   }
   return 0;
}

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/awesome-hwrng

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 :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Function for mixing entropy data
void mixEntropy(unsigned char* data, size_t size) {
    for (size_t i = 0; i < size; i++) {
        unsigned char temp = data[i];
        size_t j = rand() % size;
        data[i] = data[j];
        data[j] = temp;
    }
}

// Function for generating a random number from entropy
int generateRandomNumber(unsigned char* entropy, size_t size) {

    mixEntropy(entropy, size);
    
    // Use mixed data to generate a random number
    int randomValue = 0;
    for (size_t i = 0; i < size; i++) {
        randomValue = (randomValue << 8) | entropy[i];
    }
    return randomValue;
}

int main() {
    
    // Size of the random number
    int n = 16;
    unsigned char entropy[16];

    // Initialisation de rand()
    srand((unsigned)time(NULL)); 

    // Get the entropy from the system clock

    for (int i = 0; i < n; i++) {
        entropy[i] = (unsigned char)clock(); 
    }

    // Generate a random number from entropy
    int randomNumber = generateRandomNumber(entropy, sizeof(entropy));
    
    printf("Random number : %d\n", randomNumber);
    
    return 0;
}

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++ :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <iostream>
#include <random>

int main() {
    // Seed creation with an HRNG.
    std::random_device rd;

    // Seed handling with a PRNG
    std::mt19937 gen(rd());

    // Distribution creation
    std::uniform_int_distribution<int> distribution(1, 100);

    int random_number = distribution(gen);

    std::cout << "Random number : " << random_number << std::endl;

    return 0;
}

2.5 HRNG advantages and limits

Hardware-based 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 real-time 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 chi-square test here.

The chi-square 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++ :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <iostream>
#include <vector>
#include <random>

int main() {
    const int n = 1000;
    std::vector<float> randomNumbers(n);

    //Random generation number
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<float> distribution(0.0, 1.0);

    for (int i = 0; i < n; i++) {
        randomNumbers[i] = distribution(gen);
    }

    // Test de corrélation
    float correlation = 0.0;
    for (int i = 1; i < n; i++) {
        correlation += randomNumbers[i] * randomNumbers[i - 1];
    }

    correlation = correlation / (n * (n - 1));

    std::cout << correlation << std::endl;
    if (correlation < 0.05 && correlation > -0.05) {
        std::cout << "Test passed" << std::endl;
    } else {
        std::cout << "Test not passed" << std::endl;
    }

    return 0;
}

3.2 Various Standards

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:

Sources

https://www.sciencedirect.com/topics/computer-science/mersenne-twister

https://towardsdatascience.com/chi-square-test-for-feature-selection-in-machine-learning-206b1f0b8223

https://medium.com/unitychain/provable-randomness-how-to-test-rngs-55ac6726c5a3

https://rosettacode.org/wiki/Linear_congruential_generator

https://www.electronicdesign.com/technologies/embedded/article/21252693/ncc-group-entropy-for-embedded-devices

https://fr.wikipedia.org/wiki/G%C3%A9n%C3%A9rateur_de_nombres_pseudo-al%C3%A9atoires