System And Method For Dynamic Tuning Feedback Control For Random Number Generator

• US 20140351305A1
• Filed: 05/13/2014
• Published: 11/27/2014
• Est. Priority Date: 05/23/2013
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Elliptic Technologies, Inc. (Synopsys Incorporated)
• Inventors: Hamilton, Neil Farquhar, Hamilton, Scott Andrew, Borza, Michael
• Granted Patent: US 9,846,568 B2
• Time in Patent Office: Days
• US Class Current: 708/251
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes

Abstract

A random number generator includes a first circuit producing a random sequence of values, the first circuit having an adjustable input that changes the entropy of the random sequence of numbers; a second circuit receiving the random sequence of values from the first circuit and producing an output indicative of the degree of entropy of the random sequence of values, and a third circuit that adjusts the adjustable input of the first circuit in response to the output of the second circuit.

Claims

1. A random number generator comprising

a first circuit producing a random sequence of values, said circuit having an adjustable input that changes the entropy of the random sequence of numbers,

a second circuit receiving the random sequence of values from the first circuit and producing an output indicative of the degree of entropy of the random sequence of values, and

a third circuit that adjusts the adjustable input of the first circuit in response to the output of the second circuit.

2. The random number generator of claim 1 in which said first circuit includes

a pair of oscillators producing first and second oscillating output signals, at least the second oscillator being tunable so that the frequency of said second oscillating output signal can be adjusted, and

a sampling circuit receiving said first and second oscillating output signals and sampling said first oscillating output signal at intervals determined by said second oscillating output signal,

3. The random number generator of claim 2 in which said first and second oscillators are free-running from the first application of power, so that said first and second oscillating output signals have random phases with respect to each other.

4. The random number generator of claim 2 in which said sampling circuit is a D-type flip flop having a D input receiving said first oscillating output signal, and a clock input receiving said second oscillating output signal.

5. The random number generator of claim 1 in which said second circuit is a von Neumann de-correlator that produces a first output signal that changes states whenever the output of said first circuit is in first and second states for equal portions of a selected time period.

6. The random number generator of claim 5 in which said third circuit includes a counter that counts the state changes in said first output signal of said de-correlator, and is reset each time the count reaches a predetermined threshold value.

7. The random number generator of claim 6 in which said third circuit adjusts the adjustable input of said first circuit each time said count reaches said predetermined threshold value.

32. The circuit of claim 1 which includes an initiator circuit for initiating the oscillators from a known state in a deterministic manner.

8. A random number generator comprising

a first circuit producing a random sequence of values, said circuit having an adjustable input that changes the degree of randomness of the random sequence of values,

a second circuit receiving the random sequence of values from the first circuit and producing an output indicative of the degree of randomness of the random sequence of values, and

a third circuit that adjusts the adjustable input of the first circuit in response to the output of the second circuit.

9. A circuit for producing a random sequence of values, said circuit comprising:

a digital circuit having a state that produces a non-deterministic output that includes a random sequence of values based on inherent entropy in the digital circuit,

a tuning circuit for adjusting said entropy in said digital circuit based on said output of said digital circuit; and

an output port for providing therefrom said random sequence of values.

10. The circuit of claim 9 in which the tuning circuit comprises an entropy determination circuit for measuring entropy within the digital circuit.

11. The circuit of claim 10 in which the tuning circuit comprises an automated control system for adjusting an amount of entropy produced by the circuit.

12. The circuit of claim 9 which includes a first oscillator for oscillating at a first frequency and comprising a known amount of entropy in transitions thereof;

a second tunable oscillator for oscillating and comprising a second known amount of entropy in transitions thereof; and

a tuning circuit for adjusting at least the second tunable oscillator for affecting an amount of entropy within the random sequence of values.

13. The circuit of claim 9 which includes a first oscillator for oscillating at a first frequency and comprising a known amount of entropy in transitions thereof;

a second tunable oscillator for oscillating and comprising a second known amount of entropy in transitions thereof;

a combining circuit for combining results of the first oscillator and the second oscillator to produce a value, the value being non-deterministic and based on a known amount of entropy;

and a tuning circuit for adjusting at least the second tunable oscillator for affecting the known amount of entropy within the random sequence of values.

