CN106201436A - True Random Number Generator based on double coupling Fibonacci oscillation rings - Google Patents

Abstract

The invention discloses a true random number generator based on double-coupled Fibonacci oscillating rings, which mainly solves the problems of low rate of true random number generation and poor randomness of the true random number generator in the prior art. It includes an oscillating circuit and a sampling circuit. The oscillating circuit is composed of several Fibonacci oscillating rings. Each Fibonacci oscillating ring includes several XOR gates, XOR gates and several inverters. The number of OR gates is equal, and the number of XOR gates, NOR gates and inverters and their connection methods are determined by the feedback polynomial used in the design. The oscillating circuit is used to generate random oscillating signals; the sampling circuit is composed of several sampling sub-circuits, which are used to sample the random oscillating signals generated by the oscillating circuit. of true random numbers. The invention has simple structure, good randomness of entropy source, and can be used for secure communication.

Description

A True Random Number Generator Based on Double Coupled Fibonacci Oscillating Rings

technical field

The invention belongs to the technical field of digital circuits, in particular to a true random number generator which can be used for secure communication.

Background technique

True random number generators with high security are crucial to cryptosystems, and they are often used to generate keys, initialization vectors, and some random sequences against cryptographic attacks. Traditionally, one of the most commonly used methods for generating true random numbers is to amplify thermal noise, such as Peng Haihui, Liu Xinyu, and Huang Jie's patent (patent publication number: CN101727308A) method for generating true random numbers in integrated circuits. and the noise generated by the digital power supply signal, and then use the DES algorithm to process the data to obtain a true random number; Yu Huihong's patent (patent publication number: CN101751240B) is a true random number generated by comparing equal resistance thermal noise The number generator uses a comparator to compare the thermal noise signals of the same resistance to obtain a random number sequence. Bai Guoqiang, Zhang Xiaofeng, and Chen Hongyi's patent (patent publication number: CN101819515A) is based on a ring oscillator-based true random number generator circuit and a true random number generator, using two high-frequency ring oscillator circuits with input terminals and a low-frequency ring oscillator The circuit constitutes a true random number generation circuit, and then post-processes it; the patent (patent publication number: CN102375722A) of Wang Jian, Zhang Hongfei, Cui Ke, Gao Yuan, Liang Hao, and Jin Ge is a true random number generation method and generator, Multiple independent high-frequency oscillation rings with external enable terminals are used to generate multiple output signals, and sampling signals are selected from them to sample XOR signals from other channels to obtain true random numbers.

Because some of the above methods use external random sources, the randomness of the generated random numbers is difficult to guarantee. When the attacker controls the external random sources, it is extremely unsafe to use these random numbers; some methods are based on reversers. Oscillating rings generate random numbers. Because the randomness of such an oscillating ring is extremely small in one oscillation cycle, to obtain a true random number with high randomness, it is necessary to wait for its randomness to accumulate to a certain extent before sampling and outputting. Therefore, this method cannot Generates true random numbers at a high rate.

Contents of the invention

The object of the present invention is to propose a true random number generator based on double-coupled Fibonacci oscillating rings to improve the generation rate and security of true random numbers.

To achieve the above object, the present invention includes:

an oscillating circuit for generating a random oscillating signal with a random phase offset;

The sampling circuit is used for sampling the random oscillating signal generated by the oscillating circuit, and converting the continuous analog signal into a discrete digital signal for output.

It is characterized by:

The oscillating circuit includes:

Several identical double-coupled Fibonacci oscillation rings are formed, among which:

Each double-coupled Fibonacci oscillation ring includes two upper and lower inverter groups, k exclusive OR gates XOR and k exclusive OR gates XNOR, and the value of k is determined according to the feedback polynomial given during design;

Each inverter group is composed of r inverters connected in series, that is, the output of each inverter except the last inverter is connected to the input of the next inverter, and r is the design given The degree of the given feedback polynomial;

Each exclusive OR gate XOR and each exclusive OR gate XNOR has three input ports and one output port, and each exclusive OR gate XOR is connected to each exclusive OR gate XNOR as follows:

