Method and apparatus for cryptographically camouflaged cryptographic key storage, certification and use

• US 6,170,058 B1
• Filed: 12/23/1997
• Issued: 01/02/2001
• Est. Priority Date: 12/23/1997
• Status: Expired due to Term

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: Arcot Systems, Inc. (Broadcom, Inc.)
• Inventors: Kausik, Balas Natarajan
• Primary Examiner(s): Laufer, Pinchus M.
• Application Number:
  US08/996,758
• Time in Patent Office: 1,106 Days
• Field of Search: 380/3, 380/4, 380/23, 380/24, 380/25, 380/277, 380/279, 380/281, 380/282, 380/284, 380/286, 705/71, 705/72, 713/156, 713/159, 713/172, 713/183, 713/193, 713/184, 713/185
• US Class Current: 713/193
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06F 2221/2127 Bluffing
• CPC Class Codes: G06Q 20/02 involving a neutral party, e.g. certification authority, notary or trusted third party [TTP]
• CPC Class Codes: G06Q 20/3829 involving key management
• 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: G07F 7/1025 Identification of user by a PIN code
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/20 Manipulating the length of blocks of bits, e.g. padding or block truncation
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• 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/3247 involving digital signatures
• CPC Class Codes: H04L 9/3268 using certificate validation, registration, distribution or revocation, e.g. certificate revocation list [CRL]

Abstract

A digital wallet stores an cryptographically camouflaged access-controlled datum, e.g., a private key encrypted under the user'"'"'s PIN. Entry of the correct PIN will correctly decrypt the stored key. Entry of certain pseudo-valid PINs will also decrypt the stored key, but improperly so, resulting in a candidate key indistinguishable from the correct key. Such pseudo-valid PINs are spread thinly over the space of PINs, so that the user is unlikely to realize a pseudo-valid PIN via a typographical error in entering the correct PIN. In existing wallet technologies, which lack pseudo-valid PINs, only the correct PIN produces a decrypted key; thus, hackers can find the correct PIN by entering all possible PINs until a key is produced. The present invention'"'"'s plurality of candidate keys prevent a hacker from knowing when he has found the correct key. In addition, hacker detection may be moved off-line into devices accepting messages signed with candidate keys, and/or the lockout threshold may be increased. Thus, the wallet can be forgiving of typographic or transposition errors, yet a hacker trying large numbers of PINs will eventually guess a pseudo-valid (but still incorrect) PIN and recover a candidate private key whose fraudulent use will be detected. The wallet may be used with associated key generation, certification, and verification technologies. Such technologies may include pseudo-public keys embedded in pseudo-public certificates, i.e., public keys that are not generally known and which are contained in certificates that are verifiable only by entities so authorized by the certifying authority.

Claims

1. An apparatus for managing access to a cryptographically secured access-controlled datum, comprising:

(a) computer-implemented input logic means for receiving a candidate access code;

(b) a first computer memory configured to store a cryptographically camouflaged access-controlled datum;

(c) computer-implemented first cryptographic logic means operatively connected to said input logic means, and to said first computer memory, for processing said cryptographically camouflaged access-controlled datum using said candidate access code, said processing inhibiting the detection of cryptographic camouflaging by a fraudulent provider of said candidate access code by preserving a structural homogeneity corresponding to a pre-camouflaged state of said access-controlled datum; and

(d) computer-implemented output logic means for providing said processed access-controlled datum to a user of said apparatus.

2. The apparatus of claim 1 wherein:

(a) said access-controlled datum has been at least partially encrypted using an access code;

(b) a second computer memory configured to store a cryptographic representation of said access code;

(c) said computer-implemented first cryptographic logic means includes;

(i) computer-implemented second cryptographic logic means operatively connected to said computer-implemented input logic means and configured to regenerate said cryptographic representation of said access code in response to said candidate access code belonging to a plurality of pseudo-valid access codes; and

(ii) computer-implemented third cryptographic logic means configured to receive said regenerated cryptographic representation from said computer-implemented second cryptographic logic means, and operatively connected to said first computer memory and to said computer-implemented input logic means for using said received candidate access code in decrypting said stored encrypted access-controlled datum to produce a decrypted access-controlled datum.

3. The apparatus of claim 2 wherein said access-controlled datum is a cryptographic key.

4. The apparatus of claim 3 wherein said cryptographic key is a private key.

