TRUE RANDOM NUMBER GENERATOR

Abstract

The invention relates to devices for generating true random numbers, comprising a digital chaotically oscillating autonomous Boolean network as a source of entropy. According to the invention, the proposed digital chaotically oscillating autonomous Boolean network consists in three logic elements connected to each other, two of which represent two-input “Exclusive OR” and/or “Exclusive NOR” gates, and the third logic element has three inputs and one output, and implements a logic “counting ones” function, in which its output is set to a logic one if a logic one is present at no more than one of its inputs, otherwise it is set to a logic zero. The achieved technical result consists in an increase in true random number generation rate while decreasing energy consumption.

Claims

1. A true random number generator comprising: a digital chaotically oscillating autonomous Boolean network as a source of entropy, the digital chaotically oscillating autonomous Boolean network including three logic elements connected to each other, the wherein a first of the logic elements is a two-input “Exclusive OR” or “Exclusive NOR” gate, a second of the logic elements is a two-input “Exclusive OR” or “Exclusive NOR” gate, and a third of the logic elements has three inputs and one output, and implements a logic “counting ones” function, wherein the output of the third logic element is set to a logic one if a logic one is present at no more than one of the inputs of the third logic elements, otherwise the output of the third logic element is set to a logic zero, wherein an output of the first logic element is connected to a first input of the second logic element and to a second one of the inputs of the third logic element, wherein an output of the second logic element is connected to a second input of the second logic element, to a second input of the first logic element, and to a third one of the inputs of the third logic element, and wherein the output of the third logic element is connected to the first input of the third logic element, to the first input of the first logic element, and to an output of the entire network.

2. The generator according to claim 1, wherein the second input, the third input, or both the first and third inputs of the third logic element is or are inverted.

3. The generator according to claim 1, wherein both two-input “Exclusive OR” and/or “Exclusive NOR” gates have additional third logic inputs, which are combined together and connected to an additional external modulation input of the digital chaotically oscillating autonomous Boolean network.

4. The generator according to claim 1, wherein the generator has a shutdown input, both “Exclusive OR” and/or “Exclusive NOR” gates have additional shutdown inputs with the possibility of forcibly switching the output of both gates to a logic zero or logic one state regardless of a state of the other inputs, the additional shutdown inputs being combined together and connected to a specified generator shutdown input.

5. The generator according to claim 3, wherein the digital chaotically oscillating autonomous Boolean network is combined with a D-trigger into a synchronous chaotic oscillator block having a clock input connected to a clock input of the D-trigger, a modulation input connected to a modulation input of the autonomous Boolean network, an asynchronous output connected to the output of the autonomous Boolean network, and a synchronous output connected to an output of the D-trigger, the output of the autonomous Boolean network being connected to a data input of the D-trigger.

6. The generator according to claim 5, wherein the generator comprises an additional two-input “Exclusive OR” and/or “Exclusive NOR” gate, a first input of the additional two-input “Exclusive OR” and/or “Exclusive NOR” gate being connected to an input of external modulation, a second input of the additional two-input “Exclusive OR” and/or “Exclusive NOR” gate being connected to the output of the D-trigger, and an output of the additional two-input “Exclusive OR” and/or “Exclusive NOR” gate being connected to the modulation input of the autonomous Boolean network.

7. The generator according to claim 5, wherein the generator comprises a plurality of N blocks of synchronous chaotic oscillators combined into a chain forming a ring structure, clock inputs of the synchronous chaotic oscillators being combined together and connected to a common clock signal, and synchronous outputs of the synchronous chaotic oscillators being connected to an N-bit output of the generator, and a set of N additional two-input “Exclusive OR” and/or “Exclusive NOR” gates, so that an output of each of the N additional two-input “Exclusive OR” and/or “Exclusive NOR” gates is connected to a modulation input of a corresponding one of the N blocks of synchronous chaotic oscillators, a first input of the N additional two-input “Exclusive OR” and/or “Exclusive NOR” gates being connected to an asynchronous output of previous synchronous chaotic oscillator block in the chain, and a second input of the N additional two-input “Exclusive OR” and/or “Exclusive NOR” gates being connected to an asynchronous output of a subsequent synchronous chaotic oscillator block in the chain.

