 |
Claims  |
|
|
We 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;
digitally signing the first data string to generate a signature
corresponding to the first data string;
encoding the first data string and the signature using a predetermined
encoding function 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;
digitally verifying whether the received signature can be generated from
the first data string;
if the received signature can be generated from the first data string,
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.
2. The method as described in claim 1 wherein the digital signing and
digital verify steps use a private key of a private key cryptosystem.
3. The method as described in claim 1 wherein the digital signing step uses
a private key of a public-key cryptosystem pair and the digital verify
step uses a public key of the public-key cryptosystem pair.
4. The method as described in claim 1 wherein the encoding function is an
error-correcting function, an encryption function or an identify mapping
function.
5. The method as described in claim 4 wherein one of the functions is
applied to the first data string and another one of the functions is
applied to the signature.
6. The method as described in claim 1 further including the step of:
augmenting the first data string to include data representing one or more
facts about the authorized user.
7. The method as described in claim 1 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.
8. 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, comprising the steps of:
receiving the personal identification card at the transaction terminal;
digitally verifying 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, 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.
9. The method as described in claim 8 wherein the steps of generating a
representation from the first data string and displaying the
representation are carried out at or before the step of digitally
verifying whether the signature can be generated from the first data
string.
10. The method as described in claim 8 wherein the signature of the first
data string and the step of digitally verifying the signature use a
private key of a private key cryptosystem.
11. 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 a processor and a storage area, the storage
area for storing a data string having a portion thereof which is derived
from a physical characteristic of the authorized user and some other
authorizing information, comprising the steps of:
(a) receiving the personal identification card at the transaction terminal;
(b) exchanging one or more messages between the personal identification
card and the transaction terminal to enable the transaction terminal to
verify whether the personal identification card contains the authorizing
information;
(c) if the transaction terminal verifies that the personal identification
card contains the authorizing information, generating an indication that
the authorizing information is valid;
(d) generating a representation from the data string; and
(e) 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.
12. The method as described in claim 11 wherein the authorizing information
is a signature of the data string.
13. The method as described in claim 11 wherein the authorizing information
is not the messages exchanged between the personal identification card and
the transaction terminal.
14. The method as described in claim 11 wherein the exchanging of the one
or more messages constitutes a proof of legitimacy of the authorized user.
15. 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 a processor and a storage area, the storage
area for storing a data string Q, a value j equal to the one of the
factors .+-.1 mod M and .+-.2 mod M that causes the product of j and Q
modulo M to be a perfect square modulo M, and a signature z of the data
string equal to the square root of the product, and 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, comprising the steps of:
(a) receiving the personal identification card at the transaction terminal;
(b) determining whether a predetermined number of legitimacy checks have
been carried out on the personal identification card;
(c) if the predetermined number of legitimacy checks have not been carried
out, exchanging one or more messages between the personal identification
card and the transaction terminal to enable the transaction terminal to
verify whether the personal identification card contains the signature z;
(d) if the transaction terminal verifies that the personal identification
card contains the signature z, repeating step (b);
(e) if the predetermined number of legitimacy checks have been carried out,
generating an indication that the signature z is valid;
(f) generation a representation from the data string; and
(g) 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.
16. The method as described in claim 15, wherein the data string Q is a
password mapped using a predetermined function F, the password having a
portion thereof that is derived from a physical characteristic of the user
and need not be retained secret.
17. The method as described in claim 15 wherein step (c) comprises the
steps of:
generating a random number x modulo M in the personal identification card;
computing, in the personal identification card, the square y of the random
number x modulo M and providing y to the transaction terminal;
assigning, at the transaction terminal, a first or second value to a bit
and sending the bit to the personal identification card;
determining, in the personal identification card, whether the bit received
from the transaction terminal has the first or second value;
if the bit having the first value has been received from the transaction
terminal, providing W=x modulo M from the personal identification card to
the transaction terminal;
determining, in the transaction terminal, whether the square of W equals y;
if the square of W equals y, repeating step (b);
if the square of W does not equal y, rejecting the personal identification
card;
if the bit having the second value has been received from the transaction
terminal, computing W=xz modula M in the personal identification card and
providing W from the personal identification card to the transaction
terminal;
determining, in the transaction terminal, whether the square of W equals
the product yjQ modulo M;
if the square of W equals the product yjQ modulo M, repeating step (b); and
if the square of W does not equal the product yjQ modulo M, rejecting the
personal identification card. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
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 concatenting 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 or other
"proof of legitimacy" 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, a private-key cryptosystem, a
proof of possession of authorizing information such as a valid digital
signature, or any other type of "proof of legitimacy."
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.
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.
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. 1A 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
FIG. 6 is a block diagram of a representative multi-issuer system according
to the present invention;
FIG. 7 is a flowchart diagram of an alternate embodiment of the invention
wherein a private-key cryptosystem is used to generate a digital signature
of a password;
FIG. 8 is a flowchart diagram of yet another embodiment of the present
invention wherein a personal identification card is verified by the
cardholder's proof of possession of authorizing information such as a
valid signature.
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 according to
the present invention for effecting transactions via a transaction
terminal. As noted above, the term "personal identification card"
according to the present invention is to be read expansively and is deemed
to cover credit cards or other commonly known forms of identification such
as a passport, a driver's license, a membership card, an age
identification card, a security clearance card, a corporate identification
card, a national identification card, or the like.
Personal identification card 10 in FIG. 1 is a driver's license. Card 10
includes a body portion 12 having a display 14 and a memory 16. Although
not meant to be limiting, the memory 16 is preferably a magnetic stripe or
similar media, or an electronic memory such as a PROM, affixed to or
embedded in the card in a known manner. The personal identification card
may or may not include an integral microprocessor embedded in the body
portion. As seen in FIG. 1, the display 14 of the personal identification
card 10 supports a pictorial representation 18 of a physical
characteristic of the authorized user; e.g., the user's face. Of course,
the display 14 may also display pictorial representations of other
physical features of the user such as the user's fingerprint or palm
print.
Referring now to FIG. 1A, according to the present invention the memory 16
of the personal identification card 10 preferably includes a "password" 20
unique to the authorized user and having a portion 20a thereof which is
generated from a representation of some non-secret or "public"
characteristic of the user. As used herein, the term "non-secret" refers
to the fact that the representation of the authorized user, such as the
user's face, is readily ascertainable by viewing and comparing the
personal identification card and the authorized user directly. In the
preferred embodiment, the section 20a of the password is a digital
bitstream representing a digitized version of the pictorial representation
18 on the personal identification card 10.
As also seen in FIG. 1A, the password 20 may include a portion 20b having
data representing one or more personal facts about the authorized user
such as the user's age, address, nationality, security clearance,
employer, bank account balance, eye color, height, weight, mother's maiden
name, or any other such information. This information may or may not be
public. Moreover, the password 20 may further include a portion 20c having
one or more codewords, each of the codewords authorizing a specific
transaction such as permission to enter a country on a certain date,
permission to receive certain funds on a certain date, permission to
review certain classified documents, or one or more other such specific
transactions. Of course, the password 20 may include one or more of the
predetermined types of data, 20a, 20b, and/or 20c, shown in FIG. 1A.
As also seen in FIG. 1A, the memory 16 of the personal identification card
10 also includes a signature 22, which, as will be described in more
detail below, is derived from the password 20 using the private key of a
"public-key cryptosystem" key pair. A "public-key cryptosystem" is a well
known security scheme which includes two "keys," one key which is public
(or at least the key pair owner does not really care if it becomes public)
and one key which is private or non-public. All such public-key
cryptosystem pairs include a common feature -- the private key cannot be
determined from the public-key.
Referring now to FIG. 2, a general flowchart diagram is shown of the
preferred method of the present invention for issuing an authorized
personal identification card 10 such as shown in FIG. 1. At step 30, the
card issuer collects the necessary personal data from a card applicant.
Although not meant to be limiting, this data preferably includes a
pictorial representation of a physical characteristic of the authorized
user. For example, the data may include a photograph of the card
applicant. At step 32, the photograph, other personal data and/or code
authorizations are processed to generate a password as described above in
FIG. 1A.
At step 34, the password is mapped with a predetermined one way function
"F" to generate a mapped password "Q" which may have a length
substantially less than the length of the password. This "mapping" step is
typically required to reduce the length of the digital bitstream
comprising the password, especially when a digitized photograph of the
authorized user is stored therein. By way of example only, the
predetermined one-way function "F" may be any one or more of several
well-known, i.e., public, hashing functions such as one obtainable from
the DES scheme or the Goldwasser, Micali & Rivest scheme Alternatively,
the function "F" may be an identity function which simply transfers the
password through step 34 without modification. The identity function might
be used where the password length is sufficiently smaller than the
available storage capability of the memory 16.
At step 36, the method continues to "digitally sign" the mapped password
"Q" with a private key (P.sub.1,P.sub.2) of a public-key cryptosystem pair
to generate a so-called "signature". As will be described in more detail
below, in the preferred embodiment "P.sub.1 " and "P.sub.2 " are secret
prime numbers and the public-key cryptosystem pair includes a public-key
"M" which is equal to "P.sub.1 .multidot.P.sub.2 ". At step 38, the method
encodes the password (as opposed to the mapped password) and the signature
with an error-correcting code to generate an encoded password/signature.
Step 38 insures that the card 10 will be usable even if some of its data
is destroyed. At step 40, the encoded password/signature is stored on the
personal identification card in the manner substantially as shown in FIG.
1A.
Although not shown in detail in FIG. 2, it should be appreciated that the
card issuer may digitally sign one or more digital signatures on the card
10 at one or more different times using different public-key cryptosystem
pair keys. The card could then function as a passport with each signature
derived from a different cryptosystem key pair corresponding to a
different country (i.e., a visa). It may also be desirable in the method
of FIG. 2 to include an additional encryption step wherein the password is
encrypted with a predetermined function prior to the mapping step and/or
where the signature itself is encrypted. This enables the card to carry
information which is desired to be maintained highly confidential even if
the card were lost or stolen
Referring now to FIG. 3, a detailed flowchart diagram is shown of the
preferred digital signing routine of the present invention. As described
above, "M" is the public-key of the public-key cryptosystem and
(P.sub.1,P.sub.2) is the private key thereof. According to the routine,
the secret prime numbers "P.sub.1 " and "P.sub.2 " are selected at step 42
such that when the mapped password Q is multiplied by four predetermined
factors, .+-.1 modulo "M" and .+-.2 modulo "M," one and only one of the
resulting values .+-.Q mod M and .+-.2Q mod M is a quadratic residue
modulo "M". The security of the preferred digital signing routine is based
primarily on the fact that is it extremely difficult to compute the square
root of the quadratic residue modulo "M" without knowing the factorization
of M =P.sub.1 .multidot.P.sub.2.
Referring back to FIG. 3, at step 44 the mapped password "Q" is multiplied
by each of the factors .+-.1 mod M and .+-.2 mod M. The routine continues
at step 46 wherein each of the resulting values .+-.Q mod M and .+-.2Q mod
M are evaluated to locate the quadratic residue mod "M". When this value
is located, the routine computes the square root thereof at step 48 to
generate the digital signature.
Although not shown in detail, it should be appreciated that the private key
may include any number of secret prime numbers (P.sub.1,P.sub.2,P.sub.3, .
. P.sub.n). Preferably, the secret prime numbers are selected according to
the routine shown in FIG. 3A. At step 35, an n-bit random number "x.sub.1
" is generated. The number of bits "n" needs to be large enough (e.g., 250
bits) such that it is difficult to factor "M" At step 37, x.sub.1 is
incremented to be congruent to a predetermined value, e.g., "3 mod 8". At
step 39, a test is made to determine if x.sub.1 is prime. If so, then the
routine continues at step 41 by setting x.sub.1 =P.sub.1. If xl is not
prime, then x.sub.1 is incremented at step 43 (by setting x.sub.1 =x.sub.1
+8) and the routine returns to step 39. Once P.sub.1 is selected, the
routine continues at step 45 to generate another n-bit random number
"x.sub.2 ". At step 47, x.sub.2 is incremented to be congruent with a
second predetermined value, e.g., "7 mod 8". At step 49, a test is made to
determine if x.sub.2 is prime. If so, then the routine continues at step
51 by setting x.sub.2 =P.sub.2. If x.sub.2 is not prime, then x.sub.2 is
incremented at step 53 (by setting x.sub.2 =x.sub.2 +8) and the routine
returns to step 49. Once P.sub.2 is selected the public-key "M" is set
equal to P.sub.1 .multidot.P.sub.2 at step 55.
It is also desirable to store P.sub.1 and P.sub.2 in the issuing terminal
responsible for computing signatures. Moreover, it is possible to
distribute the private key (P.sub.1,P.sub.2) from one terminal to another
without any person being able to discern the key by using another
public-key cryptosystem pair (for which the private key is known only to
the receiving terminal). Moreover, while the digital signing routine of
FIG. 3 is preferred, other schemes, such as RSA, the Goldwasser, Micali &
Rivest scheme and/or the Rabin scheme, may be used. Such schemes may also
require knowledge of the public-key, although the | | |
