Computer readable medium having a private key encryption program

• US 6,956,950 B2
• Filed: 12/27/2000
• Issued: 10/18/2005
• 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): Song, Hosuk
• Application Number:
  US09/750,511
• Publication Number:
  US 20010008012A1
• Time in Patent Office: 1,756 Days
• Field of Search: 380277-282, 380284-285, 380/28, 380/30, 713/167, 716/167
• US Class Current: 380/277
• 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. A computer-readable medium comprising a program for encrypting a private key used in cryptography, wherein the private key conforms to a predetermined key format, the program being executable on a computer to carry out the steps of:

dividing an exponent of the private key into a most significant portion and a least significant portion;

encrypting the least significant portion using a secret known to a user associated with the private key; and

combining the most significant portion, without encryption, and the encrypted version of the least significant portion to form a storable private key sequence, the storable private key sequence being such that a decryption of the storable private key sequence using a proposed secret other than the secret known to the user results in a decrypted pseudo-key, wherein a pseudo-key is a key that conforms to the predetermined key format but does not match the private key and wherein the number of proposed secrets that lead to a pseudo-key is larger than a security threshold; and

storing the storable private key sequence as the encrypted private key.

2. The computer-readable medium of claim 1, wherein the security threshold is determined by a secured resource that validates the private key and disables at least usage of the private key after receipt of the security threshold number of pseudo-keys.

3. The computer-readable medium of claim 1, wherein the secret known to the user is a personal identification number (PIN) selected from a PIN space and more than the security threshold number of PINs in the PIN space result in pseudo-keys.

4. The computer-readable medium of claim 1, wherein the predetermined key format is a format wherein a key exponent is less than a maximum valid exponent.

5. The computer-readable medium of claim 4, wherein the program is further configured to carry out the steps of:

selecting random numbers k and m, where m is a number between d, the exponent of the private key, and n, the modulus of the private key,

computing a sum d+km from d, k and m;

encrypting the sum d+km using the secret known to the user associated with the private key, to form an encrypted sum,

storing the random number m and the encrypted sum as the encrypted private key, thereby generating a value that is less than the modulus of the private key whether decrypted with the secret known to the user or with a proposed secret other than the secret known to the user.

6. The computer-readable medium of claim 5, wherein k is a 64-bit value.

7. A computer-readable medium comprising a program for encrypting a private key used in cryptography, wherein the private key conforms to a predetermined key format, the program being executable on a computer to carry out the steps of:

dividing the private key into a first portion and a second portion;

encrypting the second portion using a secret known to a user associated with the private key to form an encrypted second portion such that a substitution of an incorrectly decrypted encrypted second portion for the correctly decrypted encrypted second portion results, for at least some proposed secrets other than the secret known to the user, in a pseudo-key that conforms to the predetermined key format but is different from the private key; and

combining the first portion, without encryption, and the encrypted second portion to form a storable private key sequence, the storable private key sequence being such that a decryption of the storable private key sequence using at least some proposed secrets other than the secret known to the user results in a decrypted pseudo-key, wherein the number of proposed secrets that lead to a pseudo-key is larger than a security threshold; and

storing the storable private key sequence as the encrypted private key.

8. The computer-readable medium of claim 7, wherein the security threshold is determined by a secured resource that validates the private key and disables at least usage of the private key after receipt of the security threshold number of pseudo-keys.

9. The computer-readable medium of claim 7, wherein the secret known to the user is a personal identification number (PIN) selected from a PIN space and more than the security threshold number of PINs in the PIN space result in pseudo-keys.

10. The computer-readable medium of claim 7, wherein the predetermined key format is a format wherein a key exponent is less than a maximum valid exponent.

11. The computer-readable medium of claim 10, wherein the program is further configured to carry out the steps of:

selecting random numbers k and m, where m is a number between d, the exponent of the private key, and n, the modulus of the private keys,

computing a sum d+km from d, k and m;

encrypting the sum d+km using the secret known to the user associated with the private key, to form an encrypted sum;

storing the random number m and the encrypted sum as the encrypted private key, thereby generating a value that is less than the modulus of the private key whether decrypted with the secret known to the user or with a proposed secret other than the secret known to the user.

12. The computer-readable medium of claim 11, wherein k is a 64-bit value.