Random number generator

• US 6,954,770 B1
• Filed: 08/23/2001
• Issued: 10/11/2005
• Est. Priority Date: 08/23/2001
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Bouchard, Gregg A., Carlson, David A., Varadharajan, Anand, Brasili, Derek S.
• Primary Examiner(s): Ngo, Chuong D
• Application Number:
  US09/938,166
• Time in Patent Office: 1,510 Days
• Field of Search: 708/250, 708/251, 708/252, 708/253, 708/254, 708/255, 708/256
• US Class Current: 708/251
• CPC Class Codes: G06F 7/582 Pseudo-random number generators
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds

Abstract

A random number generator comprising an oscillator with an output signal dependant upon a random source, a sampling device to sample the output signal from the oscillator to obtain a sampled oscillator output, and a fixed frequency clock driven linear feedback shift register (LFSR) communicatively coupled to the sampling device via a digital gate to receive the sampled oscillator output, and to provide a random number at an output of the LFSR. Additionally, the random number generator may comprise an optional mixing function communicatively coupled to the LFSR to read the random number, and to insert the random number into an algorithm to obtain a robust random number.

Claims

1. An apparatus comprising:

an oscillator with an output signal dependant upon a random source, the oscillator comprising at least two inverters;

a sampling device to sample the output signal from the oscillator to obtain a sampled oscillator output; and

a fixed frequency clock driven linear feedback shift register (LFSR) communicatively coupled to the sampling device via a digital gate to receive the sampled oscillator output, and to provide a random number at an output of the LFSR.

2. An apparatus as in claim 1, further comprising:

a processor communicatively coupled to the LFSR to read the random number, and to insert the random number into an algorithm to obtain a robust random number.

3. An apparatus as in claim 2, wherein the algorithm is a SHA-1 algorithm.

4. An apparatus as in claim 2, further comprising the processor to duplicate the random number at least once, the processor to concatenate the duplicated random numbers prior to inserting the concatenated duplicated random number into the algorithm, wherein subsequent robust random number calculations do not require initialization of any variables.

5. An apparatus as in claim 1, wherein the sampling device comprises a flip-flop.

6. An apparatus as in claim 1 wherein the digital gate coupling the LSFR to the sampling devise comprises an exclusive—

OR gate.

7. An apparatus as in claim 1, wherein the random source comprises at least one of shot noise, and switching noise from electrical components within the apparatus.

8. An apparatus as in claim 1, wherein the fixed frequency clock driven LFSR is coupled to the sampling device and to the output of the LFSR via the digital gate.

9. An apparatus as in claim 1, wherein the apparatus is implemented on an integrated circuit chip.

10. A method comprising:

generating random binary bits;

sampling and latching the generated random binary bits;

inserting the generated random binary bits into a fixed frequency clock driven linear feedback shift register (LFSR) via a digital gate to generate a random number;

duplicating the generated random number at least once;

concatenating the duplicated random numbers; and

inserting the generated random number into an algorithm to obtain a robust random number.

11. A method as in claim 10, wherein the algorithm is a SHA-1 algorithm.

12. A method as in claim 11 wherein the SHA-1 algorithm is initialized the first time the robust random number is generated.

13. An apparatus comprising:

a plurality of random oscillators each generating a random binary output signal, that includes at least a first oscillator and a second oscillator;

a plurality of sampling devices including at least a first sampling device and a second sampling device, wherein the first sampling device samples the output from the first oscillator and the second sampling device samples the output from the second oscillator; and

a fixed frequency clock driven linear feedback shift register (LFSR) that receives the sampled binary output signal from the first sampling device and the second sampled device to generate a random number.

14. An apparatus as in claim 13 further comprising a processor communicatively coupled to the LFSR to read the random number and to insert the random number in an algorithm to obtain a robust random number.

15. An apparatus as in claim 14, wherein the algorithm is a SHA-1 algorithm.

16. An apparatus as in claim 14, further comprising the processor to duplicate the random number at least once, the processor to concatenate the duplicated random numbers prior to inserting the concatenated duplicated random numbers into the algorithm.

17. An apparatus as in claim 13 wherein each oscillator in the plurality of oscillators comprises at least two inverters.

18. An apparatus as in claim 13, wherein each sampling device in the plurality of sampling devices comprises a flip-flop.

19. An apparatus as in claim 13, wherein the LFSR receives the sampled binary output signal from the first sampling device and the second sampled device via a first exclusive OR gate and a second exclusive OR gate.

20. An apparatus as in claim 13 wherein each random oscillator responds to at least one of shot noise and switching noise to generate a random frequency binary output signal.