Secure electronic messaging system requiring key retrieval for deriving decryption keys

• US 20030147536A1
• Filed: 02/05/2002
• Published: 08/07/2003
• Est. Priority Date: 02/05/2002
• Status: Active Grant

• Current Assignee: Surety, LLC
• Original Assignee: Surety, LLC
• Inventors: Carnell, Shawn Michael Edwards, Andivahis, Dimitrios Emmanouil, Fischer, Addison McElroy, Wettlaufer, Albert John
• Granted Patent: US 7,146,009 B2
• Time in Patent Office: Days
• US Class Current: 380/277
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 63/06 for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/0823 using certificates cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263
• CPC Class Codes: H04L 9/083 involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP]

Abstract

A secure electronic messaging system permits communication between registered users, with the assistance of a key server. The system requires a recipient to submit key retrieval information to a key server, and obtain decryption key information. The decryption key information is necessary for the recipient to form the decryption key which is used to read a message encrypted by the sender. The decryption key information may be an encrypted version of a decryption key, or portions thereof, or may be portions of an unencrypted version of a decryption key, among others. Typically, the key retrieval information may either be sent to the recipient by the sender, or may be generated by the recipient, based on information sent by the sender.

Claims

1. A method for secure communication of a message M between a sender and a recipient, with the assistance of a key server, the method comprising the steps of:

the sender encrypting the message M with a symmetric key Ks to form an encrypted message;

the sender encrypting first information derived from the symmetric key Ks, using a public encryption key Ke of the recipient;

the key server storing decryption key information needed by the recipient to form a decryption key suitable for decrypting the encrypted message;

the sender receiving key retrieval information Kr which indexes the decryption key information;

the sender sending to the recipient, at least the encrypted message and the key retrieval information Kr;

the recipient sending the key retrieval information Kr to the key server and receiving the decryption key information in response thereto;

the recipient forming the symmetric key Ks from at least the decryption key information and a private decryption key Kd of the recipient; and

the recipient decrypting the encrypted message with the symmetric key Ks;

without the message or the encrypted message being sent to the key server.

2. The method according to claim 1, wherein:

the first information is the symmetric key Ks;

the sender encrypts the symmetric key Ks with the recipient'"'"'s public encryption key Ke to thereby form an encrypted symmetric key Kse; and

the recipient decrypts the encrypted symmetric key Kse with the recipient'"'"'s private decryption key Kd, to thereby form the symmetric key Ks, prior to decrypting the encrypted message.

3. The method according to claim 2, wherein:

the sender splits the encrypted symmetric key Kse into first and second split-key fragments Kse1 and Kse2, respectively;

the sender sends the second split key fragment Kse2 to the key server;

the key server stores the second split-key fragment Kse2 as the decryption key information;

the sender sends the first split-key fragment Kse1 to the recipient, in addition to the encrypted message and the key retrieval information Kr;

the recipient receives the second split-key fragment Kse2 in response to sending the key retrieval information Kr to the key server; and

the recipient forms the encrypted symmetric key Kse from the first and second split-key fragments, Kse1 and Kse2, respectively.

4. The method according to claim 2, wherein:

the sender sends the encrypted symmetric key Kse to the key server;

the key server stores the encrypted symmetric key Kse as the decryption key information; and

the recipient receives the encrypted symmetric key Kse in response to sending the key retrieval information Kr to the key server.

5. The method according to claim 2, wherein the key server generates the key retrieval information Kr and the sender generates the symmetric key Ks.

6. The method according to claim 1, wherein:

the key server splits the symmetric key Ks into first and second split-key fragments Ks1 and Ks2, respectively, and stores the second split-key fragment Ks2 as the decryption key information;

the sender obtains the first and second split-key fragments Ks1 and Ks2, respectively,

the first split-key fragment Ks1 is the first information and is encrypted by the sender using the recipient'"'"'s public encryption key Ke, to form an encrypted first split-key fragment Kse1;

the sender sends to the recipient, the encrypted first split-key fragment Kse1, along with the encrypted message and the retrieval information Kr;

the recipient decrypts the encrypted first split-key fragment Kse1 with the recipient'"'"'s private decryption key Kd, to thereby form the first split-key fragment Ks1;

the recipient receives the second split-key fragment Ks2 in response to sending the key retrieval information Kr to the key server; and