5. The apparatus of claim 4 further comprising a pseudo-public key corresponding to said private key.

6. The apparatus of claim 5 further comprising a pseudo-public certificate containing said pseudo-public key.

7. The apparatus of claim 6 wherein said pseudo-public key is encrypted.

8. The apparatus of claim 7 wherein said pseudo-public key is encrypted with a public key having a corresponding private key that is not known except to authorized verifiers.

9. The apparatus of claim 4 wherein said private key is well-formed.

10. The apparatus of claim 9 wherein said private key includes a well-formed modulus, and an exponent smaller than said modulus.

11. The apparatus of claim 9 wherein said private key includes:

(a) a cleartext representation of said modulus; and

(b) a cryptographic representation of at least a part of an exponent corresponding to said modulus.

12. The apparatus of claim 11:

(a) further comprising a third computer memory for storing a number larger than said exponent and smaller than said modulus; and

(b) wherein said at least part of said exponent is stored in an expanded form which, when evaluated modulo said number, equals said at least part of said exponent.

13. The apparatus of claim 11 wherein said at least part of said exponent represents certain less significant bits of said exponent.

14. The apparatus of claim 3 wherein said second computer-implemented cryptographic logic means for said regeneration of said cryptographic representation of said access code includes a many-to-one hash.

15. The apparatus of claim 14 wherein said many-to-one hash is characterized in that said plurality of pseudo-valid access codes are scattered among a plurality of invalid access codes.

16. The apparatus of claim 2 wherein:

(a) said cryptographic representation includes a hash function; and

(b) said second computer-implemented cryptographic logic means for said regeneration of said cryptographic representation includes a many-to-one hash.

17. The apparatus of claim 16 wherein said access-controlled datum is a private key.

18. The apparatus of claim 17 wherein said private key is well-formed.

19. The apparatus of claim 17 further comprising digital signing logic means including:

(a) computer-implemented input logic means for receiving a message to be signed;

(b) randomizing logic means for generating random data; and

(c) computer-implemented fourth cryptographic logic means operatively connected to said computer-implemented input logic means and to said randomizing logic means for;

(i) padding said received message with said generated random data; and

(ii) signing said padded message with said decrypted access-controlled datum.

20. The apparatus of claim 17 further comprising a pseudo-public key corresponding to said private key.

21. The apparatus of claim 16 wherein said many-to-one hash is characterized in that said plurality of pseudo-valid access codes are scattered among a plurality of invalid access codes.

22. The apparatus of claim 1 wherein said stored access-controlled datum is a private key having a corresponding public key that includes an exponent of at least 64 bits.

23. The apparatus of claim 2 wherein said computer-implemented third cryptographic logic means is configured to disallow said decryption when said received candidate access code is an invalid access code.

24. The apparatus of claim 2 implemented as a software program interacting with a computer.

25. The apparatus of claim 2 implemented as a hardware device.

26. The apparatus of claim 2 further comprising digital signing logic means including:

(a) computer-implemented input logic means for receiving a message to be signed;

(b) randomizing logic means for providing random data; and

(c) computer-implemented fourth cryptographic logic means operatively connected to said input logic and to said randomizing logic means for;

(i) padding said received message with said generated random data; and

(ii) signing said padded message with said decrypted access-controlled datum.

27. The apparatus of claim 26 wherein said generated random data arises from a source outside of said apparatus.

28. The apparatus of claim 26 wherein said generated random data originates from a physical source.

29. The apparatus of claim 2 wherein said computer-implemented third cryptographic logic means for decrypting includes a symmetric cryptographic function.

30. The apparatus of claim 29 wherein said symmetric cryptographic function is DES.

31. A cryptographic key wallet comprising:

(a) computer-implemented input logic means for receiving a user-inputted access code that may belong to a plurality of pseudo-valid access codes;

(b) computer-implemented cryptographic logic means for inhibiting the detection of cryptographic camouflaging by a fraudulent inputter of one of said pseudo-valid access codes by;

(i) cryptographically verifying said inputted pseudo-valid access code; and

(ii) decrypting a cryptographically-camouflaged access-controlled datum using said inputted pseudo-valid access code to produce a decrypted access-controlled datum having a structural homogeneity corresponding to a pre-camouflaged state of said access-controlled datum; and

(c) computer-implemented output logic means for providing said decrypted access-controlled datum to said user.

32. The cryptographic key wallet of claim 31 wherein said access-controlled datum includes a private key having a corresponding pseudo-public key.

