Cryptographic key generation system

• US 6,701,435 B1
• Filed: 08/16/1999
• Issued: 03/02/2004
• Est. Priority Date: 08/20/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Numao, Masayuki, Kudo, Michiharu
• Primary Examiner(s): Barron, Gilberto
• Assistant Examiner(s): Lanier, Benjamin E.
• Application Number:
  US09/375,346
• Time in Patent Office: 1,660 Days
• Field of Search: 713/168, 380/277
• US Class Current: 713/168
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying

Abstract

A method and a system for safely generating a cryptographic key that is separately provided to a plurality of servers. Through the collaboration of multiple users a cryptographic key is generated for the servers. Specifically, random values are exchanged among the multiple servers, and based on these values, cryptographic keys are generated. Even though the cyclic feature of the cryptographic keys of the individual servers is lost by the exchange of the random values by at least two servers, the cyclic feature for the overall system can be maintained. Public keys for the multiple cryptographic keys are generated and are published. A new public key is generated by combining a plurality of public keys, and a corresponding cryptographic key is calculated by using the cryptographic keys of the individual servers. A key updating cycle (depending on the number of cryptographic key registers) is introduced for each server, so that decryption key information appears only during a specific cycle (this is called a cyclic system). A time key is generated by the cyclic system, and when a plurality of such cyclic systems are prepared and are autonomically activated, a safer time key can be generated. In the above described distributed system that includes multiple servers, key information can not be obtained even when one system maintains its own state. Since the servers periodically update their cryptographic keys, it is ensured that the calculation of a cryptographic key will be inhibited until a decryption time has been is reached.

Claims

1. A system for time key cryptography through the collaboration of multiple servers, each of which stores a cryptographic key that is cyclically updated, comprising:

(1) means for encrypting a message using a public time key generated from said cryptographic keys;

(2) means for thereafter updating said cryptographic keys in accordance with update cycles having a different period on each of said servers; and

(3) means for decrypting said message using a private key generated from said cryptographic keys following the lapse of a common multiple of the periods of the update cycles on said servers.

2. The system according to claim 1, wherein said common multiple is a least common multiple of the periods of the update cycles on said servers.

3. The system according to claim 1, wherein said public time key is generated from public keys derived from the cryptographic keys stored by said servers.

10. The system according to claim 1, wherein said updating means comprises:

(1) means for exchanging random values among said multiple servers; and

(2) means for synchronously generating cryptographic keys by employing said random values at at least two of said multiple servers.

11. The system according to claim 10, wherein said means for synchronously generating said cryptographic keys comprises means for generating said cryptographic keys using cryptographic key registers belonging to said servers.

12. The system according to claim 11, wherein each of said servers has a different number of cryptographic key registers corresponding to the period of the update cycle on that server.

13. The system according to claim 11, wherein said means for synchronously generating said cryptographic keys comprises means for calculating public keys using cryptographic keys generated by said cryptographic key registers and for publishing said public keys.

14. The system according to claim 13, wherein said means for exchanging said random values comprises means for encrypting said random values by using said public keys and for exchanging the resultant values.

15. The system according to claim 14, wherein said means for exchanging said random values comprises means for decrypting random values received from servers other than local use servers and for using said random values to update random value buffers.

16. The system according to claim 15, wherein said means for synchronously generating said cryptographic keys comprises means for extracting from said cryptographic key registers cryptographic keys that are next to be generated and for updating the values in said cryptographic key registers by employing said cryptographic keys and values in said random value buffers.

4. A method for time key cryptography through the collaboration of multiple servers, each of which stores a cryptographic key that is cyclically updated, comprising the steps of:

(1) encrypting a message using a public time key generated from said cryptographic keys;

(2) thereafter updating said cryptographic keys in accordance with update cycles having a different period on each of said servers; and

(3) decrypting said message using a private key generated from said cryptographic keys following the lapse of a common multiple of the periods of the update cycles on said servers.

5. The method according to claim 4, wherein said common multiple is a least common multiple of the periods of the update cycles on said servers.

6. The method according to claim 4, wherein said public time key is generated from public keys derived from the cryptographic keys stored by said servers.

17. The method according to claim 4, wherein said updating step comprises the steps of:

(1) exchanging random values among said multiple servers; and

(2) synchronously generating cryptographic keys by employing said random values at at least two of said multiple servers.

18. The method according to claim 17, wherein said step of synchronously generating said cryptographic keys comprises the step of generating said cryptographic keys using cryptographic key registers belonging to said servers.

19. The method according to claim 18, wherein each of said servers has a different number of cryptographic key registers corresponding to the period of the update cycle on that server.

20. The method according to claim 18, wherein said step of synchronously generating said cryptographic keys comprises the step of calculating public keys using cryptographic keys generated by said cryptographic key registers and publishing said public keys.

21. The method according to claim 20, wherein said step of exchanging said random values comprises the step of encrypting said random values by using said public keys and exchanging the resultant values.

22. The method according to claim 21, wherein said step of exchanging said random values comprises the step of decrypting random values received from servers other than local use servers and using said random values to update random value buffers.

23. The method according to claim 22, wherein said step of synchronously generating said cryptographic keys comprises the step of extracting from said cryptographic key registers, cryptographic keys that are next to be generated and updating the values in said cryptographic key registers by employing said cryptographic keys and values in said random value buffers.

7. A medium for storing a program for time key cryptography through the collaboration of multiple servers, each of which stores a cryptographic key that is cyclically updated, said program comprising:

(1) a function for encrypting a message using a public time key generated from said cryptographic keys;

(2) a function for thereafter updating said cryptographic keys in accordance with update cycles having a different period on each of said servers; and

(3) a function for decrypting said message using a private key generated from said cryptographic keys following the lapse of a common multiple of the periods of the update cycles on said servers.

8. The medium for storing a program according to claim 7, wherein said common multiple is a least common multiple of the periods of the update cycles on said servers.

9. The medium for storing a program according to claim 7, wherein said public time key is generated from public keys derived from the cryptographic keys stored by said servers.

24. The medium for storing a program according to claim 7, wherein said updating function comprises:

(1) a function for exchanging random values among said multiple servers; and

(2) a function for synchronously generating cryptographic keys by employing said random values at at least two of said multiple servers.

25. The medium for storing a program according to claim 24, wherein said function for synchronously generating said cryptographic keys comprises a function for generating said cryptographic keys using cryptographic key registers belonging to said servers.

26. The medium for storing a program according to claim 25, wherein said function for synchronously generating said cryptographic keys comprises a function for calculating public keys using cryptographic keys generated by said cryptographic key registers and for publishing said public keys.

27. The medium for storing a program according to claim 26, wherein said function for exchanging said random values comprises a function for encrypting said random values by using said public keys and for exchanging the resultant values.

28. The medium for storing a program according to claim 27, wherein said function for exchanging said random values comprises a function for decrypting random values received from servers other than local use servers and for using said random values to update random value buffers.

29. The medium for storing a program according to claim 28, wherein said function for synchronously generating said cryptographic keys comprises a function for extracting from said cryptographic key registers cryptographic keys that are next to be generated and for updating the values in said cryptographic key registers by employing said cryptographic keys and values in said random value buffers.