Cryptographic key recovery system

• US 5,815,573 A
• Filed: 04/10/1996
• Issued: 09/29/1998
• Est. Priority Date: 04/10/1996
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yung, Marcel Mordechay, Zunic, Nevenko, Matyas, Stephen Michael Jr., Karger, Paul Ashley, Kaufman, Charles William Jr., Johnson, Donald Byron
• Primary Examiner(s): Cain, David C.
• Application Number:
  US08/629,815
• Time in Patent Office: 902 Days
• Field of Search: 380/30, 380/28, 380/23, 380/4
• US Class Current: 380/286
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

A cryptographic key recovery system for generating a cryptographic key for use by a pair of communicating parties while simultaneously providing for its recovery using one or more key recover agents. A plurality of m-bit shared key parts (P, Q) are generated which are shared with respective key recovery agents, while an n-bit nonshared key part (R) is generated that is not shared with any key recovery agent. The shared key parts (P, Q) are combined to generate an m-bit value which is concatenated with the nonshared key part (R) to generate an (m+n)-bit value from which an encryption key is generated. The cryptographic system has the effective work factor of an n-bit key to all of the key recovery agents acting in concert, but has the effective work factor of an (m+n)-bit to any other combination of third parties. The quantity n is selected to make authorized key recovery feasible, but not so trivial as to permit routine decryption of intercepted communications, while the quantity m is selected to make decryption by unauthorized third parties infeasible. Means are provided for verifying that the shared key parts have been shared with the key recovery agents before permitting encrypted communications using the thus generated key.

Claims

1. A method of generating a cryptographic key for use by a pair of communicating parties while providing for the recovery of said key using a plurality of cooperating key recovery agents, said method comprising the steps of:

generating a plurality of shared key parts that are shared with respective key recovery agents;

generating a nonshared key part that is not shared with any key recovery agent;

generating said key as a function of said shared key parts and said nonshared key part; and

making respective ones of said shared key parts available to said key recovery agents to facilitate said recovery of said key using said key recovery agents.

2. The method of claim 1 in which said step of generating said key comprises the step of:

combining said shared key parts to generate a composite key part; and

generating said key as a function of said composite key part and said nonshared key part.

3. The method of claim 2 in which said shared key parts and said composite key part have a common length.

4. The method of claim 2 in which said shared key parts are combined by modulo 2 addition.

5. The method of claim 1 in which each of said key recovery agents has a public encryption key and a corresponding private decryption key, said step of making respective ones of said shared key parts available to said key recovery agents comprising the steps of:

encrypting said shared key parts using the public encryption keys of said key recovery agents to generate a plurality of encrypted shared key parts; and

transmitting said encrypted shared key parts over a communications channel from which said encrypted shared key parts may be provided to said key recovery agents.

6. The method of claim 1 in which said step of generating said key comprises the step of:

combining said shared key parts to generate a composite key part;

concatenating said composite key part with said nonshared key part to generate a resultant value; and

generating said key as a function of said resultant value.

19. The method of claim 1 in which a plurality of sets of key recovery agents are provided, each key recovery agent in a particular one of said sets cooperating with the other key recovery agents in said set to recover said key.

20. The method of claim 19 in which said step of generating said shared key parts is performed for each of said sets of key recovery agents.

21. The method of claim 20 in which said step of generating said shared key parts comprises the steps of:

generating a plurality of key parts that may be combined with one another to generate said key, said key parts corresponding in number to the number of key recovery agents in one of said sets; and

extracting from each of said key parts, for each of said sets of key recovery agents, a shared key part that is shared with one of the key recovery agents in said set.

22. The method of claim 21 in which said extracting step comprises, for at least one of said sets of key recovery agents, the step of:

partitioning each of said key parts into a shared key part that is shared with one of the key recovery agents in said set and a nonshared key part that is not shared with any key recovery agent in said set.

7. Apparatus for generating a cryptographic key for use by a pair of communicating parties while providing for the recovery of said key using a plurality of cooperating key recovery agents, said apparatus comprising:

means for generating a plurality of shared key parts that are shared with respective key recovery agents;

means for generating a nonshared key part that is not shared with any key recovery agent;

means for generating said key as a function of said shared key parts and said nonshared key part; and

means for making respective ones of said shared key parts available to said key recovery agents to facilitate said recovery of said key using said key recovery agents.

8. The apparatus of claim 7 in which means for generating said key comprises:

means for combining said shared key parts to generate a composite key part; and

means for generating said key as a function of said composite key part and said nonshared key part.

9. The apparatus of claim 8 in which said shared key parts and said composite key part have a common length.

10. The apparatus of claim 8 in which said shared key parts are combined by modulo 2 addition.

11. The apparatus of claim 7 in which each of said key recovery agents has a public encryption key and a corresponding private decryption key, said step of making respective ones of said shared key parts available to said key recovery agents comprising the steps of:

