Publicly verifiable key recovery

• US 6,249,585 B1
• Filed: 04/08/1997
• Issued: 06/19/2001
• Est. Priority Date: 04/08/1998
• Status: Expired due to Term

• Current Assignee: McAfee, LLC
• Original Assignee: Network Associates, Inc.
• Inventors: McGrew, David A., Carman, David W.
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US09/056,682
• Time in Patent Office: 1,533 Days
• Field of Search: 380/30, 380/286
• 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

The present invention is a system and method for publicly verifying that a session key determined according to a Diffie-Hellman key exchange can be recovered from information associated with a communication encrypted with the session key. More particularly, the present invention provides recovery information and verification information with the encrypted communication. A recovery agent is able to recover the session key using the recovery information. A verifier, using the verification information, is able to verify that the session key can, in fact, be recovered from the recovery information. Neither the recovery information nor the verification information alone reveal any secret or private information. Furthermore, only the recovery agent is able to recover the session key, and he does so without revealing any other private information. Thus, the verification can be performed by any member of the public.

Claims

1. A method for publicly verifying that information accompanying a message encrypted with a key includes information for recovering the key by a recovery agent, the key being determined according to a Diffie-Hellman key exchange, the method comprising the steps of:

providing, by a first party to the message, recovery information determined from a public key associated with the recovery agent, a public key associated with a second party to the message, and a private key associated with said first party; and

providing, by said first party, public verification information that verifies that the key can be recovered from said recovery information without revealing private information.

2. The method of claim 1, further comprising the steps of:

determining, by said first party, the key based on said second party'"'"'s public key and said first party'"'"'s private key.

3. The method of claim 1, further comprising the steps of:

determining, by said first party, the key according to the following relationship;

4. The method of claim 1, wherein said step of providing recovery information further comprises the step of:

determining said recovery information according to the following relationship;

5. The method of claim 1, wherein said step of providing verification information comprises the step of:

providing said verification information to said second party.

6. The method of claim 1, wherein said step of providing verification information comprises the step of:

providing said verification information to the recovery agent.

7. The method of claim 1, wherein said step of providing verification information comprises the step of:

providing said verification information to a verifier.

8. The method of claim 1, wherein said step of providing verification information comprises the step of:

providing said verification information in a data verification field associated with the message.

20. The method of claim 1, wherein said step of providing verification information comprises the step of:

interactively providing verification information that verifies that the key can be recovered from said recovery information without revealing private information.

21. The method of claim 20, wherein said step of interactively providing verification information comprises the step of:

performing a challenge-response digital signature protocol.

22. The method of claim 20, wherein said step of interactively providing verification information comprises the steps of:

performing a first challenge-response digital signature protocol; and

performing a second challenge-response digital signature protocol.

23. The method of claim 20, wherein said step of interactively providing verification information comprises the steps of:

performing a first challenge-response El Gamal digital signature protocol; and

performing a second challenge-response El Gamal digital signature protocol.

24. The method of claim 23, wherein said step of performing a first challenge-response comprises the steps of:

receiving a challenge;

determining a response based on said challenge and said recovery information; and

sending said response as at least a portion of said verification information.

25. The method of claim 24, wherein said step of receiving a challenge comprises the step of:

receiving a random integer from a challenger.

26. The method of claim 24, wherein said step of determining a response comprises the step of:

determining said response based on said recovery information, said second party'"'"'s public key, the recovery agent'"'"'s public key, and said challenge.

27. The method of claim 24, wherein said step of determining a response comprises the step of:

determining said response according to the following relationship;

28. The method of claim 23, wherein said step of performing a second challenge-response comprises the steps of:

receiving a challenge;

determining a response based on said challenge and said recovery information; and

sending said response as at least a portion of said verification information.

29. The method of claim 28, wherein said step of receiving a challenge comprises the step of:

receiving a random integer from a challenger.

30. The method of claim 28, wherein said step of determining a response comprises the step of:

determining said response based on said recovery information, said second party'"'"'s public key, the recovery agent'"'"'s public key, and said challenge.

31. The method of claim 28, wherein said step of determining a response comprises the step of:

determining said response according to the following relationship;

$a_2={\left(\frac{y_2}{y_r<br><br>g}\right)}^{k_2}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>p$

32. The method of claim 20, wherein said step of interactively providing verification information comprises the steps of:

performing a first challenge-response El Gamal digital signature protocol, said first challenge-response including the steps of;

receiving a first challenge;

determining a first response according to the following relationship;

35. The method of claim 1, wherein said step of providing verification information comprises the step of:

non-interactively providing verification information that verifies that the key can be recovered from said recovery information without revealing private information.

36. The method of claim 35, wherein said step of non-interactively providing verification information comprises the step of:

performing anon-interactive challenge-response digital signature protocol.

37. The method of claim 35, wherein said step of non-interactively providing verification information comprises the steps of:

performing a first non-interactive challenge-response digital signature protocol; and

performing a second non-interactive challenge-response digital signature protocol.

38. The method of claim 35, wherein said step of non-interactively providing verification information comprises the steps of:

performing a first non-interactive challenge-response El Gamal digital signature protocol; and

performing a second non-interactive challenge-response El Gamal digital signature protocol.

39. The method of claim 38, wherein said step of performing a first non-interactive challenge-response comprises the steps of:

determining a challenge;

generating a hash of said challenge;

determining a response based on said challenge and said recovery information; and

providing said challenge, said hash, and said response as at least a portion of said verification information.

40. The method of claim 39, wherein said step of determining a challenge comprises the step of:

generating a random integer.

