Distributed state random number generator and method for utilizing same

• US 6,628,786 B1
• Filed: 09/30/1997
• Issued: 09/30/2003
• Est. Priority Date: 09/30/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Dole, Bryn
• Primary Examiner(s): Barrón, Gilberto
• Assistant Examiner(s): MEISLAHN, DOUGLAS J
• Application Number:
  US08/941,677
• Time in Patent Office: 2,191 Days
• Field of Search: 380/44, 380/48, 380/262, 380/263
• US Class Current: 380/44
• 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
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying

Abstract

A system and method for generating random numbers utilizing a shared or distributed source of entropy is disclosed. In one embodiment, the invention allows networked computers to generate and share entropy in proportion to the need for random numbers utilized to initialize the internal state of random number generators residing on the computers. A shared session key generated during communications between a first and second computer is appended to the current internal state of the random number generators residing on the computers to create a bit string. The bit string is then mixed or hashed using a one-way “hash” function such as message digest function to produce a mixed bit string. At least a portion of the mixed bit string is then used to reinitialize the internal state of the random number generators residing on the computers. Since the initial state of the random number generators residing on the computers will be different, the values used to reinitialize the internal state of the generators will be different. In the case of a computer network, the internal state of each host computer'"'"'s random number will thus ultimately be dependent upon on the internal state of every other computer that the host has communicated with and the order in which the communications took place.

Claims

1. A method for generating a session key for use in electronic transmission comprising the steps of:

receiving entropy in the form of a first bit string from a first computer at a second computer, the first bit string being a first key that has previously been used in a first set of communications between two computers;

combining the entropy with a second bit string residing in the second computer to create a third bit string;

mixing the third bit string to create a fourth bit string;

using at least a portion of the fourth bit string to initialize the internal state of a random number generator residing in the second computer, thereby enabling a second key to be generated for use in a second set of communications between two computers;

generating a random number with the random number generator residing in the second computer after the internal state is initialized using at least a portion of the fourth bit string; and

creating a second key for use in a second set of communications between two computers, the second key being created using the random number generated by the random number generator residing in the second computer.

2. The method of claim 1 wherein the first key is an encryption key and the second key is an encryption key.

3. The method of claim 2 further wherein the generated random number is used as an encryption key.

4. The method of claim 1 wherein the third bit string is mixed using a one-way function.

5. The method of claim 1 wherein the second bit string comprises the internal state of the random number generator residing on the second computer.

6. The method of claim 1 further comprising the step of deleting the first bit string after the first and second bit strings have been combined.

7. The method as recited in claim 1, wherein receiving entropy comprises:

negotiating the first key with the first computer.

8. The method as recited in claim 7, the first set of communications being between the second computer and the first computer, and the second set of communications being between the second computer and a third computer.

9. A method for generating a second session key using a random number generator by initializing the internal state of a random number generator with a first session key comprising the steps of:

receiving the first session key from a first computer at a second computer;

appending the first session key to the internal state of a random number generator residing in the second computer;

mixing the appended first session key and internal state;

using at least a portion of mixed value of the first session key and the internal state of the random number generator to reinitialize the internal state of the random number generator residing in the second computer, thereby enabling a second session key to be generated;

generating a random number with the random number generator residing in the second computer after the internal state is initialized using at least a portion of the mixed value of the first session key and the internal state of the random number generator; and

creating the second session key for use in a set of communications between two computers, the second session key being created using the random number generated by the random number generator residing in the second computer.

10. The method of claim 9 wherein the first session key is a first encryption key previously used in a first session and the second session key is a second encryption key to be used in a second session.

11. The method of claim 9 wherein the first session key is mixed with the internal state of the random number generator using a one-way function.

12. The method of claim 9 wherein the first session key is negotiated by the first and second computers utilizing a key exchange protocol.

13. The method of claim 12 wherein the key exchange protocol is a Diffie-Hellman key exchange.

14. A method for generating a session key comprising the steps of:

initiating communications between a first computer and a second computer;

negotiating a first shared session key between the first and second computers;

encrypting transmissions between the first and second computers using the first session key;

appending the first session key to the internal state of a first random number generator residing on the first computer to form a first unmixed bit string;

mixing the first unmixed bit string to produce a first mixed bit string;

inputting at least a portion of the first mixed bit string into an internal state update function to update the internal state of the first random number generator residing on the first computer; and

generating a random number with the first random number generator residing on the first computer after the internal state is initialized using at least a portion of the first mixed bit string, thereby enabling a second session key to be generated; and

creating a second session key for use in a second set of communications between two computers, the second session key being created using the random number generated by the random number generator residing in the second computer.

15. The method of claim 14 wherein the first session key is an encryption key and the second session key is an encryption key.

16. The method of claim 14 further comprising the step of appending the second session key to the internal state of a second random number generator residing on the second computer to form a second unmixed bit string.

17. The method of claim 16 further comprising the step of mixing the second session key and the internal state of the second random number generator to produce a second mixed bit string.

18. The method of claim 17 further comprising the step of inputting at least a portion of the second mixed bit string into an internal state update function to update the internal state of the second random number generator residing on the second computer.

19. The method of claim 18 further comprising the step of generating a random number with the second random number generator residing on the second computer.

20. The method of claim 19 further comprising the step of using the random number generated by the second random number generator to create a third encryption key for use by the second computer in a subsequent communication.

21. A computer program embodied on a computer-readable medium for generating a session key comprising:

an initiation code segment that initiates communication between a first computer and second computer;

a negotiation code segment that generates a first shared session key between the first and second computers;

an encryption code segment that encrypts transmissions between the first and second computers using the first session key;

an append code segment that appends the first session key to the internal state of a random number generator residing on the first computer to form an unmixed bit string;

a mix code segment that mixes the unmixed bit string to produce a mixed bit string;

an input code segment that receives at least a portion of the mixed bit string into an internal state update function to update the internal state of the random number generator residing on the first computer;

a generate code segment that generates a random number with the random number generator residing on the first computer after the internal state of the random number generator is updated with at least a portion of the mixed bit string, thereby enabling a second session key to be generated for use in encrypting transmissions; and

creating a second session key for use in a second set of communications between two computers, the second session key being created using the random number generated by the random number generator residing in the first computer after the internal state of the random number generator is updated with at least a portion of the mixed bit string.

22. A method for generating a session key comprising the steps of:

receiving a first bit string at a computer transmitted from an entropy source external to the computer, the first bit string being a first key used in a first set of communications between two computers;

combining the first bit string with a second bit string residing in the computer to create a third bit string;

mixing the third bit string to create a fourth bit string;

using at least a portion of the fourth bit string to initialize the internal state of a random number generator residing in the computer, thereby enabling a second key to be generated for use in a second set of communications between two computers;

generating a random number with the random number generator residing on the computer after the internal state is initialized using at least a portion of the fourth bit string, thereby enabling a second key to be generated; and

creating a second key for use in a second set of communications between two computers, the second key being created using the random number generated by the random number generator residing in the computer.

23. The method of claim 22 wherein the first key is an encryption key and the second key is an encryption key.

24. The method of claim 22 wherein the third bit string is mixed using a one-way function.

25. The method of claim 22 wherein the first bit string is an encryption key.

26. The method of claim 22 wherein the second bit string comprises the internal state of the random number generator residing on the computer.

27. The method of claim 22 further comprising the step of erasing the first bit string after the first and second bit strings have been combined.