CN113138752B - Random number generator, random number generation circuit and random number generation method - Google Patents
Random number generator, random number generation circuit and random number generation method Download PDFInfo
- Publication number
- CN113138752B CN113138752B CN202010174948.4A CN202010174948A CN113138752B CN 113138752 B CN113138752 B CN 113138752B CN 202010174948 A CN202010174948 A CN 202010174948A CN 113138752 B CN113138752 B CN 113138752B
- Authority
- CN
- China
- Prior art keywords
- random number
- logic
- random
- shift register
- storage element
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/58—Random or pseudo-random number generators
- G06F7/588—Random number generators, i.e. based on natural stochastic processes
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- Tests Of Electronic Circuits (AREA)
- Manipulation Of Pulses (AREA)
Abstract
本发明公开了一种随机数生成器、随机数生成电路及随机数生成方法，随机数生成电路包含随机数生成器并可执行随机数生成方法，随机数生成器包含具有N个存储元件的移位寄存器以及组合逻辑电路，N个存储元件在静止状态时接收随机种子，并且在多个频率周期内重复进行位移位动作，组合逻辑电路依据随机种子和从外部来源获得的随机比特流而产生输出序列。
The present invention discloses a random number generator, a random number generation circuit and a random number generation method. The random number generation circuit includes a random number generator and can execute the random number generation method. The random number generator includes a shift register with N storage elements and a combinational logic circuit. The N storage elements receive random seeds in a static state and repeatedly perform bit shifting actions within multiple frequency cycles. The combinational logic circuit generates an output sequence based on the random seeds and a random bit stream obtained from an external source.
Description
Technical Field
The invention relates to a random number generator, a random number generation circuit and a random number generation method, which can rapidly generate an output sequence with high randomness.
Background
Random numbers have many uses, for example, they can be used to generate one-time password (OTP), the randomness (randomness) of which is important to avoid attacks, otherwise by observing several one-time passwords, it is possible to predict the next password. In addition, the random number sequence is widely used in cryptography, which is indispensable for new communication technologies such as the fifth generation mobile communication technology (5G) and the internet of things (Internet of Things, ioT), and when the random number sequence is used in the communication technology, the speed of generating the random number sequence needs to be considered, so that the randomness and the speed are two important considerations for designing the random number generator.
Disclosure of Invention
The invention relates to a random number generator, a random number generation circuit and a random number generation method, which can rapidly generate an output sequence with high randomness.
According to one embodiment, a random number generator is provided, which operates according to a plurality of frequency cycles, the random number generator includes a shift register, a combinational logic circuit, and a feedback terminal, the shift register includes N storage elements electrically connected in series, wherein the N storage elements respectively receive N bits of random seeds in a static state, and the shift register repeatedly performs bit shifting operations in the plurality of frequency cycles. The combinational logic circuit comprises a first input end, a second input end and at least one logic gate, wherein the first input end is electrically connected with an external source and can continuously receive a random bit stream from the external source in a plurality of frequency periods, the second input end is electrically connected with the first storage element and is used for grabbing data stored in the first storage element, and the at least one logic gate is used for executing at least one logic operation on the random bit stream and the data grabbed by the second input end. The feedback end is electrically connected with the second storage element and outputs an output sequence in a plurality of frequency periods according to at least one logic operation, and the data stored in the second storage element is continuously updated in the output sequence in the plurality of frequency periods.
According to another embodiment, a random number generating circuit is provided, which includes a first random number generator, the first random number generator includes a first shift register, a first combinational logic circuit, and a first feedback terminal, the first shift register includes N first storage elements electrically connected in series, wherein the N first storage elements include a first storage element and a second storage element of the first shift register, the N first storage elements correspondingly receive N random seeds in a stationary state, and the first shift register repeatedly performs a first bit shifting operation in a plurality of frequency periods. The first combinational logic circuit comprises a first input end, a second input end and at least one first logic gate, wherein the first input end of the first combinational logic circuit continuously receives a first random bit stream from a first external source in a plurality of frequency periods, the second input end of the first combinational logic circuit is electrically connected with a first storage element of a first shift register and grabs data stored in the first storage element of the first shift register, and the at least one first logic gate performs at least one first logic operation on the first random bit stream and the data grabbed by the second input end of the first combinational logic circuit. The first feedback end is electrically connected with the second storage element of the first shift register, outputs an output sequence in a plurality of frequency periods according to at least one first logic operation, and continuously updates the data stored in the second storage element of the first shift register in the output sequence in the plurality of frequency periods.
According to another embodiment, a random number generating method is provided, which is applied to a random number generating circuit, wherein the random number generating circuit comprises a shift register and a combinational logic circuit, and the random number generating method comprises the steps of firstly receiving an N-bit random seed in a static state, then the shift register repeatedly performs a bit shifting action according to the random seed and the random bit stream, the combinational logic circuit continuously receives the random bit stream in a plurality of frequency periods, then performs at least one logic operation on the random bit stream and data stored in a first storage element of the shift register, then outputs an output sequence in a plurality of frequency periods according to the at least one logic operation, and then updates the data stored in a second storage element of the shift register with the output sequence.
For a better understanding of the above and other aspects of the invention, reference will now be made in detail to the following examples, examples of which are illustrated in the accompanying drawings:
Drawings
FIG. 1 is a schematic diagram of a random number generator according to an embodiment of the present disclosure;
FIGS. 2A-2C are schematic diagrams illustrating the operation of the random number generator of FIG. 1;
FIG. 3 is a schematic diagram showing a random sequence input received by a random number generator;
FIG. 4 is a waveform diagram illustrating the operation of the random number generator of FIG. 3;
FIG. 5 is a schematic diagram illustrating the source of random seeds and the input of random sequences;
FIG. 6A is a schematic diagram of another embodiment of a combinational logic circuit;
FIG. 6B is a schematic diagram of another embodiment of a combinational logic circuit;
FIG. 7 is a schematic diagram of a random number generation circuit with a second order random number generator;
FIG. 8 is a truth table for the output signal of the random number generator of FIG. 7;
FIG. 9A is a schematic diagram illustrating the sources of random seeds corresponding to two random number generators in the same random number generation circuit;
FIG. 9B is a schematic diagram showing a random number generation circuit comprising two random number generators and receiving a random bit stream from an external source;
FIG. 10 is a schematic diagram of a random number generation circuit with a third order random number generator;
Fig. 11A and 11B are schematic diagrams showing that the connection relationship between the input terminal of the combinational logic circuit and the storage element in the shift register can be arbitrarily changed.
[ Symbolic description ]
100,100A,100b,200,300,400a,400b,500a,500b, 600',600a,600b,600c,700b: random number generator
11,21,31,41A,41b,51a,51b,61a,61b,61c random seed
33,63,73 External sources
35,45,551,553 Bitmap (dot matrix data table)
35A.35b lattice
40,50,60,70 Random number generating circuit
101,101A,101b,201,401a,401b,501a,501b, 601',601a,601b,601c, 702 b: linear feedback shift register
103,103A,103b,203,403a,403b,503a, 603b, 603',603a,603b,603c,703b, combinational logic circuit
1031,4031A,4031b,6031 ',6032,6032',7031,7032: logic gate
Clk frequency signal
In1, in2, in3, in1', in2': input terminal
Nf, nf1, nf2, nf3: feedback end
P, S random bit stream
P1, p2, p3, p4, q1, q2, q3, q4, q5, s1, s2, s3, s4: memory element
Q: output sequence
Xout, xout' output
Detailed Description
The present invention will be further described in detail below with reference to specific embodiments and with reference to the accompanying drawings, in order to make the objects, technical solutions and advantages of the present invention more apparent.
In the following description, which is to be used to explain the present invention, the details are presented merely to provide a thorough understanding of the disclosed embodiments, implementations of the embodiments do not necessarily include the provided details, and further, known structures or devices are depicted merely by way of example to simplify the illustration.
Various embodiments of random number generation circuits are presented in the specification, which can produce an output sequence Q with a high degree of randomness at high speed.
In this case, since two random sources including a random seed obtained from an entropy source and a random bit stream from an external source are used, a random number generator in a random number generation circuit is based on hardware, so that a yield rate of an output sequence Q can be ensured, and even if a hardware design of the random number generation circuit is stolen by reverse engineering (REVERSE ENGINEERING) after the random bit stream is imported, the output sequence Q cannot be predicted, and an embodiment of the random number generation circuit will be described below.
Fig. 1 is a schematic diagram of a random number generator according to an embodiment of the present disclosure, where the random number generator 100 includes a Linear Feedback shift register (Linear Feedback SHIFT REGISTER, LFSR) 101, a combinational logic circuit 103, and a Feedback terminal Nf.
The linear feedback shift register 101 has M storage elements (M is a positive integer), where the M storage elements are electrically connected in series, which may be, for example, D flip-flops (D flops), assuming M is equal to "4" in fig. 1. The linear feedback shift register 101 receives a random seed 11 from an entropy source, which may be, for example, a lattice data table (Bitmap table) with a physical copy function (PHYSICALLY UNCLONABLE FUNCTION, PUF), a random telegraph noise (Random Telegraph Noise, RTN) source, an astable electronic oscillator, a Real-Time Clock (RTC), a software-based seed, or an algorithm-based seed.
The storage elements q 1-q 4 in the linear feedback shift register 101 operate according to the clock signal clk, each storage element q 1-q 4 represents a bit "0" or "1", the period of the clock signal is referred to herein as a clock period, and the storage elements q1, q2, q3, q4 perform bit shifting according to a clock-by-clock basic sequence (clock-by-clock basic).
The combinational logic circuit 103 comprises two inputs in1, in2, the input in1 receiving a random bit stream P from an external source, which may be the same or different from the entropy source, the external source providing the random bit stream P may be an astable flip-flop, a Random Telegraph Noise (RTN) device, a Real Time Clock (RTC), an astable electronic oscillator, etc., or the random bit stream P may be from another random number generator.
The input terminal in2 captures stored data from one of the storage elements q1, q2, q3, q4 (e.g., storage element q 1), and the combinational logic circuit 103 performs a logic operation on the input terminals in1, in2 to produce an output xout, the actual logic operation depending on the logic gates within the combinational logic circuit 103.
The feedback terminal Nf is electrically connected to the storage element Q4 and the output xout of the combinational logic circuit 103, and meanwhile, the feedback terminal Nf is also used as the output of the random number generator 100, the logic level of the feedback terminal Nf is updated once in each frequency period of the frequency signal clk, the logic level of the feedback terminal Nf is used as the output sequence Q, the logic level belongs to binary logic, and two levels (logic "1" and logic "0") exist, so that the output sequence Q is not only highly random, but also difficult to predict according to the embodiment of the present invention.
According to the present embodiment, the linear feedback shift register 101 receives the random seed 11 when the random number generator 100 is started or reset, and the linear feedback shift register 101 stops receiving the random seed 11 when the bit shift operation is performed, and in fig. 2A, 2B and 2C, the combinational logic circuit 103 only shows one logic gate (such as an exclusive or (XOR) gate), which does not limit the implementation of the combinational logic circuit 103.
Fig. 2A to 2C are schematic diagrams illustrating operations of the random number generator of fig. 1, and frequency signals are not shown for convenience of illustration. Fig. 2A corresponds to a stationary state, which indicates that the linear feedback shift register 101 is receiving the random seed 11, and fig. 2B and 2C correspond to an operation state of the random number generator 10, which indicates that the linear feedback shift register 101 is performing a bit shifting operation, wherein fig. 2B and 2C respectively represent that the random number generator 100 is in a clock cycle clk1 and a clock cycle clk2, the clock cycle clk1 represents a first clock cycle after the stationary state, and the clock cycle clk2 represents a next clock cycle of the clock cycle clk 1.
Referring to fig. 2A, in the rest state, the storage element q1 receives and stores the last bit sd1 of the random seed 11, the storage element q2 receives and stores the penultimate bit sd2 of the random seed 11, the storage element q3 receives and stores the positive second bit sd3 of the random seed 11, and the storage element q4 receives and stores the positive first bit sd4 of the random seed 11. In the initial state, the input terminals in1, in2 of the combinational logic circuit 103 have not received any signal yet, and thus the value of the feedback terminal Nf in the stationary state is "unknown (unknown)".
Referring to FIG. 2B, before the clock cycle clk1 starts, the storage elements q 1-q 4 respectively store the last bit (sd 1), the penultimate bit (sd 2), the positive second bit (sd 3) and the positive first bit (sd 4) of the random seed 11.
At this time, the input terminal in1 of the combinational logic circuit 103 receives one bit P (clk 1) of the random bit stream P in the clock period clk1, and the input terminal in2 of the combinational logic circuit 103 grabs the data stored in the storage element q1, i.e. the last bit (sd 1) of the random seed 11. Because the logic inputs of the logic gate 1031 are electrically connected to the input terminals in1, in2 of the combinational logic circuit 103, respectively, the logic gate 1031 performs an exclusive or (XOR) operation on the random bit stream P (clk 1) received during the frequency period clk1 and the data captured by the input terminal in2 during the frequency period clk1 (i.e., the last bit (sd 1) of the random seed 11), so that the feedback terminal Nf during the frequency period clk1 is equal to the exclusive or (XOR) operation result between the random bit stream P (clk 1) received during the frequency period clk1 and the last bit (sd 1) of the random seed 11.
Referring to fig. 2C, in the clock cycle clk2, the linear feedback shift register 101 performs a shift operation, and only the shift operation of the storage element q1 is taken as an example for simplicity, and the shift operation of other storage elements q2, q3, q4 will not be described again.
At the clock cycle clk2, the data q2 (clk 1) =sd 2 stored by the storage element q2 at the clock cycle clk1 is transferred to the storage element q1 (data q1 (clk 2)), so as can be seen from fig. 2C, at the clock cycle clk2, the data stored in the storage element q1 is equivalent to the last second bit of the random seed 11, that is, q1 (clk 2) =q2 (clk 1) =sd 2.
As shown in fig. 2C, during the clock cycle clk2, the input terminal in1 of the combinational logic circuit 103 receives one bit (P (clk 2)) of the random bit stream P, and the input terminal in2 of the combinational logic circuit 103 grabs the data stored in the storage element q1, i.e. the penultimate bit (sd 2) of the random seed 11. Similar to the illustration of fig. 2B, the output sequence Q generated at the frequency period clk2 is equivalent to the exclusive or (XOR) result between the random bit stream P (clk 2) received at the frequency period clk2 and the penultimate bit (sd 2) of the random seed 11.
Fig. 3 is a schematic diagram showing a random sequence input received by the random number generator 200, the random number generator 200 includes a linear feedback shift register 201 having storage elements q 1-q 4, a combinational logic circuit 203, and a feedback terminal Nf, the linear feedback shift register 201 is initialized by a random seed 21 ("1000"), and when the linear feedback shift register 201 operates according to a frequency period, a signal waveform variation related to the operation of the random number generator 200 is shown in fig. 4.
Fig. 4 is a waveform diagram of the random number generator in fig. 3, wherein the vertical axis represents the random bit stream P, the data stored in the storage element Q4, the data stored in the storage element Q3, the data stored in the storage element Q2, the data stored in the storage element Q1, the output sequence Q and the frequency signal clk from top to bottom, and the horizontal axis represents time, respectively, and a plurality of continuous frequency periods clk=1 to 17 are displayed.
The dashed boxes show that the random seed "1000" is stored in the storage elements q1, q2, q3, q4, and the dashed arrows A1, A2 represent the shift-bit actions performed by the linear feedback shift register 201.
To explain the signal associated with the broken line arrow A1, the data stored in the storage element q4 is at the high logic level "1" in the frequency period clk=1, then the data stored in the storage element q4 in the frequency period clk=1 (high logic level "1") is moved to the storage element q3 in the frequency period clk=2, so the data stored in the storage element q3 in the frequency period clk=2 is at the high logic level "1", then the data stored in the storage element q3 in the frequency period clk=2 (high logic level "1") is moved to the storage element q2 in the frequency period clk=3, so the data stored in the storage element q2 in the frequency period clk=3 is at the high logic level "1", and similarly, the data stored in the storage element q2 in the frequency period clk=3 (high logic level "1") is moved to the storage element q1 again in the frequency period clk=4, so the data stored in the storage element q1 in the frequency period clk=4 is at the high logic level "1".
Further, the signal associated with the broken line arrow A2 is described, in which the data stored in the storage element Q4 is updated with the output sequence Q generated in the frequency cycle clk=1 in the frequency cycle clk=2, then the data stored in the storage element Q3 is updated with the data stored in the storage element Q4 in the frequency cycle clk=2 in the frequency cycle clk=3, then the data stored in the storage element Q2 is updated with the data stored in the storage element Q3 in the frequency cycle clk=3 in the frequency cycle clk=4, and similarly the data stored in the storage element Q1 is updated with the data stored in the storage element Q2 in the frequency cycle clk=4 in the frequency cycle clk=5.
The dashed circles c1, c2, c3 collectively show the operation of the combinational logic circuit 203 at the frequency period clk=1, the dashed circle c1 corresponds to the random bit stream P at the frequency period clk=1, i.e., the high logic level "1", and the dashed circle c2 corresponds to the data stored in the storage element q1 at the frequency period clk=1, i.e., the low logic level "0".
The dashed circle c3 corresponds to the output sequence Q generated at the frequency period clk=1, i.e., the high logic level "1", the output sequence Q generated at the frequency period clk=1 is the output of the combinational logic circuit 203, as shown in fig. 3, the combinational logic circuit 203 receives the random bit stream P (p=1 at clk=1) and the data stored in the storage element Q1 (q1=0 at clk=1) via the input terminals in1, in2, respectively, then transfers the data stored in the random bit stream P and the storage element Q1 to the logic input of the logic gate of the combinational logic circuit 203, then performs exclusive or (XOR) operation on the data stored at the frequency period clk=1 for the random bit stream P and the storage element Q1, and the output sequence Q generated at the frequency period clk=1 is equivalent to the high logic level "1". In addition, a broken line circle c4 indicates that the output of the combinational logic circuit 203 is transferred to the storage element q4 again for storage when the frequency period clk=2.
The relationship between the random bit stream P, the data stored in the storage elements Q1-Q4, and the waveform of the output sequence Q for the remaining frequency periods can be deduced as shown in the frequency period clk=1, summarizing the data sequence of fig. 4, the random seed "1100" and the random bit stream P "1001-0100-0101-1101" are received when in a stationary state, and the output sequence Q generated by the random number generator 200 is "1000-1100-1001-0100".
It should be noted that the output sequence Q is related to both the random seed value and the random bit stream P, and even if the random seed remains unchanged, the output sequence Q follows the dynamically generated random bit stream change, for example, assuming that the random number generator 200 of fig. 3 always receives the same random seed "1000" and a different random bit stream P ' = "0011-0010-1110-0110.", the output sequence Q ' corresponding to the random bit stream P ' will be "0001-1001-0010-100.".
Fig. 5 is a schematic diagram illustrating the source of the random seed and the random sequence input, the random seed 31 may be from a bitmap corresponding to a dot matrix data table with physical repeating function, the random bit stream P is from an external source 33, in the bitmap 35, it is assumed that the white grid 35a represents bit "0", the hatched grid 35b represents bit "1", the bitmap 35 may be used as an entropy source of non-deterministic, and the random bit stream P from the external source 33 is difficult to predict, so the output sequence Q has high randomness.
In practical applications, the logic gates used in the combinational logic circuit, the structure and/or connection relationship of the logic gates are not limited, and fig. 6A and 6B illustrate a combinational logic circuit having a two-stage structure.
Fig. 6A is a schematic diagram of another embodiment of a combinational logic circuit, and in fig. 6A, a random number generator 600 includes a 5-bit linear feedback shift register 601 (m=5), a combinational logic circuit 603, and a feedback terminal Nf. The combinatorial logic circuit 603 receives a random bit stream P from an external source 63.
The combinational logic circuit 603 comprises three inputs in1, in2, in3 and two logic gates 6031, 6032, the logic gates 6031, 6032 forming a two-stage arrangement, in fig. 6A, the logic gates 6031, 6032 are exclusive-or (XOR) gates, each logic gate 6031, 6032 comprises two logic inputs, the two logic inputs of the logic gate 6032 are electrically connected to the inputs in1, in2, respectively, the two logic inputs of the logic gate 6031 are electrically connected to the output and input in3 of the logic gate 6032, respectively, so that the logic gate 6032 can be defined as a first stage (first-stack) logic gate, and the logic gate 6031 can be defined as a second stage (second-stack) logic gate.
The input terminal in1 receives the random bit stream P, the input terminal in2 captures the data stored in the storage element Q1, so that the logic input of the logic gate 6032 receives the random bit stream P and the data stored in the storage element Q1 via the input terminals in1 and in2, respectively, and then the output of the logic gate 6032 is transferred to one logic input of the logic gate 6031, and the other logic input of the logic gate 6031 receives the data stored in the storage element Q3 via the input terminal in3, and then the logic gate 6031 generates the output sequence Q based on the output of the logic gate 6032 and the data stored in the storage element Q3. The bit shifting actions of the storage elements q1, q2, q3, q4 are not described here in detail.
In fig. 6A, the logic gate 6032 is used as a first stage logic gate to receive the random bit stream from the astable oscillator, and on the other hand, in fig. 6B, a second stage logic gate is used to receive the random bit stream P.
Fig. 6B is a schematic diagram of another embodiment of a combinational logic circuit, in fig. 6B, a random number generator 600 'includes a 5-bit linear feedback shift register 601' (m=5), a combinational logic circuit 603', and a feedback terminal Nf, and the combinational logic circuit 603' receives a random bit stream P from an external source 63.
The combinational logic circuit 603 'comprises three inputs in1, in2, in3 and two logic gates 6031', 6032', the logic gates 6031', 6032 'forming a two-stage arrangement, in fig. 6B, the logic gates 6031', 6032 'are exclusive-or (XOR) gates, each logic gate 603a', 603B 'comprises two logic inputs, the two logic inputs of the logic gate 6032' are electrically connected to the inputs in2, in3, respectively, and the two logic inputs of the logic gate 6031 'are electrically connected to the inputs in1 and the outputs of the logic gate 6032', respectively, so that the logic gate 6032 'can be defined as a first stage logic gate and the logic gate 6031' as a second stage logic gate.
The input terminal in1 receives the random bit stream P, the input terminal in2 captures the data stored in the storage element q1, the input terminal in3 captures the data stored in the storage element q2, then one logic input of the logic gate 6032 'receives the data stored in the storage element q1 via the input terminal in2, the other logic input receives the data stored in the storage element q2 via the input terminal in3, the logic gate 6032' performs a logic operation to generate a first-stage exclusive-or (XOR) output, and then the output of the logic gate 6032 'is transmitted to the logic gate 6031'. The logic inputs of logic gate 6031' receive the random bit stream P and the output of logic gate 6032', respectively, after which logic gate 6031' performs another logic operation to produce a second stage exclusive-or (XOR) output, i.e., output sequence Q. Bit shifting operations performed by the storage elements q1 to q4 are not described here.
In some applications, the random number generation circuit may comprise a plurality of random number generators, and FIG. 7 is a schematic diagram of a random number generation circuit having a second order random number generator, the random number generation circuit 40 comprising random number generators 400a, 400b, the random number generator 400b being defined as a first order (first-stage) random number generator, and the random number generator 400a being defined as a second order (second-stage) random number generator.
The random number generator 400b includes a linear feedback shift register 401b having storage elements p 1-p 4, a combinational logic circuit 403b, and a feedback terminal Nf2, wherein the combinational logic circuit 403b includes a logic gate 4031b having two logic inputs and two input terminals in1', in2', and the logic inputs of the logic gate 4031b are electrically connected to the input terminals in1', in2' of the combinational logic circuit 403b, respectively.
The random number generator 400a includes a linear feedback shift register 401a having storage elements q 1-q 4, a combinational logic circuit 403a, and a feedback terminal Nf1, the combinational logic circuit 403a includes a logic gate 4031a having two logic inputs and two input terminals in1, in2, and the logic inputs of the logic gate 4031a are electrically connected to the input terminals in1, in2 of the combinational logic circuit 403a, respectively.
In a stationary state, the linear feedback shift register 401b of the random number generator 400b receives the random seed 41b ("1000"), and the linear feedback shift register 401a of the random number generator 400a receives the random seed 41a ("1000"), and the linear feedback shift registers 401a, 401b each repeat the bit shift operation in response to a plurality of frequency cycles of the received frequency signal clk, assuming that the random seeds 41a, 41b are from different positions of the same bitmap.
To illustrate the operation of the random number generator 400b, after the linear feedback shift register 401b receives the random seed 41b in the static state, the storage elements P1, P2, P3, and P4 perform the bit shifting operation according to the frequency signal clk, the input terminal in1' of the combinational logic circuit 403b captures the data stored in the storage element P1, and the input terminal in2' of the combinational logic circuit 403b captures the data stored in the storage element P2, and performs the logic operation through the logic gate 4031b, and the combinational logic circuit 403b generates the output xout ' (i.e. the random bit stream P) at the feedback terminal Nf 2.
The operation of the random number generator 400a involves the random seed 41a received in a stationary state, the random bit stream P, the bit shifting action of the linear feedback shift register 401a, and the design of the combinational logic circuit 403 a. The internal design, connection and operation of the random number generator 400a are similar to those of the random number generator 300 of fig. 5, except that the random bit stream P of fig. 7 is derived from another random number generator 400b, and the random number generator 400a generates an output sequence Q at the feedback terminal Nf 1.
In fig. 7, the random seeds 41a, 41b come from different locations of the same dot matrix data table 45, the dot matrix data table 45 has a physical repeating function, the values of the random seeds 41a, 41b may be the same or different, or the linear feedback shift registers 401a, 401b may be selected from the same locations of the same dot matrix data table, in other words, the random seeds of the random number generator may be arbitrarily selected from any source capable of providing random data, such as an unsteady flip-flop, a random telegraph noise device, a real-time clock, an unsteady electronic oscillator, and the like.
Fig. 8 is a truth table of the output signal of the random number generator of fig. 7, the left and right tables correspond to the operation of the random number generators 400a and 400b, respectively, the random seed 41a supplied to the linear feedback shift register 401a in the rest state is "1000" as indicated by the dotted line box, and the random seed 41b supplied to the linear feedback shift register 401b in the rest state is "1000" as indicated by the dotted line box. The dashed arrows represent the bit shifting actions performed by the linear feedback shift registers 401a and 401 b.
Based on the random seed 41b ("1000") and the bit shifting action of the linear feedback shift register 401b, the combinational logic circuit 403b will generate a random bit stream p= "0011-0101-1110-0010-0110-1011-1100-0100-11" for a plurality of frequency cycles. Based on the random seed 41a ("1000"), the random bit stream P, and the bit shifting action of the linear feedback shift register 401a, the combinational logic circuit 403a generates an output sequence Q. The random bit stream P is equivalent to the data stored by the storage element P4 at the next frequency period. Therefore, the random bit stream P with the frequency period clk=1 to 33 is the same as the data stored in the storage element P4 in the frequency period clk2 to 34.
The output sequence Q generated during the frequency period clk=1 is equivalent to the low logic level "0" (not shown), as shown in fig. 4, the output sequence Q is equivalent to the data stored by the storage element Q4 during the next frequency period, for example, the output sequence Q is equivalent to the data stored by the storage element Q4 during the frequency period clk=k+1 during the frequency period K, so that, in fig. 8, the output sequence Q passing through the frequency periods clk=1 to 33 is "0010-0111-1001-1011-1101-0110-1010-1110-0.+ -. And the data stored by the storage element Q4 during the frequency periods clk2 to 34 are the same.
As shown in fig. 8, the data stored in the output sequence Q and the storage elements Q1, Q2, Q3, Q4, p1, p2, p3, p4 in the frequency period clk=1 to 34, it can be observed from fig. 8 that the output sequence Q has no fixed pattern between the frequency periods clk1 to 34, that is, the output sequence Q has high randomness.
Fig. 9A is a schematic diagram illustrating that two random number generators in the same random number generation circuit use random seeds of different sources, the random number generation circuit 50 includes random number generators 500a, 500b, the random number generator 500b includes a linear feedback shift register 501b having five storage elements p 1-p 5, a combinational logic circuit 503b, and a feedback terminal Nf2, and the random number generator 500a includes a linear feedback shift register 501a having four storage elements q 1-q 4, a combinational logic circuit 503a, and a feedback terminal Nf1.
In the rest state, the random number generator 500b receives the random seed 51b from the bitmap 553, the random number generator 500a receives the random seed 51a from the bitmap 551, the linear feedback shift registers 501a and 501b repeat the bit shift operation in response to a plurality of frequency periods of the received frequency signal clk, the random number generator 500b is defined as a first-order random number generator, and the random number generator 500a is defined as a second-order random number generator.
The operation of the random number generator 500b is related to the random seed 51b received in the rest state, the bit shifting action of the linear feedback shift register 501b, and the design of the combinational logic circuit 503b, while the operation of the random number generator 500a is related to the random seed 51a received in the rest state, the bit shifting action of the linear feedback shift register 501a, and the design of the combinational logic circuit 503 a. The random number generator 500b generates a random bit stream P at a feedback terminal Nf2, and the random number generator 500a generates an output sequence Q at a feedback terminal Nf 1.
In fig. 9A, the random seeds 51a, 51b are obtained from different sources, the random seed 51a transmitted to the random number generator 500a is from the dot matrix data table 551, and the random seed 51b transmitted to the random number generator 500b is from the dot matrix data table 553, and both dot matrix data tables 551, 553 have a physical repeating function.
Fig. 9B is a schematic diagram showing a random number generating circuit comprising two random number generators and receiving a random bit stream from an external source, the random number generating circuit 70 comprising random number generators 500a, 700B, the random number generator 700B comprising a linear feedback shift register 701B having five storage elements p 1-p 5, a combinational logic circuit 703B and a feedback terminal Nf2, the combinational logic circuit 703B further comprising logic gates 7031, 7032, the random number generator 500a being as shown in fig. 9A.
In the stationary state, the random number generator 700b receives the random seed 51b, and the random number generator 500a receives the random seed 51a, and the linear feedback shift registers 501a and 701b repeat the bit shifting operation in response to a plurality of frequency cycles of the received frequency signal clk.
In fig. 9B, the first-order random number generator (i.e., random number generator 700B) has a two-stage structure, and the two-stage structure of the combinational logic circuit 703B is similar to the structure of the combinational logic circuit 603' of fig. 6B, in that the random bit stream is not received by the first-stage logic gate 7032, but the random bit stream S is received by the second-stage logic gate 7031 from the external source 73.
The logic gate 7032 receives the data stored in the storage elements P1, P2 via the input terminals in2, in3, and then the logic gates 7032, 7031 perform a logic operation to generate an output (i.e., a random bit stream P) at the feedback terminal Nf2, because the operation of the random number generator 500a is similar to that of fig. 7, and the related description of the random number generator 500a of fig. 9B is omitted here.
Fig. 10 is a schematic diagram of a random number generation circuit with a third order random number generator, the random number generation circuit 60 comprises series connected random number generators 600a, 600b, 600c, in practice more random number generators may be series connected.
In fig. 10, to generate the output sequence Q includes three phases, the random number generator 600c performs an initial phase, the random number generator 600b performs an intermediate phase, and the random number generator 600a performs a final phase.
The random number generator 600c includes a linear feedback shift register 601c having memory elements S1, S2, S3, S4, a combinational logic circuit 603c, and a feedback terminal Nf3, wherein the memory elements S1, S2, S3, S4 commonly receive the random seed 61c in a stationary state, the memory elements S1, S2, S3, S4 perform bit shifting actions in each frequency period in response to the linear feedback shift register 601c receiving the frequency signal clk, and the data stored in the linear feedback shift register 601c is continuously updated in response to a plurality of frequency periods, the combinational logic circuit 603c generates a random bit stream at the feedback terminal Nf3, and the random bit stream S is transmitted to the random number generator 600b and the memory element S4.
The random number generator 600c, 600b operates in a similar manner, and the random number generator 600b includes a linear feedback shift register 601b having storage elements P1, P2, P3, P4, a combinational logic circuit 603b, and a feedback terminal Nf2, the storage elements P1-P4 of the linear feedback shift register 601b together receive the random seed 61b, the combinational logic circuit 603b performs another logic operation according to the random bit stream S and the data stored in the storage element P1, the combinational logic circuit 603b outputs the random bit stream P at the feedback terminal Nf2, and then the random bit stream P is transferred to the storage element P4 for use by the random number generator 600 a.
The random number generator 600a includes a linear feedback shift register 601a having storage elements Q1 to Q4, a combinational logic circuit 603a, and a feedback terminal Nf1, the storage elements Q1 to Q4 of the linear feedback shift register 601a commonly receive the random seed 61a, the combinational logic circuit 603a receives the random bit stream P and grabs data stored in the storage element Q1, and after performing a logic operation on the random bit stream P and the data stored in the storage element Q1, the combinational logic circuit 603a generates an output sequence Q at the feedback terminal Nf1, and the output sequence Q is transferred to and stored in the storage element Q4.
As described above, the random number generators 600b, 600c are used to generate the temporary random bit stream P, S, and since the temporary random bit stream P, S is dynamically generated in real time, the contents thereof are not visible from the outside of the random number generating circuit 60, and thus the random bit stream P, S cannot be monitored like the output sequence Q, nor can it be reverse-engineered like a hardware element (logic gate of a combinational logic circuit), and the randomness of the output sequence Q is improved by using the random number generators 600b, 600c, thereby greatly improving the security of the random number generating circuit.
In fig. 10, the combinational logic circuits 603a, 603b, 603c may be exclusive or (XOR) circuits, the linear feedback shift registers 601a, 601b, 601c may comprise four storage elements, although the implementation of the combinational logic circuits 603a, 603b, 603c and the linear feedback shift registers 601a, 601b, 601c may vary depending on the actual application, e.g. the number of storage elements of the linear feedback shift registers 601a, 601b, 601c may be different, or each combinational logic circuit 603a, 603b, 603c may comprise more than one logic gate.
In the above embodiment, one input terminal of the combinational logic circuit is electrically connected to the memory element corresponding to the last bit (i.e., the memory element q 1) by way of illustration, however, in practical application, the input terminal may be electrically connected to any memory element. Fig. 11A and 11B are schematic diagrams showing that the connection relationship between the input terminals of the combinational logic circuit and the storage elements in the linear feedback shift register can be arbitrarily changed.
In fig. 11A, the random number generator 100a includes a linear feedback shift register 101A, a combinational logic circuit 103a, and a feedback terminal Nf, the linear feedback shift register 101A includes storage elements q 1-q 4, the combinational logic circuit 103a includes input terminals in1, in2, the input terminal in1 can receive the random bit stream P, the design of the combinational logic circuit 103a is not repeated, the input terminal in2 can be electrically connected to the storage element q2, and thus the logic operation performed by the combinational logic circuit 103a is for the random bit stream P and the data captured from the storage element q 2. Details of the logic operation of the combinational logic circuit 103a are omitted here, and will not be described again.
In fig. 11B, the random number generator 100B includes a linear feedback shift register 101B, a combinational logic circuit 103B and a feedback terminal Nf, the linear feedback shift register 101B includes storage elements q 1-q 4, the combinational logic circuit 103B includes input terminals in1, in2, in3, and the design of the combinational logic circuit 103B is not repeated, the input terminals in2, in3 can be electrically connected to the storage elements q2, q3, respectively, so that the logic operation performed by the combinational logic circuit 103B is for the data captured from the storage elements q2, q3 and the random bit stream P. Details of the design and logic operation of the combinational logic circuit 103b are omitted here, and will not be described again.
According to fig. 11A and 11B, the connection relationship among the input terminal, the memory element, and the feedback terminal Nf of the combinational logic circuit can be arbitrarily changed.
Random number generators (Random Number Generator, RNG) are important in today's circuit design and can be applied in different fields like data encryption, one-time-password, music-on-a-go, statistical simulation, etc. of the fifth generation mobile communication technology (5G). Various embodiments of a random number generator and random number generation circuit are described that are implemented in hardware and require very small locations to provide good randomness at high speeds.
The random seed employed in the embodiment has a high degree of confusion (degree of entropy), and the random bit stream is used to further enhance the randomness, if the combinational logic circuit employs exclusive or (XOR) gates or exclusive nor (XNOR) gates, the output sequence Q has uniformly statistically distributed 0 and 1, according to the scheme, even if an attacker can monitor the output sequence Q and find out the circuit design of the combinational logic circuit by using reverse engineering, the mode of the output sequence Q is still difficult to predict because of adding the random bit stream P.
While the foregoing is directed to embodiments of the present invention, other and further details of the invention may be had by the present invention, it should be understood that the foregoing description is merely illustrative of the present invention and that no limitations are intended to the scope of the invention, except insofar as modifications, equivalents, improvements or modifications are within the spirit and principles of the invention.
Claims (7)
1. A random number generator that operates according to a plurality of frequency cycles, the random number generator comprising:
A shift register, comprising:
N memory elements electrically connected in series and comprising:
A first memory element, and
A second storage element, wherein the N storage elements correspondingly receive a random seed of N bits in a static state, and the shift register repeatedly performs a bit shifting action in a plurality of frequency periods;
A combinational logic circuit comprising:
A first input electrically connected to an external source for continuously receiving a random bit stream from the external source during the plurality of frequency periods;
a second input terminal electrically connected to the first memory element for capturing the data stored in the first memory element, and
At least one logic gate for performing at least one logic operation on the random bit stream and the data captured by the second input terminal, and
The feedback end is electrically connected with the second storage element and outputs an output sequence in a plurality of frequency periods according to at least one logic operation, wherein the data stored in the second storage element is continuously updated in the plurality of frequency periods according to the output sequence;
the N storage elements further comprise a third storage element, the at least one logic gate comprises a first logic gate and a second logic gate, the first logic gate is provided with a first logic input and a second logic input, the first input end is directly and electrically connected with the first logic input, and the second input end is directly and electrically connected with the second logic input;
the second logic gate is electrically connected to the feedback terminal, and includes:
a third logic input electrically connected to the third memory element for capturing data stored in the third memory element, and
A fourth logic input for receiving an output of the first logic gate,
The second logic gate performs a second logic operation on the data captured by the third logic input and the output of the first logic gate, and the output sequence is generated by the second logic gate.
2. The random number generator of claim 1, wherein the feedback terminal is directly electrically connected to an output of the first logic gate.
3. The random number generator of claim 1, wherein the external source is an astable flip-flop, a random telegraph noise device, a real time clock, an astable electronic oscillator, or another random number generator.
4. The random number generator of claim 1, wherein the N storage elements further comprise a fourth storage element, and the at least one logic gate comprises:
A third logic gate, comprising:
a fifth logic input directly electrically connected to the second input terminal, and
A sixth logic input electrically connected to the fourth memory element for capturing the data stored in the fourth memory element, wherein the third logic gate performs a third logic operation on the data captured by the second input and the sixth logic input, and
A fourth logic gate, comprising:
a seventh logic input electrically connected to the third logic gate for receiving an output of the third logic gate, and
An eighth logic input for receiving the random bit stream, wherein the fourth logic gate performs a fourth logic operation on the output of the third logic gate and the random bit stream.
5. A random number generation circuit comprising:
a first random number generator comprising:
A first shift register comprising:
n first shift register storage elements electrically connected in series, comprising:
A first memory element, and
A second storage element, wherein the N first shift register storage elements correspondingly receive a first random seed of N bits in a static state, the first shift register repeatedly performs a first shift operation in a plurality of frequency periods;
a first combinational logic circuit comprising:
a first input receiving a first random bit stream from a first external source during the plurality of frequency periods;
a second input terminal electrically connected to the first storage element of the first shift register for capturing the data stored in the first storage element of the first shift register, and
At least one first logic gate for performing at least one first logic operation on the first random bit stream and the data captured by the second input terminal of the first combinational logic circuit, and
The first feedback end is electrically connected with the second storage element of the first shift register and outputs an output sequence in a plurality of frequency periods according to at least one first logic operation, wherein the data stored in the second storage element of the first shift register is continuously updated in the plurality of frequency periods by the output sequence;
A second random number generator, as the first external source, comprising:
a second shift register comprising:
m second shift register storage elements electrically connected in series, comprising:
A first memory element;
A second memory element, and
A third storage element, wherein the M second shift register storage elements correspondingly receive a second random seed of M bits in the static state, and the second shift register repeatedly performs a second bit shift operation in the plurality of frequency periods;
a second combinational logic circuit comprising:
The first input end is electrically connected with the first storage element of the second shift register and is used for capturing data stored in the first storage element of the second shift register;
a second input terminal electrically connected to the second storage element of the second shift register for capturing the data stored in the second storage element of the second shift register, and
At least one second logic gate for performing at least one second logic operation on the data captured by the first input terminal of the second combinational logic circuit and the second input terminal of the second combinational logic circuit, and
And a second feedback end electrically connected with the first random number generator, an output of the second combinational logic circuit and the third storage element of the second shift register for outputting the first random bit stream, wherein the data stored in the third storage element of the second shift register is continuously updated with the first random bit stream in the plurality of frequency periods.
6. The random number generating circuit of claim 5, wherein the at least one second logic gate comprises a second logic gate for performing the at least one second logic operation of the at least one second logic gate.
7. A random number generation method applied to the random number generation circuit of any one of claims 5 to 6, the random number generation circuit comprising a shift register and a combinational logic circuit, wherein the random number generation method comprises the steps of:
Receiving a random seed of N bits in a stationary state;
according to the random seed and a random bit stream, the shift register performs a bit shifting action;
the combinatorial logic circuit continuously receives the random bit stream over a plurality of frequency periods;
performing at least one logic operation on the random bit stream and data stored in a first storage element of the shift register;
outputting an output sequence in the multiple frequency periods in response to the at least one logic operation, and
The data stored in a second storage element of the shift register is updated with the output sequence.
Applications Claiming Priority (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US202062962198P | 2020-01-17 | 2020-01-17 | |
| US62/962,198 | 2020-01-17 | ||
| US16/807,194 US11586418B2 (en) | 2020-01-17 | 2020-03-03 | Random number generator, random number generating circuit, and random number generating method |
| US16/807,194 | 2020-03-03 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN113138752A CN113138752A (en) | 2021-07-20 |
| CN113138752B true CN113138752B (en) | 2025-03-28 |
Family
ID=76809487
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202010174948.4A Active CN113138752B (en) | 2020-01-17 | 2020-03-13 | Random number generator, random number generation circuit and random number generation method |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN113138752B (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN116225371B (en) * | 2022-12-05 | 2025-09-26 | 湖南师范大学 | Random permutation generator and distributed particle filtering method and accelerator based on it |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101620523A (en) * | 2009-07-29 | 2010-01-06 | 深圳国微技术有限公司 | Random number generator circuit |
| CN105354008A (en) * | 2015-12-14 | 2016-02-24 | 武汉芯昌科技有限公司 | Output circuit and output method of random number generator |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100526512B1 (en) * | 1999-05-20 | 2005-11-08 | 삼성전자주식회사 | Interleaving apparatus and method for serially concatenated convolution code in a mobile telecommunication system |
| GB0102840D0 (en) * | 2001-02-05 | 2001-03-21 | Cambridge Silicon Radio Ltd | Generating random data |
| US6807553B2 (en) * | 2001-04-23 | 2004-10-19 | Safenet B.V. | Digital true random number generator circuit |
| US7047262B2 (en) * | 2002-08-21 | 2006-05-16 | Koninklijke Philips Electronics N.V. | Entropy estimation and decimation for improving the randomness of true random number generation |
| JP3732188B2 (en) * | 2003-03-31 | 2006-01-05 | Ｎｅｃマイクロシステム株式会社 | Pseudo random number generator |
| KR100576714B1 (en) * | 2003-12-23 | 2006-05-03 | 한국전자통신연구원 | Random number generating device and method using digital logic |
| US7496616B2 (en) * | 2004-11-12 | 2009-02-24 | International Business Machines Corporation | Method, apparatus and system for resistance to side channel attacks on random number generators |
| US8595277B2 (en) * | 2008-02-13 | 2013-11-26 | Infineon Technologies Ag | Hybrid random number generator |
-
2020
- 2020-03-13 CN CN202010174948.4A patent/CN113138752B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101620523A (en) * | 2009-07-29 | 2010-01-06 | 深圳国微技术有限公司 | Random number generator circuit |
| CN105354008A (en) * | 2015-12-14 | 2016-02-24 | 武汉芯昌科技有限公司 | Output circuit and output method of random number generator |
Also Published As
| Publication number | Publication date |
|---|---|
| CN113138752A (en) | 2021-07-20 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| TWI754900B (en) | Random number generator, random number generating circuit, and random number generating method | |
| Nandi et al. | Theory and applications of cellular automata in cryptography | |
| Kumaravel et al. | An application of non-uniform cellular automata for efficient cryptography | |
| US10078493B2 (en) | Secured pseudo-random number generator | |
| Dubrova | A list of maximum-period NLFSRs | |
| Sen et al. | Cellular automata based cryptosystem (CAC) | |
| JP3696209B2 (en) | Seed generation circuit, random number generation circuit, semiconductor integrated circuit, IC card and information terminal device | |
| US20190012146A1 (en) | Self-timed random number generator | |
| JP2013534336A (en) | Bit sequence generator | |
| CN106383691A (en) | Random number generation method and random number generator | |
| US9166795B2 (en) | Device and method for forming a signature | |
| CN113138752B (en) | Random number generator, random number generation circuit and random number generation method | |
| Chan et al. | The convergence properties of a clipped Hopfield network and its application in the design of keystream generator | |
| Shamir et al. | Guaranteeing the diversity of number generators | |
| Ramasamy et al. | A modified PRBS: vertical stacked LFSR primitive polynomial for secure data communication | |
| Hussain et al. | Design of Secured Lightweight PRNG Circuit using LFSR for Portable IoT Devices | |
| Li et al. | An Algorithm for Constructing a Smallest Register with Non-Linear Update Generating a Given Binary Sequence | |
| TWI662471B (en) | Multi-bit true random number generation device and generation method thereof | |
| Fisher et al. | Generation of Finite Inductive, Pseudo Random, Binary Sequences. | |
| Li et al. | An algorithm for constructing a minimal register with non-linear update generating a given sequence | |
| Ping et al. | Triple-coupling cellular automata and their application to image encryption | |
| Mandal et al. | Generating good span n sequences using orthogonal functions in nonlinear feedback shift registers | |
| WO2024226059A1 (en) | Hybrid ring generators | |
| Sekhar et al. | An Efficient Pseudo Random Number Generator for Cryptographic Applications | |
| Poornima et al. | A survey on cellular automata with the application in pseudo random number generation |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |