Random number generator with entropy accumulation

• US 6,687,721 B1
• Filed: 03/31/2000
• Issued: 02/03/2004
• Est. Priority Date: 03/31/2000
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Ward, David A., Wells, Steven E.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US09/541,375
• Time in Patent Office: 1,404 Days
• Field of Search: 708/250-256, 708/3, 380/46
• US Class Current: 708/250
• 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

Abstract

A random number generator includes a random bit source to generate random bits and circuitry to process the generated random bits to accumulate entropy in the generated random bits. The random number generator also includes circuitry to output processed random bits selectively such that at least one processed random bit is not output.

Claims

1. A method comprising:

generating random bits;

processing the generated random bits to accumulate entropy in the generated random bits; and

selectively outputting the processed random bits such that at least one processed random bit is not output.

2. The method of claim 1, wherein the processing comprises propagating the random bits through a linear feedback shift register.

3. The method of claim 2, wherein the processing comprises injecting new random bits at one or more latches in the linear feedback shift register.

4. The method of claim 1, wherein the selectively outputting comprises outputting only a first predetermined number of processed random bits of one or more sets of a second predetermined number of processed random bits, wherein the first predetermined number of bits is less than the second predetermined number of bits.

5. The method of claim 4, comprising adjusting the first predetermined number of bits and/or the second predetermined number of bits.

6. The method of claim 1, wherein the generating comprises generating random bits based on integrated circuit or thermal noise.

7. An apparatus comprising:

a random bit source to generate random bits;

circuitry to process the generated random bits to accumulate entropy in the generated random bits; and

circuitry to output the processed random bits selectively such that at least one processed random bit is not output.

8. The apparatus of claim 7, wherein the random bit source generates random bits based on integrated circuit or thermal noise.

9. The apparatus of claim 7, wherein the circuitry to process the generated random bits comprises a linear feedback shift register.

10. The apparatus of claim 9, wherein the circuitry to process the generated random bits comprises one or more other random bit sources to inject random bits into the linear feedback shift register.

11. The apparatus of claim 7, wherein the circuitry to output the processed random bits selectively outputs only a first predetermined number of processed random bits of one or more sets of a second predetermined number of processed random bits, wherein the first predetermined number of bits is less than the second predetermined number of bits.

12. The apparatus of claim 11, wherein the circuitry to output the processed random bits adjusts the first predetermined number of bits and/or the second predetermined number of bits.

13. A firmware hub comprising:

(a) a memory to store basic input/output system software; and

(b) a random number generator comprising;

(i) a random bit source to generate random bits,

(ii) circuitry to process the generated random bits to accumulate entropy in the generated random bits, and

(iii) circuitry to output the processed random bits selectively such that at least one processed random bit is not output.

14. The firmware hub of claim 13, wherein the circuitry to process the generated random bits comprises a linear feedback shift register.

15. The firmware hub of claim 14, wherein the circuitry to process the generated random bits comprises one or more other random bit sources to inject random bits into the linear feedback shift register.

16. The firmware hub of claim 13, wherein the circuitry to output the processed random bits selectively outputs only a first predetermined number of processed random bits of one or more sets of a second predetermined number of processed random bits, wherein the first predetermined number of bits is less than the second predetermined number of bits.

17. The firmware hub of claim 16, wherein the circuitry to output the processed random bits adjusts the first predetermined number of bits and/or the second predetermined number of bits.

18. The firmware hub of claim 13, wherein the random bit source generates random bits based on integrated circuit or thermal noise.

19. The firmware hub of claim 13, wherein the memory comprises flash memory.

20. A chipset comprising:

(a) a memory controller hub;

(b) an input/output controller hub; and

(c) a firmware hub comprising;

(i) a memory to store basic input/output system software, and

(ii) a random number generator comprising;

(A) a random bit source to generate random bits,

(B) circuitry to process the generated random bits to accumulate entropy in the generated random bits, and

(C) circuitry to output the processed random bits selectively such that at least one processed random bit is not output.