The first input port of the jth exclusive OR gate XOR is connected to the output port of the j+1th exclusive OR gate XOR _j+1 , and the second input port is connected to the output port of the j+1th exclusive OR gate XNOR _j+1 connected, the third input port is connected to the output port of the cjth inverter in the upper inverter group, where 1≤j≤k-1;

The value of cj is determined according to the feedback polynomial given during design.

The first input port of the jth NOR gate XNOR _j is connected to the output port of the j+1th NOR gate XNOR _j+1 , and the second input port is connected to the output of the j+1th XNOR gate XOR _j+1 port connection, the third input port is connected to the output port of the cj reverser of the lower reverser group;

The first input port of the kth XOR gate XOR _k is connected to the output port of the ckth inverter in the upper inverter group, and the second input port is connected to the rth inverter in the upper inverter group connected to the output port, and the third input port is connected to its own output port;

The first input port of the kth NOR gate XNOR _k is connected to the output port of the ckth inverter in the lower inverter group, and the second input port is connected to the rth inverter in the lower inverter group connected to the output port, and the third input port is connected to its own output port.

The present invention has the following advantages as follows:

1. The generated true random number has strong stability and high output rate.

The present invention realizes the coupling between the two Fibonacci oscillation rings by connecting the XOR gates in the two independent Fibonacci oscillation rings, can generate stable chaotic oscillation, and utilize the stable chaotic oscillation to realize Generating stable and high-speed true random numbers.

2. The present invention greatly reduces the correlation of the sampling signal due to the sampling circuit of the interval sampling pattern, that is, sampling on the two farthest XOR gates and the two farthest same OR gates, thereby improving randomness.

3. The present invention adopts feedback polynomials for design, and since different feedback polynomials correspond to different double-coupled Fibonacci oscillation rings, the diversity and flexibility of the design are increased.

Description of drawings

Fig. 1 is a block diagram of the present invention;

Fig. 2 is a circuit structure diagram 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 examples. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention.

Referring to Fig. 1, the present invention includes an oscillating circuit and a sampling circuit. The oscillation circuit is composed of several double-coupled Fibonacci oscillation rings, which are used to generate random oscillation signals; the sampling circuit is composed of several sampling sub-circuits, which are used to sample the random oscillation signals generated by the oscillation circuit. The output of the sampling sub-circuit is XORed as the output port of the sampling circuit to output a true random number sequence.

With reference to Fig. 2, oscillation circuit and sampling circuit structure of the present invention are described as follows:

The oscillating circuit is composed of several double-coupled Fibonacci oscillating rings, and each double-coupled Fibonacci oscillating ring includes: upper and lower two inverter groups, k exclusive OR gates XOR, k same OR gate XNOR, k depends on the feedback polynomial given during design;

The feedback polynomial can reflect the mathematical characteristics of the oscillation circuit and can visually express the connection mode of the logic gate in the oscillation circuit. The feedback polynomial used in this design is expressed as Among them, f _i is the coefficient of the feedback polynomial, i is the degree of the independent variable x, f ₀ =f _r =1, when 0<i<r, the value of f _i is 1 or 0, r is the degree of the feedback polynomial, r is an integer not less than 8;

k is the number of 1 in all feedback polynomial coefficients f _i in 0<i<r;

Each inverter group is composed of r inverters connected in series, that is, the output end of each inverter is connected to the input end of the next inverter except the last inverter;

Each exclusive OR gate XOR and each exclusive OR gate XNOR has three input ports and one output port, and each exclusive OR gate XOR is connected to each exclusive OR gate XNOR as follows:

The first input port of the jth XOR gate XOR _j is connected to the output port of the j+1th XOR gate XOR _j+1 , and the second input port of the jth XOR gate XOR _j is connected to the j+1th XOR gate XOR j+1 The output port of the same OR gate XNOR _j+1 is connected, and the third input port of the jth exclusive OR gate XOR _j is connected to the output port of the cjth inverter in the upper inverter group, where 1≤j≤ k-1;

