Method and system for personal identification

Claims

I claim:

1. A method for enabling an authorized user of a personal identification card to effect a transaction using a transaction terminal, comprising the steps of:

generating a first data string having a portion thereof which is derived from a physical characteristic of the authorized user and need not be retained secret;

mapping the first data string using a predetermined function F to generate a second data string Q having a length substantially less than the length of the first data string;

digitally signing the second data string with a private key of a public-key cryptosystem pair to generate a signature corresponding to the second data string, the public-key cryptosystem pair also having a public key M;

encoding the first data string and the signature to generate an encoded first data string/signature;

storing the encoded first data string/signature on the personal identification card;

receiving the personal identification card at the transaction terminal;

decoding the encoded first data string/signature on the received personal identification card to generate the first data string and a received signature;

mapping the first data string with the predetermined function F to generate the second data string;

digitally verifying, using the public key M of the public-key cryptosystem pair, whether the received signature can be generated from the second data string;

if the received signature can be generated from the second data string using the public key, generating an indication that the received signature is valid;

generating a representation from the first data string; and

displaying the representation and the indication on a display of the transaction terminal to enable an operator thereof to verify that the user is authorized to effect a transaction using the personal identification card.

2. The method for enabling an authorized user of a personal identification card to effect a transaction as described in claim 1 wherein the first data string includes data representing a pictorial representation of the physical characteristic of the authorized user.

3. The method for enabling an authorized user of a personal identification card to effect a transaction as described in claim 1 wherein the first data string includes data representing one or more personal facts about the authorized user.

4. The method for enabling an authorized user of a personal identification card to effect a transaction as described in claim 1 wherein the first data string includes one or more codewords, each of the codewords authorizing a specific transaction.

5. The method for enabling an authorized user of a personal identification card to effect a transaction as described in claim 1 wherein the first data string includes data representing a pictorial representation of the physical characteristics of the authorized user, data representing one or more personal facts about the authorized user, and at least one codeword authorizing a specific transaction using the personal identification card.

6. The method for enabling an authorized user of a personal identification card to effect a transaction as described n claim 1 wherein the predetermined function F is an identity function.

7. The method for enabling an authorized user of a personal identification card to effect a transaction as described in claim 1 wherein the predetermined function F is a hashing function based on a DES scheme.

8. The method for enabling an authorized user of a personal identification card to effect a transaction as described in claim 1 wherein the encoding step includes the step of:

encoding the first data string and the signature with an error-correcting code.

9. The method for enabling an authorized user of a personal identification card to effect a transaction as described in claim 1 wherein the decoding step includes the step of:

correcting errors in the first data string and in the received signature decoded from the encoded first data string/signature.

10. The method for enabling an authorized user of a personal identification card to effect a transaction as described in claim 1 wherein the digital signing step includes the steps of:

multiplying the second data string by each of the factors .+-.1 mod M and .+-.2 mod M;

determining which of the four values .+-.Q mod M and .+-.2Q mod M is a quadratic residue modulo M, where M equals a product of P.sub.1 multiplied by P.sub.2 and P.sub.1 and P.sub.2 are secret prime numbers which are preselected such that only one of the four values .+-.Q mod M and .+-.2Q mod M is a quadratic residue modulo M; and

computing the square root of the quadratic residue to generate the signature.

11. The method for enabling an authorized user of a personal identification card to effect a transaction as described in claim 10 wherein the digitally verifying step includes the steps of:

multiplying the second data string by each of the factors .+-.1 mod M and .+-.2 mod M;

squaring modulo the received signature to generate a value X;

determining whether X equals either .+-.Q mod M or .+-.2Q mod M; and

if X equals either .+-.Q mod M or .+-.2Q mod M, generating the indication that the received signature is valid.

12. A method for issuing a personal identification card for an authorized user of the personal identification card, comprising the steps of:

generating a pictorial representation of a physical characteristic of the authorized user;

processing the pictorial representation to generate a first data string;