41. The method of claim 39, wherein said step of determining a response comprises the step of:

determining said response based on said recovery information, said second party'"'"'s public key, the recovery agent'"'"'s public key, and said challenge.

42. The method of claim 39, wherein said step of determining a response comprises the step of:

determining said response according to the following relationship;

43. The method of claim 38, wherein said step of performing a second non-interactive challenge-response comprises the steps of:

determining a challenge;

generating a hash of said challenge;

determining a response based on said challenge and said recovery information; and

providing said challenge, said hash, and response as at least a portion of said verification information.

44. The method of claim 43, wherein said step of determining a challenge comprises the step of:

generating a random integer.

45. The method of claim 43, wherein said step of determining a response comprises the step of:

determining said response based on said recovery information, said second party'"'"'s public key, the recovery agent'"'"'s public key, and said challenge.

46. The method of claim 43, wherein said step of determining a response comprises the step of:

determining said response according to the following relationship;

$a_2={\left(\frac{y_2}{y_r<br><br>g}\right)}^{k_2}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{mod}<br><br>\text{\hspace{1em}<br><br>}<br><br>p$

47. The method of claim 35, wherein said step of non-interactively providing verification information comprises the steps of:

performing a first non-interactive challenge-response El Gamal digital signature protocol, said first challenge-response including the steps of;

determining a first challenge,

generating a first hash of said first challenge,

determining a first response according to the following relationship;

9. A method for publicly verifying that information accompanying a message encrypted with a key includes information for recovering the key by a recovery agent, the key being determined according to a Diffie-Hellman key exchange, the method comprising the steps of:

receiving recovery information determined from a public key associated with the recovery agent, a public key associated with a second party to the message, and a private key associated with a first party; and

receiving public verification information that verifies that the key can be recovered from said recovery information without revealing private information.

10. The method of claim 9, wherein said step of receiving verification information comprises the step of:

interactively receiving verification information that verifies that the key can be recovered from said recovery information without revealing private information.

11. The method of claim 10, wherein said step of interactively receiving verification information comprises the steps of:

performing a first challenge-response El Gamal digital signature protocol, said first challenge-response including the steps of;

sending a first challenge; and

receiving a first response according to the following relationship;

12. The method of claim 9, wherein said step of receiving verification information comprises the step of:

non-interactively receiving verification information that verifies that the key can be recovered from said recovery information without revealing private information.

13. The method of claim 12, wherein said step of non-interactively receiving verification information comprises the steps of:

receiving a first challenge,

receiving a first hash generated from said first challenge,

receiving a first response determined according to a non-interactive challenge-response El Gamal signature protocol as;

14. The method of claim 9, further comprising the step of:

verifying, using said verification information, that the key can be recovered by the recovery agent from the recovery information.

15. The method of claim 14, wherein said step of verifying comprises the step of:

verifying, using said verification information, that the key can be recovered by the recovery agent from the recovery information, said step of verifying performed by said second party.

16. The method of claim 14, wherein said step of verifying comprises the step of:

verifying, using said verification information, that the key can be recovered by the recovery agent from the recovery information, said step of verifying performed by the recovery agent.

17. The method of claim 14, wherein said step of verifying comprises the step of:

verifying, using said verification information, that the key can be recovered by the recovery agent from the recovery information, said step of verifying performed by a verifier.

18. The method of claim 14, wherein said step of verifying comprises the steps of:

accessing a data verification field associated with the message to obtain said verification information; and

verifying, using said verification information, that the key can be recovered by the recovery agent from the recovery information.

19. The method of claim 14, wherein said step of verifying comprises the steps of:

accessing a data recovery field associated with the message to obtain said recovery information and said verification information; and

verifying, using said recovery information and said verification information, that the key can be recovered by the recovery agent from the recovery information.

33. The method of claim 11, further comprising the step of:

verifying, using said verification information, that the key can be recovered by the recovery agent from the recovery information.

34. The method of claim 33, wherein said step of verifying comprises the steps of:

determining a verification result according to the following verification relationship;

48. The method of claim 13, further comprising the step of:

verifying, using said verification information, that the key can be recovered by the recovery agent from the recovery information.

49. The method of claim 13, wherein said step of verifying comprises the steps of:

verifying that said first hash was generated from said first challenge;

verifying that said second hash was generated from said second challenge;

determining a verification result according to the following verification relationship;

50. A method for publicly verifying that information accompanying a message encrypted by a key determined in accordance with a Diffie-Hellman key exchange includes information for recovering the key, the method comprising:

receiving recovery information determined from a public key associated with the recovery agent, a public key associated with a second party to the message, and a private key associated with a first party; and

receiving public verification information that verifies said recovery information without revealing private information.

51. The method of claim 50, wherein said step of receiving verification information comprises the step of:

interactively receiving verification information that verifies said recovery information without revealing private information.

52. The method of claim 50, wherein said step of receiving verification information comprises the step of:

non-interactively receiving verification information that verifies said recovery information without revealing private information.

53. A method for publicly verifying that information accompanying a message encrypted by a key determined in accordance with a Diffie-Hellman key exchange includes information for recovering the key, the method comprising:

providing recovery information determined from a public key associated with the recovery agent, a public key associated with a second party to the message, and a private key associated with a first party; and

providing public verification information that verifies said recovery information without revealing private information.

54. The method of claim 53, wherein said step of providing verification information comprises the step of:

interactively providing verification information that verifies said recovery information without revealing private information.

55. The method of claim 53, wherein said step of providing verification information comprises the step of:

non-interactively providing verification information that verifies said recovery information without revealing private information.