Granted Patent B2

US 9,075,674 · App. 13/712,070 · Granted Jul 7, 2015

Abstract

Claims (57)

1. A method for generating a bitstring, the method comprising the steps of:

setting a current value of a sampling parameter to an initial value;

producing a set of test bits by repeatedly sampling values of one or more bits, wherein the values are derived from a received signal, and wherein each sampling process is performed upon an expiration of a sampling interval that corresponds to the current value of the sampling parameter;

analyzing the set of test bits to determine a randomness measurement associated with the set of test bits;

determining whether the randomness measurement meets a criterion;

when the randomness measurement does not meet the criteria, changing the current value of the sampling parameter to a different value that corresponds to an increase in the sampling interval; and

repeating the steps of producing the set of test bits, analyzing the set of test bits, and determining whether the randomness measurement meets the criteria.

2. The method of claim 1 , wherein the sampling parameter comprises a number of transitions of a clock signal, and wherein:

setting the current value comprises setting the current value to a first number of clock cycle transitions that corresponds to a sampling interval of a first length of time; and

changing the current value comprises setting the current value to a second number of clock cycle transitions that is larger than the first number of clock cycle transitions, wherein the second number of transitions corresponds to a sampling interval of a second length of time that is larger than the first length of time.

3. The method of claim 1 , wherein the received signal is an oscillating signal, and wherein producing the set of test bits comprises deriving the values from the received signal by:

measuring a variable associated with the oscillating signal; and

storing a measurement of the variable in a register, wherein the one or more bits whose values are sampled include one or more bits of the register.

4. The method of claim 3 , wherein the variable of the oscillating signal is selected from a number of transitions of the oscillating signal that occur during the sampling interval, an amplitude of the oscillating signal, a frequency of the oscillating signal, and a phase of the oscillating signal.

5. The method of claim 3 , wherein the oscillating signal is a square wave produced by an oscillator, and the oscillator is characterized by producing a signal having a value that becomes less predictable over time.

6. The method of claim 3 , wherein the variable of the oscillating signal is a number of transitions of the oscillating signal that occur during the sampling interval, and wherein producing the set of test bits comprises repeatedly:

initializing the register at a beginning of a new sampling interval;

during the sampling interval, maintaining a value in the register that indicates a running count of a number of transitions that occur in the oscillating signal;

determining whether the sampling interval has expired; and

when the sampling interval has expired, sampling the one or more values of the one or more bits from one or more bits of the register, and beginning a new sampling interval.

7. The method of claim 6 , wherein the transitions that are included in the running count are selected from low-to-high transitions, high-to-low transitions, and both low-to-high and high-to-low transitions.

8. The method of claim 6 , wherein the one or more bits include one or more of the least significant bits of the register.

9. The method of claim 1 , further comprising:

prior to changing the current value of the sampling parameter, performing a pre-defined number of retry operations without changing the current value, wherein each retry operation includes again producing the set of test bits, again analyzing the set of test bits to determine the randomness measurement, and again determining whether the randomness measurement meets the criteria.

10. The method of claim 1 , wherein:

producing the set of test bits includes storing at least some of the test bits as they are produced in a buffer; and

after determining whether the randomness measurement meets the criterion, and when the randomness measurement meets the criterion, producing an indication to a random number generator that the test bits in the buffer may be used as an entropy bitstring by the random number generator.

11. A method for a bitstring generator to generate a bitstring, the method comprising the steps of:

setting a sampling parameter to a current value, wherein different values of the sampling parameter are associated with different probabilities of being able to correctly predict values of one or more bits produced by the bitstring generator, wherein the values are derived from a received signal;

repeatedly sampling the values of the one or more bits, wherein each sampling process is performed based on the current value of the sampling parameter, and wherein the repeated sampling results in a set of test bits;

analyzing the set of test bits to determine a randomness measurement associated with the set of test bits;

determining whether the randomness measurement meets a criterion;

when the randomness measurement does not meet the criteria, changing the current value of the sampling parameter to a different value that corresponds to a lower probability of being able to correctly predict the values of the one or more bits produced by the bitstring generator; and

repeating the steps of repeatedly sampling, analyzing the set of test bits, and determining whether the randomness measurement meets the criteria.

12. The method of claim 11 , wherein the sampling parameter is selected from a parameter that specifies an interval of time, a parameter that specifies a number of clock cycles, a parameter that specifies a number of clock signal transitions, a parameter that specifies a number of sampling bits, a parameter that specifies a voltage range, and a parameter that specifies a current adjustment.

13. The method of claim 11 , wherein the received signal is an oscillating signal, and wherein the method further comprises the steps, performed before sampling the values of the one or more bits, of:

measuring a variable associated with the oscillating signal; and

storing a measurement of the variable in a register, wherein the one or more bits whose values are sampled include one or more bits of the register.

14. The method of claim 13 , wherein the oscillating signal is a square wave produced by an oscillator, and the oscillator is characterized by producing a signal having a value that becomes less predictable over time.

15. A system comprising:

a sampling parameter register configured to retain a current value of a sampling parameter;

a sampling parameter setting module configured to store the current value of the sampling parameter in the sampling parameter register;

a sampling control module configured to produce a set of test bits by repeatedly causing values of one or more bits to be sampled, wherein the values are derived from a received signal, and wherein the sampling control module causes each sampling process to be performed upon an expiration of a sampling interval that corresponds to the current value of the sampling parameter; and

a testing module configured to analyze the set of test bits to determine a randomness measurement associated with the set of test bits, and to determine whether the randomness measurement meets a criterion,

wherein the sampling parameter setting module is further configured to change the current value of the sampling parameter to a different value that corresponds to an increase in the sampling interval when the randomness measurement does not meet the criteria.

16. The system of claim 15 , further comprising:

a measurement module configured to produce a measurement of a variable associated with an oscillating signal; and

a register coupled to the measurement module and to the sampling control module, wherein the register is configured to receive the measurement of the variable from the measurement module and to store the measurement of the variable, and wherein

the sampling control module is configured to produce the set of test bits by causing the one or more bits whose values are sampled to include one or more bits of the register.

17. The system of claim 15 , further comprising:

an oscillator that is characterized by producing a signal having a value that becomes less predictable over time.

18. The system of claim 17 , wherein the oscillator comprises a ring oscillator configured to produce a square wave.

19. The system of claim 15 , further comprising:

a buffer configured to store at least some of the test bits as they are produced; and

a random number generator configured to receive an entropy bitstring, and

wherein the testing module is further configured to provide a signal to the random number generator when the randomness measurement meets the criteria, wherein the signal indicates to the random number generator that the test bits in the data structure may be used as the entropy bitstring.

20. The system of claim 19 , wherein the random number generator is a deterministic random number generator.

Assignments (22)