The first input port of the jth NOR gate XNOR _j is connected to the output port of the j+1th NOR gate XNOR _j+1 , and the second input port of the jth NOR gate XNOR _j is connected to the j+1th NOR gate XNOR j+1 The output port of the exclusive OR gate XOR _j+1 is connected, and the third input port of the jth same OR gate XNOR _j is connected with the output port of the cj inverter of the lower inverter group;

The first input port of the kth XOR gate XOR _k is connected to the output port of the ck inverter in the upper inverter group, and the second input port of the kth XOR gate XOR _k is connected to the upper inverter The output port of the rth inverter in the group is connected, and the third input port of the kth XOR gate XOR _k is connected with its own output port;

The first input port of the k-th NOR gate XNOR _k is connected to the output port of the ck-th inverter in the lower inverter group, and the second input port of the k-th NOR gate XNOR _k is connected to the lower inverter The output port of the rth inverter in the group is connected, and the third input port of the kth NOR gate XNOR _k is connected with its own output port.

The values of cj and ck above depend on the feedback polynomial used in the design;

The feedback polynomial used in this design is expressed as Among them, f _i is the coefficient of the feedback polynomial, i is the degree of the independent variable x, f ₀ =f _r =1, when 0<i<r, the value of f _i is 1 or 0, r is the degree of the feedback polynomial, r is an integer not less than 8;

Arrange the subscript i of all feedback polynomial coefficients f _i with a value of 1 into a sequence from small to large, which can be expressed as c1, c2, ..cj, ..ck, where cj is the jth number in this sequence value.

The sampling circuit is composed of several sampling sub-circuits and an exclusive OR gate, that is, the k+2th exclusive OR gate XOR _k+2 .

Each sampling sub-circuit includes: four D flip-flops, respectively the first D flip-flop D ₁ , the second D flip-flop D ₂ , the third D flip-flop D ₃ , the fourth D flip-flop D ₄ and one The exclusive OR gate is the k+1th exclusive OR gate XOR _k+1 . The four D flip-flops are respectively connected to the four exclusive OR gates in the double-coupled Fibonacci oscillation ring in the oscillation circuit, that is, the input of the _first flip-flop D1 is the output of the first exclusive OR gate XOR ₁ , and the first The input of the _second flip-flop D2 is the output of the first exclusive OR gate XNOR ₁ , the input of the third flip-flop _D3 is the output of the kth exclusive OR gate XOR _k , and the input of the _fourth flip-flop D4 is the kth exclusive OR gate The output of the gate XNOR _k ; the output of the four D flip-flops is used as the input of the k+1 exclusive OR gate XOR _k +1, and the output of the k+1 exclusive OR gate XOR _k+1 is used as the output of the sampling circuit sub-circuit, The output of all sampling sub-circuits is used as the input of the k+2 exclusive OR gate XOR _k +2, and the output of the k+2 exclusive OR gate XOR _k+2 is the output of the entire true random number generator. The four D flip-flops, Both the k+1th XOR gate XOR _k+1 and the k+2th XOR gate XOR _k+2 are controlled by the clock CLK provided by the external clock circuit, and the maximum frequency of the clock CLK is 200 MHz.

Example:

In this example, the feedback polynomial is used: f(x)=1+x+x ³ +x ⁵ +x ¹³ +x ¹⁶ , which is equivalent to the feedback polynomial where f ₀ =f _r =1, when 0<i<r, its feedback polynomial coefficient f ₁ =f ₃ =f ₅ =f ₁₃ =1, the number of coefficients with a value of 1 among the feedback polynomial coefficients is 4 , that is, k is 4;

The subscript i of the feedback polynomial coefficient f _i with a coefficient value of 1 is arranged in a sequence c1, c2, ..cj, ..ck from small to large, which is 1, 3, 5, 13;

