CN107025092A - A kind of random number extracting method based on latch structure real random number generators - Google Patents

Abstract

The present invention provides a random number extraction method based on a latch structure true random number generator, which specifically includes the following steps: realizing a latch structure true random number generator on an FPGA; using metastable phenomena to make a true random number generation module start to oscillate, The oscillation period of the true random number generator module is recorded by the counter, and the oscillation time is recorded by the system clock of the FPGA; The period is greater than 70; the lowest 2 bits of the counter are extracted as random number output, and the metastable phenomenon is used to make the latch structure true random number generator generate true random numbers that meet the quantity requirements. The beneficial effect of the present invention is that: the speed of random number generation is greatly improved; the method has high robustness against changes in temperature, voltage and process, and the data generated under different conditions can all pass the NIST randomness test.

Description

A Random Number Extraction Method Based on Latch Structure True Random Number Generator

technical field

The invention belongs to the technical fields of information security and integrated circuits, and in particular relates to a random number extraction method based on a latch structure true random number generator.

Background technique

With the widespread application of cloud computing, the Internet of Things and big data, the scale of communication between people and between people and things has increased rapidly, and information security issues have become more and more important. Data encryption is the main method or even the only method to ensure information security, and random numbers are the basis of data encryption. The application of random numbers includes generating security keys in cryptographic algorithms, generating session IDs in secure Internet protocols, and generating mobile Internet device IDs. And various operating system protocols, etc. Random number generators can be divided into true random and pseudo-random. Pseudo-random number generators (PRNG) use deterministic algorithms to expand short random strings into "random search" bit streams, and are periodic, so the generated random numbers cannot meet the requirements of randomness. Encryption systems with high performance requirements. The true random number generator (TRNG) harvests entropy from physical noise sources, is non-periodic, unpredictable, and has real-time randomness, providing a guarantee for a highly reliable encryption system.

There are many kinds of research on TRNG at home and abroad, and the main research focuses on three aspects: random number generator based on resistance thermal noise, random number generator based on oscillator and random number generator based on metastable state. In the early days, the method of directly amplifying and extracting random numbers by resistive thermal noise was used. However, the disadvantages of this method are manifested in two aspects. On the one hand, it is difficult to eliminate the coupling noise between the power supply and the substrate, or other non-ideal factors also affect the generated random numbers to a certain extent. The randomness of the sequence. On the other hand, most of these methods use analog devices, which makes it difficult to apply this type of analog design to system integration and technology transplantation on a chip. The method based on oscillator sampling is an all-digital method. Compared with the method of directly amplifying noise, the method of all-digital circuit has the advantages of high robustness and easy integration for changes in process, voltage and temperature. The quality of its randomness mainly depends on the phase jitter of the low-frequency oscillator, and the phase jitter of the low-frequency oscillator relative to the period of the high-frequency oscillator. Therefore, multiple oscillators are needed to increase the phase jitter, but also increase the hardware overhead. Metastability-based methods can also be implemented entirely in digital technology, using the metastable phenomenon in bistable devices to generate random numbers. However, traditional metastable methods are sensitive to environmental changes and usually require extensive design-in calibration to eliminate system and timing mismatches in the device due to process variations. It can be seen that there are deficiencies in all kinds of methods, and there are still many places to be studied. For example, throughput and power consumption have always been the focus of research in this area, providing efficiency guarantees for existing or upcoming needs.

Contents of the invention

In order to solve the above-mentioned technical defects existing in the prior art, the present invention provides a random number extraction method based on a latch-structured true random number generator, which has great advantages for the random number generation speed on the basis of ensuring high robustness To improve the application efficiency of true random numbers in the field of information security.

The present invention is achieved through the following technical solutions:

A random number extraction method based on a latch structure true random number generator, wherein the latch structure true random number generator includes Microblaze soft cores connected in sequence, a true random number generation module, a counter, and a finite state machine; the Microblaze soft core is connected with The counter is connected with the finite state machine; the true random number generation module is a latch structure with an even number of gates. The random number extraction method includes the following steps:

Initialization steps:

Implement a latch structure true random number generator on FPGA;

Oscillation start steps:

The metastable phenomenon is used to make the true random number generator module start to oscillate, the oscillation period of the true random number generator module is recorded by the counter, and the oscillation time is recorded by the system clock of the FPGA;

Oscillation adjustment steps:

