CERTIFY AND SPLIT SYSTEM AND METHOD FOR REPLACING CRYPTOGRAPHIC KEYS

• US 20070223706A1
• Filed: 12/11/2006
• Published: 09/27/2007
• Est. Priority Date: 12/12/2005
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Gantman, Alexander, Rose, Gregory
• Granted Patent: US 8,989,390 B2
• Time in Patent Office: Days
• US Class Current: 380/286
• CPC Class Codes: G06F 21/34 involving the use of external additional devices, e.g. dongles or smart cards
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/77 in smart cards
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04L 9/3268 using certificate validation, registration, distribution or revocation, e.g. certificate revocation list [CRL]

Abstract

A feature is provided that facilitates securely creating, and/or replacing cryptographic keys. A first key pair is created comprising first private key and first public key. A second (spare) key pair is created comprising second private key and second public key. The second key pair is associated with the first private key. The second key pair is divided into shares and distributed to at least two shareholders. When the first key pair is to be replace, the second key pair is recreated and authenticated with at least a portion of the distributed shares. A trust level is associated with the second key pair corresponding to a trust level of the first key pair. The first key pair may be invalidated upon authentication of the second key pair. Further configurations provide for the creation of additional spare key pairs.

Claims

1. A method operational on a token device for replacing asymmetric cryptographic keys, comprising:

obtaining a pseudorandom first key pair that comprises a first private key and a corresponding first public key;

obtaining a pseudorandom spare second key pair that comprises a second private key and a second public key,

signing the second public key with the first private key to obtain a signed certificate;

dividing the second key pair and signed certificate into n shares, where n is an integer; and

distributing the n shares to at least two shareholders for safekeeping.

2. The method of claim 1, further comprising:

retrieving at least a portion of the n shares from the at least two shareholders;

reconstructing the second key pair and signed certificate from at least a portion of the n shares retrieved; and

presenting the signed certificate to a verification device to replace the first public key with the second public key.

3. The method of claim 2, further comprising:

distributing the signed certificate to an authentication device to replace the first public key with the second public key and invalidate the first key pair upon authentication of the second key pair.

4. The method of claim 2, further comprising:

obtaining a third key pair when replacing the first key with the second key, the third key pair comprising a third public key and a third private key.

5. The method of claim 4, further comprising:

signing the third public key with the second private key to obtain a second signed certificate;

dividing the third key pair and second signed certificate into n shares, where n is an integer; and

distributing the n shares of the third key pair to at least two shareholders for safekeeping.

6. The method of claim 5, further comprising:

retrieving at least a portion of the n shares of the third key pair;

recreating the third key pair from the at least a portion of n shares retrieved; and

presenting the second signed certificate to a verification device to replace the second public key with the third public key.

7. The method of claim 1, further comprising:

associating a trust level of the first key pair with a trust level for the second key pair.

8. The method of claim 1, wherein dividing the second key pair and signed certificate into shares is determined by a secret sharing scheme.

9. The method of claim 1 further comprising:

creating a duplicate key pair of the first key pair;

associating a set of use rules with the duplicate key pair; and

distributing the duplicate key pair and use rules to a second token device.

10. The method of claim 1 further comprising:

invalidating the duplicate key pair according to use rules.

11. A token device that facilitates replacing cryptographic keys, comprising:

means for obtaining a pseudorandom first key pair that comprises a first private key and a corresponding first public key;

means for obtaining a pseudorandom spare second key pair that comprises a second private key and a second public key,

means for signing the second public key with the first private key to obtain a signed certificate;

means for dividing the second key pair and signed certificate into n shares, where n is an integer; and

means for distributing the n shares to at least two shareholders for safekeeping.

12. The device of claim 11, further comprising:

means for retrieving at least a portion of the n shares from the at least two shareholders;

means for reconstructing the second key pair and signed certificate from the at least a portion of the n shares retrieved; and

means for presenting the signed certificate to a verification device to replace the first public key with the second public key.

13. The device of claim 12, further comprising:

means for sending the second public key to a verification device that authenticates the second key pair and invalidates the first key pair upon authentication of the second key pair; and

means for associating a trust level with the second key pair that corresponds with a trust level associated with the first key pair.

14. The device of claim 12, further comprising:

means for distributing the signed certificate to an authentication device to replace the first public key with the second public key and invalidate the first key pair upon authentication of the second key pair.

15. A token device that facilitates replacing cryptographic keys, comprising:

a key assignment component configured to

obtain a pseudorandom first key pair that comprises a first private key and a corresponding first public key,

obtain a pseudorandom spare second key pair that comprises a second private key and a second public key,

sign the second public key with the first private key to obtain a signed certificate;

a distribution component coupled to the key assignment component, the distribution component configured to divide the second key pair and signed certificate into n shares, where n is an integer; and

a transmitter that distributes the n shares to at least two shareholders for safekeeping.

16. The device of claim 15, further comprising:

a key verification component including

a receiver that receives at least a portion of the n shares from the at least two shareholders;

an aggregation component that reconstructs the second key pair and signed certificate from the at least a portion of the n shares received; and

a transmitter that sends the signed certificate to a verification device to replace the first public key with the second public key.