21. The chipset of claim 20, wherein the circuitry to output the processed random bits selectively outputs only a first predetermined number of processed random bits of one or more sets of a second predetermined number of processed random bits, wherein the first predetermined number of bits is less than the second predetermined number of bits.

22. The chipset of claim 21, wherein the circuitry to output the processed random bits adjusts the first predetermined number of bits and/or the second predetermined number of bits.

23. The chipset of claim 20, wherein the random bit source generates random bits based on semiconductor or thermal noise.

24. The chipset of claim 20, wherein the memory comprises flash memory.

25. The chipset of claim 20, wherein the circuitry to process the generated random bits comprises a linear feedback shift register.

26. The chipset of claim 25, wherein the circuitry to process the generated random bits comprises one or more other random bit sources to inject random bits into the linear feedback shift register.

27. A processor comprising:

a random number generator comprising;

(i) a random bit source to generate random bits,

(ii) circuitry to process the generated random bits to accumulate entropy in the generated random bits, and

(iii) circuitry to output the processed random bits selectively such that at least one processed random bit is not output.

28. The processor of claim 27, wherein the circuitry to output the processed random bits selectively outputs only a first predetermined number of processed random bits of one or more sets of a second predetermined number of processed random bits, wherein the first predetermined number of bits is less than the second predetermined number of bits.

29. The processor of claim 28 wherein the circuitry to output the processed random bits adjusts the first predetermined number of bits and/or the second predetermined number of bits.

30. The processor of claim 27, wherein the circuitry to process the generated random bits comprises a linear feedback shift register.

31. The processor of claim 30, wherein the circuitry to process the generated random bits comprises one or more other random bit sources to inject random bits into the linear feedback shift register.

32. The processor of claim 27, wherein the random bit source generates random bits based on integrated circuit or thermal noise.

33. A computer system comprising:

(a) one or more processors;

(b) a memory controller hub;

(c) an input/output controller hub; and

(d) a firmware hub comprising;

(i) a memory to store basic input/output system software, and

(ii) a random number generator comprising;

(A) a random bit source to generate random bits,

(B) circuitry to process the generated random bits to accumulate entropy in the generated random bits, and

(C) circuitry to output the processed random bits selectively such that at least one processed random bit is not output.

34. The computer system of claim 33, wherein the circuitry to output the processed random bits selectively outputs only a first predetermined number of processed random bits of one or more sets of a second predetermined number of processed random bits, wherein the first predetermined number of bits is less than the second predetermined number of bits.

35. The computer system of claim 34, wherein the circuitry to output the processed random bits adjusts the first predetermined number of bits and/or the second predetermined number of bits.

36. The computer system of claim 33, wherein the circuitry to process the generated random bits comprises a linear feedback shift register.

37. The computer system of claim 36, wherein the circuitry to process the generated random bits comprises one or more other random bit sources to inject random bits into the linear feedback shift register.

38. The computer system of claim 33, wherein the random bit source generates random bits based on integrated circuit or thermal noise.

39. The computer system of claim 33, wherein the memory comprises flash memory.

40. A computer readable medium having computer executable instructions for:

processing generated random bits to accumulate entropy in the generated random bits; and

selectively outputting the processed random bits such that at least one processed random bit is not output.

41. The computer readable medium of claim 40, wherein the selectively outputting comprises outputting only a first predetermined number of processed random bits of one or more sets of a second predetermined number of processed random bits, wherein the first predetermined number of bits is less than the second predetermined number of bits.

42. The computer readable medium of claim 41, having computer executable instructions for adjusting the first predetermined number of bits and/or the second predetermined number of bits.

43. The computer readable medium of claim 40, wherein the processing comprises emulating propagating the random bits through a linear feedback shift register.

44. The computer readable medium of claim 43, wherein the processing comprises emulating injecting new random bits at one or more latches in the linear feedback shift register.

45. The computer readable medium of claim 40, having computer executable instructions for generating random bits.