Method and apparatus for asymetric key management in a cryptographic system

• US 6,128,391 A
• Filed: 09/22/1997
• Issued: 10/03/2000
• Est. Priority Date: 09/22/1997
• Status: Expired due to Term

• Current Assignee: Visa International Service Association (Visa, Inc.)
• Original Assignee: Visa International Service Association (Visa, Inc.)
• Inventors: Johnson, Lance James, Denno, Rodney Grant
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Callahan, Paul E.
• Application Number:
  US08/934,838
• Time in Patent Office: 1,107 Days
• Field of Search: 380/200, 380/231, 380/232, 380/255, 380/273, 380/277, 380/278, 380/281, 380/282, 380/283, 380/284, 380/285, 380/44, 705/65, 705/66, 705/67, 705/71, 705/73, 713/169, 713/171
• US Class Current: 380/283
• CPC Class Codes: G06Q 20/341 Active cards, i.e. cards including their own processing means, e.g. including an IC or chip
• CPC Class Codes: G06Q 20/3672 initialising or reloading thereof
• CPC Class Codes: G06Q 20/3829 involving key management
• CPC Class Codes: G06Q 20/40975 using encryption therefor
• CPC Class Codes: G07F 7/1008 Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/0833 involving conference or group key network architectures or network communication protocols for key management in group communication in a packet data network H04L63/065
• CPC Class Codes: H04L 9/3226 using a predetermined code, e.g. password, passphrase or PIN network architectures or network communication protocols for supporting authentication of entities using passwords in a packet data network H04L63/083
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

A method and apparatus for asymmetrical key management in a cryptographic system is provided. Embodiments of the invention implement varying levels of diversification to manage the encryption keys. In one embodiment, a unique key per device approach is used that minimizes the risks due to unauthorized key access. In yet another embodiment, a unique key per device per transaction is used. The keys generated in embodiments of the invention can be used to authenticate one device with another. An authenticating device generates a current key that is initially unknown to an unauthenticated device. The authenticating device sends information to an unauthenticated device to assist it in determining the value of the current key. The unauthenticated device uses the determined value of the current key to derive the authenticating device'"'"'s authentication value. Each device generates a authentication value that must be correctly determined by an unauthenticated device for successful authentication. Authentication is performed between two devices such that each device is authenticated with the other device. Computing devices of a system can be grouped. In one embodiment devices are grouped such that one group includes devices that have a master key and another group includes devices that have a key that is derived from the master key. Another embodiment includes groups whose devices have the group'"'"'s master key and a key derived from each of the master keys of the other group(s). In this embodiment, a dual authentication process can be used to authenticate two devices from different groups.

Claims

1. A method of asymmetric key management in card-to-card transactions comprising the steps of:

generating an identifier, KI₁, and a derived key, DK₁, for a first card;

generating a key, K₁, using said KI₁ and DK₁ ;

installing K₁ in said first card;

generating an identifier, KI₂ and a derived key, DK₂, for a second card;

generating a key, K₂, that is different than said K₁ using said KI₂ and said DK₂ ; and

installing said K₂ in said second card.

2. The method of claim 1 further comprising the step of generating a set of future keys.

3. The method of claim 2 further comprising the steps of:

using a future key from said set of future keys; and

destroying said future key.

4. The method of claim 2 wherein said set of future keys is generated using said K₁.

5. The method of claim 4 wherein said future key is used in a single card-to-card transaction.

6. The method of claim 1 wherein said identifiers KI₁ and KI₂ include a variable portion and a constant portion.

7. The method of claim 1 wherein the step of generating K₁ further comprises the step of encrypting KI₁ using DK₁.

8. The method of claim 1 wherein the step of generating K₂ further comprises the step of encrypting KI₂ using DK₂.

9. The method of claim 1 further comprising the steps of:

installing in said second card said DK₁ ;

deriving a current key of said first card using said KI₁, DK and a key calculation algorithm.

10. The method of claim 9 wherein said current key is said K₁.

11. A method for bilaterally authenticating devices in a cryptographic system comprising the steps of:

determining a current key for a first device;

said first device generating a first message for a second device;

said second device determining a current key value using said first message;

said second device determining a first authentication value using said message and said current key value;

said second device generating a second message for said first device;

said first device extracting said first authentication value from said second message;

said first device determining whether said extracted first authentication value is the same as said first authentication value;

performing the following when said extracted first authentication value is the same as said first authentication value;

said first device determining a second authentication value from said second message;

said first device generating a third message for said second device;

said second device extracting said second authentication value from said third message; and

said second device determining whether said extracted second authentication value is the same as said second authentication value.

12. The method of claim 11 wherein said current key is dynamically generated, said step of determining a current key comprising the steps of:

generating a plurality of future keys; and

