Method of uniforming physical random number and physical number generation device

• US 7,461,111 B2
• Filed: 09/25/2003
• Issued: 12/02/2008
• Est. Priority Date: 09/30/2002
• Status: Active Grant

• Current Assignee: FDK Corporation (Fujitsu Limited)
• Original Assignee: FDK Corporation (Fujitsu Limited)
• Inventors: Watanabe, Toshiyuki, Nakano, Hatsumi, Shimizu, Takakuni, Koibuchi, Misako, Yamamoto, Hiroyasu, Vithanage, Ananda, Shiga, Takaaki, Soga, Ryuji, Katono, Masayoshi, Fujita, Kaoru
• Primary Examiner(s): Malzahn; David H
• Application Number:
  US10/528,910
• Publication Number:
  US 20060040731A1
• Time in Patent Office: 1,895 Days
• Field of Search: 708/255, 708/801
• US Class Current: 708/255
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes

Abstract

A method of uniforming physical random numbers while concurrently maintaining a random number generating rate and ensuring security. The method sequentially inputs a plurality of physical random numbers to a shift register to hold them there, and shifts them every time a reference pulse signal rises. Physical random numbers held in the shift register are randomly selected and output by a selector based on part of them. Accordingly, physical random numbers input to the shift register are uniformed and then output even thought they have a deviation, thereby eliminating the chance of not outputting random numbers or letting others recognize the deviation of random numbers.

Claims

1. A method of uniforming physical random numbers, comprising the steps of:

inputting a plurality of physical random numbers to a random number holding device to hold the physical random numbers;

inputting a part of the physical random numbers held in the random number holding device into addresses a selector; and

randomly selecting and outputting, from the selector, a residual part of the physical random numbers, based on an address value of the part of the physical numbers input into the addresses of the selector.

2. The method of uniforming physical random numbers according to claim 1, further comprising:

inputting the output of the selector and a physical random number to an exclusive OR circuit; and

outputting an output of the exclusive OR circuit into the random number holding device, as a physical random number input into the random number holding device.

3. A method of uniforming physical random numbers, the method comprising uniforming physical random numbers at multiple stages by repeating the method of claim 1 for two or more cycles.

4. The method of uniforming physical random numbers according to claim 1, wherein the random number holding device is a shift register.

5. A physical random number generation device comprising a physical random number generator, the physical random number generator comprising:

a serial physical random number generator for generating a serial random number in accordance with a reference clock signal;

a serial/parallel converter for converting the serial random number to a parallel random number;

a plurality of registers capable of storing the parallel random number; and

a control circuit for (i) sequentially storing the parallel random number in the plurality of registers each time the parallel random number is generated by the serial/parallel converter, (ii) reading and outputting the parallel random number from the plurality of registers in accordance with a read clock signal, and (iii) successively updating contents of the plurality of registers by shifting the stored parallel random number from a register of the plurality of registers to another register of the plurality of registers, the other register being a register for which the reading of the parallel random number has completed.

6. The physical random number generation device according to claim 5, wherein the physical random number generator comprises:

an up/down counter for determining, from among the plurality of registers, a register to hold the parallel random number and outputting a write address; and

a selector for selecting the register to hold the parallel random number, the selection being made based on the write address output by the up/down counter, and the selector being for outputting a load signal based on the selection,

wherein the control circuit sequentially stores the parallel random numbers in the serial/parallel converter from a latter stage register to a former stage register, from among the plurality of registers, based on the load signal output from the selector, and reads and outputs the parallel random number from a last stage register, from among the plurality of registers, in accordance with the read clock signal, and sequentially shift the parallel random number within the former stage register to the latter stage register.

7. The physical random number generation device according to claim 5, wherein the physical random number generator comprises (i) total counter for counting a total number of serial random numbers generated by the serial physical random number generator, and (ii) a random number verification circuit for verifying a uniformity of random numbers, based on the serial random numbers, when the total number of serial random numbers counted by the total counter reaches a predetermined bit number.

8. The physical random number generation device according to claim 7, wherein a random number verification method of using the random number verification circuit comprises verifying the uniformity of random numbers by counting an appearance frequency of a random number value “

0”

or “

1” and

comparing the counted appearance frequency with a prescribed value.

9. The physical random number generation device according to claim 7, wherein a random number verification method for using the random number verification circuit comprises verifying the uniformity of random numbers by comparing a χ

square value calculated based on an appearance frequency of each random number value with a prescribed value, wherein one random number value is 4 bits.

10. The physical random number generation device according to claim 7, wherein a random number verification method for using the random number verification circuit comprises verifying the uniformity of random numbers by counting an appearance frequency of string for every length of string and comparing each counted appearance frequency with a prescribed value.

11. The physical random number generation device according to claim 7, wherein a random number verification method for using the random number verification circuit comprises verifying the uniformity of random numbers by comparing a length of a longest string appearing in the random numbers of certain bits with a prescribed value.

12. The physical random number generation device according to claim 5, further comprising a plurality of physical random number generators, wherein a first physical random number generator is selected, from among the plurality of physical random number generators, based on a select signal of the selector, to output the random number or random number verification data.