Utilize the multiplexer in the true random number generating module to configure different paths of the true random number generating module to adjust the oscillation period, so that the oscillation period is greater than 70;

Output steps:

The lowest 2 bits of the counter are extracted as the random number output, and the metastable phenomenon is used to make the latch structure true random number generator generate true random numbers that meet the quantity requirements.

The beneficial effect of the present invention with respect to prior art is:

1. The method for extracting random numbers proposed by the present invention is to extract random numbers before the oscillation of the latch structure ends. Compared with the existing methods, the speed of random number generation is greatly improved.

2. The random number extraction method proposed by the present invention has high robustness to changes in temperature, voltage and process, and the data generated under different conditions can pass the NIST randomness test.

3. The random number extraction method proposed by the present invention is implemented on the FPGA platform. Compared with the widely used true random number generator on the FPGA, the method in this paper has lower resource consumption, and provides a new reference for related research on the FPGA.

Description of drawings

Fig. 1 is a general flowchart of the random number extraction method of the present invention.

FIG. 2 is a schematic structural diagram of a true random number generator with a latch structure.

FIG. 3 is a schematic structural diagram of a true random number generating module.

Figure 4a shows the basic metastable structure.

Figure 4b is the metastable transition curve.

FIG. 5 is a signal sequence diagram of the random number extraction method of the present invention.

Fig. 6 is an overall working flow chart of the random number extraction method of the present invention.

detailed description

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described here are only used to explain the present invention, and are not intended to limit the present invention.

Example 1:

This experiment implements a true random number generator on the xc6vlx240t-1ffg1156FPGA development board. The system operating frequency of the development board is 50Mhz, the normal operating voltage is 1.0V, the normal operating temperature is 25°C, and the Microblaze operating frequency is 100Mhz. The software uses ISE14.3 version for Verilog code writing, synthesis, mapping, layout and routing, and bit file generation. As shown in Figure 1, this embodiment provides a random number extraction method based on a latch structure true random number generator, wherein:

The specific structure of the latch structure true random number generator is shown in Figure 2, including the Microblaze soft core connected in sequence, the true random number generation module, the counter, and the finite state machine; the Microblaze soft core is connected with the counter and the finite state machine respectively; the true random The number generating module is a latch structure with an even number of gates. In Figure 2, Microblaze is the FPGA with its own soft core, which uses serial ports and interrupts to control data transmission; latch is a true random number generator module with an even number of gate structures; Counter is a counter; FMS is a finite state machine; The true random number generation module latch starts to oscillate, count is the counter value, the Clear signal is used to clear the counter value, and TRN is the value of the counter at a certain moment obtained by the finite state machine according to the program setting. The Microblaze soft core realizes the connection between the latch structure true random number generator and the external computer HOST (PC) through the USB port.

The specific structure of the true random number generation module shown in this embodiment is shown in Figure 1, including 2 selection channels, wherein: each selection channel includes 1 NOR gate and 2 NOR gate selection units connected in sequence; The two input terminals of the gate are used as the two input terminals of the selection channel respectively, and the output terminal of the selection unit of the non-gate at the end is used as the output terminal of the selection channel. The NOT gate selection unit includes 4 NOT gates and 1 multiplexer, the output of each NOT gate corresponds to an input terminal of the multiplexer, and the input terminals of the 4 NOT gates are jointly used as the input of the NOT gate selection unit terminal, the output terminal of the multiplexer is used as the output terminal of the NOT gate selection unit.

One input terminal of one selection channel and one input terminal of another selection channel are used as the input terminal of the true random number generator module, the other input terminal of one selection channel is connected with the output terminal of another selection channel, and the output terminal of one selection channel The terminal is connected to the other input terminal of another selection channel, and the output terminals of the two selection channels are jointly used as the output terminal of the true random number generating module.

The random number extraction method includes the following steps:

Step S1, initialization step:

Implement a latch structure true random number generator on FPGA. Specifically include: use the preset constraint file to define the position of the latch structure true random number generator on the FPGA; then use the constraint file to perform timing constraints to prevent timing violations. Taking the implementation as shown in Figure 3 as an example, the true random number generator module occupies 6 slices in the FPGA, 2 of which are configured as NOR gates, each occupying 2 input terminals of a look-up table. The remaining structures are each configured as 4 NOT gates connected to a multiplexer, each occupying 6 input terminals of a look-up table.

Step S2, the oscillation start step:

The metastable phenomenon is used to make the true random number generation module start to oscillate, the oscillation period of the true random number generation module is recorded by the counter, and the oscillation time is recorded by the system clock of the FPGA.

First briefly introduce the metastability phenomenon, as shown in Figure 4a, where the input signal Enable drives two NOR gates A and B. When Enable=1, Y ₁ Y ₂ =00. Figure 4b is the transfer curve of Y ₁ Y ₂ , from which it can be seen that Y ₁ Y ₂ =00 is forced to be in a metastable state. When Enable jumps from 1 to 0, both gates A and B are equivalent to inverters, so both Y ₁ and Y ₂ have a tendency to transform into a stable state, causing the structure to oscillate. Since the gates in the latch will be affected by noise and process deviation, the level signal transmission on one side will be fast, and the entire latch structure will eventually reach a stable state, Y ₁ Y ₂ =01 or Y ₁ Y ₂ =10, this process is a traditional metastable phenomenon.

Combined with the structure of the latch structure true random number generator shown in Figure 2, the metastable phenomenon is used to make the latch structure of the true random number generation module start to oscillate, and its operation sequence is shown in Figure 5, where the Enable signal is the oscillation enable signal, when the Enable falling edge arrives, the latch structure starts to oscillate. The Clear signal clears the counter value, and keeps the counter value cleared when it is 1. CLK is the system clock, which is used to record the number of oscillation cycles, and Counter is a counter, which records the oscillation cycle.

Step S3, oscillation adjustment step:

The multiplexer in the true random number generating module is used to configure different paths of the true random number generating module to adjust the oscillation period, so that the oscillation period is greater than or equal to 70.

If the layout is asymmetrical, the delay difference between the two sides of the latch is large, and the system deviation is large, the crash cycle can only reach a dozen times, and the rate of generating random numbers is slow. If the layout is symmetrical, the delay difference on both sides of the latch is very close and the system deviation is small, the oscillation cycle can reach hundreds of thousands of times, with a high rate. By configuring different paths, adjust the oscillation period to the required range. If the oscillation period is greater than 70, at least 2 bits of the counter can be output as random bits.

The specific configuration method of the multiplexer here is as follows: the NOT gate selection unit is 4 NOT gates connected to a multiplexer, and the unit is implemented with a 6-input lookup table, two of which are used as multiplexer control ports , and the remaining four input terminals are four NOT gates. When adjusting the oscillation period, the value of the multiplexer control port is changed through the state machine to select different NOT gates, and different paths are selected.

Step S4, calibration step:

Before the oscillation ends, use the finite state machine to adjust the sampling time, and select the moment when the oscillation period is greater than or equal to 70 for sampling.

Due to the influence of process deviation, the same sampling time may get different results on different chips. In order to ensure that the sampling time meets the requirements, the realization of the true random number generation module TRNG on different FPGA chips also needs to be implemented through a finite state machine. to calibrate. The calibration method is as follows: adjust the sampling time, after collecting 5000 sets of data, judge whether the average value is greater than or equal to 70, and select the time when the oscillation cycle is greater than or equal to 70 to sample; if the average value is less than 70, add 1 to the sampling time backward, and continue The data is collected for judgment, and the calibration is completed when the mean value is greater than or equal to 70, and the subsequent random number collection is based on this moment.

Step S5, the output step:

The lowest 2 bits of the counter are extracted as the random number output, and the metastable phenomenon is used to make the latch structure true random number generator generate true random numbers that meet the quantity requirements.

Since the whole structure is a metastable node structure, the counting distribution at the specified time obeys the inverse Gaussian distribution, so the lowest 2 bits of the counter can be used as the random number output, and these 2 bits have the same 0, 1 distribution. After the previous steps are completed, the follow-up is to generate random numbers according to the requirements. The overall operation flow chart is shown in Figure 6. Random numbers are continuously generated according to the sequence in Figure 5. When the amount of data meets the requirements, the random numbers are output.

In this embodiment, in order to test the output random number and ensure the accuracy of the data, it may further include step S6, the testing step:

Use the NIST randomness test suite to test the random numbers generated by the latch structure true random number generator. The test results output a series of P values. When the P value is greater than 0.0001, it means that the data has passed the randomness.