17. The device of claim 16, wherein the key verification component is further configured to

authenticate the second key pair and invalidate the first key pair upon authentication of the second key pair.

18. The device of claim 17, wherein the key assignment component is further configured to

obtain a third key pair when replacing the first key with the second key, the third key pair comprising a third public key and a third private key.

19. The device of claim 16, wherein the key verification component is further configured to

distribute the signed certificate to an authentication device to replace the first public key with the second public key and invalidate the first key pair upon authentication of the second key pair.

20. The device of claim 15, wherein the key assignment component is further configured to

create a duplicate key pair of the first key pair;

associate a set of use rules with the duplicate key pair; and

distribute the duplicate key pair and use rules to a second token device.

21. The device of claim 15 wherein the key assignment component is further configured to

invalidate the duplicate key pair according to use rules.

22. A machine-readable medium having one or more instructions for replacing cryptographic keys, which when executed by a processor causes the processor to:

obtain a pseudorandom first key pair that comprises a first private key and a corresponding first public key;

obtain a pseudorandom spare second key pair that comprises a second private key and a second public key;

sign the second public key with the first private key to obtain a signed certificate;

divide the second key pair and signed certificate into n shares, where n is an integer; and

distribute the n shares to at least two shareholders for safekeeping.

23. The machine-readable medium of claim 22 having one or more instructions which when executed by a processor causes the processor to further:

retrieve at least a portion of the n shares from the at least two shareholders;

reconstruct the second key pair and signed certificate from the at least a portion of the n shares retrieved; and

present the signed certificate to a verification device to replace the first public key with the second public key; and

authenticate the second key pair and invalidate the first key pair upon authentication of the second key pair.

24. The machine-readable medium of claim 23 having one or more instructions which when executed by a processor causes the processor to further:

distribute the signed certificate to an authentication device to replace the first public key with the second public key and invalidate the first key pair upon authentication of the second key pair.

25. The machine-readable medium of claim 22 having one or more instructions which when executed by a processor causes the processor to further:

associate a trust level with the second key pair that corresponds with a trust level associated with the first key pair.

26. The machine-readable medium of claim 22 having one or more instructions which when executed by a processor causes the processor to further:

create a duplicate key pair of the first key pair;

associate a set of use rules with the duplicate key pair; and

distribute the duplicate key pair and use rules to a duplicate user device.

27. A method operational on an authentication device for replacing asymmetric cryptographic keys, comprising:

obtaining a first public key associated with a user, the first public key having an associated first private key;

receiving a digital certificate of a second public key digitally signed with the first private key;

authenticating the user by using the first public key to authenticate the digital certificate; and

replacing the first public key with the second public key to secure communications with the user if the digital certificate is successfully authenticated.

28. The method of claim 27 further comprising:

receiving one or more other intervening digital certificates that create an authentication chain between the first public key and the second public key; and

authenticating each intervening digital certificate to determine whether the first public key should be replaced by the second public key.

29. The method of claim 27 further comprising:

rejecting the second public key if the digital certificate authentication by the first public key fails.

30. An authentication device, comprising:

means for obtaining a first public key associated with a user, the first public key having an associated first private key;

means for receiving a digital certificate of a second public key digitally signed with the first private key;

means for authenticating the user by using the first public key to authenticate the digital certificate; and

means for replacing the first public key with the second public key to secure communications with the user if the digital certificate is successfully authenticated.

31. The device of claim 30 further comprising:

means for receiving one or more other intervening digital certificates that create an authentication chain between the first public key and the second public key; and

means for authenticating each intervening digital certificate to determine whether the first public key should be replaced by the second public key.

32. The device of claim 30 further comprising:

means for rejecting the second public key if the digital certificate authentication by the first public key fails.

33. An authentication device, comprising:

a communication module configured to

receive a first public key associated with a user, the first public key having an associated first private key, and

receive a digital certificate of a second public key digitally signed with the first private key; and

a processing circuit coupled to the communication module, the processing circuit configured to

authenticate the user by using the first public key to authenticate the digital certificate; and

replace the first public key with the second public key to secure communications with the user if the digital certificate is successfully authenticated.

34. The device of claim 33 wherein the communication module is further configured to

receive one or more other intervening digital certificates that create an authentication chain between the first public key and the second public key;

and

the processing circuit is further configured to

authenticate each intervening digital certificate to determine whether the first public key should be replaced by the second public key, and

reject the second public key if the digital certificate authentication by the first public key fails.

35. A machine-readable medium having one or more instructions for replacing cryptographic keys, which when executed by a processor causes the processor to:

obtain a first public key associated with a user, the first public key having an associated first private key;

receive a digital certificate of a second public key digitally signed with the first private key;

authenticate the user by using the first public key to authenticate the digital certificate; and

replace the first public key with the second public key to secure communications with the user if the digital certificate is successfully authenticated.

36. The machine-readable medium of claim 35 having one or more instructions which when executed by a processor causes the processor to further:

receive one or more other intervening digital certificates that create an authentication chain between the first public key and the second public key;

authenticate each intervening digital certificate to determine whether the first public key should be replaced by the second public key.