JP5670849B2 - Pseudorandom number generation device and pseudorandom number generation method - Google Patents

Description

  The present invention relates to a pseudo-random number generator that generates pseudo-random numbers.

  Pseudo random numbers are used for encryption and authentication. The pseudo random number is generated by, for example, a linear feedback shift register (LFSR). The LFSR has a plurality of registers connected in series. A predetermined output among the plurality of registers is fed back to the first register via an exclusive OR circuit (EXOR circuit). After the initial value is set, the LFSR operates based on a predetermined shift clock. As a result, the LFSR repeatedly outputs a pseudo random number sequence having a pattern depending on the initial value at a predetermined cycle. Such an LFSR makes it possible to obtain a long-period random number sequence by providing an EXOR circuit in the feedback path.

  However, the pseudo-random number generation logic by LFSR can be easily analyzed mathematically from the output pattern. Therefore, in the pseudo random number generation circuit using LFSR, a device for increasing the randomness of the generated pseudo random number is required. For example, it is common that the initial value can be changed or a plurality of LFSRs are cascade-connected. Alternatively, it is possible to use a non-linear feedback shift register (NLFSR) or to randomize the initial value.

  Patent Document 1 describes a pseudo-random number generator that generates pseudo-random numbers by applying nonlinearity using LFSR. Patent Document 2 and Patent Document 3 describe a pseudo-random number generator using a random initial value.

JP 2009-259013 A WO2003 / 096181 JP 11-252069 A

  The pseudorandom number generator described in Patent Document 1 generates an initial value using a plurality of counters. Here, the output value of the counter returns to 0 when it overflows. That is, the output value of the counter has periodicity. For this reason, when an initial value is generated using a counter, the same initial value may be generated at a constant period. Therefore, in such a pseudo-random number generator, it is required to increase the period of the initial value to reduce the predictability thereof. However, in the configuration of such a pseudorandom number generator, the counter size needs to be increased in order to increase the period of the initial value. An increase in the counter size causes an increase in circuit scale and power consumption. Further, in such a pseudo random number generator, when the counter operation is stopped due to factors such as no clock being supplied to the counter, the initial value becomes a fixed value. In such a case, there is also a problem that the predictability of the initial value is increased.

  Moreover, the pseudorandom number generation device described in Patent Document 2 calculates a value based on an elapsed time after power-on of the electronic device as a random initial value. However, this pseudo-random number generator uses a counter for measuring elapsed time. Even if such elapsed time itself is a random value, when a counter is used for the measurement, the range of the measured value is up to an upper limit value depending on the counter size. Therefore, even in such a pseudorandom number generator, it is required to increase the upper limit value of the measurement value and reduce the predictability of the initial value. However, like the one described in Patent Document 1, in such a configuration of the pseudorandom number generation device, the counter size needs to be increased in order to increase the upper limit value of the measurement value. An increase in the counter size causes an increase in circuit scale and power consumption. Also in this pseudo random number generation device, the initial value becomes a fixed value when the function of measuring the elapsed time since the electronic device is turned on is stopped due to an external factor. In such a case, there is also a problem that the predictability of the initial value is increased.

  The present invention has been made in order to solve the above-described problems, and improves the randomness of pseudorandom numbers by increasing the randomness of initial values used in pseudorandom number generation without increasing the circuit scale. An object is to provide an apparatus.

  The pseudorandom number generator of the present invention is obtained by performing a logical operation on a pseudorandom number generator that generates a pseudorandom number using an initial value, external data input from the outside, and a pseudorandom number output from the pseudorandom number generator. And an initial value control unit that outputs the obtained value as the initial value to the pseudo-random number generation unit.

  The pseudo-random number generation method of the present invention is a pseudo-random number generation method that generates a pseudo-random number using an initial value. The generated pseudo-random number is used as feedback data, and the pseudo-random number and external data input from the outside are The next pseudorandom number is generated with the value obtained by the logical operation as the initial value.

  It is possible to provide a pseudo-random number generator that improves the randomness of a pseudo-random number by increasing the randomness of an initial value used in the pseudo-random number generation process without increasing the circuit scale.