13. A physical random number generator comprising:

two integration circuits, each integration circuit for integrating a clock signal through a resistor and a capacitor to output a respective integral waveform;

two noise sources;

two amplifiers, each amplifier for amplifying a noise from a respective noise source of the two noise sources, to output a respective noise signal;

two mixers, each mixer for mixing a respective integral waveform and a respective noise signal;

two edge detection circuits, each edge detection circuit for detecting a first edge of jitter generated based on an output waveform of a respective mixer of the two mixers;

a flip-flop for outputting “

0”

or “

1”

based on a phase differences between respective output signals output from the two edge detection circuits;

a phase adjuster for adjusting a phase of an input signal input into each integration circuit, the phase adjuster including a delay, a first selector and an up/down counter; and

a feedback circuit for feeding back the output of the flip-flop to the phase adjuster so that the “

0”

or the “

1”

output from the flip-flop converges to 50%;

wherein a second selector and a third selector are provided at a former stage of each integration circuit, respectively, and

wherein the physical random number generator includes a polarity switching circuit for switching a polarity of an input to the first selector, the second selector and the third selector by a most significant bit of the up/down counter.

14. The physical random number generator according to claim 13, wherein a FET (Field Effect Transistor) is additionally provided in parallel to the capacitor of each integration circuit at a latter stage of the resistor of each integration circuit.

15. A physical random number generation device wherein two or more physical random number generators according to claim 13 are connected in parallel, such that physical random numbers input into each physical random number generator are input to each physical random number generator in parallel and are rearranged by the physical random number generators into serial physical random numbers that are output from the physical random number generators in serial form.

16. A physical random number generator comprising:

one integration circuit for integrating a clock signal through a resistor and a capacitor to output an integral waveform;

two noise sources;

two amplifiers, each amplifier for amplifying a noise from a respective noise source of the two noise sources, to output a respective noise signal;

two mixers, each mixer for mixing the integral waveform and a respective noise signal;

two edge detection circuits, each edge detection circuit for detecting a first edge of jitter generated based on an output waveform of a respective mixer of the two mixers; and

a flip-flop for outputting “

0”

or “

1”

based on a phase differences between respective output signals output from the two edge detection circuits;

wherein a variable delay, including a delay and a selector, for adjusting a phase of an input signal input into the flip-flop is provided at a former or latter stage of each edge detection circuit, and

wherein the physical random number generator includes a feedback circuit for feeding back the output of the flip-flop to the variable delay so that the “

0”

or the “

1”

output from the flip-flop converges to 50%.

17. The physical random number generator according to claim 16, wherein a FET (Field Effect Transistor) is additionally provided in parallel to the capacitor of each integration circuit at a latter stage of the resistor of each integration circuit.

18. A physical random number generation device wherein two or more physical random number generators according to claim 16 are connected in parallel, such that the physical random numbers input into each physical random number generator are input to each physical random number generator in parallel and are rearranged by the physical random number generators into serial physical random numbers that are output from the physical random number generators in serial form.

19. A physical random number generator comprising:

two integration circuits, each integration circuit for integrating a clock signal using a constant current circuit and a capacitor to output a respective integral waveform;

two noise sources;

two amplifiers, each amplifier for amplifying a noise from a respective noise source of the two noise sources, to output a respective noise signal;

two mixers, each mixer for mixing a respective integral waveform and a respective noise signal;

two edge detection circuits each edge detection circuit for detecting a first edge of jitter generated based on an output waveform of a respective mixer of the two mixers;

a flip-flop for outputting “

0”

or “

1”

based on a phase difference between respective output signals output from the two edge detection circuits;

a phase adjuster for adjusting a phase of an input signal input into each integration circuit, the phase adjuster including a delay, a first selector and an up/down counter; and

a feedback circuit for feeding back the output of the flip-flop to the phase adjuster so that the “

0”

or the “

1”

output from the flip-flop converges to 50%;

wherein a second selector and a third selector are provided at a former stage of each integration circuit, respectively, and

wherein the physical random number generator includes a polarity switching circuit for switching a polarity of an input to the first selector, the second selector and the third selector by a most significant bit of the up/down counter.

20. A physical random number generator comprising:

one integration circuit for integrating a clock signal using a constant current circuit and a capacitor to output an integral waveform;

two noise sources;

two amplifiers each amplifier for amplifying a noise from a respective noise source of the two noise sources, to output a respective noise signal;

two mixers, each mixer for mixing the integral waveform and a respective noise signal;

two edge detection circuits, each edge detection circuit for detecting a first edge of jitter generated based on an output waveform of a respective mixer of the two mixers; and

a flip-flop for outputting “

0”

or “

1”

based on a phase difference between respective output signals output from the two edge detection circuits;

wherein a variable delay, including a delay and a selector, for adjusting a phase of an input signal input into the flip-flop is provided at a former or latter stage of each edge detection circuit, and

wherein the physical random number generator includes a feedback circuit for feeding back the output of the flip-flop to the variable delay so that the “

0”

or the “

1”

output from the flip-flop converges to 50%.