Recreating a cryptographic key in a replacement device

• US 8,259,947 B2
• Filed: 01/05/2004
• Issued: 09/04/2012
• Est. Priority Date: 01/07/2003
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Rose, Gregory Gordon, Gantman, Alexander, Noerenberg, John W. II
• Primary Examiner(s): ZECHER, CORDELIA P K
• Application Number:
  US10/752,420
• Publication Number:
  US 20040218763A1
• Time in Patent Office: 3,165 Days
• Field of Search: 380/277
• US Class Current: 380/277
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

Embodiments describe a method and/or system whereby a secret key in a cryptographic system may be replaced without revealing the secret key. One embodiment comprises creating a first private key and corresponding first public key. A second private key associated with the first private key and a second public key corresponding to the second private key are also created. The second private key is output once such that it can be re-created and the second public key is output when outputting the first public key. The first private key is used for authentication. The method further comprises re-creating the second private key; and using the second private key for authentication. Another embodiment comprises creating a private key and corresponding public key with associated system parameter; outputting the system parameter when outputting the public key; and using the private key for authentication. The method may further comprise creating a new private key using the previous key and the system parameter.

Claims

1. A method operational for authentication in a public cryptographic system comprising:

creating a first private key and corresponding first public key at a mobile user device;

creating a second private key associated with the first private key and creating a second public key corresponding to the second private key at the mobile user device;

outputting the second private key from the mobile user device such that it is not stored on the mobile user device while retaining the first private key in the mobile user device, wherein outputting the second private key comprises transmitting a plurality of shares of the second private key from the mobile user device to a plurality of different entities once, such that the second private key can be re-created and used when the first private key is inaccessible;

transmitting the first public key and the second public key to a verifier device; and

using the retained first private key for authentication of the mobile user device prior to using the second private key.

2. The method of claim 1, wherein transmitting the plurality of shares of the second private key comprises:

creating at least two shares of the second private key at the mobile user device; and

wireles sly outputting each share once to a different entity.

3. The method of claim 1, further comprising:

re-creating the second private key at one of the mobile user device or a replacement mobile user device using at least some shares of the plurality of shares; and

using the second private key independent of the first private key for authentication of the mobile user device or the replacement mobile user device.

4. The method of claim 3, further comprising:

creating a third private key associated with the second private key and creating a third public key corresponding to the third private key; and

outputting the third public key to the verifier device.

5. The method of claim 4, further comprising:

outputting the third private key once as a plurality of shares such that it can be re-created;

re-creating the third private key using at least some of the plurality of shares; and

using the third private key for authentication.

6. The method of claim 3, further comprising:

creating a third private key associated with the second private key and creating a third public key corresponding to the third private key;

creating a fourth private key associated with the third private key and creating a fourth public key corresponding to the fourth private key;

outputting the fourth private key once such that it can be re-created; and

outputting the third and fourth public keys.

7. The method of claim 6, further comprising:

disabling use of the second private key for authentication;

using the third private key for authentication;

re-creating the fourth private key; and

using the fourth private key for authentication.

8. The method of claim 1, wherein the second public and private keys are created independently from the first public and private keys.

9. The method of claim 1, further comprising:

preventing retransmission of the second private key.

10. The method of claim 1, wherein the second private key is removed from the mobile user device upon transmission of the plurality of shares of the second private key.

11. A method for verification in a public cryptographic system comprising:

receiving a first public key from a mobile user device, wherein the first public key has a corresponding first private key stored on the mobile user device;

receiving a second public key from the mobile user device, the second public key associated with the first public key, wherein the second public key has a corresponding second private key that is split into a plurality of shares that are sent to a plurality of different entities such that it is not stored on the mobile user device, where each share is sent only once and to a different entity, such that the second private key can be re-created and used when there is no access to a first private key corresponding to the first public key, wherein the first private key is disabled when the second private key is re-created and used for authentication;

using the first public key for authentication of the mobile user device; and

using the second public key for authentication if the first public key fails.

12. The method of claim 11, further comprising:

receiving a third public key from one of the mobile user device or another mobile user device, the third public key associated with the second public key, if the first public key fails and if the second public key results in a successful authentication.

13. The method of claim 11, further comprising:

receiving a third public key and a fourth public key if the first public key fails and if the second public key results in a successful authentication, wherein the third and the fourth public keys are associated with the second public key.

14. A mobile user device configured for authentication in a public cryptographic system comprising:

means for creating a first private key and corresponding first public key at the mobile user device;

means for storing the first private key at the mobile user device;

means for creating a second private key associated with the first private key and creating a second public key corresponding to the second private key at the mobile user device;

means for outputting the second private key from the mobile user device such that it is not stored on the mobile user device while retaining the first private key in the mobile user device, wherein outputting the second private key comprises outputting a plurality of shares of the second private key to a plurality of different entities once such that the second private key can be re-created and used when the first private key is inaccessible, wherein the first private key is disabled when the second private key is re-created and used for authentication;

means for outputting the first public key and the second public key to a verifier device; and