It is a block diagram which shows the structure of the pseudorandom number generation apparatus as the 1st Embodiment of this invention. It is a block diagram which shows the structure of the pseudorandom number generator as the 2nd Embodiment of this invention. It is a block diagram which shows the structure of the initial value control part in the 2nd Embodiment of this invention. It is a block diagram which shows the structure of the pseudorandom number generation part in the 2nd Embodiment of this invention. It is a block diagram which shows the structure of the pseudorandom number control part in the 2nd Embodiment of this invention.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

(First embodiment)
FIG. 1 shows a configuration of a pseudo random number generation device 1 as a first embodiment of the present invention. In FIG. 1, the pseudo random number generation device 1 includes an initial value control unit 11 and a pseudo random number generation unit 12.

  The initial value controller 11 receives the feedback data from the pseudorandom number generator 12 and external data. This external data is digital data. The external data is preferably not a fixed value. For example, the external data may be time data acquired from a digital clock function built in an electronic device in which the pseudorandom number generator 1 is mounted. The external data may be data obtained by digitally converting random analog data. For example, the external data is analog data acquired from an analog data measuring device (for example, a hygrometer, seismometer, photometer, anemometer, noise meter, etc.) connected to the outside of the electronic device on which the pseudorandom number generator 1 is mounted. The data may be digitally converted.

  Further, the initial value control unit 11 outputs a value (logical operation value) obtained by performing a logical operation on the feedback data and the external data to the pseudo random number generation unit 12. For example, the initial value control unit 11 may output an exclusive OR of the feedback data and the external data to the pseudo random number generation unit 12.

  The pseudo random number generation unit 12 executes a pseudo random number generation process using the value output from the initial value control unit 11 as an initial value to generate a pseudo random number. A known technique for generating a pseudo random number using an initial value can be applied to the pseudo random number generator 12. For example, the pseudo-random number generation unit 12 may be configured by a non-linear feedback register that uses the initial value to non-linearly transform the output value of its own circuit to obtain the next output value.

  The operation of the pseudorandom number generator 1 configured as described above will be described.

  First, external data and feedback data from the pseudorandom number generator 12 are input to the initial value controller 11. Note that data with low randomness is input to the initial value control unit 11 as feedback data from the pseudo-random number generation unit 12 immediately after the power is turned on. However, after once operating as described below, the initial value control unit 11 receives a pseudo-random number having high randomness as feedback data.

  Next, the initial value control unit 11 outputs a logical operation value (for example, exclusive OR) of the input external data and feedback data to the pseudo-random number generation unit 12.

  Next, the pseudo random number generation unit 12 performs a pseudo random number generation process using the value input from the initial value control unit 11 as an initial value, and generates a pseudo random number.

  The generated pseudo-random number is input as feedback data to the initial value control unit 11 and output as an output value of the pseudo-random number generation device 1.

  Above, description of operation | movement of the pseudorandom number generation apparatus 1 is complete | finished.

  Next, effects of the embodiment of the present invention will be described.

  The pseudo random number generation device as the first exemplary embodiment of the present invention can improve the randomness of the pseudo random number by increasing the randomness of the initial value used in the pseudo random number generation without increasing the circuit scale. .

  This is because the initial value control unit outputs the logical operation value of the external data and the feedback data from the pseudo random number generation unit to the pseudo random number generation unit as the initial value used in the pseudo random number generation process. As a result, the pseudo-random number generation device according to the present embodiment is configured so that the initial value is the logical operation value of the feedback data from the external data and the pseudo-random number generation circuit even if the external data has periodicity. The periodicity of the value can be disturbed. In addition, the pseudo random number generation device according to the present embodiment uses the logical operation values of the feedback data and the external data as initial values as compared with the case where only the feedback data from the pseudo random number generation unit is used as the initial value of the pseudo random number generation process. By doing so, the randomness of the pseudo-random number is increased. In addition, the pseudo-random number generation device as the present embodiment uses the logical operation value of the feedback data from the external data and the pseudo-random number generation circuit as the initial value even when the external data becomes a fixed value due to an external factor. The value is not used as an initial value. As a result, the pseudo random number generation device according to the present embodiment can make it more difficult to analyze the output pseudo random numbers. In addition, the initial value control unit of the present embodiment that generates such an initial value with high randomness is an initial value generation circuit having a counter with an enormous number of bits and a clock so that the counter does not have the same value. This can be realized using only a logic operation circuit. Thereby, the pseudo-random number generation device as the present embodiment does not increase the circuit scale and power consumption in order to improve the randomness of the initial value.