According to the feedback polynomial given above: f(x)=1+x+x ³ +x ⁵ +x ¹³ +x ¹⁶ , each coupling Fibonacci oscillation ring of the designed oscillation circuit includes: the upper and the lower have 16 Two inverter groups of three inverters, four exclusive OR gates, namely the first exclusive OR gate XOR ₁ , the second exclusive OR gate XOR ₂ , the third exclusive OR gate XOR ₃ , the fourth exclusive OR gate XOR ₄ and The four XNOR gates are the first XNOR gate XNOR ₁ , the second XNOR gate XNOR ₂ , the third XNOR gate XNOR ₃ , and the fourth XNOR gate XNOR ₄ , each XOR gate is connected with each XNOR gate The XNOR connection is as follows:

The first input port of the first exclusive OR gate XOR ₁ is connected to the output port of the second exclusive OR gate XOR ₂ , the second input port of the first exclusive OR gate XOR ₁ is connected to the output port of the second exclusive OR gate XNOR ₂ , The third input port of the first XOR gate XOR ₁ is connected to the output port of the first inverter in the upper inverter group;

The first input port of the first NOR gate XNOR ₁ is connected to the output port of the second NOR gate XNOR ₂ , the second input port of the first NOR gate XNOR ₁ is connected to the output port of the second XOR gate XOR ₂ , The third input port of the first NOR gate XNOR ₁ is connected to the output port of the first inverter in the lower inverter group;

The first input port of the second exclusive OR gate XOR ₂ is connected to the output port of the third exclusive OR gate XOR ₃ , the second input port of the second exclusive OR gate XOR ₂ is connected to the output port of the third exclusive OR gate XNOR ₃ , The third input port of the second XOR gate XOR ₂ is connected to the output port of the third inverter in the upper inverter group;

The first input port of the second NOR gate XNOR ₂ is connected to the output port of the third NOR gate XNOR ₃ , and the second input port of the second NOR gate XNOR ₂ is connected to the output port of the third XNOR gate XOR ₃ , The third input port of the second NOR gate XNOR ₂ is connected to the output port of the third inverter in the lower inverter group;

The first input port of the third exclusive OR gate XOR ₃ is connected to the output port of the fourth exclusive OR gate XOR ₄ , the second input port of the third exclusive OR gate XOR ₃ is connected to the output port of the fourth exclusive OR gate XNOR ₄ , The third input port of the third XOR gate XOR ₃ is connected to the output port of the fifth inverter in the upper inverter group;

The first input port of the third NOR gate XNOR ₃ is connected to the output port of the fourth NOR gate XNOR ₄ , and the second input port of the third NOR gate XNOR ₃ is connected to the output port of the fourth XNOR gate XOR ₄ , The third input port of the third NOR gate XNOR ₃ is connected to the output port of the fifth inverter in the lower inverter group;

The first input port of the fourth exclusive OR gate XOR ₄ is connected to the output port of the 13th inverter in the upper inverter group, and the second input port of the fourth exclusive OR gate XOR ₄ is connected to the output port of the upper inverter group. The output port of the 16th inverter is connected, and the third input port of the fourth XOR gate XOR ₄ is connected with its own output port;

The first input port of the fourth NOR gate XNOR ₄ is connected with the output port of the 13th inverter in the lower inverter group, and the second input port of the fourth NOR gate XNOR ₄ is connected with the output port of the 13th inverter in the lower inverter group. The output port of the 16th inverter is connected, and the third input port of the fourth NOR gate XNOR ₄ is connected with its own output port.

The four D flip-flops of the sampling sub-circuit respectively sample the four XOR gates in the double-coupled Fibonacci oscillation ring in the oscillation circuit under the drive of an external clock with a frequency of 100MHZ, that is, the first flip-flop D ₁ operates at 100MHZ The first XOR gate XOR ₁ is sampled under the drive of an external clock with a frequency of 100MHZ, the second flip-flop D ₂ is driven by an external clock with a frequency of 100MHZ to sample the first XNOR gate XNOR ₁ , and the third flip-flop D ₃ is at 100MHZ The fourth XOR gate XOR ₄ is sampled under the drive of an external clock with a frequency of 100 MHz, and the fourth flip-flop D ₄ is sampled with the fourth NOR gate XNOR ₄ driven by an external clock with a frequency of 100 MHz; the sampling results of the four D flip-flops After the fifth exclusive OR gate XOR ₅ is used as the output of the sampling circuit sub-circuit, the outputs of all sampling sub-circuits are output through the sixth exclusive OR gate XOR ₆ to generate 1000 groups of 1M true random sequences.