mapping the first data string with a predetermined one-way function to generate a second data string Q having a length substantially less than the length of the first data string;

digitally signing the second data string Q with a private key of a first public-key cryptosystem pair to generate a first signature, where P.sub.1 and P.sub.2 are secret prime numbers and the first public-key cryptosystem pair also includes a public key M which is equal to a product of P.sub.1 multiplied by P.sub.2 ;

encoding the first data string and the first signature with an error-correcting code to generate an encoded first data string/signature; and

storing the encoded first data string/signature on the personal identification card.

13. The method for issuing a personal identification card as described in claim 12 further including the steps of:

digitally signing the second data string with a private key of a second public-key cryptosystem pair to generate a second signature; and

encoding the second signature along with the first data string and the first signature.

14. The method for issuing a personal identification card as described in claim 12 further including the step of:

augmenting the first data string to include data representing one or more personal facts about the authorized user.

15. The method for issuing a personal identification card as described in claim 12 further including the step of:

augmenting the first data string to include one or more codewords, each of said codewords authorizing a specific transaction using the personal identification card.

16. The method for issuing a personal identification card as described in claim 15 wherein the personal identification card is a passport and each of the cryptosystem pairs corresponds to a different country.

17. The method for issuing a personal identification card as described in claim 12 wherein the digital signing step includes the steps of:

multiplying the second data string by each of the predetermined factors .+-.1 mod M and .+-.2mod M;

determining which of the values .+-.Q mod M and .+-.2Q mod M is a quadratic residue modulo M, where the secret prime numbers P.sub.1 and P.sub.2 are preselected such that only one of the four values .+-.Q mod M and .+-.2Q mod M is a quadratic residue modulo M; and

computing the square root of the quadratic residue modulo M to generate the first signature.

18. The method for issuing a personal identification card as described in claim 12 further including the step of:

encrypting the first data string with a predetermined function prior to the mapping step.

19. A system for issuing authorized personal identification cards and for preventing unauthorized use thereof, comprising:

issuing terminal means for issuing a plurality of personal identification cards, each of said cards having stored therein a first data string with a portion thereof derived from a physical characteristic of an authorized user of the card, each of said cards also having stored therein a signature derived from a second data string using a private key of a public-key cryptosystem pair, the public-key cryptosystem pair also having a public key, the second data string being derived from the first data string using a predetermined one-way function and having a length substantially less than the length of the first data string; and

transaction terminal means including at least one transaction terminal for receiving a personal identification card offered to effect a transaction using the transaction terminal, the personal identification card having the first data string and a received signature stored therein, wherein the transaction terminal comprises means, using the public key of the public-key cryptosystem pair, for verifying that the received signature can be generated from the first data string, means responsive to the verifying means for generating a representation from the first data string, and means for displaying the representation and an indication of whether the received signature can be generated from the first data string to enable an operator of the transaction terminal to verify that the user of the offered personal identification card is authorized to effect a transaction.

20. The system as described in claim 19 wherein the issuing terminal means includes at least one issuing terminal for one or more independent issuers of authorized personal identification cards, each of the independent issuers having a distinctive public-key cryptosystem pair unknown to the other issuers.

21. A system for allowing authorizing users of personal identification cards to effect transactions via at least one transaction terminal comprising a plurality of said cards each having stored therein a signature which is the digital signature of a second data string, the second data string being derived from a first data string derived from a physical characteristic associated with a respective user, the second data string derived from the first data string using a predetermined one-way function and having a length substantially less than the length of the first data string, the signature stored in each of said cards having been derived with the same private key of a public-key cryptosystem pair also having a public key; and at least one transaction terminal having means for controlling (1) the retrieval of the first data string and the signature stored in the inserted card, (2) the digital verification of the signature with the use of the public key of the public-key cryptosystem pair, (3) the generation of a pictorial representation from the first data string, and (4) the effecting of a transaction only if the signature is verified and the pictorial representation matches the user.