the recipient forms symmetric key Ks from the first and second split-key fragment Ks1 and Ks2, respectively, prior to decrypting the encrypted message.

7. The method according to claim 6, wherein:

the key server sends to the sender, the first and second split-key fragments Ks1 and Ks2, respectively, so that the sender obtains Ks1 and Ks2; and

the sender combines Ks1 and Ks2 received from the key server, to form symmetric key Ks, prior to the sender encrypting message M.

8. The method according to claim 6, wherein:

the key server sends the symmetric key Ks to the sender, prior to the sender encrypting message M; and

the sender splits the symmetric key Ks into said first and second split-key fragments Ks1 and Ks2, respectively.

9. The method according to claim 6, wherein the key server generates the key retrieval information Kr and also generates the symmetric key Ks.

42. The method according to any one of claims 1, 10, 14 or 18, further comprising, by the sender, establishing at least one policy governing the retrieval of decryption key information.

43. The method according to any one of claims 1, 10, 14, 18 or 25, further comprising, by the key server, establishing at least one policy governing the retrieval of decryption key information.

44. The method according to any one of claims 1, 10, 14, or 18 further comprising:

updating a first audit log at the key server to reflect at least one of storing the decryption key information and sending the decryption key information to the recipient; and

updating a second audit log at the sender to reflect transmission of a message from the sender to the recipient.

45. The method according to claim 44, further comprising:

verifying a correspondence between entries in the first audit log that correspond to messages sent by the sender, with entries in the second audit log.

46. The method according to any one of claims 1, 10, 14, or 18 further comprising:

the sender requesting that the recipient attest to the sender'"'"'s identity.

10. A method for secure communication of a message M between a sender and a recipient, with the assistance of a key server, the method comprising the steps of:

the sender obtaining a symmetric key Ks and encrypting the message M with said symmetric key Ks to thereby form an encrypted message Me;

the sender encrypting first information comprising the symmetric key Ks with a public encryption key Ke associated with the recipient to thereby form an encrypted symmetric key Kse;

the sender forming first and second split-key fragments Kse1 and Kse2, respectively, from said encrypted symmetric key Kse;

the sender sending the second split-key fragment Kse2 to the key server;

the key server storing decryption key information needed by the recipient to form a decryption key suitable for decrypting the encrypted message, the decryption key information being formed from the second split-key fragment Kse2;

the key server transmitting to the sender, key retrieval information Kr that indexes the decryption key information;

the sender transmitting to the recipient, the encrypted message Me, the first split-key fragment Kse1 and the key retrieval information Kr;

the recipient transmitting the key retrieval information Kr to the key server and receiving said decryption key information in response thereto;

the recipient forming the encrypted symmetric key Kse from the first split-key fragment Kse1 and Kse2, Kse2 being derived from the decryption key information;

the recipient decrypting the encrypted symmetric key Kse with a private decryption key Kd of the recipient to thereby form the symmetric key Ks; and

the recipient decrypting the encrypted message Me with the symmetric key Ks to read the original message M.

11. The method according to claim 10, comprising the additional step of adding at least one of signing data and timestamp data to the message M, before encrypting the message with said symmetric key Ks.

12. The method according to claim 10, wherein the decryption key information comprises the second split-key fragment Kse2.

13. The method according to claim 10, wherein the sender generates the symmetric key Ks.

14. A method for secure communication of a message M between a sender and a recipient, with the assistance of a key server, the method comprising the steps of:

the sender obtaining a symmetric key Ks and encrypting the message M with said symmetric key Ks to thereby form an encrypted message Me;

the sender encrypting first information comprising the symmetric key Ks with a public encryption key Ke associated with the recipient to thereby form an encrypted symmetric key Kse;

the sender sending the encrypted symmetric key Kse to the key server;

the key server storing decryption key information needed by the recipient to form a decryption key suitable for decrypting the encrypted message, the decryption key information being formed from the encrypted symmetric key Kse;

the key server transmitting to the sender, key retrieval information Kr that indexes the decryption key information;

the sender transmitting to the recipient, the encrypted message and the key retrieval information Kr;

the recipient transmitting the key retrieval information to the key server and receiving said decryption key information in response thereto;

the recipient deriving the encrypted symmetric key Kse from said decryption key information;

