Method and apparatus for generating a random bit stream in true random number generator fashion

• US 7,587,439 B1
• Filed: 08/16/2002
• Issued: 09/08/2009
• Est. Priority Date: 08/31/2001
• Status: Active Grant

• Current Assignee: SK Hynix Inc.
• Original Assignee: Integrated Device Technology Incorporated (Renesas Electronics Corporation)
• Inventors: Onufryk, Peter Z., Yue, Nelson L.
• Primary Examiner(s): Do, Chat C
• Application Number:
  US10/222,543
• Time in Patent Office: 2,580 Days
• Field of Search: 708250-256
• US Class Current: 708/250
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes

Abstract

A method and apparatus for generating a random bit stream in true random number generator fashion are described. Two periodic signals are employed in generating the random bit stream. A first periodic signal having preferably an approximately fifty percent duty cycle and jitter induced by supply and substrate noise is sampled by a second periodic signal that is relatively jitter-free and of a lower frequency than the first periodic signal.

Claims

1. A method for generating a random bit stream, comprising:

generating an oscillating signal subjected to random noise using a plurality of bit source oscillators to provide random bit streams generated using supply and substrate noise on an integrated circuit chip as jitter sources and tapping said oscillating signal from a ring oscillator circuit including single-ended inverting stages that are sensitive to supply and substrate noise;

generating a first periodic signal having jitter from the oscillating signal by passing said oscillating signal through a frequency divider, thereby restoring its duty cycle to an approximately fifty percent duty cycle;

generating a second periodic signal that is relatively jitter-free and has a lower frequency than said first periodic signal;

sampling the first periodic signal with the second periodic signal to generate a random bit stream; and

coupling the random bit stream to a security engine, the security engine operable to perform cryptographic applications using the random bit stream.

2. The method according to claim 1, wherein said second periodic signal is a system clock signal.

3. The method according to claim 2, wherein said system clock signal is generated by a phase locked loop.

4. The method according to claim 1, wherein said sampling the first periodic signal with the second periodic signal to generate a random bit stream is performed on an integrated circuit device, and said random noise derives from noise on a voltage reference line on said integrated circuit device.

5. The method according to claim 4, wherein said voltage reference line is affected by supply noise on said integrated circuit device.

6. The method according to claim 4, wherein said voltage reference line is affected by substrate noise on said integrated circuit device.

7. The method according to claim 1, wherein said single-ended inverting stages are selectably includable in said ring oscillator circuit.

8. The method according to claim 7, wherein individual of said single-ended inverting stages include fan-out loads, and said ring oscillator circuit further includes a selection circuit for selectably including individual of said single-ended inverting stages into said ring oscillator circuit so that said ring oscillator circuit is of selectable fan-out and length.

9. The method according to claim 8, wherein said selection circuit includes a multiplexer having inputs coupled to outputs of individual of said single-ended inverting stages, and an output coupled to an input of one of said single-ended inverting stages.

10. The method according to claim 1, wherein said single-ended inverting stages include NOT logic.

11. The method according to claim 1, wherein said single-ended inverting stages include XOR logic.

12. The method according to claim 1, wherein said single-ended inverting stages include NAND logic.

13. The method according to claim 1, wherein said single-ended inverting stages include NOR logic.

14. An apparatus for generating a random bit stream, comprising:

a plurality of bit source oscillators providing random bit streams generated using a supply and substrate noise on an integrated circuit chip as a jitter source, wherein each of the plurality of bit source oscillators comprises a ring oscillator circuit including a plurality of inverting stages comprising single-ended inverting stages that are sensitive to said supply and substrate noise, said plurality of inverting stages subjected to said jitter source for generating an oscillating signal having jitter;

a duty cycle restorer circuit coupled to said ring oscillator circuit for generating a first periodic signal from said oscillating signal so as to exhibit jitter and an approximately fifty percent duty cycle; and