encrypting said shared key parts using the public encryption keys of said key recovery agents to generate a plurality of encrypted shared key parts; and

transmitting said encrypted shared key parts over a communications channel from which said encrypted shared key parts may be provided to said key recovery agents.

12. The apparatus of claim 7 in which said means for generating said key comprises:

means for combining said shared key parts to generate a composite key part;

means for concatenating said composite key part with said nonshared key part to generate a resultant value; and

means for generating said key as a function of said resultant value.

13. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for generating a cryptographic key for use by a pair of communicating parties while providing for the recovery of said key using a plurality of cooperating key recovery agents, said method steps comprising:

generating a plurality of shared key parts that are shared with respective key recovery agents;

generating a nonshared key part that is not shared with any key recovery agent;

generating said key as a function of said shared key parts and said nonshared key part; and

making respective ones of said shared key parts available to said key recovery agents to facilitate said recovery of said key using said key recovery agents.

14. The program storage device of claim 13 in which said step of generating said key comprises the step of:

combining said shared key parts to generate a composite key part; and

generating said key as a function of said composite key part and said nonshared key part.

15. The program storage device of claim 14 in which said shared key parts and said composite key part have a common length.

16. The program storage device of claim 14 in which said shared key parts are combined by modulo 2 addition.

17. The program storage device of claim 13 in which each of said key recovery agents has a public encryption key and a corresponding private decryption key, said step of making respective ones of said shared key parts available to said key recovery agents comprising the steps of:

encrypting said shared key parts using the public encryption keys of said key recovery agents to generate a plurality of encrypted shared key parts; and

transmitting said encrypted shared key parts over a communications channel from which said encrypted shared key parts may be provided to said key recovery agents.

18. The program storage device of claim 13 in which said step of generating said key comprises the step of:

combining said shared key parts to generate a composite key part;

concatenating said composite key part with said nonshared key part to generate a resultant value; and

generating said key as a function of said resultant value.

23. A method of providing for the recovery of a cryptographic key using a set of key recovery agents selected from a plurality of sets of key recovery agents, each key recovery agent in a particular one of said sets cooperating with the other key recovery agents in said set to recover said key, said method comprising the steps of:

generating a plurality of sets of key recovery values, each of said sets of key recovery values corresponding to one of said sets of key recovery agents, each key recovery value in one of said sets corresponding to a key recovery agent in that set, each of said sets of key recovery values having the property that said cryptographic key is recoverable from the key recovery values in said set without requiring the key recovery values in any other of said sets; and

making the respective key recovery values of each of said sets of key recovery values available to the corresponding key recovery agents in that set to facilitate the recovery of said key using a selected one of said sets of key recovery agents and without requiring the cooperation the key recovery agents of any other of said sets.

24. The method of claim 23 in which each of said key recovery agents has a public encryption key and a corresponding private decryption key, said step of making of said key recovery values available to said key recovery agents comprising the steps of:

encrypting said key recovery values using the public encryption keys of said key recovery agents to generate a plurality of encrypted key recovery values; and

transmitting said encrypted key recovery values over a communications channel from which said encrypted key recovery values may be provided to said key recovery agents.

25. The method of claim 24 in which said encrypted key recovery values are transmitted over said communications channel along with a message encrypted under said key.

26. Apparatus for providing for the recovery of a cryptographic key using a set of key recovery agents selected from a plurality of sets of key recovery agents, each key recovery agent in a particular one of said sets cooperating with the other key recovery agents in said set to recover said key, said apparatus comprising:

means for generating a plurality of sets of key recovery values, each of said sets of key recovery values corresponding to one of said sets of key recovery agents, each key recovery value in one of said sets corresponding to a key recovery agent in that set, each of said sets of key recovery values having the property that said cryptographic key is recoverable from the key recovery values in said set without requiring the key recovery values in any other of said sets; and

means for making the respective key recovery values of each of said sets of key recovery values available to the corresponding key recovery agents in that set to facilitate the recovery of said key using a selected one of said sets of key recovery agents and without requiring the cooperation the key recovery agents of any other of said sets.

27. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for providing for the recovery of a cryptographic key using a set of key recovery agents selected from a plurality of sets of key recovery agents, each key recovery agent in a particular one of said sets cooperating with the other key recovery agents in said set to recover said key, said method steps comprising:

generating a plurality of sets of key recovery values, each of said sets of key recovery values corresponding to one of said sets of key recovery agents, each key recovery value in one of said sets corresponding to a key recovery agent in that set, each of said sets of key recovery values having the property that said cryptographic key is recoverable from the key recovery values in said set without requiring the key recovery values in any other of said sets; and

making the respective key recovery values of each of said sets of key recovery values available to the corresponding key recovery agents in that set to facilitate the recovery of said key using a selected one of said sets of key recovery agents and without requiring the cooperation the key recovery agents of any other of said sets.