Effect of the present invention can be illustrated by following test:

1. Test method:

Use the SP800-22 random number detection standard provided by the National Institute of Standards and Technology NIST to detect the randomness of the 1000 sets of 1M true random sequences generated in the above example. The detection standard includes 15 detection items, each of which is The generated test result contains a P-value value and a pass rate Propotion value. When the P-value value is not lower than 0.001 and the pass rate value is not lower than 0.9806, it means that the test content is passed.

2. Test results:

For the 1000 sets of 1M true random sequences generated in this example, use the SP800-22 random number detection standard provided by the National Institute of Standards and Technology NIST to detect the results, as shown in Table 1

Table 1 Test results

Statistical Test P-value Proposition Result Frequency 0.659937 0.9902 Pass Block Frequency 0.350368 0.9922 Pass Cumulative Sums 0.784843 0.9883 Pass run 0.681807 0.9873 Pass Longest Run 0.918651 0.9873 Pass Rank 0.549642 0.9922 Pass FFT 0.363621 0.9902 Pass OverlappingTemplate 0.491928 0.9902 Pass Universal 0.703826 0.9883 Pass Linear Complexity 0.212153 0.9883 Pass ApproximateEntropy 0.440591 0.9922 Pass Serial 0.280016 0.9912 Pass NonOverlappingTemplate 0.191187 0.9873 Pass Random Excursions 0.228806 0.9881 Pass RandomExcursionsVariant 0.484628 0.9898 Pass

It can be seen from Table 1 that each index of the true random sequence generated in this example meets the requirements of random numbers, indicating that the random numbers generated in this example have good randomness.

The above examples only illustrate the implementation method of the present invention with specific implementation, and there can be many modifications on this basis, and such structural changes based on the present invention are all included in the protection scope of the present invention.

Claims (9)

