Non-biased pseudo random number generator

• US 5,778,069 A
• Filed: 04/10/1996
• Issued: 07/07/1998
• Est. Priority Date: 04/10/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yee, Bennet, Simon, Daniel R., Thomlinson, Matthew W.
• Primary Examiner(s): Dombroske, George M.
• Assistant Examiner(s): AMROZOWICZ, PAUL DOUGLAS
• Application Number:
  US08/628,552
• Time in Patent Office: 818 Days
• Field of Search: 380/25, 380/28, 380/30, 380/42, 380/46, 364/717.01
• US Class Current: 380/262
• CPC Class Codes: G06F 7/582 Pseudo-random number generators
• CPC Class Codes: G06Q 20/367 involving electronic purses or money safes
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 2209/20 Manipulating the length of blocks of bits, e.g. padding or block truncation
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator

Abstract

A computer-implemented pseudo random number generator includes an input device to assemble multiple classes of bits from multiple sources into an input bit string. The multiple classes of bits include an internal class of bits from at least one source internal to the random number generator, such as a static bit register which maintains the current state of the generator. The input device also gathers one or more external classes of bits from one or more sources external to the random number generator, such as a machine class of bits which relate to operating parameters of the computer and an application class of bits which relate to execution of an application running on the computer. The input device concatenates the three classes of bits into an arbitrary length input bit string. The random number generator also has a hash computing device which computes an m-bit hash value of the input bit string assembled by the input device. The hash computing device computes the hash value using a hashing function, such as SHA (secure hash algorithm), whereby it is computationally infeasible to derive the concatenated input bit string from the output hash value or intentionally bias the output of the hash function. The SHA is a one-way hash that reduces the 512-bit input bit string to a 160-bit hash value. The hash value becomes the initializing seed for the random number generator. A stream generator (i.e., a stream cipher) is coupled to the hash computing device to receive the hash value. The stream generator uses the hash value as the initializing seed to produce an output bit string of random (or pseudo random) bits.

Claims

1. A random number generator comprising:

an input device to assemble multiple classes of bits from multiple sources into an input bit string;

a hash computing device to compute a hash value of the input bit string using a hashing function; and

a stream generator coupled to the hash computing device to receive the hash value and to produce an output bit string of random bits using the hash value.

2. A random number generator as recited in claim 1 wherein the multiple classes of bits include an internal class of bits from at least one source internal to the random number generator, and an external class of bits from at least one source external to the random number generator.

3. A random number generator as recited in claim 1 wherein the random number generator is configured to operate on a computer that has multiple operating parameters and executes one or more applications, wherein the multiple classes of bits assembled by the input device include (1) a static class of bits that is maintained within the random number generator, (2) a machine class of bits relating to at least one operating parameter of the computer, and (3) an application class of bits relating to execution of an application running on the computer.

4. A random number generator as recited in claim 1 wherein the stream generator comprises:

a state register to initially store the hash value received from the hash computing device; and

transforming logic connected to the state register to transform the hash value into the output bit string of random bits according to a selected transformation, the transforming logic providing feed back bits to the state register to alter the bits held therein from the hash value to another value.

5. A random number generator as recited in claim 1 wherein the hash computing device computes the hash value using a secure hash algorithm.

6. A cryptography system for encrypting and decrypting messages which incorporates the random number generator as recited in claim 1.

7. A processing unit incorporating the random number generator as recited in claim 1.

8. A smart card incorporating the random number generator as recited in claim 1.

9. A random number generator for use on a computer, the computer having multiple operating parameters and executing one or more applications, the random number generator comprising:

a static bit register to hold a static class of bits;

a machine bit register to hold a machine class of bits relating to at least one operating parameter of the computer;

an application bit register to hold an application class of bits relating to execution of an application running on the computer;

a hash computing device coupled to the static bit register, the machine bit register, and the application bit register, the hash computing device computing a hash value of an input bit string that comprises at least one bit from the static bit register, at least one bit from the machine bit register, and at least one bit from the application bit register; and

a stream generator coupled to the hash computing device to receive the hash value and to produce an output bit string of random bits using the hash value.

10. A random number generator as recited in claim 9 further comprising:

a bit manipulating device coupled to the static bit register to change a previous bit value that has been used by the hash computing device to a next bit value that is different from the previous bit value.

11. A random number generator as recited in claim 9 further comprising:

a bit manipulating device coupled to the static bit register and to the hash computing device, the bit manipulating device being configured to change a previous bit value that has been used in the hash computing device to a next bit value according to a function of the hash value previously computed by the hash computing device.

12. A random number generator as recited in claim 9 further comprising:

a bit manipulating device coupled to the static bit register and to the hash computing device, the bit manipulating device being configured to change a previous bit value that has been used in the hash computing device to a next bit value according to a hashing function of the previous bit value and the hash value previously computed by the hash computing device.

13. A cryptography system for encrypting and decrypting messages which incorporates the random number generator as recited in claim 9.

14. A processing unit incorporating the random number generator as recited in claim 9.

15. A smart card incorporating the random number generator as recited in claim 9.

16. A random bit seed creating unit for use in a random number generator, the random bit seed creating unit comprising:

a first register to hold a first class of bits;