(Second Embodiment)
Next, a second embodiment of the present invention will be described in detail with reference to the drawings. First, FIG. 2 shows a configuration of a pseudo random number generation device 2 as a second embodiment of the present invention.

  In FIG. 2, the pseudo random number generation device 2 includes an initial value control unit 21, a pseudo random number generation unit 22, and a pseudo random number control unit 23. The pseudo random number generation unit 22 includes pseudo random number generation circuits 24a to 24d (hereinafter collectively referred to as pseudo random number generation circuit 24). 2 shows four pseudo random number generation circuits 24, the number of pseudo random number generation circuits included in the pseudo random number generation unit of the present invention is not limited.

  External data DD and pseudorandom numbers DOa to DOd are input to the initial value control unit 21. The pseudo random numbers DOa to DOd are output values (feedback data) from the pseudo random number generation circuits 24a to 24d. A circuit configuration example of the initial value control unit 21 is shown in FIG. In FIG. 3, the initial value control unit 21 includes EXOR circuits 201 to 204. The initial value control unit 21 outputs signals DI based on the external data DD and the pseudo random numbers DOa to DOd using these circuits.

  The pseudo random number generation circuit 24 is a circuit that performs pseudo random number generation processing using the initial value DI and outputs the generated pseudo random number DO. As shown in FIG. 2, these pseudo random number generation circuits 24 are connected in series. That is, the output value DI from the initial value control unit 21 is input to the pseudo random number generation circuit 24a as the initial value DIa. The pseudo random number generation circuit 24b receives the pseudo random number DOa output from the pseudo random number generation circuit 24a as an initial value DIb for generating pseudo random numbers. Further, the pseudo random number generation circuit 24c receives the pseudo random number DOb output from the pseudo random number generation circuit 24b as an initial value DIc for pseudo random number generation. Further, the pseudo random number generation circuit 24d receives the pseudo random number DOc output from the pseudo random number generation circuit 24c as an initial value DId for pseudo random number generation.

  The pseudo random numbers DOa to DOd output from each pseudo random number generation circuit 24 are input to the initial value control unit 21 as described above.

  The pseudo random number generation circuit 24 has a function equivalent to that of a non-linear feedback shift register (NLFSR). A circuit configuration example of such a pseudorandom number generation circuit 24 is shown in FIG. In FIG. 4, the pseudorandom number generation circuit 24 includes a shift register 205 and a nonlinear conversion unit 206.

  The shift register 205 is composed of N flip-flops 207. N is an integer of 2 or more, for example, 16. N-bit data is input to the shift register 205 in parallel. The shift register 205 outputs N-bit data in parallel. This output data becomes DO (pseudorandom number). The clock signal CLK is supplied to each of the N flip-flops 207. The shift register 205 operates based on the clock signal CLK. That is, the shift register 205 captures the value of input data in synchronization with the clock signal CLK. The shift register 205 holds and outputs the captured value until the next rising edge of the clock signal CLK. That is, the data value of the shift register 205 is updated in synchronization with the clock signal CLK.

  The nonlinear conversion unit 206 includes EXOR circuits 208 and 210 that calculate an exclusive OR, an AND circuit 209 that calculates a logical product, and a replacement circuit 211. Using these circuits, the non-linear conversion unit 206 performs non-linear conversion on the output data from the shift register 205 using the initial value DI and inputs the converted data to the shift register 205. The non-linearly converted data is taken into the shift register 205 in synchronization with the next clock signal CLK. Specifically, the non-linear conversion unit 206 calculates the exclusive OR of the output data from the shift register 205 and the initial value DI and the logical product of the output data from the shift register 205 and the initial value DI. By performing replacement, non-linearization is realized.

  The pseudo random number control unit 23 selects and outputs one of the pseudo random numbers DOa to DOd output from the pseudo random number generation circuits 24a to 24d. An example of the circuit configuration of such a pseudorandom number control unit 23 is shown in FIG. The pseudo random number control unit 23 includes EXOR circuits 212 to 217 and a selector 218. The pseudo random number control unit 23 uses these circuits to generate a selection signal based on the pseudo random numbers DOa to DOd, and selects one of the pseudo random numbers DOa to DOd based on the selection signal. Here, the selection signal is a signal that can take different values corresponding to the number of pseudo-random number generation circuits 24. In this embodiment, since the number of pseudo random number generation circuits 24 is 4, the selection signal is a 2-bit signal.

  The operation of the pseudorandom number generator 2 configured as described above will be described with reference to FIGS.

  First, the external data DD and the feedback data DOa to DOd from the pseudo random number control circuits 24a to 24d are input to the initial value control unit 21 of FIG. As described above, the external data DD is digital data input from the outside of the pseudorandom number generator 2. As described above, it is desirable that the external data DD is not a fixed value. Here, it is assumed that the external data DD is time data acquired from a digital timer device built in an electronic device in which the pseudorandom number generator 2 is mounted. The external data DD is not limited to time data.

  The initial value control unit 21 receives the initial value of the shift register 205 as feedback data DOa to DOd from the pseudo random number control circuits 24a to 24d immediately after the power is turned on. Then, after repeating the operation described below several times, pseudo-random numbers are input to the initial value control unit 21 as feedback data DOa to DOd.

  Next, in the initial value control unit 21, the EXOR circuit 201 takes an exclusive OR of the signals DOa and DOb. The EXOR circuit 202 takes an exclusive OR of the signal DOc and the signal DOd. The EXOR circuit 203 takes an exclusive OR of the outputs of the EXOR circuit 201 and the EXOR circuit 202. The EXOR circuit 204 takes an exclusive OR of the external data DD and each output of the EXOR circuit 203. The output DI of the EXOR circuit 204 is output to the pseudo random number generation circuit 24a.

  Next, in the pseudo random number generation circuit 24a of FIG. 4, the EXOR circuit 208 takes an exclusive OR of the initial value DIa and the pseudo random number DOa output from the shift register 205, and outputs the result as a signal a. The AND circuit 209 calculates the logical product of the initial value DIa and the pseudo random number DOa output from the shift register 205 and outputs the logical product as a signal b. The EXOR circuit 210 takes an exclusive OR of each bit of the signal b and outputs it as a 1-bit signal c. The replacement circuit 211 outputs replacement data in which the N-1 bits excluding the most significant signal in the signal a are higher N-1 bits and the signal c is the least significant bit. This replacement data is input to the shift register 205 in parallel. The shift register 205 captures input replacement data in synchronization with the clock CLK. The fetched N-bit data is output as a pseudo random number DOa.

  Further, the pseudo random number generation circuit 24b receives the pseudo random number DOa generated by the pseudo random number generation circuit 24a as the initial value DIb. Then, the pseudo random number generation circuit 24b operates in the same manner as the pseudo random number generation circuit 24a, thereby outputting the pseudo random number DOb.

  Further, the pseudo random number generation circuit 24c receives the pseudo random number DOb generated by the pseudo random number generation circuit 24b as an initial value DIc. Then, the pseudo random number generation circuit 24c operates in the same manner as the pseudo random number generation circuit 24a, and outputs the pseudo random number DOc.

  The pseudo random number generation circuit 24d receives the pseudo random number DOc generated by the pseudo random number generation circuit 24c as an initial value DId. Then, the pseudo random number generation circuit 24d operates in the same manner as the pseudo random number generation circuit 24a, and outputs a pseudo random number DOd.

  Here, the random number period of each pseudo random number generated by the pseudo random number generation circuits 24b to 24d is the square of the random number period of each pseudo random number generated by the preceding pseudo random number generation circuit. Therefore, the pseudo random number generation circuits 24a to 24d output pseudo random numbers having different periods. Moreover, since the values of the pseudo random numbers DOa to DOd generated by the pseudo random number generation circuits 24a to 24d are updated in synchronization with the same clock signal CLK, the possibility of having the same value is extremely low.

  Next, the pseudo random numbers DOa to DOd output from the pseudo random number generation circuits 24 a to 24 d are input to the pseudo random number control unit 23.

  In the pseudo random number control unit 23 of FIG. 5, the EXOR circuit 212 outputs a 1-bit signal e obtained by performing an exclusive OR of each bit of the pseudo random number DOd. Similarly, the EXOR circuits 213 to 215 output 1-bit signals f to h obtained by performing exclusive OR of the respective bits of the pseudo random numbers DOc to DOa. Then, the EXOR circuit 216 outputs a signal i that is an exclusive OR of the signal e and the signal f. The EXOR circuit 217 outputs a signal j obtained by exclusive ORing the signal g and the signal h.

  Next, the selector 218 regards four possible values of the signal i and the signal j as selection signals and selects and outputs one of the pseudo random numbers DOa to DOb. For example, when both the signal i and j values are 0, the pseudo random number DOa may be selectively output. When the signal i is 0 and the signal j is 1, the pseudo random number DOb may be selectively output. Thus, the selection signals generated by the pseudo random numbers DOa to DOd having different random number strengths have randomness. That is, the pseudo random number control unit 23 selects and outputs any one of the pseudo random numbers DOa to DOd based on the random selection signal.

  Above, description of operation | movement of the pseudorandom number generation apparatus 2 is complete | finished.

  Next, the effect of the second exemplary embodiment of the present invention will be described.

  The pseudo random number generation device as the second exemplary embodiment of the present invention can further increase the randomness of the initial value used in the pseudo random number generation without increasing the circuit scale. The property can be further improved.

  The reason is that a pseudo-random number generator is configured by connecting a plurality of pseudo-random number generators in series. This is because a value obtained by exclusive OR of the value and external data is used. This is because the pseudo random number generation circuit in the second and subsequent stages uses the output value from the pseudo random number generation circuit in the previous stage as an initial value for random number generation. Thereby, the random number cycle of the output value from each pseudo-random number generation circuit becomes the square of the previous stage. Further, since the output values from the respective pseudo-random number generation circuits are updated in synchronization with the same clock, the possibility of being the same value is extremely low. In this way, by generating an exclusive OR of a plurality of pseudo-random numbers having different random number periods and external data as an initial value of the first-stage random number generation circuit, the random number generation device of the present embodiment can generate random numbers. This will further enhance the randomness of the initial value at. Furthermore, the pseudo random number control unit generates a selection signal based on the output value from each pseudo random number generation circuit. Since such a selection signal is generated based on a plurality of pseudo random numbers having different random number cycles as described above, the selection signal has high randomness. Therefore, the random number generation device according to the present embodiment outputs one of the output values from each pseudo-random number generation circuit based on such a highly random selection signal. As a result, the pseudo-random number generated by the random number generation device according to the present embodiment has higher randomness.

  In addition, the random number generation device according to the present embodiment uses the exclusive OR of the external data DD and the feedback data from each pseudo random number generation circuit as the initial value of the first stage pseudo random number generation circuit. Even if DD is a fixed value, the initial value is not set to a fixed value. For this reason, the random number generation device according to the present embodiment does not reduce the predictability of the initial value even when the external data DD becomes a fixed value due to an external factor. As a result, the random number generation device according to the present embodiment can maintain the high randomness of the pseudo random number to be generated.

  The random number generation device according to the present embodiment realizes an initial value control unit that generates an initial value with high randomness as described above by a combination of exclusive OR circuits. Therefore, the random number generation device according to the present embodiment does not increase the circuit scale in order to improve the randomness of the initial value.

  In the embodiment of the present invention, the pseudo random number generation unit is described as including four pseudo random number generation circuits, but the number of pseudo random number generation circuits included in the pseudo random number generation unit of the present invention is not limited. . When the pseudo random number generation unit includes M (M is an integer equal to or greater than 2) pseudo random number generation circuits connected in series, the initial value control unit according to the present embodiment includes each of the M pseudo random number generation circuits. The initial value DI may be generated by taking two exclusive ORs of the output value and the external data. Alternatively, the initial value control unit may be realized by a combination of other logic circuits as long as the initial value DI is generated by performing a logical operation on each output value and external data from the M pseudorandom number generation circuits. Good.

  Further, when the pseudo random number generation unit includes M pseudo random number generation circuits connected in series, the pseudo random number control unit according to the present embodiment is configured to output each bit of each output value from the M pseudo random number generation circuits. What is necessary is just to generate M 1-bit signals by taking exclusive OR. Then, the pseudo random number control unit of the present embodiment may generate an m-bit selection signal that can take M values based on the generated M signals. Alternatively, the pseudo-random number control unit may have other configurations as long as it generates an m-bit selection signal that can take M values based on the output values from the M pseudo-random number generation circuits. .

  Moreover, each embodiment mentioned above can be implemented in combination as appropriate.

  The present invention is not limited to the above-described embodiments, and can be implemented in various modes.

