Method and apparatus for verifiably providing key recovery information in a cryptographic system

• US 5,907,618 A
• Filed: 01/03/1997
• Issued: 05/25/1999
• Est. Priority Date: 01/03/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gennaro, Rosario, Peyravian, Mohammad, Zunic, Nevenko, Safford, David Robert, Matyas, Stephen Michael Jr., Karger, Paul Ashley
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): CODDINGTON, TREVOR Q
• Application Number:
  US08/775,348
• Time in Patent Office: 872 Days
• Field of Search: 380/21, 380/30, 380/28, 380/49, 380/59
• US Class Current: 380/286
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

A method and apparatus for verifiably providing key recovery information to one or more trustees in a cryptographic communication system having a sender and a receiver Each communicating party has its own Diffie-Hellman key pair comprising a secret value and corresponding public value, as does each trustee The sender non-interactively generates from its own secret value and the public value held by the receiver a first shared Diffie-Hellman key pair comprising a first shared secret value, shared with the receiver but not with any trustee, and a corresponding public value. For each trustee, the sender then non-interactively generates an additional shared secret value, shared with the receiver and the trustee, from the first shared secret value and the public value corresponding to the secret value held by the trustee. The sender uses the additional shared secret value to encrypt recovery information for each trustee, which is transmitted to the receiver along with the encrypted message. Each trustee can decrypt its recovery information by regenerating its additional shared secret value from its own secret value and the public value of the first shared Diffie-Hellman key pair. The receiver can verify the correctness of the recovery information for each trustee by decrypting the information using the additional shared secret value for that trustee, without having to recreate the recovery information or perform computationally expensive public key operations.

Claims

1. In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channel, said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said trustee, said trustee holding a secret value from which a corresponding public value is generated, a method for making said recovery information available to said trustee, wherein said sender performs the steps of:

generating a first shared public value from said first shared secret value;

generating an additional shared secret value from said first shared secret value and the public value generated from the secret value held by said trustee,

encrypting said recovery information using said additional shared secret value generated for said trustee; and

transmitting said encrypted recovery information to said receiver via said communications channel, said trustee being able to decrypt said recovery information by regenerating said additional shared secret value from said first shared public value and the secret value held by said trustee.

2. The method of claim 1 in which said encryption key is a session key.

3. The method of claim 1 in which said sender and said receiver hold respective secret values from which corresponding public values are generated, said first shared secret value being generated from said secret value held by said sender and the public value generated from the secret value held by said receiver.

4. The method of claim 3 in which said first shared secret value is generated as:

space="preserve" listing-type="equation">u=g.sup.xy mod p,

where x is the secret value held by said sender, y is the secret value held by said receiver, p is a prime modulus, and g is a generator.

5. The method of claim 1 in which said sender performs the further step of:

transmitting said encrypted data to said receiver via said communications channel.

6. The method of claim 1 in which said sender performs the further step of:

transmitting said first shared public value to said receiver via said communications channel.

7. The method of claim 1 in which said first shared public value is generated as g^u mod p, where u is said first shared secret value, p is a prime modulus, and g is a generator.

8. The method of claim 7 in which said additional shared secret value is generated as

9. The method of claim 1 in which said recovery information comprises said encryption key.

10. The method of claim 1 in which said system has a plurality of trustees, each of which is provided with recovery information and holds a secret value from which a corresponding public value is generated, said steps of generating an additional shared secret value and encrypting said recovery information being performed for each of said trustees.

11. The method of claim 10 in which said encryption key is split into shares that may be combined to regenerate said encryption key, each of said trustees being provided one of said shares as recovery information.

12. The method of claim 1 in which said system has one or more trustees for each of a plurality of key recovery jurisdictions.

13. The method of claim 1 in which said recovery information is generated independently of said encryption key, said sender performing the further steps of:

generating additional recovery information as a function of said encryption key; and

transmitting said additional recovery information to said receiver via said communications channel.

14. The method of claim 1 in which said sender performs the further steps of:

encrypting said encryption key using a key-encrypting key generated from said recovery information; and

transmitting said encrypted encryption key to said receiver via said communications channel.

15. The method of claim 14 in which said encryption key is one of a plurality of encryption keys, each of which has a corresponding key-encrypting key that is generated as a function of said recovery information and information that is specific to the encryption key.

16. The method of claim 14 in which said system has a plurality of trustees, each of which is provided with recovery information from which a different key-encrypting key is generated, said encryption key being multiply encrypted with said key-encrypting keys.

17. The method of claim 1 in which said receiver performs the steps of:

