System and method for generating pseudo-random numbers

• US 7,894,602 B2
• Filed: 03/31/2006
• Issued: 02/22/2011
• Est. Priority Date: 03/31/2006
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Schneider, Juergen, Miko, Ralf, Freidrich, Michael, Mueller, Maik, Kiefer, Klaus
• Primary Examiner(s): Arani; Taghi T
• Assistant Examiner(s): LANE, GREGORY A
• Application Number:
  US11/394,762
• Publication Number:
  US 20070230693A1
• Time in Patent Office: 1,789 Days
• Field of Search: 380276-278, 380/284, 380/286, 380/46, 713182-185, 713/176, 726/28, 726/30, 726/33, 714 22- 30
• US Class Current: 380/46
• 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
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator

Abstract

A process and system for generating a pseudo-random number is presented. Input data having entropy is gathered in an Entropy Pool and transformed once by a cryptographic hash function. The transformed data forms the internal state of the pseudo-random number generator. The generator forms the output by applying a second cryptographic hash function to this internal state. Finally, the generator updates the internal state by inputting the current internal state and data from the Entropy Pool into a third cryptographic hash function. The output of the third hash function forms the new internal state of the pseudo-random number generator.

Claims

1. A system for generating a pseudo-random number, the system comprising:

an entropy value collector for collecting entropy values, wherein the entropy value collector breaks obtained values into entropy values of a desired entropy value length when the obtained values are longer than the desired entropy value length;

a first data memory for storing at least one set of entropy values collected by the entropy value collector;

a second data memory for storing an internal state; and

a processor for;

transforming a first set of entropy values stored in the first data memory to form the internal state;

generating a pseudo-random number by transforming the internal state;

updating the internal state using the current value of the internal state and entropy values from the entropy value collector; and

refreshing the internal state by transforming a second set of entropy values stored in the first data memory and combining the result of the transformation of the second set of entropy values with the current value of the internal state, wherein the entropy value collector collects entropy values using at least one of a high performance counter model and a system timer.

2. The pseudo-random number generator of claim 1, wherein the processor performs the step of transforming the first set of entropy values using a cryptographic hash function.

3. The pseudo-random number generator of claim 1, wherein a number of entropy values are contained in the first set of entropy values, wherein the number of entropy values is a function of the amount of entropy contained in the entropy values.

4. The pseudo-random number generator of claim 1, wherein the entropy value collector further:

creates entropy values, at least partly, by applying a logical operation.

5. The pseudo-random number generator of claim 4, wherein the output of the logical operation contains the same amount of entropy as the input to the logical operation.

6. The pseudo-random number generator of claim 1, wherein the processor refreshes the internal state on a periodic basis.

7. The pseudo-random number generator of claim 6, wherein the processor further receives information from a user for determining when refreshing the internal state is accomplished.

16. The pseudo-random number generator of claim 1, where updating the internal state using the current value of the internal state and entropy values from the entropy value collector includes appending an entropy value of the desired length to the current value of internal state.

8. A computer-implemented method for generating a pseudo-random number, the method comprising:

collecting data having entropy in a memory, wherein an entropy value collector breaks the collected data into entropy values of a desired entropy value length when the collected data is longer than the desired entropy value length;

using a processor to transform a first set of entropy values using a first cryptographic hash function to form an internal state;

using the internal state to generate a pseudo-random number by applying a second cryptographic hash function such that no correlation exists between the first cryptographic hash function and the second cryptographic hash function;

updating the internal state by applying a third cryptographic hash function to newly collected entropy values and the internal state, wherein updating the internal state by applying a third cryptographic hash function to newly collected entropy values and the internal state includes appending an entropy value of the desired length to the internal state; and

refreshing the internal state by transforming a second set of entropy values using the first cryptographic hash function and combining the result of the transformation of the second set of entropy values with the internal state.

9. The method of claim 8, wherein the amount of collected data varies as a function of the entropy of the data.

10. A non-transitory computer-readable medium containing instructions for causing a computer to perform a method for generating a pseudo-random number, and the method comprising:

receiving data having entropy, wherein an entropy value collector breaks the received data into entropy values of a desired entropy value length when the received data is longer than a desired entropy value length;

transforming at least some of the entropy values to form an internal state;

using the internal state to generate a pseudo-random number;

updating the internal state using data from at least one of entropy values having entropy and the internal state; and

refreshing the internal state by transforming a new set of entropy values and combining the result of the transformation of the new set of entropy values with the internal state, wherein the entropy value collector collects entropy values using at least one of a high performance counter model and a system timer.

11. The computer readable medium of claim 10, wherein the step of transforming the received data is accomplished using a cryptographic hash function.

12. The computer readable medium of claim 10, wherein the amount of received data transformed to form the internal state is a function of the amount of entropy contained in the received data.

13. The computer readable medium of claim 10, further comprising applying a logical function to at least some of the received data.

14. The computer readable medium of claim 10, wherein the internal state is refreshed on a periodic basis.

15. The computer readable medium of claim 14, further comprising receiving information from a user for determining when refreshing the internal state occurs.

17. The computer readable medium of claim 10, wherein the step of updating the internal state using data from at least one of entropy values having entropy and the internal state includes appending an entropy value of the desired length to the internal state.