22. A terminal for initializing personal identification cards, to be used with at least one transaction terminal, each card having a memory therein, comprising means for assigning a first data string having a portion thereof which is derived from a physical characteristic of a user whose card is to be initialized, means for mapping the first data string with a predetermined one-way function to generate a second data string having a length substantially less than the length of the first data string, means for deriving a digital signature from the second data string, the signature for each user being derived with use of a private key of a public-key cryptosystem pair also having a public key, and means for controlling the storing in a user card of the respective derived digital signature.

23. A personal identification card, for use in effecting transactions via at least one transaction terminal, comprising a body portion, a memory within said body portion for storing a signature, said signature being the digital signature of a second data string derived from a first data string having at least a portion thereof being derived from a physical characteristic of a respective card user, the second data string being derived from the first data string using a predetermined one-way function and having a length substantially less than the length of the first data string, wherein said signature is derived from the second data string with the private key of a public-key cryptosystem pair.

24. A method for personal identification, comprising the steps of:

generating a first data string having a portion thereof which is derived from a physical characteristic of a user and need not be retained secret;

mapping the first data string using a predetermined function to generate a second data string;

digitally signing the second data string with a private key of a public-key cryptosystem pair to generate a signature corresponding to the second data string, the public-key cryptosystem pair also including a public key;

encoding the first data string and the signature to generate an encoded first data string/signature;

transmitting the encoded first data string/signature over a communications channel;

receiving the encoded first data string/signature at a transaction terminal;

decoding the received encoded first data string/signature to generate the first data string and a received signature;

mapping the first data string with the predetermined function to generate the second data string;

digitally verifying, using the public key of the public-key cryptosystem pair, whether the received signature can be generated from the second data string;

if the received signature can be generated from the second data string using the public key, generating an indication that the received signature is valid;

generating a representation from the first data string; and

displaying the representation and the indication on a display of the transaction terminal to enable an operator thereof to verify that the user is authorized to effect a transaction.

25. A method for enabling an authorized user of a personal identification card to effect a transaction using a transaction terminal, comprising the steps of:

generating a first data string having a portion thereof which is derived from a physical characteristic of the authorized user and need not be retained secret;

digitally signing the first data string with a private key of a public-key cryptosystem pair to generate a signature corresponding to the first data string, the public-key cryptosystem pair also having a public key M;

storing the first data string and the signature on the personal identification card;

receiving the personal identification card at the transaction terminal;

digitally verifying, using the public key M of the public-key cryptosystem pair, whether the signature on the personal identification card received at the transaction terminal can be generated from the first data string;

if the signature can be generated from the first data string using the public key, generating an indication that the signature is valid;

generating a representation from the first data string; and

displaying the representation and the indication on a display of the transaction terminal to enable an operator thereof to verify that the user is authorized to effect a transaction using the personal identification card.

26. A method for enabling an authorized user of a personal identification card to effect a transaction using a transaction terminal, the personal identification card having stored therein a first data string having a portion thereof which is derived from a physical characteristic of the authorized user and need not be retained secret, and a signature of the first data string derived from a private key of a public-key cryptosystem pair, the public-key cryptosystem pair also having a public key M, comprising the steps of:

receiving the personal identification card at the transaction terminal;

digitally verifying, using the public key M of the public-key cryptosystem pair, whether the signature on the personal identification card received at the transaction terminal an be generated from the first data string;

if the signature can be generated from the first data string using the public key, generating an indication that the signature is valid;

generating a representation from the first data string; and

displaying the representation and the indication on a display of the transaction terminal to enable an operator thereof to verify that the user is authorized to effect a transaction using the personal identification card.

TECHNICAL FIELD

The present invention relates generally to personal identification schemes and more particularly to a method and system for issuing authorized personal identification cards and for preventing unauthorized use thereof during transaction processing.

BACKGROUND OF THE INVENTION