14. The circuit of claim 12 which includes a power saving control circuit for controlling operation of the first oscillator and the second tunable oscillator to switchably control their operation between a first normal mode of operation and a second low power mode of operation.

15. The circuit of claim 12 which includes a power saving control circuit for controlling operation of the first oscillator and the second tunable oscillator to switchably control their operation between a first low power mode of operation in which the first oscillator and the second tunable oscillator other than oscillate and a second normal mode of operation.

16. The circuit of claim 9 in which the first digital oscillator acts to provide a gate signal to produce a bit of output data for forming part of the sequence of values, and the second digital oscillator is disposed for being gated to provide the output data therefrom.

17. The circuit of claim 16 in which circuit for being gated comprises a transmission gate.

18. The circuit of claim 16 in which circuit for being gated comprises a transparent latch.

19. The circuit of claim 16 which includes filters for filtering of sampled values.

22. The circuit of claim 16 in which said circuit for being gated comprises a cascade of transparent latches, each latch gated inversely to its mate within the cascade of transparent latches.

23. The circuit of claim 9 which includes a third digital oscillator and a fourth digital oscillator wherein the third digital oscillator acts to provide a gate signal to produce a bit of output data for forming part of the sequence of values and the fourth digital oscillator is disposed for being gated to provide the output data therefrom, timing between the third digital oscillator and the fourth digital oscillator being tunable.

24. The circuit of claim 9 which includes a buffering subsystem having an input port and an output port and for buffering values received at said input port to form a sequence of values at said output port.

25. The circuit of claim 9 which includes a monitor for monitoring entropy within the sequence of values and for providing a signal indicative of said entropy.

26. The circuit of claim 9 which includes a monitor for monitoring entropy within the sequence of values and for providing a signal in dependence thereon;

and an automatic tuning circuit for varying at least a parameter of at least one of the first digital oscillator and the second digital oscillator for affecting the monitored entropy within the sequence of values.

27. The circuit of claims 9 which includes a third digital oscillator and a fourth digital oscillator wherein the third digital oscillator acts to provide a gate signal to produce a bit of output data for forming part of the sequence of values and the fourth digital oscillator is disposed for being gated to provide the output data therefrom, the timing between the third digital oscillator and the fourth digital oscillator being tunable.

28. The circuit of claim 27 in which the first oscillator and the second digital oscillator from a first oscillator pair and wherein the third digital oscillator and the fourth digital oscillator from a second oscillator pair and wherein the oscillator pairs are disposed such that sampling one oscillator synchronously with the other produces with high probability a sample obtained during a metastable transition of an input port to a sampling gate.

29. The circuit of claim 28 in which at least one oscillator from each pair is tuned by adjusting one of a sampling timing and a transition timing to result in a sample obtained during a metastable transition of an input port to a sampling gate.

30. The circuit of claim 22 which includes a monitoring subsystem that accumulates rates of successive sample rejections by the von Neumann de-correlators.

31. The circuit of claim 30 which includes a control circuit, the control circuit for adjusting relative frequencies of oscillators in each pair to reduce the rates of sample rejection.

20. The circuit of claim 20 in which the filters comprise von Neumann de-correlators.

21. The circuit of claim 20 in which the filters comprise a cascade of von Neumann de-correlators.

33. A method of generating random numbers comprising

producing a random sequence of values that has adjustable entropy,

de-correlating said random sequence of values from the first circuit and producing a signal indicative of the degree of entropy of said random sequence of values, and

adjusting the entropy of said random sequence of values in response to said signal indicative of the degree of entropy of said random sequence of values.

34. A method of producing a random sequence of values comprising:

providing a first digital oscillator starting from a first known state,

providing a second digital oscillator starting from a second known state,

tuning at least one of the first digital oscillator and the second digital oscillator to result in an interaction between the first digital oscillator and the second digital oscillator that depends upon an entropy of at least one of the first digital oscillator and the second digital oscillator, and

sampling of at least one of the first digital oscillator and the second digital oscillator such that a value is determined in dependence upon both the first digital oscillator and the second other digital oscillator and an entropy therein.

35. A circuit comprising

a first circuit portion having entropy therein for affecting a result thereof to from a sequence of non-deterministic values;

and

an automated control system for adjusting an amount of entropy within the sequence of non-deterministic values.