Method and apparatus for generating random numbers

• US 6,480,072 B1
• Filed: 04/18/2000
• Issued: 11/12/2002
• Est. Priority Date: 04/18/2000
• Status: Expired due to Term

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Biesterfeldt, Randall Paul, Walsh, James J.
• Primary Examiner(s): KINKEAD, ARNOLD M
• Application Number:
  US09/551,109
• Time in Patent Office: 938 Days
• Field of Search: 708/251, 708/250, 708/252, 331/78, 331/57, 331/46
• US Class Current: 331/78
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes

Abstract

A random number generator generates high quality random numbers by sampling the output of a voltage controlled oscillator (VCO) at a frequency much lower than the frequency of the oscillator output. The output frequency of the oscillator is changed significantly during each sampling interval to help ensure the phase relationship of the VCO output and the sampling frequency is unpredictable. That may be accomplished by logically combing the sampling clock and an output from a linear feedback shift register in an exclusive OR gate and supplying that output as the most significant bit used to generate the voltage to control the oscillator. Additional outputs from the linear feedback shift register are also used to generate the control input to the VCO. A distilling circuit such as a CRC circuit or a linear feedback shift register shifts in successive output samples and generates a number therefrom to further increase the randomness of the generated random number.

Claims

1. A random number generator comprising:

an oscillator supplying an oscillator output signal having a frequency determined according to a control input;

a sampling circuit coupled to the oscillator to sample the oscillator output signal, using a sample clock at a sampling frequency that is asynchronous to and lower than the frequency of the oscillator output signal;

wherein the control input is coupled to cause the oscillator output frequency to change significantly within each sample period of the sample clock; and

wherein the oscillator is one of a numeric controlled, voltage controlled and current controlled oscillator; and

further comprising an exclusive OR circuit coupled to provide a signal used in generating the control input for the oscillator, an output from the exclusive OR gate changing within each sample period, thereby causing the oscillator output frequency to change significantly within each sample period.

14. The random number generator as recited in claim 1 wherein the oscillator is free running and not initialized at startup.

15. The random number generator as recited in claim 1 wherein at initial power up, phase of the oscillator output signal is random with respect to the sample clock and wherein the phase of the oscillator output signal is dependent upon on all past history of oscillator state, starting from initial power up, thereby further contributing to the oscillator output signal being unpredictably random, with respect to the sample clock.

2. A random number generator comprising:

an oscillator supplying an oscillator output signal having a frequency determined according to a control input;

a sampling circuit coupled to the oscillator to sample the oscillator output signal, using a sample clock at a sampling frequency that is asynchronous to and lower than the frequency of the oscillator output signal;

wherein the control input is coupled to cause the oscillator output frequency to change significantly within each sample period of the sample clock; and

wherein the oscillator is one of a numeric controlled, voltage controlled and current controlled oscillator; and

wherein the sample clock is coupled to generate, at least in part, the control input for the oscillator, the sample clock changing values within each sample period, thereby causing the oscillator output frequency to change significantly within each sample period.

3. A random number generator comprising:

an oscillator supplying an oscillator output signal having a frequency determined according to a control input;

a sampling circuit coupled to the oscillator to sample the oscillator output signal, using a sample clock at a sampling frequency that is asynchronous to and lower than the frequency of the oscillator output signal;

a linear feedback shift register whose outputs are coupled to generate at least, in part, the control input; and

wherein the control input is coupled to cause the oscillator output frequency to change significantly within each sample period of the sample clock.

4. The random number generator as recited in claim 3 further comprising an exclusive OR circuit coupled between the linear feedback shift register and the oscillator, the exclusive OR circuit being coupled to receive one of the linear feedback shift register outputs and to supply one of the signals used to generate the control input to the oscillator.

5. The random number generator as recited in claim 4 wherein the one of the signals supplied from the exclusive OR circuit is a most significant bit used to generate the control signal, thereby providing that the oscillator output signal is changed significantly during each sample period.

6. The random number generator as recited in claim 4 wherein the exclusive OR circuit logically combines the sample clock and the one of the linear feedback shift register outputs to provide the most significant bit used to generate the control input.

7. The random number generator as recited in claim 6 wherein the exclusive OR circuit further receives a second clock signal that is asynchronous to the sample clock.

8. The random number generator as recited in claim 6 wherein the exclusive OR circuit further receives a clock whose period is relatively prime with respect to the sample clock.

9. The random number generator as recited in claim 6 further comprising a pulse circuit generating a pulse signal coupled as an input to the exclusive OR circuit, the pulse circuit generating the pulse signal whenever an input to the pulse circuit changes.

10. The random number generator as recited in claim 9 wherein the pulse circuit receives a clock signal as an input, the clock signal being different from a clock used to clock the linear feedback shifter register clock signal.

11. The random number generator as recited in claim 9 wherein the pulse circuit receives an aperiodic signal as an input.

12. The random number generator as recited in claim 6 further comprising a plurality of pulse circuits generating a respective plurality of pulse signals coupled as inputs to the exclusive OR circuit, each of the pulse circuits receiving a different clock as an input signal.

13. The random number generator as recited in claim 4 further comprising a digital to analog converter coupled to received outputs from the linear feedback shift register and the exclusive OR circuit, convert them to analog signals and supply the analog signals as the control input to the oscillator.