receiving said encrypted recovery information;

generating said additional shared secret value from said first shared secret value and said public value generated from said secret value held by said trustee; and

decrypting said encrypted recovery information using a said additional shared secret value.

18. The method of claim 17 in which said sender performs the further step of transmitting said encrypted data to said receiver via said communications channel, said receiver performing the further steps of:

receiving said encrypted data; and

decrypting said encrypted data using said encryption key.

19. The method of claim 18 in which said receiver obtains said encryption key using said recovery information.

20. The method of claim 18 in which said step of decrypting said encrypted data comprises the steps of:

determining whether said encrypted recovery information was correctly decrypted; and

decrypting said encrypted data only if it is determined that said recovery information was correctly encrypted.

21. The method of claim 20 in which said encrypted recovery information includes a message authentication code, said step of determining whether said encrypted recovery information was correctly decrypted comprising the step of testing said message authentication code.

22. The method of claim 1 in which said trustee performs the steps of:

receiving said encrypted recovery information;

generating said additional shared secret value from said first shared public value and said secret value held by said trustee; and

decrypting said encrypted recovery information using said regenerated additional shared secret value.

23. The method of claim 1 in which said recovery information comprises non-key-specific recovery information usable to recover other keys.

24. The method of claim 23 in which said sender caches said recovery information for use in recovering said other keys.

25. The method of claim 23 in which said sender also generates and transmits to said receiver key-dependent recovery information used in conjunction with said non-key-specific recovery information to recover said encryption key.

26. The method of claim 25 in which said key-dependent recovery information is generated by generating a key-specific recovery value from said non-key-specific recovery information and key-specific recovery information and generating said key-dependent recovery information from said key-specific recovery value and said encryption key.

27. The method of claim 26 in which said key-dependent recovery information is generated by encrypting said encryption key with said key-specific recovery value.

28. A program storage device readable by a machines tangibly embodying a program of instructions executable by the machine to perform the method steps of claim 1.

29. In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channels said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said a trustee and a first shared public value generated from said first shared secret value, said trustee holding a secret value from which a corresponding public value is generated, said transmitted recovery information being encrypted using an additional shared secret value generated from said first shared secret value and the public value generated from the secret value held by said trustee, a method for regenerating said recovery information for said receiver, wherein said receiver performs the steps of:

receiving said encrypted recovery information;

generating said additional shared secret value from said first shared secret value and said public value generated from said secret value held by said trustee; and

decrypting said encrypted recovery information using said additional shared secret value.

30. The method of claim 29 in which said receiver performs the further steps of:

receiving said encrypted data; and

decrypting said encrypted data using said encryption key.

31. The method of claim 30 in which said receiver regenerates said encryption key using said decrypted recovery information.

32. The method of claim 31 in which said decrypted recovery information comprises non-key-specific recovery information usable to recover other keys.

33. The method of claim 32 in which said receiver caches said decrypted recovery information for use in recovering said other keys.

34. The method of claim 32 in which said sender also transmits key-dependent recovery information used in conjunction with said non-key-specific recovery information to recover said encryption keys said receiver regenerating said encryption key from said key-dependent recovery information and said non-key-specific recovery information.

35. The method of claim 34 in which said key-dependent recovery information is generated by generating a key-specific recovery value from said non-key-specific recovery information and key-specific recovery information and generating said key-dependent recovery information from said key-specific recovery value and said encryption keys said receiver regenerating said encryption key by:

regenerating said key-specific recovery value from said non-key-specific recovery information and said key-specific recovery information; and

regenerating said encryption key from said regenerated key-specific recovery value and said key-dependent recovery information.

36. The method of claim 35 in which said key-dependent recovery information is generated by encrypting said encryption key with said key-specific recovery value, said receiver regenerating said encryption key by decrypting said key-dependent recovery information using said regenerated key-specific recovery value.

37. The method of claim 30 in which said step of decrypting said encrypted data comprises the steps of:

determining whether said encrypted recovery information was correctly decrypted; and

decrypting said encrypted data only if it is determined that said recovery information was correctly encrypted.

38. The method of claim 37 in which said encrypted recovery information includes a message authentication code, said step of determining whether said encrypted recovery information was correctly decrypted comprising the step of testing said message authentication code.

39. The method of claim 29 in which said sender and said receiver hold respective secret values from which corresponding public values are generated, said first shared secret value being generated from said secret value held by said sender and the public value generated from the secret value held by said receiver.

40. The method of claim 39 in which said first shared secret value is generated as:

space="preserve" listing-type="equation">u=g.sup.xy mod p,