a second register to hold a second class of bits; and

a hash computing device coupled to the first and second registers, the hash computing device computing a hash value of a bit string that comprises at least one bit from the first register and at least one bit from the second register, the hash value being a random bit seed for use in initializing a random number generator.

17. A random bit seed creating unit as recited in claim 16 wherein:

the first register holds an internal class of bits derived from at least one source internal to the random bit seed creating unit; and

the second register holds an external class of bits derived from at least one source external to the random bit seed creating unit.

18. A random bit seed creating unit as recited in claim 16 adapted for operation in conjunction with the random number generator on a computer, the computer having multiple operating parameters and executing one or more applications, wherein:

the first register holds a static class of bits that is maintained within the random bit seed creating unit;

the second register holds a machine class of bits relating to at least one operating parameter of the computer; and

the random bit seed creating unit further comprising;

a third register to hold an application class of bits relating to execution of an application running on the computer.

19. A random bit seed creating unit as recited in claim 16 further comprising:

a bit manipulating device coupled to the first register to change a previous bit value that has been used by the hash computing device to a next bit value that is different from the previous bit value.

20. A random bit seed creating unit as recited in claim 16 further comprising:

a bit manipulating device coupled to the first bit register and to the hash computing device, the bit manipulating device being configured to change a previous bit value that has been used in the hash computing device to a next bit value according to a function of the hash value previously computed by the hash computing device.

21. A random bit seed creating unit as recited in claim 16 further comprising:

a bit manipulating device coupled to the first bit register and to the hash computing device, the bit manipulating device being configured to change a previous bit value that has been used in the hash computing device to a next bit value according to a hashing function of the previous bit value and the hash value previously computed by the hash computing device.

22. A processing unit incorporating the random bit seed creating unit as recited in claim 16.

23. A smart card incorporating the random bit seed creating unit as recited in claim 16.

24. A computer-readable memory used to direct a computer to generate random numbers, the computer-readable memory directing the computer to perform the following steps:

assemble multiple classes of bits from various sources into an input bit string; and

compute a hash value of the input bit string according to a hashing function, the hash value being an initializing seed for use in generating random numbers.

25. A computer-readable memory as recited in claim 24 wherein the computer-readable memory directs the computer during the assemble step to perform the following steps:

hold a static class of bits;

hold a machine class of bits relating to at least one operating parameter of the computer; and

hold an application class of bits relating to execution of an application running on the computer.

26. A computer-readable memory as recited in claim 24 further directing the computer to perform an additional step of generating random numbers using the initializing seed.

27. A computer-readable memory as recited in claim 24 further directing the computer to perform the following additional steps:

hold the classes of bits in associated registers; and

change a bit value of one of the classes of bits in one of the registers according to a function of the hash value.

28. A computer adapted to generate random numbers, the computer also having multiple operating parameters and executing one or more applications during operation, the computer comprising:

a data processor;

said data processor being programmed to generate random numbers according to the following steps;

(a) gathering a static class of bits;

(b) gathering a machine class of bits relating to at least one operating parameter of the computer;

(c) gathering an application class of bits relating to execution of an application running on the computer;

(d) computing a hash value of an input bit string that comprises at least one bit from the static class of bits , at least one bit from the machine class of bits, and at least one bit from the application class of bits; and

(e) producing an output bit string of random bits as a function of the hash value.

29. A computer as recited in claim 28 wherein said data processor is further programmed to perform an additional step of altering a previous bit value in at least one of the classes of bits that has been used to compute the hash value to a next bit value that is different from the previous bit value.

30. A computer as recited in claim 28 wherein said data processor is further programmed to perform an additional step of altering a previous bit value in at least one of the classes of bits that has been used to compute the hash value to a next bit value according to a function of the hash value.

31. A computer as recited in claim 28 wherein said data processor is further programmed to perform an additional step of altering a previous bit value in at least one of the classes of bits that has been used to compute the hash value to a next bit value according to a hashing function of the previous bit value and the hash value.

32. A random number generator comprising:

a hash computing device to compute a hash value of an input bit string using a hashing function; and

a stream generator coupled to the hash computing device to receive the hash value and to produce an output bit string of random bits using the hash value.

33. A cryptography system for encrypting and decrypting messages which incorporates the random number generator as recited in claim 32.

34. A processing unit incorporating the random number generator as recited in claim 32.

35. An integrated circuit card incorporating the random number generator as recited in claim 32.

36. A random bit seed creating unit for use in a random number generator, the random bit seed creating unit comprising:

a register to hold a bit string; and

a hash computing device coupled to the register, the hash computing device computing a hash value of the bit string, the hash value being a random bit seed for use in initializing a random number generator.

37. A processing unit incorporating the random bit seed creating unit as recited in claim 36.

38. A computer-readable memory used to direct a computer to generate random numbers, the computer-readable memory directing the computer to perform the step of computing a hash value of an input bit string according to a hashing function, the hash value being an initializing seed for use in generating random numbers.

39. A computer adapted to generate random numbers, comprising:

a data processor; and

said data processor being programmed to generate random numbers from an initializing seed, the data processor computing the initializing seed by computing a hash value of an input bit string according to a hashing function.