a sampling circuit coupled to said duty cycle restorer circuit for generating a random bit stream by sampling said first periodic signal with a second periodic signal relatively jitter-free with a lower frequency than said first periodic signal.

15. The apparatus according to claim 14, wherein said second periodic signal is a system clock signal.

16. The apparatus according to claim 15, further comprising a phase locked loop circuit for generating said system clock signal relatively jitter-free.

17. The apparatus according to claim 14, wherein said duty cycle restorer circuit comprises a frequency divider circuit receiving said oscillating signal and providing said first periodic signal.

18. The apparatus according to claim 14, wherein said single-ended inverting stages are selectably includable in said ring oscillator circuit.

19. The apparatus according to claim 18, wherein individual of said single-ended inverting stages include fan-out loads.

20. The apparatus according to claim 19, wherein said ring oscillator circuit further comprises a selection circuit for selectably including individual of said single-ended inverting stages into said ring oscillator circuit so that said ring oscillator circuit is of selectable fan-out and length.

21. The apparatus according to claim 20, wherein said selection circuit comprises a multiplexer circuit having inputs coupled to outputs of individual of said single-ended inverting stages, and a output coupled to an input of one of said single-ended inverting stages.

22. The apparatus according to claim 14, wherein said single-ended inverting stages include NOT logic.

23. The apparatus according to claim 14, wherein said single-ended inverting stages include XOR logic.

24. The apparatus according to claim 14, wherein said single-ended inverting stages include NAND logic.

25. The apparatus according to claim 14, wherein said single-ended inverting stages include NOR logic.

26. The apparatus according to claim 14, wherein said duty cycle restorer circuit comprises a frequency divider circuit receiving said oscillating signal and providing said first periodic signal.

27. The apparatus according to claim 14, further comprising:

a first mixing circuit for generating an enhanced random bit stream from said random bit streams by performing a mixing function.

28. The apparatus according to claim 27, wherein said mixing function is an XOR mixing function.

29. The apparatus according to claim 27, wherein said first mixing circuit includes a bias corrector circuit to reduce bit biasing in providing said enhanced random bit stream.

30. The apparatus according to claim 27, further comprising:

a pseudorandom pattern generator responsive to a seed value for generating a pseudorandom bit stream; and

a second mixing circuit for generating a further enhanced random bit stream by performing a mixing function on said enhanced random bit stream and said pseudorandom bit stream.

31. The apparatus according to claim 30, wherein said pseudorandom pattern generator comprises a linear feedback shift register.

32. The apparatus according to claim 30, wherein said apparatus is formed on an integrated circuit device, and said seed value is unique to said integrated circuit device so that said pseudorandom bit stream is unique to said integrated circuit device.

33. The apparatus according to claim 32, wherein said seed value is formed from information including manufacturing information of said integrated circuit device.

34. The apparatus according to claim 33, wherein said manufacturing information includes an identification number identifying a manufacturer of said integrated circuit device.

35. The apparatus according to claim 33, wherein said manufacturing information includes a lot number identifying a manufacturing lot from which said integrated circuit device came from in said manufacturing lot.

36. The apparatus according to claim 33, wherein said manufacturing information includes a wafer number identifying a wafer from which said integrated circuit device came from in said manufacturing lot.

37. The apparatus according to claim 33, wherein said manufacturing information includes coordinate information identifying a location in said wafer where a die of said integrated circuit device came from.

38. The apparatus according to claim 30, further comprising:

a configuration ROM storing manufacturing information unique to said integrated circuit device;

a seed register storing a programmable seed value; and

a third mixing circuit for generating said seed value by performing a mixing function on said manufacturing information and said programmable seed value.

39. The apparatus according to claim 38, wherein said seed register is real-time programmable.

40. The apparatus according to claim 14, wherein said plurality of bit source oscillators are dispersed throughout said integrated circuit chip so as to be subjected to supply and substrate noise from different parts of said integrated circuit chip.