Random number generator

• US 20050055391A1
• Filed: 10/22/2004
• Published: 03/10/2005
• Est. Priority Date: 08/23/2001
• Status: Abandoned Application

• Current Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Original Assignee: Cavium, LLC (Marvell Technology Group Limited)
• Inventors: Varadharajan, Anand, Brasili, Derek S., Bouchard, Gregg A., Carlson, David A.
• Application Number:
  US10/972,150
• Publication Number:
  US 20050055391A1
• Time in Patent Office: Days
• US Class Current: 708/250
• 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/0869 involving random numbers or seeds

Abstract

A random number generator comprising an entropy generator and a mixing function. The mixing function to read a seed from the entropy generator, to modify the seed, to insert the modified seed into a mixing function, to initialize a set of input variables used in the mixing function to generate a robust random number, and to generate subsequent robust random numbers using the mixing function without re-initializing any of the set of input variables.

Claims

1. A method for generating robust random numbers using a mixing function comprising:

reading a seed from an entropy generator;

modifying the seed;

inserting the modified seed into the mixing function;

initializing a set of input variable used in the mixing function;

generating a robust random number using the mixing function; and

generating subsequent robust random numbers using the mixing function without re-initializing any of the set of input variables.

2. A method as in claim 1, wherein said modifying the seed comprises:

duplicating a portion of the seed at least once;

concatenating the duplicated portions; and

padding the concatenated duplicated portions with a binary string to obtain a 512-bit modified seed.

3. A method as in claim 1, wherein the mixing function is the SHA-1 algorithm.

4. A method as in claim 3, wherein the initializing the set of input variables comprises setting the set of input variables to values other than those specified by the SHA-1 algorithm.

5. A method as in claim 3, wherein the initializing the set of input variables comprises providing one or more random initialization words for the values.

6. A method as in claim 1, wherein the initializing the set of input variables comprises setting the set of input variables with one or more random initialization words.

7. A method as in claim 1, wherein the mixing function is the MD5 algorithm.

8. A method as in claim 1, wherein the seed comprises 128 bits.

9. A method as in claim 1, wherein the generating subsequent robust random numbers comprises basing the set of input variables used in the mixing function on a previously generated robust random number.

10. A method as in claim 1, wherein the mixing function destroys residual statistical structure of the seed.

11. A method as in claim 1, wherein the generating subsequent random numbers comprises repeating the reading, modifying, inserting, and the generating a robust random number.

12. A method as in claim 1, wherein the generating a robust random number comprises generating a plurality of robust random numbers based on a bit digest output from the mixing function.

13. An apparatus comprising:

a processor to read a seed from an entropy generator, to modify the seed, to insert the modified seed into a mixing function, to initialize a set of input variables used in the mixing function, to generate a robust random number using the mixing function, and to generate subsequent robust random numbers using the mixing function without re-initializing any of the set of input variables.

14. A apparatus as in claim 13, wherein to modify the seed comprises:

the processor to duplicate a portion of the seed at least once;

the processor to concatenate the duplicated portions; and

the processor to pad the concatenated duplicated portions with a binary string to obtain a 512-bit modified seed.

15. The apparatus as in claim 13 wherein the mixing function is the SHA-1 algorithm.

16. The apparatus as in claim 13, wherein the seed comprises 128 bits.

17. A method as in claim 13, wherein to generate subsequent robust random numbers comprises basing the set of input variables used in the mixing function on a previously generated robust random number.

18. A method for generating robust random numbers using a SHA-1 algorithm, the method comprising:

generating entropy bits;

generating a seed for the SHA-1 algorithm based at least in part on the entropy bits;

initializing the SHA-1 algorithm with other than the particular set of the initialization words specified for the SHA-1 algorithm;

destroying residual statistical structure of the seed with the SHA-1 algorithm to generate a bit digest; and

generating one or more robust random numbers based on the bit digest.

19. A method as in claim 18, repeating the generating entropy bits, generating the seed, destroying, and generating one or more robust random numbers without reinitializing the SHA-1 algorithm.

20. A method as in claim 19, wherein the repeating includes basing the set of input variables used in the mixing function on a previously generated robust random number.

21. A method as in claim 18, wherein the initializing comprises initializing the SHA-1 algorithm with a random initialization word.

22. A method for generating robust random numbers using a mixing function comprising:

generating entropy bits;

initializing the mixing function with a random initialization word;

generating a seed for the mixing function at least in part from the entropy bits;

destroying residual statistical structure of the seed with the mixing function to generate a bit digest, and

generating one or more robust random numbers based on the bit digest.

23. A method as in claim 22, further comprising repeating the generating entropy bits, generating the seed, destroying, and generating one or more robust random numbers without repeating the initializing.

24. A method as in claim 22, wherein the mixing function is the SHA-1 algorithm.

25. A method for generating random numbers using a mixing function having a set of input variables for which is specified initialization words, the method comprising:

generating entropy bits;

generating a seed based at least in part from the entropy bits;

applying the mixing function to the seed to generate one or more robust random numbers;

repeating the generating entropy bits, generating the seed, and generating one or more random numbers using as the set of input variables values based on the result of said applying the mixing function, rather than the specified initialization words.

26. A method of claim 25, further comprising initializing the set of input variables with random initialization words.

27. A method as in claim 25, wherein the mixing function is the SHA-1 algorithm.