In specific applications, NIST SP800-22 standard randomness testing software can be used for testing. Table 1 shows that the second lowest bit of the counter is experimentally tested under normal temperature and voltage and 1K data is collected. After testing, it can be seen that the output data have all passed 15 NIST randomness tests and have a high P value , and higher entropy (Proportion is the probability of passing the test 300 times).

Table 1 2 LSB NIST test results

The beneficial effect of the present invention with respect to prior art is:

1. The method for extracting random numbers proposed by the present invention is to extract random numbers before the oscillation of the latch structure ends. Compared with the existing methods, the speed of random number generation is greatly improved.

2. The random number extraction method proposed by the present invention has high robustness to changes in temperature, voltage and process, and the data generated under different conditions can pass the NIST randomness test.

3. The random number extraction method proposed by the present invention is implemented on the FPGA platform. Compared with the widely used true random number generator on the FPGA, the method in this paper has lower resource consumption, and provides a new reference for related research on the FPGA.

Those skilled in the art can easily understand that the above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention, All should be included within the protection scope of the present invention.

Claims (6)

1. a method for extracting random numbers based on a latch structure true random number generator, wherein the latch structure true random number generator includes a Microblaze soft core connected successively, a true random number generation module, a counter, and a finite state machine; The Microblaze soft core is connected with the counter and the finite state machine respectively; the true random number generating module is a latch structure adopting an even number of gates; it is characterized in that the random number extraction method comprises the steps: Initialization steps: Realize described latch structure true random number generator on FPGA; Oscillation start steps: Using the metastable phenomenon to make the true random number generation module start to oscillate, record the oscillation period of the true random number generation module by the counter, and utilize the system clock of the FPGA to record the oscillation time; Oscillation adjustment steps: Using the multiplexer in the true random number generating module to configure different paths of the true random number generating module to adjust the oscillation period, so that the oscillation period is greater than or equal to 70; Output steps: The lowest 2 bits of the counter are extracted as random number output, and the metastable phenomenon is used to make the latch structure true random number generator generate true random numbers meeting the quantity requirement. 2. the random number extraction method based on the latch structure true random number generator according to claim 1, is characterized in that, described true random number generation module specifically comprises 2 selection channels, wherein: The selection channel includes 1 NOR gate and 2 NOR gate selection units connected in sequence; the two input terminals of the NOR gate are respectively used as the two input terminals of the selection channel, and the NOR gate at the end selects The output terminal of the unit is used as the output terminal of the selected channel; The NOT gate selection unit includes 4 NOT gates and 1 multiplexer, the output of each of the NOT gates is correspondingly connected to an input of the multiplexer, and the input terminals of the 4 NOT gates Commonly used as the input terminal of the NOT gate selection unit, and the output terminal of the multiplexer is used as the output terminal of the NOT gate selection unit; An input end of one said selection channel and an input end of another said selection channel are jointly used as the input end of said true random number generating module, and the other input end of one said selection channel is connected with another said selection channel The output terminals of one of the selection channels are connected to the other input terminal of the other selection channel, and the output terminals of the two selection channels are jointly used as the output terminals of the true random number generation module. 3. the random number extracting method based on latch structure true random number generator according to claim 1 or 2, is characterized in that, described initialization step further comprises: Using a preset constraint file to define the position of the latch structure true random number generator on the FPGA; and then using the constraint file to perform timing constraints to prevent timing violations. 4. the random number extracting method based on latch structure true random number generator according to claim 1 or 2, is characterized in that, also comprises calibration step before described output step: Before the oscillation ends, the finite state machine is used to adjust the sampling time, and the time when the oscillation cycle is greater than or equal to 70 is selected for sampling. 5. the random number extracting method based on latch structure true random number generator according to claim 4, is characterized in that, described calibration step further comprises: Utilize described finite state machine to carry out calibration first, adjust sampling time, after collecting 5000 groups of data, judge whether its mean value is greater than or equal to 70, select the moment of oscillation cycle greater than or equal to 70 to sample; if mean value is less than 70, then change sampling time to After adding 1, continue to collect data for judgment. When the average value is greater than or equal to 70, the calibration is completed, and the subsequent random number collection is based on this moment. 6. according to the random number extracting method based on latch structure true random number generator according to claim 1 and 2, it is characterized in that, also comprise testing step after described outputting step: Use the NIST randomness test suite to test the random numbers generated by the latch structure true random number generator. The test results output a series of P values. When the P value is greater than 0.0001, it means that the data has passed the randomness.