where x is the secret value held by said sender, y is the secret value held by said receiver, p is a prime modulus, and g is a generator.

41. The method of claim 29 in which said first shared public value is generated as g^u mod p, where u is said first shared secret value, p is a prime modulus, and g is a generator.

42. The method of claim 41 in which said additional shared secret value is generated as

43. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps of claim 29.

44. In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channel, said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said trustee and a first shared public value generated from said first shared secret value, said trustee holding a secret value from which a corresponding public value is generated, said transmitted recovery information being encrypted using an additional shared secret value generated from said first shared secret value and the public value generated from the secret value held by said trustee, a method for regenerating said recovery information for said trustee, wherein said trustee performs the steps of:

receiving said encrypted recovery information and said first shared public value;

regenerating said additional shared secret value from said first shared public value and said secret value held by said trustee; and

decrypting said encrypted recovery information using said regenerated additional shared secret value.

45. The method of claim 44 in which said trustee receives said encrypted recovery information and said first shared public value from a party seeking recovery of said encryption key.

46. The method of claim 44 in which said first shared public value is generated as g^u mod p, where u is said first shared secret value, p is a prime modulus, and g is a generator.

47. The method of claim 46 in which said additional shared secret value is generated as

48. The method of claim 44 in which said trustee performs the further step of:

revealing said decrypted recovery information to a party seeking recovery of said encryption key.

49. The method of claim 44 in which said trustee performs the further step of:

generating a recovery value from said decrypted recovery information;

revealing said recovery value to a party seeking recovery of said encryption key.

50. The method of claim 44 in which said recovery value is generated as a one-way function of said decrypted recovery information and additional recovery information specific to said encryption key.

51. The method of claim 44 in which said trustee receives said additional recovery information from a party seeking recovery of said encryption key.

52. The method of claim 44 in which said decrypted recovery information comprises non-key-specific recovery information usable to recover other keys.

53. The method of claim 52 in which said trustee caches said decrypted recovery information for use in recovering said other keys.

54. The method of claim 52 in which said sender also transmits key-dependent recovery information used in conjunction with said non-key-specific recovery information to recover said encryption key, said key-dependent recovery information being generated by generating a key-specific recovery value from said non-key-specific recovery information and key-specific recovery information and a generating said key-dependent recovery information from said key-specific recovery value and said encryption key, said trustee regenerating said key-specific recovery value from said non-key-specific recovery information and said key-specific recovery information.

55. The method of claim 54 in which said trustee presents said key-specific recovery value to a party seeking recovery of said encryption key while not revealing said non-key-specific recovery information.

56. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps of claim 44.

57. In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channel, said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said a trustee, said trustee holding a secret value from which a corresponding public value is generated, apparatus associated with said sender for making said recovery information available to said trustee, comprising:

means for generating a first shared public value from said first shared secret value;

means for generating an additional shared secret value from said first shared secret value and the public value generated from the secret value held by said trustee,

means for encrypting said recovery information using said additional shared secret value generated for said trustee; and

means for transmitting said encrypted recovery information to said receiver via said communications channel, said trustee being able to decrypt said recovery information by regenerating said additional shared secret value from said first shared public value and the secret value held by said trustee.

58. In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channel, said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said trustee and a first shared public value generated from said first shared secret value, said trustee holding a secret value from which a corresponding public value is generated, said transmitted recovery information being encrypted using an additional shared secret value generated from said first shared secret value and the public value generated from the secret value held by said trustee, apparatus within said receiver for regenerating said recovery information for said receiver, comprising:

means for receiving said encrypted recovery information;

means for generating said additional shared secret value from said first shared secret value and said public value generated from said secret value held by said trustee; and

means for decrypting said encrypted recovery information using said additional shared secret value.

59. In a system in which a sender encrypts data under an encryption key to generate encrypted data and transmits said encrypted data along with recovery information to a receiver via a communications channel, said system having a trustee for enabling the recovery of said encryption key using said recovery information, said sender and said receiver having a first shared secret value that is not shared with said trustee and a first shared public value generated from said first shared secret value, said trustee holding a secret value from which a corresponding public value is generated, said transmitted recovery information being encrypted using an additional shared secret value generated from said first shared secret value and the public value generated from the secret value held by said trustee, apparatus associated with said trustee for regenerating said recovery information for said trustee, comprising:

means for receiving said encrypted recovery information and said first shared public value;

means for regenerating said additional shared secret value from said first shared public value and said secret value held by said trustee; and

means for decrypting said encrypted recovery information using said regenerated additional shared secret value.