1. A true random number generator based on double-coupled Fibonacci oscillation rings, including: an oscillating circuit for generating a random oscillating signal with a random phase offset; The sampling circuit is used for sampling the random oscillating signal generated by the oscillating circuit, and converting the continuous analog signal into a discrete digital signal for output. It is characterized by: The oscillating circuit includes: Several identical double-coupled Fibonacci oscillation rings are formed, among which: Each double-coupled Fibonacci oscillation ring includes two upper and lower inverter groups, k exclusive OR gates XOR and k exclusive OR gates XNOR, and the value of k is determined according to the feedback polynomial given during design; Each inverter group is composed of r inverters connected in series, that is, the output of each inverter except the last inverter is connected to the input of the next inverter, and r is the design given The degree of the given feedback polynomial; Each exclusive OR gate XOR and each exclusive OR gate XNOR has three input ports and one output port, and each exclusive OR gate XOR is connected to each exclusive OR gate XNOR as follows: The first input port of the jth exclusive OR gate XOR is connected to the output port of the j+1th exclusive OR gate XOR _j+1 , and the second input port is connected to the output port of the j+1th exclusive OR gate XNOR _j+1 connected, the third input port is connected to the output port of the cjth inverter in the upper inverter group, where 1≤j≤k-1; The value of cj is determined according to the feedback polynomial given during design. The first input port of the jth NOR gate XNOR _j is connected to the output port of the j+1th NOR gate XNOR _j+1 , and the second input port is connected to the output of the j+1th XNOR gate XOR _j+1 port connection, the third input port is connected to the output port of the cj reverser of the lower reverser group; The first input port of the kth XOR gate XOR _k is connected to the output port of the ckth inverter in the upper inverter group, and the second input port is connected to the rth inverter in the upper inverter group connected to the output port, and the third input port is connected to its own output port; The first input port of the kth NOR gate XNOR _k is connected to the output port of the ckth inverter in the lower inverter group, and the second input port is connected to the rth inverter in the lower inverter group connected to the output port, and the third input port is connected to its own output port. 2. the true random number generator based on double-coupled Fibonacci oscillating ring according to claim 1, is characterized in that: described feedback polynomial, it is expressed as Where f _i is the coefficient of the feedback polynomial, i is the degree of the independent variable x, f ₀ =f _r =1; when 0<i<r, f _i =1 or 0, r is an integer not less than 8. 3. the true random number generator based on double coupling Fibonacci oscillating ring according to claim 1, is characterized in that: the value of k determines according to the given feedback polynomial when designing, and it determines as follows: The feedback polynomial, which is expressed as Wherein f _i is the coefficient of the feedback polynomial, i is the degree of the independent variable x, f ₀ =f _r =1, when 0<i<r, the value of f _i is 1 or 0, and r is an integer not less than 8; The value of k is the number of 1 among all feedback polynomial coefficients f _i when 0<i<r. 4. the true random number generator based on double coupling Fibonacci oscillating ring according to claim 1, is characterized in that: cj value is determined according to the given feedback polynomial when designing, and it is determined as follows: The feedback polynomial, which is expressed as Among them, f _i is the i-th coefficient of the feedback polynomial, i is the degree of the independent variable x, f ₀ =f _r =1, when 0<i<r, the value of f _i is 1 or 0, and r is not less than 8 integer; Arrange the subscript i of all feedback polynomial coefficients f _i with a value of 1 into a sequence from small to large, which can be expressed as c1, c2, ..cj, ..ck, and cj represents the value of the jth number in this sequence value. 5. the true random number generator based on double-coupled Fibonacci oscillating ring according to claim 1, is characterized in that: The several inverters are realized by the basic programmable logic unit of FPGA, the logic unit is composed of a reverse lookup table LUT and a register, the pure digital logic of the inverter is realized through the lookup table, and the digital state is saved through the register. 6. the true random number generator based on double-coupled Fibonacci oscillating ring according to claim 1, is characterized in that: The several XOR gates are realized by the basic programmable logic unit of FPGA. The logic unit is composed of an XOR lookup table LUT and a register. The XOR pure digital logic is realized through the lookup table, and the digital state is saved through the register. 7. the true random number generator based on double-coupled Fibonacci oscillating ring according to claim 1, is characterized in that: The several NOR gates are realized by the basic programmable logic unit of FPGA, which is composed of a NOR lookup table LUT and a register, and the NOR pure digital logic is realized through the lookup table, and the digital state is saved through the register. 8. the true random number generator based on double-coupling Fibonacci oscillating ring according to claim 1, is characterized in that: described sampling circuit is made of several sampling sub-circuits, and each sampling sub-circuit is made of four D Flip-flops D1, D2, D3, D4 and 1 XOR gate, that is, the k+1th XOR gate XOR _k+1 , these four D flip-flops are respectively connected to the four XOR gates in the oscillation circuit, that is, the first The input of a flip-flop D1 is the output of the first XOR gate XOR1, the input of the second flip-flop D2 is the output of the first NOR gate XNOR1, and the input of the third flip-flop D3 is the output of the kth XOR gate XOR _k output, the input of the fourth flip-flop D ₄ is the output of the kth exclusive OR gate XNOR _k ; the outputs of the four D flip-flops D ₁ , D ₂ , D ₃ , D ₄ are used as the k+1th exclusive OR gate XOR _k The input of ₊₁ , the output of the k+1th XOR gate XOR _k+1 is used as the output of the sampling circuit sub-module. 9. The true random number generator based on double-coupled Fibonacci oscillating ring according to claim 8, characterized in that: four D flip-flops D ₁ , D ₂ , D ₃ , D ₄ and the k+1th The XOR gate XOR _k+1 is controlled by the same clock, which is provided by an external clock circuit.