33. The cryptographic key wallet of claim 32 further comprising a pseudo-public certificate containing said pseudo-public key.

34. A digital certificate server comprising:

(a) computer-implemented input logic means for receiving from a requester a digitally signed request for a pseudo-public digital certificate, said request including;

(i) a pseudo-public key to be certified, and

(ii) an identifying attribute of said requestor;

(b) computer-implemented cryptographic logic means for verifying said digitally signed request using said pseudo-public key;

(c) computer-implemented logic means for creating said pseudo-public certificate upon said verifying said digitally signed request, said certificate including said pseudo-public key encrypted under a cryptographic key whose corresponding decryption key is available only to authorized verifiers; and

(d) computer-implemented output logic means for providing said pseudo-public certificate for said requestor.

35. The digital certificate server of claim 34 implemented as an add-on module for use with a conventional digital certificate server.

36. The digital certificate server of claim 34 configured for use with a digital wallet, said digital wallet comprising:

(a) computer-implemented input logic means for receiving a candidate access code;

(b) a first computer memory configured to store a cryptographically camouflaged access-controlled datum;

(c) computer-implemented first cryptographic logic means operatively connected to said computer-implemented input logic means and said first computer memory for processing said cryptographically camouflaged access-controlled datum using said candidate access code; and

(d) computer-implemented output logic means for providing said processed datum access-controlled datum to a user of said apparatus.

37. The digital certificate server of claim 34 wherein said pseudo-public certificate is of a modified conventional format.

38. The digital certificate server of claim 34 wherein said pseudo-public key is encrypted.

39. The digital certificate server of claim 38 wherein said pseudo-public key is encrypted with a public key having a corresponding private key that is not known except to authorized verifiers.

40. Apparatus for verifying a digitally-signed message, comprising:

(a) computer-implemented input logic means for receiving a digitally-signed message and a pseudo-public key allegedly corresponding to a signer of said message, said pseudo-public key encrypted under a cryptographic key whose corresponding decryption key is available only to authorized verifiers;

(b) computer-implemented cryptographic logic means for using a decryption key of at least one of said authorized verifiers to cryptographically recover the pseudo-public key; and

(c) computer-implemented signalling logic means for detecting fraudulent use of said message upon failure of said verified pseudo-public key to successfully verify said signed message.

41. The apparatus of claim 40 wherein said received pseudo-public key is contained in a pseudo-public certificate.

42. The apparatus of claim 40 wherein said digitally-signed message is signed using a candidate private key that was generated by a cryptographic key wallet in response to a pseudo-valid access code.

43. The apparatus of claim 42 wherein said key wallet includes:

(a) computer-implemented input logic means for receiving a candidate access code;

(b) a first computer memory configured to store a cryptographically camouflaged access-controlled datum;

(c) computer-implemented first cryptographic logic means operatively connected to said computer-implemented input logic means and said first computer memory for processing said cryptographically camouflaged access-controlled datum using said candidate access code; and

(d) computer-implemented output logic means for providing said processed datum access-controlled datum to a user of said apparatus.

44. The apparatus of claim 40 wherein said logic for detecting said fraudulent use includes computer-implemented logic means for freezing access to said apparatus upon a plurality of unsuccessful attempted verifications.

45. The apparatus of claim 40 wherein said logic means for detecting said fraudulent use includes computer-implemented logic means for effecting an alarm upon unsuccessful attempted verification.

46. The apparatus of claim 40 wherein said decryption key is a private key of a private-public key pair of at least one of said authorized verifiers.

47. A method for providing a stored cryptographically-secured access-controlled datum, comprising the steps of:

(a) receiving a candidate access code from a user of a digital wallet;

(b) accessing a stored, cryptographically camouflaged access-controlled datum;

(c) cryptographically processing said cryptographically camouflaged access-controlled datum using said candidate access code, said processing inhibiting the detection of cryptographic camouflaging by a fraudulent provider of said candidate access code by preserving a structural homogeneity corresponding to a pre-camouflaged state of said access-controlled datum; and

(d) providing said processed access-controlled datum to said user of said wallet.

48. The method of claim 47 wherein said step of cryptographically processing said cryptographically camouflaged access-controlled datum using said candidate access code includes:

(a) accessing from a first memory within a digital wallet, an access-controlled datum that has been at least partially encrypted using an access code;