8. The generator according to claim 6, wherein the generator comprises a plurality of N blocks of synchronous chaotic oscillators combined into a chain forming a ring structure, clock inputs of the synchronous chaotic oscillators being combined together and connected to a common clock signal, and synchronous outputs of the synchronous chaotic oscillators being connected to an N-bit output of the generator, and a set of N additional two-input “Exclusive OR” and/or “Exclusive NOR” gates, so that an output of each of the N additional two-input “Exclusive OR” and/or “Exclusive NOR” gates is connected to a modulation input of a corresponding one of the N blocks of synchronous chaotic oscillators, a first input of the N additional two-input “Exclusive OR” and/or “Exclusive NOR” gates being connected to an asynchronous output of a previous synchronous chaotic oscillator block in the chain, and a second input of the N additional two-input “Exclusive OR” and/or “Exclusive NOR” gates being connected to an asynchronous output of a subsequent synchronous chaotic oscillator block in the chain.

9. The generator according to claim 4, wherein the digital chaotically oscillating autonomous Boolean network is combined with a D-trigger into a synchronous chaotic oscillator block having a clock input connected to a clock input of the D-trigger, a modulation input connected to a modulation input of the autonomous Boolean network, an asynchronous output connected to the output of the autonomous Boolean network, and a synchronous output connected to an output of the D-trigger, the output of the autonomous Boolean network being connected to a data input of the D-trigger.

10. The generator according to claim 9, wherein the generator comprises an additional two-input “Exclusive OR” and/or “Exclusive NOR” gate, a first input of the additional two-input “Exclusive OR” and/or “Exclusive NOR” gate being connected to an input of external modulation, a second input of the additional two-input “Exclusive OR” and/or “Exclusive NOR” gate being connected to the output of the D-trigger, and an output of the additional two-input “Exclusive OR” and/or “Exclusive NOR” gate being connected to the modulation input of the autonomous Boolean network.

11. The generator according to claim 9, wherein the generator comprises a plurality of N blocks of synchronous chaotic oscillators combined into a chain forming a ring structure, clock inputs of the synchronous chaotic oscillators being combined together and connected to a common clock signal, and synchronous outputs of the synchronous chaotic oscillators being connected to an N-bit output of the generator, and a set of N additional two-input “Exclusive OR” and/or “Exclusive NOR” gates, so that an output of each of the N additional two-input “Exclusive OR” and/or “Exclusive NOR” gates is connected to a modulation input of a corresponding one of the N blocks of synchronous chaotic oscillators, a first input of the N additional two-input “Exclusive OR” and/or “Exclusive NOR” gates being connected to an asynchronous output of a previous synchronous chaotic oscillator block in the chain, and a second input of the N additional two-input “Exclusive OR” and/or “Exclusive NOR” gates being connected to an asynchronous output of a subsequent synchronous chaotic oscillator block in the chain.

12. The generator according to claim 10, wherein the generator comprises a plurality of N blocks of synchronous chaotic oscillators combined into a chain forming a ring structure, clock inputs of the synchronous chaotic oscillators being combined together and connected to a common clock signal, and synchronous outputs of the synchronous chaotic oscillators being connected to an N-bit output of the generator, and a set of N additional two-input “Exclusive OR” and/or “Exclusive NOR” gates, so that an output of each of the N additional two-input “Exclusive OR” and/or “Exclusive NOR” gates is connected to a modulation input of a corresponding one of the N blocks of synchronous chaotic oscillators, a first input of the N additional two-input “Exclusive OR” and/or “Exclusive NOR” gates being connected to an asynchronous output of a previous synchronous chaotic oscillator block in the chain, and a second input of the N additional two-input “Exclusive OR” and/or “Exclusive NOR” gates being connected to an asynchronous output of a subsequent synchronous chaotic oscillator block in the chain.

13. The generator according to claim 2, wherein both two-input “Exclusive OR” and/or “Exclusive NOR” gates have additional third logic inputs, which are combined together and connected to an additional external modulation input of the digital chaotically oscillating autonomous Boolean network.

14. The generator according to claim 13, wherein the generator has a shutdown input, both “Exclusive OR” and/or “Exclusive NOR” gates have additional shutdown inputs with the possibility of forcibly switching the output of both gates to a logic zero or logic one state regardless of a state of the other inputs, the additional shutdown inputs being combined together and connected to a specified generator shutdown input.

15. The generator according to claim 2, wherein the generator has a shutdown input, both “Exclusive OR” and/or “Exclusive NOR” gates have additional shutdown inputs with the possibility of forcibly switching the output of both gates to a logic zero or logic one state regardless of a state of the other inputs, the additional shutdown inputs being combined together and connected to a specified generator shutdown input.

