Method and apparatus for reconstituting an encryption key based on multiple user responses

• US 6,662,299 B1
• Filed: 10/28/1999
• Issued: 12/09/2003
• Est. Priority Date: 10/28/1999
• Status: Expired due to Term

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: PGP Corporation (Gen Digital Inc.)
• Inventors: Price, William F. III
• Primary Examiner(s): Peeso, Thomas R.
• Application Number:
  US09/429,217
• Time in Patent Office: 1,503 Days
• Field of Search: 713/171, 713/200, 713/201
• US Class Current: 713/171
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 21/6209 to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: G06F 2221/2131 Lost password, e.g. recovery of lost or forgotten passwords

Abstract

One embodiment of the present invention provides a system that facilitates encrypting and decrypting a data item. The system operates by encrypting a data item with a session key using a symmetric encryption mechanism to produce an encrypted data item. Next, the system splits the session key into a plurality of shares so that the session key can be reconstituted from a predefined number of shares. The system also receives a plurality of responses from the user (which may be responses to questions), and encrypts the plurality of shares with the plurality of responses using the symmetric encryption mechanism to generate a plurality of encrypted shares. The plurality of encrypted shares are stored for later retrieval. In one embodiment of the present invention, the system decrypts the data item by, receiving a plurality of new responses from the user, and attempting to decrypt the plurality of encrypted shares with the plurality of new responses. Note that a share will be successfully decrypted if a new response matches a response that was previously used to encrypt the share. If the predefined number of shares are successfully decrypted, the system uses the successfully decrypted shares to reconstitute the session key, and then uses the session key to decrypt the encrypted data item.

Claims

1. A method that facilitates encrypting and decrypting a data item, comprising:

receiving a session key;

encrypting the data item with the session key using a symmetric encryption mechanism to generate an encrypted data item, the symmetric encryption mechanism allowing the encrypted data item to be decrypted using the session key;

splitting the session key into a plurality of shares so that the session key can be reconstituted from a predefined number of shares from the plurality of shares;

receiving a plurality of responses from the user;

encrypting the plurality of shares with the plurality of responses using the symmetric encryption mechanism to generate a plurality of encrypted shares, the symmetric encryption mechanism allowing the plurality of encrypted shares to be decrypted using the plurality of responses;

erasing the session key; and

storing the plurality of encrypted shares for later retrieval.

2. The method of claim 1, further comprising encrypting the session key with a password belonging to a user using the symmetric encryption mechanism to produce an encrypted session key.

3. The method of claim 2, further comprising decrypting the encrypted data item using the password by,

decrypting the encrypted session key with the password to restore the session key; and

decrypting the encrypted data item with the session key to restore the data item.

4. The method of claim 1, further comprising decrypting the encrypted data item by,

receiving a plurality of new responses from the user;

attempting to decrypt the plurality of encrypted shares with the plurality of new responses, wherein a share will be successfully decrypted if a new response matches a response that was used to encrypt the share;

if the predefined number of shares are successfully decrypted, using the predefined number of shares to reconstitute the session key; and

decrypting the encrypted data item with the session key to restore the data item.

5. The method of claim 4, further comprising determining if a share from the plurality of shares can be decrypted by encrypting a marker with the share and then looking for the marker in the share after the share is decrypted.

6. The method of claim 1, wherein the data item includes a private key that is associated with a public key to form a public key-private key pair.

7. The method of claim 1, wherein the password includes a passphrase made up of at least one word.

8. The method of claim 1, wherein the plurality of responses are answers to questions supplied by the user.

9. The method of claim 1, wherein the plurality of responses are different passwords.

10. The method of claim 1, wherein the plurality of responses are answers to default questions.

11. The method of claim 1, wherein there are five shares in the plurality of shares, and wherein three out of five shares can be used to reconstitute the session key.

12. The method of claim 1, wherein receiving the session key further comprises generating the session key using a random number generator.

13. A computer readable storage medium storing instructions that when executed by a computer cause the computer to perform a method that facilitates encrypting and decrypting a data item, comprising:

receiving a session key;

encrypting the data item with the session key using a symmetric encryption mechanism to generate an encrypted data item, the symmetric encryption mechanism allowing the encrypted data item to be decrypted using the session key;

splitting the session key into a plurality of shares so that the session key can be reconstituted from a predefined number of shares from the plurality of shares;

receiving a plurality of responses from the user;

encrypting the plurality of shares with the plurality of responses using the symmetric encryption mechanism to generate a plurality of encrypted shares, the symmetric encryption mechanism allowing the plurality of encrypted shares to be decrypted using the plurality of responses;

erasing the session key; and

storing the plurality of encrypted shares for later retrieval.

14. The computer readable storage medium storing instructions of claim 13, wherein the instructions additionally cause the computer to decrypt the encrypted data item by,

receiving a plurality of new responses from the user;

attempting to decrypt the plurality of encrypted shares with the plurality of new responses, wherein a share will be successfully decrypted if a new response matches a response that was used to encrypt the share;

if the predefined number of shares are successfully decrypted, using the predefined number of shares to reconstitute the session key; and

decrypting the encrypted data item with the session key to restore the data item.

15. An apparatus that facilitates encrypting and decrypting a data item, comprising:

a receiving mechanism that receives a session key;

a symmetric encryption mechanism that is configured to encrypt the data item with the session key to generate an encrypted data item, the symmetric encryption mechanism allowing the encrypted data item to be decrypted using the session key;

a splitting mechanism that is configured to split the session key into a plurality of shares so that the session key can be reconstituted from a predefined number of shares from the plurality of shares;

a receiving mechanism that is configured to receive a plurality of responses from the user;

wherein the symmetric encryption mechanism is configured to encrypt the plurality of shares with the plurality of responses using the symmetric encryption mechanism to generate a plurality of encrypted shares, the symmetric encryption mechanism allowing the plurality of encrypted shares to be decrypted using the plurality of responses; and

a storage mechanism that stores the plurality of encrypted shares for later retrieval.

16. The apparatus of claim 15, further comprising a decryption mechanism that decrypts the encrypted data item, the decryption mechanism being configured to,

receive a plurality of new responses from the user;

decrypt the plurality of encrypted shares with the plurality of new responses, wherein a share will be successfully decrypted if a new response matches a response that was used to encrypt the share;

use the predefined number of shares to reconstitute the session key if the predefined number of shares are successfully decrypted; and

decrypt the encrypted data item with the session key to restore the data item.

17. The apparatus of claim 15, wherein the data item includes a private key that is associated with a public key to form a public key-private key pair.

18. The apparatus of claim 15, wherein the plurality of responses are answers to questions.

19. The apparatus of claim 15, wherein the plurality of responses are different passwords.

20. A method that facilitates decrypting a private key that has been encrypted using a password if the password becomes unavailable, the private key belonging to a user and being associated with a public key to form a public key-private key pair, the method comprising:

generating a session key;

encrypting the private key with the session key using a symmetric encryption mechanism to generate an encrypted private key, the symmetric encryption mechanism allowing the encrypted private key to be decrypted using the session key;

encrypting the session key with the password belonging to a user using the symmetric encryption mechanism to produce an encrypted session key;

splitting the session key into a plurality of shares so that the session key can be reconstituted from a predefined number of shares from the plurality of shares;

receiving a plurality of responses from the user;

hashing each of the plurality of responses with a first value to produce a first plurality of hashed responses;

encrypting the plurality of shares with the first plurality of hashed responses using the symmetric encryption mechanism to generate a plurality of encrypted shares;

hashing each of the plurality of responses with a second value to produce a second plurality of hashed responses;

encrypting the plurality of encrypted shares with the second plurality of hashed responses using the symmetric encryption mechanism to generate a plurality of final encrypted shares; and

sending the plurality of final encrypted shares to a server so that the server can store the plurality of final encrypted shares.

21. The method of claim 20, further comprising decrypting the private key using the password by,

decrypting the encrypted session key with the password to restore the session key; and

decrypting the encrypted private key with the session key to restore the private key.

22. The method of claim 20, further comprising decrypting the encrypted private key when the password is unavailable by,

receiving a plurality of new responses from the user;

hashing each of the plurality of new responses with the first value to produce a first plurality of hashed new responses;

hashing each of the plurality of new responses with the second value to produce a second plurality of hashed new responses;

sending the second plurality of hashed new responses from a computer belonging to the user to the server;

attempting to decrypt the plurality of final encrypted shares with the second plurality of hashed new responses at the server;

wherein successfully decrypting a share from the plurality of final encrypted shares results in a corresponding share from the plurality of encrypted shares;

if the predefined number of shares are successfully decrypted, sending the successfully decrypted shares from the server to the computer belonging to the user;

at the computer belonging to the user, decrypting the successfully decrypted shares with the first plurality of hashed new responses to produce at least the predefined number of shares of the session key;

using the predefined number of shares to reconstitute the session key; and

decrypting the encrypted private key with the session key to restore the private key.

23. The method of claim 20, further comprising determining if a share from the plurality of final encrypted shares can be decrypted by encrypting a marker with the share and then looking for the marker after the share is decrypted.

24. The method of claim 20, wherein the plurality of responses are answers to questions.

25. The method of claim 20, wherein the plurality of responses are different passwords.

26. The method of claim 20, wherein there are five shares in the plurality of shares, and wherein three out of five shares can be used to reconstitute the session key.