DESCRIPTION OF SYMBOLS 1, 2 Pseudo random number generator 11, 21 Initial value control part 12, 22 Pseudo random number generation part 23 Pseudo random number control part 24, 24a-24d Pseudo random number generation circuit 201-204, 208, 210, 212-217 EXOR circuit 205 Shift Register 206 Nonlinear converter 207 Flip-flop 209 AND circuit 211 Replacement circuit 218 Selector

Claims (4)

  Each has a plurality of pseudo-random number generation circuits connected in series, each of which generates a next output value (pseudo-random number) by nonlinearly transforming its own output value using an initial value. Each pseudo-random number generation circuit generates a pseudo-random number using the pseudo-random number output from the pseudo-random number generation circuit in the previous stage as an initial value; and
  A pseudo-random number control unit that selects any one of the pseudo-random numbers output from the plurality of pseudo-random number generation circuits as an output value of the own device;
  A value obtained by performing a logical operation on a pseudo-random number output from each of the plurality of pseudo-random number generation circuits and external data input from the outside is used as a first-stage pseudo-random number generation circuit among the plurality of pseudo-random number generation circuits. An initial value control unit that outputs the output value as a next initial value for nonlinear conversion of the output value of itself,
  A pseudo-random number generation device comprising:   The pseudo random number control unit generates a selection signal that can take different values as many as the number of the pseudo random number generation circuits based on the output values of the plurality of pseudo random number generation circuits, and based on the generated selection signals 2. The pseudo-random number generation device according to claim 1, wherein one of the output values of the plurality of pseudo-random number generation circuits is selected and output.   The initial value control unit outputs a pseudo-random number output from each of the plurality of pseudo-random number generation circuits and an exclusive OR of the external data as the initial value. The pseudorandom number generator according to 2.   1st to nth (n is an integer of 2 or more) pseudorandom number generation circuits, each of which generates a next output value (pseudorandom number) by nonlinearly transforming its own output value using an initial value In an apparatus having a pseudo-random number generation circuit that
  Using the pseudorandom number generated by the i-th (i is an integer of 1 or more) pseudorandom number generator as an initial value, the (i + 1) th pseudorandom number generator generates a pseudorandom number,
  Selecting and outputting one of the n pseudo-random numbers generated by the n pseudo-random number generation circuits;
  A value obtained by performing a logical operation on n pseudo-random numbers generated by the n pseudo-random number generation circuits and external data input from the outside, and an output value of the first pseudo-random number generation circuit in a non-linear manner A pseudo-random number generation method used as the next initial value for conversion.

Images