Technique for split knowledge backup and recovery of a cryptographic key

• US 20080031460A1
• Filed: 02/21/2007
• Published: 02/07/2008
• Est. Priority Date: 05/26/1999
• Status: Active Grant

• Current Assignee: Quadient Technologies France
• Original Assignee: George Brookner, Lorenz Frey
• Inventors: Frey, Lorenz, Brookner, George
• Granted Patent: US 7,916,871 B2
• Time in Patent Office: Days
• US Class Current: 380/282
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

In a secure cryptographic environment, a private key in a private/public key cryptographic scheme needs to be backed up and recovered in case of a loss or corruption of the private key. To back up the private key, multiple key segments are generated based on the private key which are distributed to a corresponding number of trusted individuals, each of whom has knowledge of only his or her key segment. The key can be restored only when all of the trusted individuals provide the respective key segments, based on which the original private key is reconstructed. In addition, each trusted individual is uniquely identifiable by a personal identification number. Advantageously, the private key which is secret can be backed up and restored without any individual having knowledge of the full key.

Claims

1. A method for storing and retrieving a cryptographic private key, comprising:

calculating a one-way hash value of an initial cryptographic private key;

generating a plurality of key segments, at least a first of the plurality of key segments being a random number, and at least a second of the plurality of key segments being a combination of the random number and a portion of the initial cryptographic private key;

distributing each of the plurality of key segments to one of a plurality of trusted users; and

when the cryptographic private key is to be recovered;

receiving the plurality of key segments from the plurality of trusted users;

generating a recovered key from the plurality of key segments;

calculating a one-way hash value of the recovered key;

comparing the hash value of the recovered key to the hash value of the initial cryptographic private key; and

if the hash value of the recovered key is the same as the hash value of the initial cryptographic private key, using the recovered key as the private key in a cryptographic communication system.

2. The method of claim 1, wherein the second of the plurality of key segments is generated using a bitwise exclusive-OR operation performed between the portion of the initial cryptographic private key and the random number.

3. The method of claim 1, wherein distributing each of the plurality of key segments comprises transferring each of the plurality of key segments to one of the plurality of trusted users such that no trusted user receives more than one of the key segments.

4. The method of claim 1, wherein each of the plurality of trusted users has no knowledge of key segments received by the other trusted users.

5. The method of claim 1, wherein the cryptographic private key is an encoding key for a postal security device.

6. The method of claim 1, wherein the plurality of key segments are received from the plurality of trusted users in response to the initial cryptographic private key being lost or corrupted.

7. The method of claim 1, wherein at least a third of the plurality of key segments is a bit string comprising a second portion of the initial cryptographic private key.

8. The method of claim 7, wherein each of the plurality of key segments is the same length as the initial cryptographic private key.

9. A method for storing a cryptographic private key, comprising:

generating a plurality of key segments, at least a first of the plurality of key segments being a random number, and at least a second of the plurality of key segments being a combination of the random number and a portion of an initial cryptographic private key; and

distributing each of the plurality of key segments to one of a plurality of trusted users.

10. The method of claim 9, further comprising calculating a one-way hash value of the initial cryptographic private key.

11. The method of claim 9, wherein the second of the plurality of key segments is generated using a bitwise exclusive-OR operation performed between the portion of the initial cryptographic private key and the random number.

12. The method of claim 9, wherein each of the plurality of trusted users has no knowledge of key segments received by the other trusted users.

13. A method for retrieving a cryptographic private key, comprising:

receiving a plurality of key segments from a plurality of trusted users, at least a first of the plurality of key segments being a random number, and at least a second of the plurality of key segments being a combination of the random number and a portion of an initial cryptographic private key; and

generating a recovered key from the plurality of key segments.

14. The method of claim 13, further comprising:

calculating a one-way hash value of the recovered key;

comparing the hash value of the recovered key to a stored hash value of the initial cryptographic private key; and

if the hash value of the recovered key is not the same as the hash value of the initial cryptographic private key, discarding the recovered key.

15. The method of claim 13, wherein the second of the plurality of key segments is a bitwise exclusive-OR combination of the portion of the initial cryptographic private key and the random number.

16. The method of claim 13, wherein each of the plurality of trusted users has no knowledge of key segments received from the other trusted users.

17. The method of claim 13, wherein the plurality of key segments are received from the plurality of trusted users in response to the initial cryptographic private key being lost or corrupted.

18. The method of claim 13, wherein generating the recovered key comprises performing a bitwise exclusive-OR operation between the first of the plurality of key segments and the second of the plurality of key segments.