Using a random number generator in Arduino: Random and RandomSeed functions. Arduino Course - Time and Random Arduino generating a random bit sequence
When programming Arduino, there are times when you need to get a number that will not be known in advance either to the programmer writing the sketch or to the user who will use the Arduino with such a program. In this case, a random (or rather pseudo-random) number generator comes to the rescue.
To activate this generator, just use the random() or randomSeed() functions. This material will show you how to work with these functions, as well as how to get rid of pseudo-randomness when generating numbers.
In general, a pseudorandom number generator simulates the chaotic or random appearance of numbers, but in fact, if you analyze a series of these numbers over a sufficiently long period, you can notice a certain pattern.
So, the random function for generating pseudo-random numbers can have up to two parameters and is written as random(max) or random(min, max). Here max parameter, which is mandatory, specifies the upper limit of the range for generating pseudorandom numbers. By using additional parameter min you can set the lower limit of the range. As a result, the function will return some pseudo-random number in the range from min to max-1.
It is important to understand that when using the random() function, the exact same list of pseudo random numbers will be generated each time. For example, if you make a slot machine and the first time you press the handle, it shows a winning combination, then you can be sure that if you reset the Arduino and press the handle again, that slot machine will show the same winning combination. Indeed, it is not easy to implement a gaming machine with completely random number generation on Arduino, as is, for example, implemented in gaming machines www.igrovye-apparati-vulcan.com/, but you can partially solve the problem using the randomSeed() function.
This function takes a value (such as an integer), and uses the number to modify the random list generated by the random() function. You can put randomSeed() in the setup function, and use the random() function in an infinite loop. But even then, the catch is that although the random number sequence will be different when using the randomSeed() function, it will still be the same every time the sketch is run.
The only solution in this case may be to use analog peripherals (ADC) and the corresponding analogRead() function. If the analog input is not connected to anything, that is, left “hanging” in the air, then thanks to the noise on this line you can get truly random numbers. Then in the setup setting you can write randomSeed(analogRead(A0)). Provided that analog port A0 is not connected anywhere.
A lot has been written about random number generators, but almost always when it comes to implementation, it is implied (or explicitly stated) that we're talking about about x86/x64 and other “adult” architectures. At the same time, forums dedicated to the development of devices on microcontrollers are full of questions “how can I generate a random number at %controllername%?” Moreover, the range of answers extends from “look at Google/Wikipedia” to “use the standard function.” This “standard function” does not always exist and suits the developer in all respects; more often it’s the other way around: sometimes the numbers are far from random, sometimes the speed of operation is too low, or sometimes the resulting code does not fit into free memory at all.
Let's try to figure out what random number generation algorithms are, how to choose the right one, and most importantly, what are the features of implementing these algorithms on controllers.
Assessing "randomness"
The applications for RNG can be very different, from toys to serious cryptography. Accordingly, the requirements for the generator also vary greatly. There are special tests to assess the quality (level of “randomness”) of the generator. Here are the most basic of them:- Frequency test. Consists of counting the number of zeros and ones in a sequence of bits. There should be approximately equal numbers of ones and zeros.
- Test for a sequence of identical bits. Rows of identical bits are searched, like 000...0 or 111...1. The distribution of frequencies with which the series occur, depending on their length, should correspond to this distribution for a truly random signal.
- Spectral test. A discrete Fourier transform is applied to the original sequence. The resulting spectrum should not have significant peaks that would indicate the presence of periodic properties of the sequence.
- Autocorrelation test. The correlation value between sequence copies shifted relative to each other is calculated. The test allows you to find repeating regions in a sequence.
NIST - used in the AES competition to evaluate encryption algorithms.
DIEHARD is one of the most rigorous sets in existence.
PRNG Algorithms
Any sequence generated according to a strictly defined algorithm cannot be considered truly random, therefore, when talking about algorithmic generators, they use the term pseudorandom subsequence. Any pseudo-random number generator (PRNG) will go into loop sooner or later, the other thing is that this “late” can come in a few milliseconds, or maybe in a few years. The length of the cycle depends on the size of the internal state of the generator N (in fact, this is the amount of memory needed by the generator), and ranges from 2 (N/2) to 2 N bits.A huge variety of PRNG algorithms have been invented, but not all of them are convenient for implementation on microcontrollers. We are severely limited in speed and available memory; many controllers do not support real arithmetic or even multiplication instructions. Keeping these limitations in mind, let's look at some well-known algorithms.
Linear congruent method
The next member of the sequence is calculated using the formulaX i+1 = (aX i + c) mod m
Number m defines the maximum period of the sequence, integers a And c- “magic” coefficients. Number m It is reasonable to choose equal to a power of two; in this case, the modulo conversion operation is reduced to discarding the most significant bits. In order to obtain the maximum period, the following conditions must be met:
- c and m must be relatively prime,
- a-1 must be a multiple p for all prime factors p numbers m,
- If m is a multiple of 4 (and in our case it will be a multiple), then a-1 must be a multiple of 4.
There is one more subtlety: only the most significant bits of the state variable X should be taken as the result, since for the lowest bits the statistical parameters of randomness are much worse. The linear congruent algorithm is commonly implemented as standard rand() in many libraries.
Pros:
- the maximum possible period for a given size of the state variable;
- fast enough;
- often already implemented in the compiler library.
- a multiplication operation is required;
- not all bits are equally random.
Fibonacci method with lags
This algorithm uses the relationX i = X i-a - X i-b ,
where is the state variable X- unsigned integer. Delay values a And b not just any, but strictly defined ones are taken; to achieve maximum quality, pairs (17.5), (55.24) or (97.33) are recommended. The greater the delay, the longer the period and the better the spectral properties of the sequence. On the other hand, for the generator to work, it is necessary to store max(a,b) of previous numbers, which is not always acceptable. Also, to run the generator you need max(a,b) numbers, which are usually obtained using a simpler PRNG.
Pros:
- does not require multiplication operations;
- all bits of a random number are equivalent in statistical properties.
- requires a large amount of memory;
- requires a large array of numbers to run.
Linear Feedback Shift Register
The state variable is stored in a register of length N. Generating the next state involves two steps:
- The value of the bit is calculated C = X i1 xor X i2 xor… X ik, where i1, i2…ik- register bit numbers, called bends.
- The register is shifted 1 bit to the right, the leftmost bit takes on the value WITH.
In addition to the configuration described above, which, by the way, is called the Fibonacci configuration (not to be confused with the PRNG method of the same name!), there is the so-called. Galois configuration.
Instead of using the sum of the bits in the tap sequence to generate a new leftmost bit, it XORs each bit in the tap sequence with the rightmost bit, then rotates the entire register to the right. This scheme is more difficult to understand, but easier to implement, since all XOR operations can be performed simultaneously. In terms of period length and quality of pseudorandom numbers, Fibonacci and Galois schemes are equivalent.
Pros:
- very simple implementation, doesn’t even require arithmetic, only bit operations and shifts;
- very fast algorithm (especially the Galois scheme);
- good statistical properties.
- you need to check the initial value for inequality to zero.
Cryptoproof algorithms
For use in cryptography, PRNGs have one more essential requirement: irreversibility. All the algorithms listed above do not have this property: knowing several output values of the PRNG, you can, by solving a simple system of equations, find the parameters of the algorithm (the same “magic” constants a, b, c etc). And knowing the parameters, you can reproduce the entire pseudo-random sequence.Any sufficiently strong block cipher can be used as a cryptographically strong PRNG algorithm. By choosing a secret key, you can obtain blocks of pseudorandom numbers by applying the algorithm to sequential natural numbers. For an N-bit block cipher, the period will be no more than 2 N. The security of such a scheme depends entirely on the secrecy of the key.
All modern cryptographic algorithms are tested for use as PRNGs, that is, using a certified algorithm, there is no need to specially care about the statistical and spectral properties of the output stream. You only need to worry about the computational “gluttony” of crypto algorithms. If you need to perform a large number of encryption operations, it makes sense to choose a controller with hardware cryptographic blocks. Often such controllers also have a very good crypto-resistant hardware PRNG.
Sources of entropy
As already stated, using only deterministic algorithms, it is impossible to generate a truly random number. Therefore, a combination of PRNG + external is usually used source of entropy. The entropy source is used to set the initial value for the PRNG, and the latter’s task is to ensure the spectral and statistical purity of the sequence. What can be used as a source of entropy? Yes, almost anything.User activity
If the device interacts with the user in any way, quite good decision will use the user himself as a source of entropy. For example, the time of pressing a button, measured with an accuracy of a microsecond (or rather, its least significant digits), is completely unpredictable. However, often the device must work autonomously, which means we are deprived of this wonderful channel of information.Analog-to-digital converter
Many controllers have built-in ADCs. And in many controllers they are of very mediocre quality, made just “to be.” The low-order bits of the ADC result almost always contain significant noise, even when measuring DC voltage. This can be used: connect the ADC input to the supply voltage through a divider, take a few dozen measurements, take the least significant bits - here you have a great random number. If the ADC contains a built-in preamp, turn it on, it is also noisy.Asynchronous generators
You can use the difference in periods of two unsynchronized clock generators. Most controllers contain, for example, a watchdog timer. To increase reliability, it is clocked from a separate generator, which is in no way connected with the main clock signal. It is enough to count the number of cycles of the main clock signal during one period of the watchdog timer. If you choose periods so that the counter overflows many times during the measurement, you can get a fairly random number. The disadvantage of this method is that it takes a lot of time, up to several seconds.Real time clock
If the diagram has real time clock, you can use their current readings to initialize the PRNG. For example, by converting the current date/time to the Unix time format, we immediately get 32 bits, which never will not happen again unless you take readings more than once per second. Using real time gives uniqueness of values, but does not provide any unpredictability, so it is better to combine this method with others.RC circuit
If the controller has no peripheral devices, in addition to the I/O ports, you can do the following: one of the legs is connected through a capacitor to ground, and through a resistor to the supply voltage. If the controller inputs have internal pull-up resistors, an external resistor is not needed.
We output a “0” signal to this port - the capacitor is discharged. We switch the port to input mode - the capacitor begins to charge. When the voltage across it reaches the threshold, the input will switch from state “0” to “1”. The charging time strongly depends on many factors: supply voltage, drift of RC circuit parameters, threshold instability, temperature, leaks, interference. By measuring it with sufficient accuracy and taking the least significant bits, you can get good randomness.
Hardware noise generator
For many serious applications (most notably cryptography), a more reliable source of entropy than those listed above is required. In such cases, they use digitization of the signal from a noise generator based on thermal, shot, or even quantum effects. The noise element is usually a special diode or zener diode, the signal from which is amplified and fed to a comparator that generates a binary bit stream.
To ensure that the comparator response threshold does not affect the statistical properties of the received signal, two noise generators are used, operating on one comparator:
Conclusion
Finally, I’ll tell you one story from my life. It started with another question asked on the forum: “how can I generate a random number on the controller?” The author of the question explained that as a course project he is making a device that emulates throwing dice. After several unsuccessful attempts to understand the algorithms, the topicstarter shared his solution: he simply rolled a real die 1000 times and filled all the free memory of the controller with the resulting numbers. The generator brilliantly passed all the “randomness” tests, given that during the demonstration it used up less than a third of its “reserve”.Therefore, such a solution also has a right to life, especially if very strict requirements are imposed on the randomness of numbers, but they are not required too often. With memory prices plummeting, it may be wise to equip a device with a "chaos reserve" that will last the entire life of the device.
Thank you for attention!
UPD1: As was rightly noted in the comments, if an attack on the RNG is expected, and the attacker has hardware access to the device, external sources of entropy must be used with great caution, since it is not very difficult to replace the signal from external source. Internal sources should be used, in addition to external ones.
It's also a good idea to accumulate entropy everything free time, and use it when you need to generate another random number. Usually in such cases the so-called Entropy pool- an array over which one of the PRNG functions is periodically performed, and into which data from entropy sources is constantly mixed.
UPD2: In many cases, it is useful to save the contents of the Entropy pool (sorry, I don’t know the normal Russian translation) in EEPROM so that after turning the device off and on it does not accumulate it again. This relates, first of all, to obtaining entropy using the method of asynchronous generators: under sufficiently stable conditions, the same sequence can be generated after each switching on.
If an attack is expected, take precautions against EEPROM tampering. If the controller allows it, block reading/erasing/writing using lock bits, and when turning it on, monitor the integrity of the EEPROM, at least using simple checksums.
Tags:
- RNG
- gpsch
- microcontrollers
- algorithms
randomSeed(seed)
Sets the value, or seed, as the starting point for the random() function.
randomSeed(value); // sets 'value' as the initial random value
Since the Arduino can't generate truly random numbers, randomSeed allows you to put a variable, constant, or other function into the random function, which helps generate more random numbers.
"random" numbers. There are many different seeds, or functions, that can be used in this function, including millis(), or even analogRead() to read electrical noise through an analog pin.
random (max)
random(min,max)
The random function allows you to return a pseudo-random number within the range specified by the min and max values.
value = random(100, 200); // sets 'value' to random
// a number between 100 and 200
Note: Use this after using the randomSeed() function. The following example creates a random number between 0 and 255 and outputs the PWM
signal to the PWM output equal to a random value:
int randNumber; // variable to store a random value
int led = 10; // LED with resistor on pin 10
void setup() () // setup is not needed
randomSeed(millis()); // sets millis() with the initial number
randNumber = random(255); // random number from 0 – 255 analogWrite (led, randNumber); // output PWM signal
delay(500); // pause for half a second
Source: Gololobov V. – Where do robots begin. About the Arduino project for schoolchildren (and not only) – 2011
Related Posts
Serial.begin (rate) Opens the serial port and sets the speed for serial data transfer. The typical baud rate for computer communications is 9600, although other speeds are supported. void setup() (Serial.begin…….
All variables must be declared before they can be used. Declaring a variable means defining the type of its value: int, long, float, etc., assigning a unique name to the variable, and additionally…….
Okay, we have installed this program. We have debugged the “mechanism” of working with the module. And we looked at several examples. But I would like to create something useful myself. Let's try. First, let's close the previous project. For this…….
Attention! When working with the Arduino module in other development environments, you should be careful about the microcontroller configuration (Fuses). Until you know exactly what the change might lead to…….
Time and randomness. Reaction
This time we will learn what “Random” values are and also learn how to work with time.
We will need:
- Tact button
- Squeaker
- Connecting wires “MALE-MALE”
Reaction
Our task for today is to assemble a diagram that allows us to find out the speed of our reaction.
When you click on left button, a signal sounds after a “random” time. And when you press the right button, it is noted how much time has passed from the squeak to pressing the right button.
Those who are skilled try it themselves, and we look at the diagram.
#define BUZ 8 #define START 9 #define STOP 7 int time; //Variable for synchronization void setup() ( Serial. begin(9600); pinMode(START, INPUT_PULLUP); pinMode(STOP, INPUT_PULLUP); pinMode(BUZ, OUTPUT); ) void loop() ( if(digitalRead(START) == 0) // When you press the START Button.. ( int start_time = millis(); // Remember the time of pressing time = start_time; // Write it to a global variable. int Rand = random(0, 4000); // Let's generate a "random" delay time = time + Rand; //Add the delay time delay(Rand); //Wait for tone(BUZ, 3000, 500); //Beep! ) if(digitalRead(STOP) == 0 && digitalRead( START) == 1) // When you press the STOP button... ( int stop_time = millis(); // Remember the stop time. time = stop_time - time; // Calculate the time difference. Serial.println("Time: "); // Output the time to Serial. Serial.println(time); delay(1000); ) ) // Before the second attempt, press the START button again.
Explanations
int time; Variables (not all), when denoting them, do not have to be given any value. We used this variable to link two if statements.
In C++, variables declared inside a loop will not be accessible in other loops, since they only have effect within that loop. This is done to prevent programming errors. When the program code grows, you will understand what I'm talking about.
To make a variable available to multiple statements, you need to make it global. Those. declare a variable outside of functions.
millis(); Returns the number of milliseconds that have passed since the program was launched.
We need it in order to measure the amount of time that has passed from the signal being given to the button being pressed.
random(min,max); This is a random number generator. Takes two values. It generates a number in the range from min to max.
"Random" numbers because they are a specific sequence of values. Very long, but the same. In order to get different sequences, you should use RandomSeed();
This function initializes the generator. And if we set the parameter to random, then we will get the sequences we need. The sequence will be the same if the parameter is fixed.
Conclusion
Now you can train your reaction using a device you made yourself. Or you can continue to study further.
List of radioelements
| Designation | Type | Denomination | Quantity | Note | Shop | My notepad |
|---|---|---|---|---|---|---|
| Arduino board | Arduino Uno | 1 | To notepad | |||
| Bread board | Breadboard-half | 1 | To notepad | |||
| Piezo emitter | Passive | 1 | To notepad | |||
| Tact button | Without lock | 2 | To notepad | |||
| Connecting wires | "Papa-Papa" | 1 |
