JP3604658B2 - Random number generation circuit - Google Patents

Description

[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a random number generation circuit, and more particularly to a random number generation circuit that can be compactly configured by a digital logic circuit, generates random numbers with a high degree of authenticity, and is suitable for use in an encryption algorithm.
[0002]
[Prior art]
The digital random number is used for simulation of a phenomenon involving a stochastic process, generation of an encryption key by an encryption algorithm used for security, and the like. Conventionally, as a digital random number, a “pseudo random number” generated by calculation by a CPU has been used. This pseudo random number is typically created by a logic circuit called a “feedback shift register”.
[0003]
On the other hand, a method of generating a random number using noise generated in a resistor or a diode has been put to practical use. In this case, no bias or periodicity is found in the random numbers, and a value close to a “true random number” is obtained. In this type of random number generation circuit, the noise generated by passing a constant current through the noise source element is passed through a high-pass filter circuit to extract the AC component, which is then amplified by an analog circuit, and then converted by AD and digitized. I do. At this time, a certain value is set as a threshold value, a value exceeding the threshold value is set to “1”, and a value below it is set to “0”. Furthermore, since the random number sequence that has appeared is biased, it is often used after correcting it with a digital circuit.
[0004]
[Problems to be solved by the invention]
It is known that the pseudorandom number generated by the CPU is not suitable as a random number because the same random number is generated if the initially given number (seed) is the same, or it has periodicity based on the number of registers. Have been. In particular, when used for security, this may cause the risk of breaking the "encryption key".
[0005]
On the other hand, in the case of a type that amplifies noise, the thermal noise and shot noise of resistors and diodes are generally analog signals, and the output is small. Is difficult. In particular, it is difficult to incorporate it into a small device such as an IC card equipped with an encryption security function.
[0006]
That is, there is a need for a small-sized integrated circuit that generates high-quality random numbers having no periodicity.
[0007]
In order to reduce the size, it is desirable to configure a digital circuit such as TTL or CMOS. However, a digital circuit basically gives the same output to a certain input, and therefore can only generate random numbers by algorithmic processing. For this reason, only a pseudo random number can be generated similarly to the feedback shift register.
[0008]
In order to solve this inconsistency, it is necessary to create a digital circuit whose output is uncertain.
[0009]
The present invention has been made based on the recognition of such a problem. That is, an object of the present invention is to provide a random number generation circuit that generates random numbers with a high degree of trueness and that can be formed into a small-sized integrated circuit.
[Means for Solving the Problems]
In order to achieve the above object, according to one embodiment of the present invention, there is provided an uncertain output circuit for generating an uncertain digital signal sequence, wherein the uncertain output circuit sets a “0” level and a “1” level. The "0" level and the "1" level are held by the channel resistance of the MOS transistor which outputs alternately and determines the time for holding the "0" level and the "1" level respectively fluctuates with time. Have a multivibrator that varies in any of the times
The MOS transistor has a gate insulating film in which a plurality of electron traps are formed. Electrons passing through a channel tunnel through the gate insulating film and are captured by the trap. A random number generation circuit characterized in that the random number generation circuit is configured to be capable of tunneling to a random number.
Here, the gate insulating film may be formed of a silicon oxide film in which silicon nanocrystals are dispersed.
Alternatively, the gate insulating film can be made of silicon nitride oxide.
Alternatively, the gate insulating film may be formed by introducing at least one of a defect and an impurity into a layer inside the film.
[0010]
According to the above configuration, an uncertain signal sequence corresponding to the variation in the characteristics of the elements constituting the multivibrator can be obtained, and the random number generation circuit can be configured with a small number of logic gates, so that a small-scale circuit is sufficient.
[0011]
According to another aspect of the present invention, there is provided an uncertain output circuit for generating an uncertain digital signal sequence, wherein the uncertain output circuit alternately outputs a “0” level and a “1” level. Then, when the resistance of the photodiode that determines the time for holding the “0” level and the “1” level changes with time, either of the time for holding the “0” level and the time for holding the “1” level is reduced. Has a multi-vibrator that fluctuates,
The photodiode is characterized in that a high voltage is applied to a drain of a MOSFET having a submicrometer-sized gate to generate hot electrons, and the resistance changes in response to light emission generated in the process of relaxing the hot electrons. A generation circuit is provided.
[0012]
Here, if the indeterminate output circuit further includes a counter that reads the signal sequence of the “0” level and the “1” level output from the multivibrator at a constant cycle, An uncertain digital signal sequence can be obtained from the above signal sequence.
[0013]
Further, if the constant period read by the counter is sufficiently longer than an average transition period in the signal sequence of the “0” level and the “1” level output from the multivibrator, In addition, the influence of the periodicity of the signal train output from the multivibrator can be eliminated.
[0014]
A count circuit that counts the frequency of occurrence of “0” and “1” in the uncertain digital signal sequence output from the uncertain output circuit; and a feedback signal based on the occurrence frequency counted by the count circuit. And a feedback circuit that provides the circuit element of the multivibrator with the above-mentioned configuration, it is possible to suppress the “bias” in the digital output string from the indeterminate output circuit.
[0015]
A logic operation circuit for calculating an exclusive OR of a plurality of digital signals included in the uncertain digital signal sequence output from the uncertain output circuit and outputting the operation result as a random number; Then, random numbers without "bias" can be obtained.
[0016]
Alternatively, an exclusive OR of a digital signal sequence in which the appearance frequency of “0” and “1” is 1: 1 and the uncertain digital signal sequence output from the uncertain output circuit is calculated. If a logic operation circuit that outputs the operation result as a digital random number sequence is further provided, a random number sequence without “bias” can be obtained.
[0017]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
[0018]
FIG. 1 is a block diagram illustrating a main configuration of a random number generation circuit according to the present invention.
[0019]
That is, the random number generation circuit of the present invention includes an uncertain output circuit 10 and a uniforming circuit 20 receiving the output.
[0020]
The uncertain output circuit 10 has an astable multivibrator 10A and a counter 10B which are constituted by digital circuits. In the astable multivibrator 10A, an element is introduced in which the resistance value of the resistor that determines the oscillation period or the capacitance of the capacitor easily fluctuates with time based on a physical phenomenon. It fluctuates irregularly.
[0021]
Then, the counter 10B reads out the vibrator signal that fluctuates irregularly in this manner with a constant clock, whereby a random digital signal sequence of “0” and “1” can be obtained.
[0022]
Since the arrangement of the digital signal sequence of “0” and “1” obtained by this method depends on the characteristics of the elements constituting the multivibrator, the appearance frequency of “0” and “1” is “biased”. May occur.
[0023]
Therefore, in such a case, the uniforming circuit 20 performs digital processing again on them to eliminate the bias and obtain digital random numbers with a high degree of intrinsicity.
[0024]
With this configuration, the random number generation circuit can be configured with a small number of logic gates, so that a small-scale circuit is sufficient. A circuit for correcting the frequency of “0” and “1” can also be configured by a relatively small-scale logic circuit.
[0025]
In the present invention, the equalizing circuit 20 is not indispensable. If the digital random number sequence output from the uncertain output circuit 10 is sufficiently uniform, the uniformizing circuit 20 needs to be provided. There is no.
[0026]
Hereinafter, the astable multivibrator used in the uncertain output circuit 10 of the present invention will be described.
[0027]
FIG. 2 is a schematic diagram showing a digital circuit usually called an “astable multivibrator”. This astable multivibrator has a configuration in which resistors R1, R2 and capacitors C1, C2 are respectively connected to two NAND circuits 11, 12 connected in a flip-flop type.
[0028]
The operation of the multivibrator starts when the control input on the B side is turned on. That is, if the control input on the B side is initially “0” (ie, the capacitor C2 is empty), the output of the NAND circuit 12 becomes “1”, and the capacitor C1 on the A side starts to be charged. When the charging proceeds to a certain point, the input on the A side becomes “0”, so that the output of the NAND circuit 11 on the A side becomes “1”, and this time, the capacitor C2 on the B side starts to be charged. This is alternately repeated, so that the output of the NAND circuit 11 on the A side alternately repeats "1" and "0".
[0029]
The cycle of this repetition is determined by the charging time of the capacitors C1 and C2, and is proportional to the product of the capacitances of the capacitors and the magnitudes of the resistors R1 and R2, ie, (C × R).
[0030]
In the case of the multivibrator shown in FIG. 2, the repetition cycle is about 0.7 (C1R1 + C2R2).
[0031]
In the present invention, unique elements are arranged so that the repetition period varies.
[0032]
FIG. 3 is a schematic view illustrating the main structure of the multivibrator used in the random number generation circuit of the present invention.
[0033]
That is, the astable multivibrator shown in the figure has a structure in which at least one of the resistors R1 and R2 is replaced by a special MOS transistor 14 whose channel resistance has a temporal fluctuation.
[0034]
FIG. 4 is a conceptual diagram illustrating the main structure of the MOS transistor 14.
[0035]
A plurality of electron traps T are formed on the gate insulating film 14G of this MOS transistor. The electrons passing through the channel 14C tunnel through the insulating film 14G and are frequently captured by the trap T, and the device parameters are adjusted so that the captured electrons can tunnel to the channel 14C.
[0036]
The electron trap T can be formed by, for example, dispersing silicon nanocrystals in an insulating film of a silicon oxide film, or using SiON _x (silicon oxynitride) having many electron traps as the insulating film 14G. .
[0037]
Alternatively, the electron trap T can be formed in the insulating film 14G by interrupting the formation of the insulating film 14G and exposing it to a different gas atmosphere to introduce defects or impurities.
[0038]
When electrons are trapped in the trap T, electrons moving on the channel 14C near the interface with the insulating film 14G are scattered by Coulomb interaction, and the channel resistance increases.
[0039]
Therefore, in designing the MOS transistor 14, the channel resistance is fluctuated by about several tens% with respect to the average value by narrowing down the channel 14C to capture and desorb electrons to the electron trap T. Thus, it is desirable to adjust the initial gate voltage. Further, the smaller the gate width (channel width), the larger the fluctuation rate of the channel resistance. Therefore, a MOSFET having a narrow gate width is desirable.
[0040]
The cycle of the multivibrator is determined by the capacitances of the capacitors C1 and C2 and the channel resistance of the MOS transistor 14 (more strictly, the parasitic capacitance of the transistor 14 is also affected). The cycle of the vibrator fluctuates by several tens of percent.
[0041]
FIG. 5 is a schematic diagram illustrating a state where the channel resistance of the transistor fluctuates with time. Naturally, the frequency or pitch of this "fluctuation" is not constant, and its amplitude is not constant either. The frequency of occurrence of the “fluctuation” depends on the frequency of trapping electrons in the trap T and the staying time of the electrons in the trap T. Therefore, the type of the trap T and the conditions for forming the trap T can be adjusted so that the frequency of occurrence of “fluctuation” is in an optimum range.
[0042]
Besides the MOSFET, a phototransistor or a photodiode can be used. FIG. 11 shows an example in which a PIN photodiode is used. The photodiode 21 is an element that detects weak light and converts it into a photocurrent. Based on the principle, when light strikes, the resistance changes significantly depending on the amount of light. Therefore, a small LED-type light emitting element 22 is provided near the photodiode, and the light emitting element is operated with a control voltage for operating the multivibrator circuit. Since the light quantity of the light emitting element changes due to noise or the like, the photodiode changes the resistance component in response to the change, so that the cycle of the multivibrator also changes accordingly. Since the light quantity of the light emitting element 22 may be weak, a high electric field may be applied to the drain of the MOSFET having a sub-μm size gate to generate hot electrons, and light emission in the process of relaxing the hot electrons may be used.
[0043]
In the present invention, the operation of the astable multivibrator is destabilized by providing the transistor 14 in which "fluctuation" occurs.
[0044]
FIG. 6 is a conceptual diagram illustrating an output signal obtained from the astable multivibrator according to the present invention. When a change in the digital signal that is not a fixed cycle is read by the counter 10B having a cycle sufficiently longer than the cycle of the change, the value becomes a 1-bit random number sequence.
[0045]
Here, the reason why the reading cycle of the counter 10B is made sufficiently longer than the cycle of the change of the output signal of the multivibrator 10A is to prevent occurrence of periodicity in the obtained random number sequence. In order to sufficiently reduce the periodicity, it is desirable that the reading cycle of the counter 10B be 10 times or more the changing cycle of the output signal of the multivibrator 10A.
[0046]
If the digital random number sequence obtained in this manner is sufficiently uniform, it can be used as it is as a random number sequence.
[0047]
On the other hand, if there is a “bias” in the appearance probabilities of “0” and “1” in the random number sequence thus obtained, the “bias” is corrected in the uniforming circuit 20.
[0048]
Therefore, next, the equalizing circuit 20 will be described.
[0049]
FIG. 7 is a conceptual diagram for explaining the operation of the equalizing circuit in the present embodiment.
[0050]
As shown in the figure, the outputs of the uncertain output circuit 10 are Qn,... Qn + k in time series, and an XOR (exclusive OR) logical operation is performed on these k + 1 data. Let the result be T. Assuming that the appearance probability of “1” is p and the appearance probability of “0” is 1−p in the output of the uncertain output circuit 1, the probability that T becomes 1 is
0.5 + 0.5 · (1-2p) ^{k + 1}
It becomes. As k increases, the probability approaches 0.5, and the bias is corrected.
[0051]
In the SR-FF actually prototyped in the above-described first embodiment, the “bias” was large and almost p = 0.1. When k = 10, the probability that T becomes 1 is 0.543, when K = 20, it approaches 0.505, and when K = 30, it approaches 0.5005 and 0.5, and there is almost no “bias”. .
[0052]
When k becomes large, the generation speed of random numbers becomes slow. For example, if the power ON / OFF cycle is set to 30 MHz, even if k = 30, a digital random number sequence can be generated at a speed of about 1 Mbit / sec. Therefore, there is often no problem in practical use.
[0053]
Further, the random number sequence data thus obtained may be used as a seed of the feedback shift register.
[0054]
Also, by using the method described below, the appearance probabilities of “0” and “1” can be easily equalized.
[0055]
That is, assuming that the probability that the digital signal P becomes “1” is p and the probability that the digital signal Q becomes “1” is q, the operation value T of the exclusive OR (XOR) of P and Q becomes “1”. Is different from the probability of being “0” by the following equation.
4 (0.5-p) (0.5-q) (1)
Therefore, if "the probability that P becomes" 1 "is 0.5", the operation value T of the exclusive OR of P and Q is obtained even if the probability that Q becomes "1" is not 1/2. Have the same appearance probability of “0” and “1”.
[0056]
Here, as shown in FIG. 10, when the input signal to the counter 10B is branched and input to the T-type flip-flop 20B, the signal becomes a signal whose period is doubled, which is the same as the output of the uncertain output circuit 10. At the timing, "0" and "1" are alternately arranged. In this signal, the appearance rates of “0” and “1” are naturally equal. Therefore, when the exclusive OR of this signal and the signal of the indeterminate output circuit 10 is taken, the appearance probabilities of “0” and “1” are naturally equal in the operation output T, and the digital random number sequence having a high intrinsic degree Can be used as
[0057]
Further, as shown in FIG. 11, the pseudo-random number R generated by the feedback shift register (FSR) 20C at the same clock as the counter 10B outputs "0" and "1" evenly. When the exclusive OR with the output of the definite output circuit 10 is calculated, the calculated value T has the same appearance rate of “0” and “1” and can be used as a digital random number sequence having a high degree of intrinsicity.
[0058]
On the other hand, in the present invention, "bias" can be corrected by monitoring the output of the uncertain output circuit 10 and applying feedback.
[0059]
FIG. 10 is a schematic diagram illustrating a main configuration of such a random number generation circuit.
[0060]
In this specific example, the equalizing circuit 20 applies feedback to the gate 14G of the transistor 14 of the astable multivibrator. With such feedback, the appearance probabilities of “0” and “1” of the uncertain flip-flop can be made nearly equal.
[0061]
That is, in the figure, the output of the indeterminate output circuit 10 is counted by the digital counter 20D, and the feedback circuit 20E changes the predetermined gate voltage of the multivibrator according to the difference between the counts of “0” and “1”. The voltage is applied to the gate 14G of the MOS transistor.
[0062]
Then, the magnitude of the relative fluctuation of the channel resistance of the MOS transistor 14 is adjusted, and the “bias” can be corrected.
[0063]
Also in this case, as described above with reference to FIGS. 7 to 9, the combination of the logic circuits for eliminating the “bias” can further reduce the “bias” of the random numbers. In this case, the number of pieces of data k to be XORed can be reduced, so that the speed of generating random numbers can be increased.
[0064]
The embodiment of the invention has been described with reference to specific examples. However, the present invention is not limited to the specific examples described above.
[0065]
For example, the specific configurations of the uncertain output circuit and the unifying circuit used in the present invention are not limited to the specific examples described above, and those in which the functions or operations are replaced by all similar circuits of the present invention are also included. Included in the scope.
[0066]
Further, in the specific example described above, the case where the MOS transistor is arranged only in one of the NAND circuits of the multivibrator 10A is illustrated, but it may be arranged on both the A side and the B side.
[0067]
Further, any one of the capacitances C1 and C2 of the multivibrator may be varied with time.
[0068]
Further, in the present invention, not only an astable multivibrator but also a similar unstable output can be formed by using a “monostable multivibrator” or a “bistable multivibrator”. Included in the scope.
[0069]
Further, among the above-described embodiments, a combination of a digital circuit having an uncertain output and a circuit for correcting the frequency of the digital output may be used as the random number generation circuit. Is included.
[0070]
The digital random number generated by the random number generation circuit of the present invention can be used as it is, but a new random number can be generated by using it as a seed of the feedback shift register.
[0071]
【The invention's effect】
As described in detail above, according to the present invention, in the astable multivibrator, by introducing an element that makes the output unstable, the random number generation circuit can be configured with a small number of logic gates. Only needs to be done.
[0072]
At the same time, a uniforming circuit for correcting the frequency of "0" and "1" can also be constituted by a relatively small-scale logic circuit.
[0073]
Since the phenomenon that causes the random number is based on the physical phenomenon of the elements constituting the astable multivibrator 10A, an indeterminate output is obtained for the same input. Does not appear, and it is possible to obtain a high-quality random number different from a pseudo random number from which a random number can be estimated.
[0074]
That is, according to the present invention, a random number having a high degree of authenticity can be realized at a compact size and at a low price. For example, an inexpensive card system with secure security can be realized by applying it to an IC card or the like. The benefits are enormous.
[Brief description of the drawings]
FIG. 1 is a block diagram illustrating a main configuration of a random number generation circuit according to the present invention.
FIG. 2 is a schematic diagram showing a digital circuit usually called an “astable multivibrator”.
FIG. 3 is a schematic diagram illustrating a main structure of a multivibrator used in a random number generation circuit according to the present invention.
FIG. 4 is a conceptual diagram exemplifying a main structure of a MOS transistor 14;
FIG. 5 is a schematic diagram illustrating a state where channel resistance of a transistor fluctuates with time.
FIG. 6 is a conceptual diagram illustrating an output signal obtained from an astable multivibrator according to the present invention.
FIG. 7 is a conceptual diagram for explaining the operation of the equalizing circuit according to the present invention.
FIG. 8 is a schematic diagram illustrating another specific example of the uniforming circuit.
FIG. 9 is a schematic diagram illustrating another specific example of the uniforming circuit.
FIG. 10 is a schematic diagram illustrating a configuration of a main part of a random number generation circuit according to a specific example of the present invention.
FIG. 11 is a schematic diagram illustrating a multivibrator using a photodiode.
[Explanation of symbols]
Reference Signs List 10 Indeterminate output circuit 10A Astable multivibrator 10B Counter 11, 12 NAND circuit 14 Transistor 12C Channel 12G Gate insulating film 20 Uniform circuit 20A XOR circuit 20B Flip flop 20C FSR
20D Digital counter 20E Feedback circuit T Trap 21 Photodiode 22 Light emitting element

Claims (10)

An uncertain output circuit that generates an uncertain digital signal sequence,
The indeterminate output circuit alternately outputs a “0” level and a “1” level, and the channel resistance of the MOS transistor that determines the time for holding the “0” level and the “1” level is changed with time. Having a multivibrator in which either of the “0” level and the time for holding the “1” level fluctuates due to fluctuation,
The MOS transistor has a gate insulating film in which a plurality of electron traps are formed. Electrons passing through a channel tunnel through the gate insulating film and are captured by the trap. A random number generation circuit characterized in that the random number generation circuit is configured to be capable of tunneling to. 2. The random number generation circuit according to claim 1, wherein the gate insulating film comprises a silicon oxide film in which silicon nanocrystals are dispersed. 2. The random number generation circuit according to claim 1, wherein said gate insulating film is made of silicon nitride oxide. 2. The random number generation circuit according to claim 1, wherein the gate insulating film is formed by introducing at least one of a defect and an impurity into a layer inside the film. An uncertain output circuit that generates an uncertain digital signal sequence,
The indeterminate output circuit alternately outputs the “0” level and the “1” level, and the resistance of the photodiode that determines the time for holding the “0” level and the “1” level varies with time. By doing so, there is provided a multivibrator in which any one of the time for holding the “0” level and the “1” level fluctuates,
The random number is characterized in that the photodiode changes a resistance in response to light emission generated in the process of applying a high voltage to a drain of a MOSFET having a gate of a sub-micrometer size to generate hot electrons and relaxing the hot electrons. Generation circuit. The uncertain output circuit,
The counter according to any one of claims 1 to 5, further comprising a counter that reads a signal sequence of the “0” level and the “1” level output from the multivibrator at a constant cycle. Random number generation circuit. The fixed period read by the counter is sufficiently longer than an average transition period in the signal sequence of the “0” level and the “1” level output from the multivibrator. Item 7. A random number generation circuit according to Item 6. A count circuit that counts the appearance frequency of “0” and “1” in the uncertain digital signal sequence output from the uncertain output circuit;
A feedback circuit that provides a feedback signal based on the appearance frequency counted by the counting circuit to the circuit element of the multivibrator,
The random number generation circuit according to any one of claims 1 to 7, further comprising: A logic operation circuit that performs an exclusive OR operation of a plurality of digital signals included in the uncertain digital signal sequence output from the uncertain output signal circuit and outputs a result of the calculation as a random number, The random number generation circuit according to claim 1. The exclusive OR of a digital signal sequence in which the appearance frequency of “0” and “1” is 1: 1 and the uncertain digital signal sequence output from the uncertain output circuit is calculated, and the calculation is performed. 9. The random number generation circuit according to claim 1, further comprising a logic operation circuit for outputting a result as a digital random number sequence.

Images