16. The generator according to claim 3, wherein the generator has a shutdown input, both “Exclusive OR” and/or “Exclusive NOR” gates have additional shutdown inputs with the possibility of forcibly switching the output of both gates to a logic zero or logic one state regardless of a state of the other inputs, the additional shutdown inputs being combined together and connected to a specified generator shutdown input.

17. The generator according to claim 13, wherein the digital chaotically oscillating autonomous Boolean network is combined with a D-trigger into a synchronous chaotic oscillator block having a clock input connected to a clock input of the D-trigger, a modulation input connected to a modulation input of the autonomous Boolean network, an asynchronous output connected to the output of the autonomous Boolean network, and a synchronous output connected to an output of the D-trigger, the output of the autonomous Boolean network being connected to a data input of the D-trigger.

18. The generator according to claim 17, wherein the generator comprises an additional two-input “Exclusive OR” and/or “Exclusive NOR” gate, a first input of the additional two-input “Exclusive OR” and/or “Exclusive NOR” gate being connected to an input of external modulation, a second input of the additional two-input “Exclusive OR” and/or “Exclusive NOR” gate being connected to the output of the D-trigger, and an output of the additional two-input “Exclusive OR” and/or “Exclusive NOR” gate being connected to the modulation input of the autonomous Boolean network.

19. The generator according to claim 14, wherein the digital chaotically oscillating autonomous Boolean network is combined with a D-trigger into a synchronous chaotic oscillator block having a clock input connected to a clock input of the D-trigger, a modulation input connected to a modulation input of the autonomous Boolean network, an asynchronous output connected to the output of the autonomous Boolean network, and a synchronous output connected to an output of the D-trigger, the output of the autonomous Boolean network being connected to a data input of the D-trigger.

20. The generator according to claim 19, wherein the generator comprises an additional two-input “Exclusive OR” and/or “Exclusive NOR” gate, a first input of the additional two-input “Exclusive OR” and/or “Exclusive NOR” gate being connected to an input of external modulation, a second input of the additional two-input “Exclusive OR” and/or “Exclusive NOR” gate being connected to the output of the D-trigger, and an output of the additional two-input “Exclusive OR” and/or “Exclusive NOR” gate being connected to the modulation input of the autonomous Boolean network.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0067] Other distinctive features and advantages of this invention clearly follow from the description provided below for illustration purposes, without limitations, using the references to the accompanying drawings, in which:

[0068] FIG. 1 shows a functional diagram of the autonomous Boolean network according to the invention;

[0069] FIG. 2 shows a logical structure of the autonomous Boolean network using XOR elements according to the invention;

[0070] FIG. 3 shows a logical structure of the autonomous Boolean network using XNOR elements according to the invention;

[0071] FIG. 4 shows a logical structure of the autonomous Boolean network using XOR elements and input inversion of the “counting ones” element according to the invention;

[0072] FIG. 5 shows a logical structure of the autonomous Boolean network using XNOR elements and input inversion of the “counting ones’ element according to the invention;

[0073] FIG. 6 shows a logical structure of the autonomous Boolean network using XOR and XNOR elements according to the invention:

[0074] FIG. 7 shows a logical structure of the autonomous Boolean network using XNOR and XOR elements according to the invention;

[0075] FIG. 8 shows a logical structure of the autonomous Boolean network using XOR and XNOR elements and input inversion of the “counting ones” element according to the invention;

[0076] FIG. 9 shows a logical structure of the autonomous Boolean network using XNOR and XOR elements and input inversion of the “counting ones” element according to the invention;

[0077] FIG. 10 shows a logical structure of the autonomous Boolean network having a modulation input according to the invention;

[0078] FIG. 11 shows a logical structure of the autonomous Boolean network having a modulation input and enabled generation according to the invention,

[0079] FIG. 12 shows the layout of the synchronous chaotic oscillator based on the described Boolean networks according to the invention,

[0080] FIG. 13 shows the designation of the synchronous chaotic oscillator according to the invention;

[0081] FIG. 14 shows a variant of the synchronous chaotic oscillator using the previous value as a seed according to the invention; and

[0082] FIG. 15 shows a diagram of the random number generator based on a synchronous chaotic oscillator according to the invention.

[0083] Indications on the drawings are as follows: [0084] 1—first logic element; [0085] 2—second logic element; [0086] 3—third logic element; [0087] 4—XOR gate; [0088] 5—XNOR gate; [0089] 6—synchronous chaotic oscillator; [0090] 7—chaotic oscillator; [0091] 8—D-trigger; [0092] Modulation—modulation input; [0093] Enable—enabled generation input; [0094] Out—output; [0095] Sync out—synchronous output; [0096] Async out—asynchronous output; [0097] Clock—clock signal.