23. The random number generator as recited in claim 3 wherein a clock used to clock the linear feedback shift register is asynchronous to the sampling frequency.

24. The random number generator as recited in claim 3 wherein a clock used to clock linear feedback shift register operates at a frequency different from the sampling frequency.

25. The random number generator as recited in claim 3 wherein a clock used to clock the linear feedback shift register operates at a frequency relatively prime with respect to the period of the sampling frequency.

26. The random number generator as recited in claim 3 wherein a clock used to clock linear feedback shift register is a periodic waveform modified to be aperiodic by an external event.

27. The random number generator as recited in claim 26 wherein the external event causes an extra clock to be provided to the linear feedback shift register.

28. The random number generator as recited in claim 26 wherein the external event is a keystroke on a keyboard.

29. The random number generator as recited in claim 13 further comprising a filter providing a combined transient response time of the digital to analog converter and the VCO to be approximately a period of the sampling frequency.

30. The random number generator as recited in claim 3 further comprising a ring oscillator coupled the linear feedback shift register.

31. The random number generator as recited in claim 3 further comprising a plurality of ring oscillators, each ring oscillator having a different frequency and independent and being coupled to respective registers of the linear feedback shift register.

32. The random number generator as recited in claim 31 further comprising a plurality of exclusive OR gates coupled to receive respective outputs of the ring oscillators, the output of the exclusive OR gates being coupled to respective inputs of the respective registers of the linear feedback shift register.

16. A random number generator comprising:

an oscillator supplying an oscillator output signal having a frequency determined according to a control input;

a sampling circuit coupled to the oscillator to sample the oscillator output signal, using a sample clock at a sampling frequency that is asynchronous to and lower than the frequency of the oscillator output signal;

a distilling circuit coupled to receive the output of the sampling circuit and generate an N bit output therefrom; and

wherein the control input is coupled to cause the oscillator output frequency to change significantly within each sample period of the sample clock.

17. The random number generator as recited in claim 16 wherein the distilling circuit is a cyclic redundancy check (CRC) circuit.

18. The random number generator as recited in claim 16 wherein the distilling circuit is a linear feedback shift register.

19. The random number generator as recited in claim 16 wherein the distilling circuit is coupled to shift in a number of bits from the sampling circuit greater than the number of output bits of the distilling circuit before providing a valid output available outside of the random number generator.

20. The random number generator as recited in claim 16 wherein the number of bits shifted into the distilling circuit is randomized within a predetermined range.

21. The random number generator as recited in claim 20 wherein the number of bits shifted into the distilling circuit are randomized by shifting in N bits plus an output of a linear feedback shift register.

22. The random number generator as recited in claim 16 further comprising a linear feedback shift register coupled to provide a serial output coupled to selectively enable shifting into the distilling circuit according to the serial output.

33. A method of generating a random number comprising:

supplying an oscillator output signal having a frequency determined according to a control input;

sampling the oscillator output signal in a sampling circuit using a sampling clock at a sampling frequency lower than and asynchronous to the frequency of the oscillator output signal and supplying a sampled output signal indicative thereof,

changing the oscillator output frequency significantly during each sampling interval using the control input;

shifting the sampled output signal into a linear feedback shift register;

generating pseudo random numbers in the linear feedback shift register; and

generating the control input using the pseudo random numbers.

34. The method as recited in claim 33 further comprising:

supplying the sampling clock as the most significant bit used in generating the control input, thereby causing the oscillator output frequency to change significantly during each sampling interval.

35. The method as recited in claim 33 further comprising:

providing the outputs from the linear feedback shift register to a digital to analog converter and supplying an analog output from the digital to analog converter as the control input to the oscillator.

36. The method as recited in claim 33 wherein generating the control input further includes logically combining one of the outputs of the linear feedback shift register in an exclusive OR circuit and providing an output from the exclusive OR circuit to generate, at least in part, the control input.

37. The method as recited in claim 33 wherein the output from the exclusive OR circuit is the most significant bit used to generate the control input.

43. The method as recited in claim 33 further comprising modifying a clock, which is a periodic waveform used to clock the linear feedback shift register, to be aperiodic by an external event.

38. A method of generating a random number comprising:

supplying an oscillator output signal having a frequency determined according to a control input;

sampling the oscillator output signal in a sampling circuit using a sampling clock at a sampling frequency lower than and asynchronous to the frequency of the oscillator output signal and supplying a sampled output signal indicative thereof;

changing the oscillator output frequency significantly during each sampling interval using the control input; and

shifting successive outputs from the sampling circuit into a distilling circuit to generate an N bit random number.

39. The method as recited in claim 38 wherein the distilling circuit is a cyclic redundancy check circuit.

40. The method as recited in claim 38 wherein more than N successive samples are shifted into the distilling circuit to generate the N bit random number.

41. The method as recited in claim 38 further comprising generating a signal indicating when the N-bit random number is valid.

42. The method as recited in claim 38 wherein a random number of samples between a lower bound and an upper bound are shifted into the distilling circuit from the sampling circuit.

44. A random number generator comprising:

an oscillator supplying an output signal;

means for sampling the output signal and supplying a sample signal indicative thereof;

means for changing oscillator output frequency significantly during each sampling period; and

means for distilling successive sample signals.

45. The random number generator as recited in claim 44 further comprising means for randomly controlling the output frequency of the oscillator.