the recipient decrypting the encrypted symmetric key Kse with a private decryption key Kd of the recipient to thereby form the symmetric key Ks; and

the recipient decrypting the encrypted message Me with the symmetric key Ks to read the original message M.

15. The method according to claim 14, comprising the additional step of adding at least one of signing data and timestamp data to the message M, before encrypting the message with said symmetric key Ks.

16. The method according to claim 14, wherein the decryption key information comprises the encrypted symmetric key Kse.

17. The method according to claim 14, wherein the key server generates the symmetric key Ks.

18. A method for secure communication of a message M between a sender and a recipient, with the assistance of a key server, the method comprising the steps of:

the key server obtaining first and second split-key fragments Ks1 and Ks2, respectively, corresponding to a symmetric key Ks;

the key server storing decryption key information needed by the recipient to form a decryption key suitable for decrypting the encrypted message, the decryption key information being formed from the second split-key fragment Ks2;

the key server transmitting to the sender, a public encryption key Ke associated with the recipient, symmetric key information sufficient to form Ks, and key retrieval information Kr that indexes the decryption key information;

the sender encrypting the message M with Ks to thereby form an encrypted message Me, the sender also encrypting first information comprising the first split-key fragment Ks1 with the recipient'"'"'s public encryption key Ke to form an encrypted first split-key fragment Kse1;

the sender transmitting to the recipient, the encrypted message Me, the key retrieval information Kr, and the encrypted first split-key fragment Kse1;

the recipient transmitting the key retrieval information Kr to the key server and receiving said decryption key information in response thereto;

the recipient decrypting the encrypted first split-key fragment Kse1 with a private decryption key Kd of the recipient to thereby form the first split-key fragment Ks1;

the recipient forming Ks from the first and second split-key fragments Ks1 and Ks2, respective, Ks2 being derived from the decryption key information; and

the recipient decrypting the encrypted message Me with the symmetric key Ks to read the original message M.

19. The method according to claim 18, comprising the additional step of adding at least one of signing data and timestamp data to the message M, before encrypting the message with Ks.

20. The method according to claim 18, wherein the decryption key information comprises the second split-key fragment Ks2.

21. The method according to claim 18, wherein:

the decryption key information comprises an encrypted second split-key fragment Kse2 formed by encrypting the second split-key fragment Ks2 with the recipient'"'"'s public encryption key Ke; and

the recipient forms Ks2 by decrypting Kse2 with the recipient'"'"'s private decryption key Kd.

22. The method according to claim 18, wherein the symmetric key information comprises the symmetric key Ks, and wherein the sender forms the first split-key fragment Ks1 from the symmetric key Ks received from the key server.

23. The method according to claim 18, wherein the symmetric key information comprises the first and second split-key fragments Ks1 and Ks2, respectively.

24. The method according to claim 18, wherein:

the symmetric key information comprises the first and second split-key fragments Ks1 and Ks2, respectively; and

.

the decryption key information comprises the second split-key fragment Ks2.

25. A method of operating a key server in a secure communication system to facilitate secure transmission of a message M between a first entity and a second entity, the method comprising the steps of:

during a first sequence of exchanges;

receiving from a first entity, a request to provide a public encryption key Ke corresponding to a second entity specified by the first entity;

transmitting to the first entity, said public encryption key Ke;

storing decryption key information needed by the second entity to form a decryption key suitable for decrypting an encrypted version of message M;

transmitting to the first entity, key retrieval information Kr which indexes said decryption key information; and

during a second sequence of exchanges;

receiving from the second entity, the key retrieval information Kr; and

transmitting to the second entity, said decryption key information, without ever receiving the message or the encrypted version of the message.

26. The method according to claim 25, comprising the step of receiving from the first entity, the decryption key information, prior to the step of storing the decryption key information.

27. The method according to claim 26, wherein the decryption key information comprises a split-key fragment of a symmetric key encrypted by said public encryption key Ke.

28. The method according to claim 26, wherein the decryption key information comprises a symmetric key encrypted by said public encryption key Ke.

29. The method according to claim 25, further comprising during the first sequence of exchanges, the steps of:

providing first and second split-key fragments Ks1 and Ks2, respectively, associated with a symmetric key Ks; and