(b) accessing from a second memory within said digital wallet, a cryptographic representation of said access code;

(c) regenerating said cryptographic representation of said access code in response to said candidate access code belonging to a plurality of pseudo-valid access codes; and

(d) using said received candidate access code, decrypting said encrypted access-controlled datum to produce a decrypted access-controlled datum.

49. The method of claim 48 wherein said access-controlled datum is a cryptographic key.

50. The method of claim 49 wherein said stored access-controlled datum is a private key having a corresponding public key that includes a long exponent.

51. The method of claim 49 wherein said cryptographic key is a private key.

52. The method of claim 51 wherein said private key is a member of a cryptographic key pair including a pseudo-public key corresponding to said private key.

53. The method of claim 52 wherein said digital wallet includes a pseudo-public certificate containing said pseudo-public key.

54. The method of claim 53 wherein said pseudo-public key is encrypted.

55. The method of claim 54 wherein said pseudo-public key is encrypted with a public key having a corresponding private key that is not known except to authorized verifiers.

56. The method of claim 52 wherein said private key is well-formed.

57. The method of claim 56 wherein said private key includes a well-formed modulus, and an exponent smaller than said modulus.

58. The method of claim 56 wherein said private key includes:

(a) a cleartext representation of said modulus; and

(b) a cryptographic representation of at least a part of an exponent corresponding to said modulus.

59. The method of claim 58 wherein:

(a) said private key is stored in said first memory as an expanded form of at least part of said exponent; and

(b) said step of decrypting said encrypted access-controlled datum includes;

(i) retrieving from a third memory a number larger than said exponent and smaller than said modulus;

(ii) retrieving said expanded form of at least part of said exponent from said first memory; and

(iii) evaluating said expanded form of at least part of said exponent, modulo said number, to recover said at least part of said exponent.

60. The method of claim 58 wherein said at least part of said exponent represents certain less significant bits of said exponent.

61. The method of claim 51 wherein said step of regenerating said cryptographic representation of said access code includes performing a many-to-one hash.

62. The method of claim 61 wherein said many-to-one hash is characterized in that said plurality of pseudo-valid access codes are scattered among a plurality of invalid access codes.

63. The method of claim 49 wherein:

(a) said cryptographic representation includes a hash function; and

(b) said step of regenerating said cryptographic representation of said access code includes performing a many-to-one hash.

64. The method of claim 63 wherein said many-to-one hash is characterized in that said plurality of pseudo-valid access codes are scattered among a plurality of invalid access codes.

65. The method of claim 63 wherein said access-controlled datum is a private key.

66. The method of claim 65 further comprising the steps of:

(a) receiving a message to be signed;

(b) generating random data;

(c) padding said received message with said generated random data; and

(d) signing said padded message with said decrypted access-controlled datum.

67. The method of claim 65 wherein said private key is a member of a cryptographic key pair including a pseudo-public key corresponding to said private key.

68. The method of claim 65 wherein said private key is well-formed.

69. The method of claim 49 implemented via a hardware device.

70. The method of claim 49 wherein said step of decrypting said access-controlled datum is disallowed when said received candidate access code is an invalid access code.

71. The method of claim 49 implemented as a software program.

72. The method of claim 49 further comprising the steps of:

(a) receiving a message to be signed;

(b) generating random data;

(c) padding said received message with said generated random data; and

(d) signing said padded message with said decrypted access-controlled datum.

73. The method of claim 72 wherein said generated random data arises from a source outside of said apparatus.

74. The method of claim 72 wherein said generated random data originates from a physical source.

75. The method of claim 49 wherein said step of decrypting said encrypted access-controlled datum includes performing a symmetric cryptographic operation thereon.

76. The method of claim 75 wherein said symmetric cryptographic operation is DES.

77. A method for providing a stored cryptographically-secured access-controlled datum, comprising the steps of:

(a) receiving, at a digital wallet, a user-inputted access code that may belong to a plurality of pseudo-valid access codes;

(b) inhibiting the detection of cryptographic camouflaging by a fraudulent inputter of one of said pseudo-valid access codes by;

(i) cryptographically verifying said inputted pseudo-valid access code; and

(ii) decrypting a cryptographically-camouflaged access-controlled datum using said inputted pseudo-valid access code to produce a decrypted access-controlled datum having a structural homogeneity corresponding to a pre-camouflaged state of said access-controlled datum; and