[0098] According to FIGS. 1-15, a true random number generator comprising a digital chaotically oscillating autonomous Boolean network as an entropy source includes the following. A digital chaotically oscillating autonomous Boolean network includes three logic elements: 1—first, 2—second, and 3—third, connected to each other, two of which (1 and 2) represent two-input “Exclusive OR” and/or “Exclusive NOR” gates, and the third logic element (3) has three inputs (inputs of all logic elements are designated by Roman numerals I, II, and III) and one output.

[0099] Logic element 3 implements a special logic “counting ones” function, in which its output is set to a logic one if a logic one is present at no more than one of its inputs, otherwise it is set to a logic zero.

[0100] The output of the first two-input logic element 1 is preferably connected to the first input of the second two-input logic element 2 and to the second input of the third logic “counting ones” element 3. The output of the second two-input logic element 2 is connected to its second input, to the second input of the first two-input logic element 1, and to the third input of the third logic “counting ones” element 3. The output of the third logic “counting ones” element 3 is connected to its first input, to the first input of the first two-input logic element 1, and to the output of the entire network.

[0101] The second and/or third inputs of the third logic “counting ones” element 3 can be inverted.

[0102] In a particular embodiment of the invention, both two-input gates 1 and 2 (“Exclusive OR” and/or “Exclusive NOR”) have additional third logic inputs, which are combined together and connected to an additional external modulation input of a digital chaotically oscillating autonomous Boolean network (see FIG. 10).

[0103] In a particular embodiment of the invention, the generator has a shutdown input, and both “Exclusive OR” and/or “Exclusive NOR” gates have additional shutdown inputs with the possibility of forcibly switching the output of both said gates to the state of logic zero or logic one regardless of the state of other inputs, these inputs being combined together and connected to the specified generator shutdown input (see FIG. 11).

[0104] In particular, a digital chaotically oscillating autonomous Boolean network can be combined with a D-trigger into a synchronous chaotic oscillator block having a clock input connected to the clock input of the D-trigger, a modulation input connected to the modulation input of the autonomous Boolean network, an asynchronous output connected to the output of the autonomous Boolean network, and a synchronous output connected to the output of the D-trigger, while the output of the autonomous Boolean network is connected to the data input of the D-trigger (see FIGS. 12-13).

[0105] In a particular embodiment of the invention, the generator includes an additional two-input “Exclusive OR” and/or “Exclusive NOR” gate, the first input of which is connected to the external modulation input, the second input is connected to the output of the D-trigger, and the output is connected to the modulation input of the autonomous Boolean network (see FIG. 14).

[0106] In a particular embodiment, the invention includes a plurality of N blocks of synchronous chaotic oscillators combined into a ring structure, the clock inputs of which are combined together and connected to a common clock signal, and their synchronous outputs are connected to the N-bit output of the generator, and a plurality of N additional two-input “Exclusive OR” and/or “Exclusive NOR” gates so that the output of each such gate is connected to the modulation input of the corresponding block of the synchronous chaotic oscillator, its first input is connected to the asynchronous output of the previous synchronous chaotic oscillator block in the chain, and the second input is connected to the asynchronous output of the subsequent synchronous chaotic oscillator block in the chain (see FIG. 15).

[0107] Implementation of the Invention

[0108] The true random number generator operates as follows. We will provide the most comprehensive example of the implementation of the invention with the realization that this example does not limit the application of the invention.

[0109] A digital chaotically oscillating autonomous Boolean network is formed from three logic elements connected to each other, two of which represent two-input “Exclusive OR” and/or “Exclusive NOR” gates, and the third logic element is used to implement a special logical “counting ones” function, in which its output is set to a logic one if a logic one is present at no more than one of its inputs, otherwise it is set to a logic zero.

[0110] A synchronous chaotic oscillator (SCO) is formed, which has clock and modulation inputs and two outputs—a synchronous output used to obtain a random number and an asynchronous output required for modulation of other SCOs. Along each front of the clock signal, a D-trigger captures the value of the asynchronous signal. The obtained value is fed to the synchronous output and, on the other hand, is used for conditional inversion of the input modulation signal using a two-input XOR gate.

[0111] The random number generator is built on such SCO blocks.

[0112] A multi-bit true random number generator is built according to a circuit, in which a ring of SCO blocks is used, modulated in opposite directions. The modulation input of each SCO block receives a signal from the “Exclusive OR” gate, the inputs of which are connected to the asynchronous outputs of the previous and subsequent SCO blocks in the ring.