Password-based protection schemes for credit cards or other personal identification cards are well-known in the prior art. Such cards typically include a memory comprising a magnetic tape or other storage media affixed to the card. They may also include a data processing capability in the form of a microprocessor and an associated control program. In operation, a card issuer initially stores in the memory a personal identification number, i.e., a secret password, as well as a value representing a maximum dollar amount. To effect a transaction, the card is placed in a terminal and the user is required to input his or her password. If the terminal verifies a match between the user-inputted password and the password stored on the card, the transaction is allowed to proceed. The value of the transaction is then subtracted from the value remaining on the card, and the resulting value represents the available user credit.

Techniques have also been described in the prior art for protecting against the illegitimate issuance of credit cards such as the type described above. In U.S. Pat. No. 4,453,074 to Weinstein, each such card has stored therein a code which is the encryption of a concatenation of a user's secret password and a common reference text. The encryption is derived in an initialization terminal through the use of a private key associated with the public key of a public-key cryptosystem key pair. In operation, a cardholder presents his or her card to a transaction terminal. The terminal decrypts the stored code on the card in accordance with the public key of the public-key cryptosystem pair. A transaction is effected only if the stored code decrypts into the user password, inputted on a keyboard by the cardholder, and the common reference text.

While the method described in the Weinstein patent provides an adequate protection scheme for preventing the fraudulent issuance of credit cards, this scheme requires each user to have a secret or "private" password which must be memorized and inputted into the transaction terminal. Weinstein also requires additional circuitry for concatenating the user's secret password with the common reference text. This latter requirement, while purportedly required to insure the integrity of the protection scheme, increases the complexity and the cost of the system.

It would therefore be desirable to provide an improved method for issuing personal identification cards using a public-key cryptosystem in which a "secret" password need not be memorized by the authorized user or concatenated with a common reference text to maintain the system security.

BRIEF SUMMARY OF THE INVENTION

The present invention describes a method and system for issuing authorized personal identification cards and for preventing the unauthorized use thereof using a public-key cryptosystem.

According to one feature of the invention, each authorized user of a card is assigned a password having a portion thereof which is generated from a representation of some non-secret or "public" characteristic of the user. The password is then processed to produce a digital "signature" which, along with the password, is thereafter stored on the card. To authorize a transaction at a transaction terminal, the digital signature from a received card must first be shown to have been generated from the password on the received card. The password is also processed at the transaction terminal to display a representation of the "public" characteristic encoded thereon. The public characteristic is then verified by an operator of the transaction terminal before a transaction is authorized.

It is very difficult to create a valid signature for any personal data without the proper private key, although it is simple for anyone to verify whether or not the signature for a password on the card is authentic, even without the private key. Only a card issuer can thus make a valid card and only a user with matching personal characteristics can use the card.

In the preferred embodiment, the password includes data representing a pictorial representation of a physical characteristic (e.g., the face, fingerprint, voice sample or the like) of the authorized user. Alternatively, or in addition to the pictorial representation data, the password may contain other data pertinent to the user, such as the user's age, address, nationality, security clearance, bank account balance, employer, proof of ownership, or the like. The password may also include one or more codewords, each of the codewords authorizing a specific transaction such as permission to receive certain funds on a certain date, permission to see classified documents, permission to enter into a country on a certain date (i.e., a visa), attestation to perform certain acts, or the like. Although not meant to be limiting, the personal identification card may be a credit card, a driver's license, a passport, a membership card, an age verification card, a bank card, a security clearance card, a corporate identification card or a national identification card.

In the preferred embodiment, a method for issuing an authorized personal identification card comprises the steps of generating the pictorial representation of a physical characteristic of the authorized user, processing the pictorial representation to generate a password, mapping the password with a predetermined function to generate a mapped password, digitally signing the mapped password with a private key of a public-key cryptosystem pair to generate a signature corresponding to the mapped password, encoding the password and the signature with a predetermined function to generate an encoded password/signature, and storing the encoded password/signature on a personal identification card.