(c) providing said decrypted access-controlled datum to said user of said digital wallet.

78. The method of claim 77 wherein said access-controlled datum includes a private key having a corresponding pseudo-public key.

79. The method of claim 78 wherein said digital wallet includes a pseudo-public certificate containing said pseudo-public key.

80. A method for generating a pseudo-public digital certificate comprising the steps of:

(a) receiving from a requestor a digitally signed request for a pseudo-public digital certificate, said request including;

(i) a pseudo-public key to be certified, and

(ii) an identifying attribute of said requestor;

(b) cryptographically verifying said digitally signed request using said pseudo-public key;

(c) creating said pseudo-public certificate upon said verifying said digitally signed request, said certificate including said pseudo-public key encrypted under a cryptographic key whose corresponding decryption key is available only to authorized verifiers; and

(d) outputting said pseudo-public certificate for said requestor.

81. The method of claim 80 further comprising the step of placing said created digital certificate in a digital wallet, said digital wallet comprising:

(a) computer-implemented input logic means for receiving a candidate access code;

(b) a first computer memory configured to store a cryptographically camouflaged access-controlled datum;

(c) computer-implemented first cryptographic logic means operatively connected to said input logic means and said first computer memory for processing said cryptographically camouflaged access-controlled datum using said candidate access code; and

(d) computer-implemented output logic means for providing said processed access-controlled datum to a user of said apparatus.

82. The method of claim 80 wherein said pseudo-public certificate is of a modified conventional format.

83. The apparatus of claim 82 wherein said pseudo-public key is encrypted.

84. The method of claim 83 wherein:

(a) said pseudo-public key is encrypted with a public key having a corresponding private key that is not known except to authorized verifiers.

85. The method of claim 80 performed via an add-on module for use with a conventional digital certificate server.

86. A method for verifying a digitally-signed message, comprising the steps of:

(a) receiving, at a message verification apparatus, a digitally-signed message and a pseudo-public key allegedly corresponding to a signer of said message, said pseudo-public key encrypted under a cryptographic key whose corresponding decryption key is available only to authorized verifiers;

(b) using a decryption key of at least one of said authorized verifiers to cryptographically recover the pseudo-public key; and

(c) detecting fraudulent use of said message upon failure of said verified pseudo-public key to successfully verify said signed message.

87. The method of claim 86 wherein said decryption key is a private key of a private-public key pair of at least one of said authorized verifiers.

88. The apparatus of claim 86 wherein said received pseudo-public key is contained in a pseudo-public certificate.

89. The method of claim 86 wherein said digitally-signed message is signed using a candidate private key that was generated by a cryptographic key wallet in response to a pseudo-valid access code.

90. The method of claim 89 wherein said key wallet includes:

(a) computer-implemented input logic means for receiving a candidate access code;

(b) a first computer memory configured to store a cryptographically camouflaged access-controlled datum;

(c) computer-implemented first cryptographic logic means operatively connected to said input logic means and said first computer memory for processing said cryptographically camouflaged access-controlled datum using said candidate access code; and

(d) computer-implemented output logic means for providing said processed access-controlled datum to a user of said apparatus.

91. The method of claim 86 wherein said step of detecting said fraudulent use includes freezing access to said message verification apparatus upon a plurality of unsuccessful attempted verifications.

92. The method of claim 86 wherein said step of detecting said fraudulent use includes effecting an alarm upon unsuccessful attempted verification.

93. A method for storing a stored cryptographically-secured access-controlled datum, comprising the steps of:

(a) receiving an access-controlled datum;

(b) cryptographically camouflaging said access-controlled datum such to be recognizable by an authorized user thereof but unrecognizable to an unauthorized user thereof by preserving a structural homogeneity corresponding to a pre-camouflaged state of said access-controlled datum; and

(c) storing said camouflaged access-controlled datum in a digital wallet.

94. The method of claim 93 wherein said step of cryptographically camouflaging said access-controlled datum includes:

(a) receiving an access code;

(b) computing a cryptographic representation of said access code, said representation having the property of being reproducible in response to a plurality of pseudo-valid access codes;

(c) storing said computed cryptographic representation of said access code;

(d) at least partially encrypting said access-controlled datum using said access code;

(e) storing said at least partially encrypted access-controlled datum for subsequent access by a user providing one of said plurality of said pseudo-valid access codes.

95. The method of claim 94 wherein said access-controlled datum is a cryptographic key.