transmitting to the first entity, said first and second split-key fragments Ks1 and Ks2 in addition to the public encryption key Ke and the key retrieval information Kr.

30. The method according to claim 29, wherein the decryption key information comprises the second split-key fragment Ks2.

31. The method according to claim 25, further comprising during the first sequence of exchanges, the steps of:

the key server checking whether the second entity is a registered user of the secure communication system, and

if the second entity is not a registered user;

the key server generating an encryption key and a decryption key for the second entity, and

the key server sending the encryption key to the first entity, along with a notification that the second entity is not a registered user.

32. The method according to claim 31, further comprising during the second sequence of exchanges, the step of:

if the second entity is not a registered user,

inviting the second entity to register; and

sending the decryption key to the second entity.

33. A key server computer in a secure communication system configured to facilitate secure transmission of a message M between a sender and a recipient, the key server computer being programmed to:

during a first sequence of exchanges;

receive from a first entity, a request to provide a public encryption key Ke corresponding to a second entity specified by the first entity;

transmit to the first entity, said public encryption key Ke;

store decryption key information needed by the second entity to form a decryption key suitable for decrypting an encrypted version of message M;

transmit to the first entity, key retrieval information Kr which indexes said decryption key information; and

during a second sequence of exchanges;

receive from the second entity, the key retrieval information Kr; and

transmit to the second entity, said decryption key information, without having to receive the message or the encrypted version of the message.

34. A computer-readable memory having executable code stored thereon, the code including:

a first set of code comprising;

code to receive from a first entity, a request to provide a public encryption key Ke corresponding to a second entity specified by the first entity;

code to transmit to the first entity, said public encryption key Ke;

code to store decryption key information needed by the second entity to form a decryption key suitable for decrypting an encrypted version of a message M;

code to transmit to the first entity, key retrieval information Kr which indexes said decryption key information; and

a second set of code comprising;

code to receive from the second entity, the key retrieval information Kr; and

code to transmit to the second entity, said decryption key information.

35. A method for secure communication of a message M between a sender and a recipient, with the assistance of a key server, the method comprising the steps of:

the sender encrypting the message M with a message encryption key Kme to form an encrypted message;

the sender encrypting first information derived from a message decryption key Kmd corresponding to the message encryption key Kme, using a public encryption key Ke of the recipient;

the key server storing decryption key information needed by the recipient to form said message decryption key Kmd suitable for decrypting the encrypted message;

the sender receiving key retrieval information Kr which indexes the decryption key information;

the sender sending to the recipient, at least the encrypted message and the key retrieval information Kr;

the recipient sending the key retrieval information Kr to the key server and receiving the decryption key information in response thereto;

the recipient forming the message decryption key Kmd from at least the decryption key information and a private decryption key Kd of the recipient; and

the recipient decrypting the encrypted message with the message decryption key Kmd;

without the message or the encrypted message being sent to the key server.

36. The method according to claim 35, wherein the message encryption key Kme and the message decryption key Kmd form an asymmetric key pair.

37. The method according to claim 35, wherein the message encryption key Kme and the message decryption key Kmd are identical and are a symmetric key Ks.

38. A method for secure communication of a message M between a sender and a recipient, with the assistance of a key server, the method comprising the steps of:

the sender encrypting the message M with a message encryption key Kme to form an encrypted message;

the sender encrypting first information derived from a message decryption key Kmd corresponding to the message encryption key Kme, using a public encryption key Ke of the recipient;

the key server storing decryption key information needed by the recipient to form said message decryption key Kmd suitable for decrypting the encrypted message;

the sender sending to the recipient, at least the encrypted message;

the recipient sending key retrieval information Kr to the key server which indexes the decryption key information, and receiving the decryption key information in response thereto;

the recipient forming the message decryption key Kmd from at least the decryption key information and a private decryption key Kd of the recipient; and

the recipient decrypting the encrypted message with the message decryption key Kmd;

without the message or the encrypted message being sent to the key server.

39. The method according to claim 38, wherein the message encryption key Kme and the message decryption key Kmd form an asymmetric key pair.

40. The method according to claim 38, wherein the message encryption key Kme and the message decryption key Kmd are identical and are a symmetric key Ks.

41. The method according to claim 38, wherein the recipient creates the key retrieval information Kr based on information received from the sender.