means for using the retained first private key for authentication prior to using the second private key.

15. The device of claim 14, wherein means for outputting the second private key comprises:

means for creating at least two shares of the second private key at the mobile user device; and

means for outputting each share once to a different entity, wherein subsequent outputting of the second private key is prevented.

16. The device of claim 14, further comprising:

means for re-creating the second private key at one of the mobile user device or another mobile user device using at least some shares of the plurality of shares; and

means for using the second private key for authentication of the one of the mobile user device or the other mobile user device.

17. The device of claim 16, further comprising:

means for creating a third private key associated with the second private key and creating a third public key corresponding to the third private key; and

means for outputting the third public key to the verifier device.

18. The device of claim 16, further comprising:

means for creating a third private key associated with the second private key and for creating a third public key corresponding to the third private key;

means for creating a fourth private key associated with the third private key and for creating a fourth public key corresponding to the fourth private key;

means for outputting the fourth private key once such that it can be re-created; and

means for outputting the third and fourth public keys to the verifier device.

19. The device of claim 14, wherein the means for outputting the plurality of shares of the second private key comprise means for removing the second private key from the mobile user device.

20. A verifier apparatus configured for verification in a public cryptographic system comprising:

means for receiving a first public key from a mobile user device, wherein the first public key has a corresponding first private key stored on the mobile user device;

means for receiving a second public key from the mobile user device, the second public key associated with the first public key, wherein the second public key has a corresponding second private key that is split into a plurality of shares that are sent to a plurality of different entities such that it is not stored on the mobile user device, where each share is sent only once and to a different entity, such that the second private key can be re-created and used when there is no access to a first private key corresponding to the first public key, wherein the first private key is disabled when the second private key is re-created and used for authentication;

means for storing the first public key and the second public key;

means for using the first public key for authentication of the mobile user device; and

means for using the second public key for authentication if the first public key fails.

21. The apparatus of claim 20, further comprising:

means for receiving a third public key associated with the second public key from one of the mobile user device or another mobile user device, if the first public key fails and if the second public key results in a successful authentication of the mobile user device or the other mobile user device.

22. The apparatus of claim 20, further comprising:

means for receiving a third public key and a fourth public key, if the first public key fails and if the second public key results in a successful authentication, wherein the third and fourth public keys are associated with the second public key.

23. A non-transitory machine-readable medium comprising instructions for performing a public cryptography, which when executed by a processor causes the processor to:

create a first private key and corresponding first public key;

create a second private key associated with the first private key and create a second public key corresponding to the second private key;

retain the first private key and output the second private key such that it is not stored on a device where the second private key was created, the second private key being output as a plurality of shares to a plurality of different entities once such that the second private key can be re-created and used when there is no access to the first private key, wherein the first private key is disabled when the second private key is re-created and used for authentication;

output the first public key and the second public key to a verifier device; and

use the retained first private key for authentication prior to using the second private key for authentication.

24. The machine-readable medium of claim 23, wherein outputting the second private key further comprises instructions to:

create at least two shares of the second private key; and

output each share once to a different entity.

25. The machine-readable medium of claim 23 further comprising instructions to:

recreate the second private key; and

use the second private key for authentication.

26. The machine-readable medium of claim 23, wherein the processor is further caused to remove the second private key from the mobile device upon outputting the plurality of shares of the second private key to the plurality of different entities.

27. A non-transitory machine-readable medium comprising instructions for performing a public cryptography at a verifier device, which when executed by a processor causes the processor to:

receive a first public key from a mobile user device, wherein the first public key has a corresponding first private key stored on the mobile user device;

receive a second public key from the mobile user device, the second public key associated with the first public key, wherein the second public key has a corresponding second private key that is split into a plurality of shares that are sent to a plurality of different entities such that it is not stored on a device where the second private key was created, where each share is sent only once and to a different entity, such that the second private key can be re-created and used when there is no access to a first private key corresponding to the first public key, wherein the first private key is disabled when the second private key is re-created and used for authentication;

use the first public key for authentication of the mobile user device; and

use the second public key for authentication if the first public key fails.

28. The machine-readable medium of claim 27 further comprising instructions to:

receive a third public key associated with the second public key, if the first public key fails and if the second public key results in a successful authentication.

29. The machine-readable medium of claim 27 further comprising instructions to:

receive a third public key and a fourth public key associated with the second public key, if the first public key fails and if the second public key results in a successful authentication.

30. A mobile user device used for authentication comprising:

a processor configured to;

generate a first private key and corresponding first public key;

generate a second private key associated with the first private key; and

create a second public key corresponding to the second private key;

a storage medium coupled to the processor, the storage medium configured to store the first private key; and

a transmitter coupled to the processor to;

output the second private key such that it is not stored in the storage medium, the second private key being output as a plurality of shares to a plurality of different entities once, such that the second private key can be re-created and used when there is no access to the first private key, wherein the first private key is disabled when the second private key is re-created and used for authentication; and

output the first public key and the second public key to a verifier device;

wherein the processor uses the stored first private key for authentication of the mobile user device prior to using the second private key.