selecting said current key from said plurality of future keys.

13. The method of claim 12 further comprising the step of removing said current key from said plurality of future keys.

14. The method of claim 12 wherein said step of generating further comprises the steps of:

generating an initial key; and

generating said plurality of future keys from said initial key.

15. The method of claim 14 wherein said step of generating uses a key calculation algorithm.

16. The method of claim 15 wherein said key calculation algorithm uses a derived unique key per transaction (DUKPT) scheme.

17. The method of claim 11 wherein said step of generating a first message further comprises the steps of:

generating said first authentication value;

encrypting said first authentication value using said current key; and

including in said first message a key identifier, said key identifier used to determine said first authentication value.

18. The method of claim 11 wherein said step of determining a current key value further comprises the step of calculating said current key value using a key calculation algorithm, an initial key and a key identifier value.

19. The method of claim 18 wherein said initial key was used to generate said current key.

20. The method of claim 11 wherein said step of determining a first authentication value further comprises the step of decrypting an encrypted portion of said first message using said current key value.

21. The method of claim 11 wherein said step of generating a second message further comprises the steps of:

combining said first authentication value with said second authentication value;

generating a first portion of said second message by encrypting said combination using said current key value; and

generating a second portion of said second message by encrypting said second authentication value using said current key value.

22. The method of claim 21 wherein said step of combining uses an exclusive-or operation.

23. The method of claim 21 wherein said step of extracting said first authentication value further comprises the steps of:

decrypting said first portion of said second message using said current key;

decrypting said second portion using said current key; and

extracting said first authentication value from said decrypted first portion using said decrypted second portion of said second message.

24. The method of claim 21 wherein said step of determining a second authentication value further comprises the step of decrypting said second portion using said current key.

25. The method of claim 11 wherein said step of generating further comprises the steps of:

combining said second authentication value with a blinding factor; and

encrypting said combination using said current key.

26. The method of claim 25 wherein said step of combining uses an exclusive-or operation.

27. The method of claim 11 wherein said step of extracting said second authentication value further comprises the steps of:

decrypting said third message using said current key value; and

extracting said first authentication value from said decrypted third message using said blinding factor.

28. A system for bilaterally authenticating devices in a cryptographic system comprising:

a first device for generating a current key and a first authentication value, for verifying a derived first authentication value and for deriving a second authentication value, said first device comprising;

a first central processing unit (CPU) for generating said first authentication value and deriving a second authentication value;

a first memory coupled to said first CPU for storing a plurality of future keys from which said current key is selected; and

a first input/output port coupled to said first CPU and said first memory;

a second device coupled to said first device, said second device for generating said second authentication value, for verifying a derived second authentication value and for deriving a first authentication value, said second device comprising;

a second central processing unit (CPU) for generating said second authentication value;

a second memory coupled to said first CPU for storing an initial key for deriving said first authentication value; and

a second input/output port coupled to said first CPU and said first memory.

29. The system of claim 28 wherein said first and second CPUs implement key calculation algorithms.

30. The system of claim 28 wherein said first and second devices are smart cards.

31. An article of manufacture comprising:

a computer usable medium having computer readable program code embodied therein for bilaterally authenticating devices in a cryptographic system comprising;

computer readable program code configured to cause a computer to determine a current key and a first authentication value;

computer readable program code configured to cause a computer to generate a first message, said first message containing said first authentication value encrypted using said current key;

computer readable program code configured to cause a computer to transmit said first message to a second device;

computer readable program code configured to cause a computer to receive a second message from said second device;

computer readable program code configured to cause a computer to extract a first authentication value from said second message;

computer readable program code configured to cause a computer to determine whether said extracted first authentication value is the same as said first authentication value;

computer readable program code configured to cause a computer to validate said second device when said extracted first authentication value is the same as said first authentication value;

computer readable program code configured to cause a computer to determine a second authentication value from said second message;

computer readable program code configured to cause a computer to generate a third message for said second device, said third message containing said second authentication value.

32. The article of manufacture of claim 31 wherein said current key is dynamically generated, said computer readable code configured to cause a computer to determine a current key further comprises:

computer readable code configured to cause a computer to generate a plurality of future keys; and

computer readable code configured to cause a computer to select said current key from said plurality of future keys.

33. The article of manufacture of claim 32 further comprising computer readable code configured to cause a computer to remove said current key from said plurality of future keys.

34. The article of manufacture of claim 32 wherein computer readable code configured to cause a computer to generate further comprises:

computer readable code configured to cause a computer to generate an initial key; and

computer readable code configured to cause a computer to generate said plurality of future keys from said initial key.

35. The article of manufacture of claim 31 wherein said computer readable code configured to cause a computer to generate a first message further comprises:

computer readable code configured to cause a computer to include in said first message a key identifier, said key identifier used to determine said first authentication value.

36. The article of manufacture of claim 31 wherein said computer readable code configured to cause a computer to generate said third message further comprises the steps of:

computer readable code configured to cause a computer to combine said second authentication value with a blinding factor; and

computer readable code configured to cause a computer to encrypt said combination using said current key.

37. An article of manufacture comprising:

a computer usable medium having computer readable program code embodied therein for bilaterally authenticating devices in a cryptographic system comprising;

computer readable program code configured to cause a computer to receive a first message from a first device;

computer readable program code configured to cause a computer to determine a current key value using said first message, a key calculation algorithm and an initial key;

computer readable program code configured to cause a computer to determine a first authentication value using said first message and said current key value;

computer readable program code configured to cause a computer to generate a second message for said first device, said second message containing said first authentication value and a second authentication value;

computer readable program code configured to cause a computer to transmit said second message to said first device;

computer readable program code configured to cause a computer to receive a third message from said first device;

computer readable program code configured to cause a computer to extract a second authentication value from said third message; and

computer readable program code configured to cause a computer to determine whether said extracted second authentication value is the same as said second authentication value;

computer readable program code configured to cause a computer to validate said first device when said extracted second authentication value is the same as said second authentication value.

38. The article of manufacture of claim 37 wherein said computer readable program code configured to cause a computer to determine a first authentication value further comprises computer readable program code configured to cause a computer to decrypt an encrypted portion of said first message using said current key value.

39. The article of manufacture of claim 37 wherein said computer readable program code configured to cause a computer to generate a second message further comprises:

computer readable program code configured to cause a computer to combine said first authentication value with said second authentication value;

computer readable program code configured to cause a computer to generate a first portion of said second message by encrypting said combination using said current key value; and

computer readable program code configured to cause a computer to generate a second portion of said second message by encrypting said second authentication value using said current key value.

40. The article of manufacture of claim 39 wherein said computer readable program code configured to cause a computer to extract said first authentication value further comprises the steps of:

computer readable program code configured to cause a computer to decrypt said first portion of said second message using said current key;

computer readable program code configured to cause a computer to decrypt said second portion using said current key; and

computer readable program code configured to cause a computer to extract said first authentication value from said decrypted first portion using said decrypted second portion of said second message.

41. The article of manufacture of claim 37 wherein said computer readable code configured to cause a computer to extract said second authentication value further comprises:

computer readable code configured to cause a computer to decrypt said third message using said current key value; and

computer readable code configured to cause a computer to extract said second authentication value from said decrypted third message using said blinding factor.

42. A method of reducing exposure of keys in the distribution of computing devices in a cryptographic system comprising the steps of:

storing a master key in a computing device resident in a secured environment;

generating using said master key a unique key for a plurality of distributable computing devices, said unique key being different for each of said plurality of distributable computing devices and different from said master key; and

using said unique key in a transaction in said cryptographic system.

43. The method of claim 42 wherein said step of using further comprising the steps of:

generating using said unique key at least one future key; and

deleting said unique key.

44. The method of claim 42 wherein said computing device resident in said secured environment and said plurality of computing devices are smart cards.

45. The method of claim 44 wherein said smart cards are used in an off-line payment authorization system, said computing device resident in said secured environment is a merchant'"'"'s smart card and said plurality of computing devices are consumer smart cards.

46. The method of claim 42 wherein said master key and said unique key are used for authentication between said computing device resident in said secured environment and one of said plurality of computing devices.

47. The method of claim 46 wherein said authentication is bilateral authentication.

48. A method for asymmetric key management in a system of computing devices comprising the steps of:

for a first grouping of computer devices of said system;

generating a first master key that is stored in each device in said first grouping;

deriving a unique key for each device in said first grouping;

for a second grouping of computer devices of said system;

generating a second master key that is stored in each device in said second grouping, said second master key is used to derive said unique key for each device in said first grouping;

deriving a unique key for each device in said second grouping using said first master key.

49. The method of claim 48 further comprising:

for a third grouping of computer devices of said system;

generating a third master key that is stored in each device in said third grouping of computer;

deriving a unique key for each device in said third grouping using said first master key;

deriving a unique key for each device in said third grouping using said second master key;

for said first grouping of computer devices of said system;

deriving a unique key for each device in said first grouping using said third master key;

for said second grouping of computer devices of said system;

deriving a unique key for each device in said second grouping using said third master key.

50. The method of claim 48 further comprising the steps of:

performing a first authentication between a first device from said first device group and a second device from said second device group using said unique key of said first device and said second master key; and

performing a second authentication between said first device and said second device using said unique key of said second device and said first master key.

51. The method of claim 48 wherein said unique key of said first and second devices are unique per device per transaction.