INDUSTRIAL APPLICABILITY

[0113] The proposed true random number generator can be practically realized by those skilled in the art and, once implemented, will provide the realization of the declared purpose, which makes it possible to conclude that the industrial applicability criterion of the invention is met.

[0114] In accordance with the proposed invention, a prototype of a true random number generator was produced. During the study, both the already mentioned Zhang and Rosin generators as well as the generator based on the described Boolean network were experimentally tested in the PLIC. The random nature of the numbers of the proposed generator is confirmed by the following experiment, which was carried out using the following PLIC: Altera Cyclone IV EP4CE22F17C6N. The network is in a “reset” state, i.e., the outputs of all logic elements are set to a predefined state of “zero”. Then, in one clock cycle, the reset signal is removed, and in the next clock cycle, the state of the output of the chaotic oscillator is captured. The data obtained during multiple network restarts passed the randomness test and did not show significant correlation with each other at a clock frequency of up to 150 megahertz, which indicates the onset of chaos in less than 7 nanoseconds. After the whitening procedure, the resulting random numbers passed the NIST randomness tests.

[0115] Thus, testing of the prototype of a true random number generator has shown that the declared technical result is achieved (namely, an increase in the true random number generation rate while decreasing energy consumption) due to the fact that a digital chaotically oscillating autonomous Boolean network includes three logic elements connected to each other, two of which represent two-input “Exclusive OR” and/or “Exclusive NOR” gates, and the third logic element has three inputs and one output, and implements a special logical “counting ones” function, in which a logic one is set at its output if a logic one is present at no more than one of its inputs, otherwise a logic zero is set.

[0116] In addition, the technical result of the invention is a set of the only possible networks of logic elements, each of which has the following properties:

[0117] 1. It has no stable states and short cycles, which would cause ordering of the network operation and disappearance of Boolean chaos.

[0118] 2. Output signals of all elements have the lowest theoretically possible autocorrelation, which forces the network to fall into a chaotic behavior.

[0119] 3. There is no correlation of the shape of the output signals of all elements, which excludes cross-phase modulation of the elements during network operation.

[0120] 4. It has the smallest possible size, which provides the fastest possible chaos build-up rate due to short propagation loops within the network.

[0121] 5. It has an external modulation input that allows destabilizing the network (thus, preventing physical equilibrium) and combining networks into scalable clusters using cross-modulation.

[0122] In addition, only one network from this set uses the logic elements, which are input-symmetrical.

[0123] Thus, such networks enable creation of a random number generator with the following unique characteristics:

[0124] 1. The resulting numbers are truly random, which allows using them for cryptographic purposes.

[0125] 2. The random number generation rate is so high that the behavior of the network is unpredictable even during the propagation of the signal through several logic elements. Thus, when implemented in microprocessor systems, a random number can be obtained in one clock cycle. Such generation rate virtually satisfies any possible need.

[0126] 3. The modulation input allows to further improve the characteristics, since it can be fed with another random number (a so-called “seed” of the proposed random number generator). This forces the network to start from a new state each time.

[0127] 4. The same input allows for cross-modulation of bits of the proposed generator, thereby increasing the chaos onset rate.

[0128] 5. The minimum network size makes the proposed generator the most economical in terms of energy consumption.

[0129] 6. The proposed generator can be implemented with equal efficiency on both discrete elements and in PLICs or ASICs.

[0130] 7. The design of the proposed generator is simple and the costs of its implementation are negligible, which makes it possible to use it everywhere, including low-cost and energy-saving devices.

LITERATURE

[0131] [1] Maxim Semiconductors. Building a Low-Cost White-Noise Generator. Application note 3469. [0132] [2] R. Zhang, H. L. D. de S. Cavalcante, Z. Gao, D. J. Gauthier, J. E. S. Socolar, M. M. Adams, and D. P. Lathrop. Boolean Chaos. Phys. Rev. E 80, 045202 (2009). [0133] [3] David P. Rosin, Damien Rontani, Daniel J. Gauthier, and Eckehard Schöll. Experiments on autonomous Boolean networks. Chaos 23, 025102 (2013). [0134] [4] Hugo L. D. de S. Cavalcante, Daniel J. Gauthier, Joshua E. S. Socolar and Rui Zhang. On the origin of chaos in autonomous Boolean networks. Phil. Trans. R. Soc. A 368, 495-513 (2010). [0135] [5] David Rosin, Dynamics of Complex Autonomous Boolean Networks. Doctoral dissertation. Technische Universitft Berlin.