31. The mobile user device of claim 30, wherein the processor is configured to remove the second private key upon the output of the plurality of shares of the second private key to the plurality of different entities.

32. Apparatus used for verification comprising:

a receiver configured to receive a first public key from a mobile user device and to receive a second public key from the mobile user device, wherein the first public key has a corresponding first private key stored on the mobile user device and the second public key associated with the first public key, wherein the second public key has a corresponding second private key that is split into a plurality of shares that are sent to a plurality of different entities such that the second private key is not stored on a device where it was created, where each share is sent only once and to a different entity, such that the second private key can be re-created and used when there is no access to a first private key corresponding to the first public key, wherein the first private key is disabled when the second private key is re-created and used for authentication;

a storage medium coupled to the receiver, configured to store the first and second public keys; and

a processor coupled to the receiver and the storage medium, the processor configured to use the first public key for authentication of the mobile user device, the processor configured to use the second public key for authentication if the first public key fails.

33. A method operational for authentication in a public cryptographic system, comprising:

re-creating a second private key at a mobile user device that has no access to a first private key associated with the second private key, wherein the second private key is re-created using at least some shares of a plurality of shares of the second private key located at a plurality of different entities;

creating a third private key and a corresponding third public key;

outputting the third private key from the mobile user device such that it is not stored on the mobile user device while retaining the second private key at the mobile user device; and

using the second private key for authentication of the mobile user device before using the third private key.

34. The method of claim 33, wherein re-creating the second private key at a mobile user device that has no access to the first private key includes re-creating the second private key at a mobile user device different from a mobile user device that created the first private key and the second private key.

35. The method of claim 33, wherein outputting the third private key comprises transmitting a plurality of shares of the third private key from the mobile user device to a plurality of different entities once, such that the third private key can be re-created to replace use of the second private key;

and

further comprising transmitting the third public key to a verifier device.

36. The method of claim 33, further comprising:

creating a fourth private and a corresponding fourth public key;

outputting the fourth private key from the mobile user device while retaining the third private key in the mobile user device, wherein outputting the fourth private key comprises transmitting a plurality of shares of the fourth private key from the mobile user device to a plurality of different entities once, such that the fourth private key can be re-created to replace use of the third private key; and

transmitting the third public key and the fourth public key to a verifier device.

37. A mobile user device adapted for authentication in a public cryptographic system, comprising:

means for re-creating a second private key at a mobile user device that has no access to a first private key associated with the second private key, wherein the second private key is re-created using at least some shares of a plurality of shares of the second private key located at a plurality of different entities;

means for creating a third private key and a corresponding third public key;

means for outputting the third private key from the mobile user device such that it is not stored on the mobile user device while retaining the second private key at the mobile user device; and

means for using the second private key for authentication of the mobile user device before using the third private key.

38. The mobile user device of claim 37, wherein the means for re-creating a second private key at a mobile user device that has no access to a first private key includes means located at a mobile user device different from a mobile user device that created the first private key and the second private key.

39. The mobile user device of claim 37, wherein outputting the third private key comprises transmitting a plurality of shares of the third private key from the mobile user device to a plurality of different entities once, such that the third private key can be re-created to replace use of the second private key;

and

further comprising means for transmitting the third public key to a verifier device.

40. The mobile device of claim 37, further comprising:

means for creating a fourth private and a corresponding fourth public key;

means for outputting the fourth private key from the mobile user device while retaining the third private key in the mobile user device, wherein outputting the fourth private key comprises transmitting a plurality of shares of the fourth private key from the mobile user device to a plurality of different entities once, such that the fourth private key can be re-created to replace use of the third private key; and

means for transmitting the third public key and the fourth public key to a verifier device.

41. A non-transitory machine-readable medium comprising instructions for performing a public cryptography, which when executed by a processor causes the processor to:

re-create a second private key at a mobile user device that has no access to a first private key associated with the second private key, wherein the second private key is re-created using at least some shares of a plurality of shares of the second private key located at a plurality of different entities;

create a third private key and a corresponding third public key;

output the third private key from the mobile user device such that it is not stored on the mobile user device while retaining the second private key at the mobile user device; and

use the second private key for authentication of the mobile user device before using the third private key.

42. The machine-readable medium of claim 41, wherein the mobile user device at which the second private key is re-created is a different device from a mobile user device that created the first private key and the second private key.

43. The machine-readable medium of claim 41, wherein outputting the third private key comprises transmitting a plurality of shares of the third private key from the mobile user device to a plurality of different entities once, such that the third private key can be re-created to replace use of the second private key;

and

further comprising instructions to transmit the third public key to a verifier device.

44. The machine-readable medium of claim 41, further comprising instructions to:

create a fourth private and a corresponding fourth public key;

output the fourth private key from the mobile user device while retaining the third private key in the mobile user device, wherein outputting the fourth private key comprises transmitting a plurality of shares of the fourth private key from the mobile user device to a plurality of different entities once, such that the fourth private key can be re-created to replace use of the third private key; and

transmit the third public key and the fourth public key to a verifier device.