To enable an authorized user of the personal identification card to effect a transaction using a transaction terminal, the subject invention describes a method comprising the steps of receiving the personal identification card at the transaction terminal, decoding the encoded password/signature of the received personal identification card to generate a received password and a received signature, mapping the received password with the predetermined function to generate a mapped password for the received personal identification card, and digitally verifying, using the public key of the public-key cryptosystem pair, whether the received signature can be generated from the mapped password for the received personal identification card. If the received signature can be generated from the mapped password using the public key, the method continues by generating an indication that the received signature is valid. A pictorial representation is then generated from the received password, and the pictorial representation and the indication are then displayed on a display of the transaction terminal to enable an operator thereof to verify that the user is authorized to effect a transaction using the personal identification card.

Preferably, the digital signing routine of the method includes the steps of multiplying the mapped password "Q" by each of the four factors .+-.1 modulo "M" and .+-.2 modulo "M", where M=P.sub.1 .multidot.P.sub.2. As used herein, "M" refers to the public key of the public-key cryptosystem pair and (P.sub.1,P.sub.2) refers to the private key thereof, where "P.sub.1 " and "P.sub.2 " are secret prime numbers which are preselected such that only one of the four values .+-.Q mod M and .+-.2Q mod M is a quadratic residue modulo "M". According to the digital signing routine, the four values .+-.Q mod M and .+-.2Q mod M are evaluated to determine which of these values is a quadratic residue modulo "M". The square root of the quadratic residue is then computed to generate the signature. Because the square root computation is extremely difficult to carry out without knowing the factorization of the secret prime numbers of the private key, unauthorized third parties are not capable of producing a card "signature" which, when digitally verified at the transaction terminal, can be shown to have been generated from the mapped password on the received personal identification card.

In accordance with yet another feature of the invention, a system for issuing authorized personal identification cards and for preventing unauthorized use thereof includes a plurality of issuing transaction terminals, each of the issuing transaction terminals being uniquely associated with one issuer of personal identification cards. Each issuer is assigned or selects its own public-key cryptosystem key pair which may or may not be different from the public-key cryptosystem key pair of every other issuer in the system. This arrangement, especially suited to a passport control system or the like, enables the operator of a transaction terminal to verify signatures from one or more of the issuers.

According to a further feature of the invention, a unique personal identification card is provided for effecting transactions via at least one transaction terminal. The identification card preferably includes a body portion and a memory within the body portion for storing a password and a signature derived from the password. The password includes a portion thereof which is generated from a pictorial representation of a non-secret characteristic of the authorized user, such as the user's face. The signature is derived from the password with the private key of a public-key cryptosystem pair.

BRIEF DESCRIPTION OF THE DRAWINGS

For a more complete understanding of the present invention and the advantages thereof, reference is now made to the following Description taken in conjunction with the accompanying Drawings in which:

FIG. 1 is a schematic representation of one type of personal identification card according to the invention, the card having a picture of a physical characteristic of an authorized user of the identification card;

FIG. lA is a diagrammatic representation of a portion of a magnetic stripe of the personal identification card of FIG. 1 showing a "password" generated in part from the picture on the identification card;

FIG. 2 is a general flowchart diagram of the preferred method of the present invention for issuing an authorized personal identification card such as shown in FIG. 1;

FIG. 3 is a detailed flowchart diagram of the digital signing routine of FIG. 2;

FIG. 3A is a flowchart diagram of a routine for selecting the secret prime numbers of the private key (P.sub.1,P.sub.2);

FIG. 4 is a general flowchart diagram of the preferred method of the present invention for preventing unauthorized use of the personal identification card of FIG. 1 which is issued according to the method of FIG. 2;

FIG. 5 is a detailed flowchart diagram of the digital verifying routine of FIG. 4; and

FIG. 6 is a block diagram of a representative multi-issuer system according to the present invention.

DETAILED DESCRIPTION

With reference now to the drawings wherein like reference numerals designate like or similar parts or steps, FIG. 1 is a schematic representation of a personal identification card 10 for use