Method and Means for Providing and Testing Secure Identification Data

Identification media such as plastic credit cards and debit cards have become widely employed in commerce, particularly in retail and financial systems, for the purpose of positively and accurately identifying to the system the legitimacy of the card to enable the holder of the card to consummate a desired transaction. In many instances, a magnetic stripe has been incorporated into the card to permit various categories of customer and account information to be read from and optionally written on the card by suitable electronic equipment associated with the system.

The ease of reading from and writing on the magnetic stripe has become a source of fraud in debit and credit card usage. Without great effort or extensive knowledge of the system, a criminal can counterfeit or duplicate a card, and the data stored on the magnetic stripe of the card can be altered, to allow fraudulent access to the system. Various ways of producing counterfeit cards or altering magnetic stripe information on legitimate cards have been well documented in the literature.

In order to thwart the possibility of such criminal actions which could result in substantial financial loss to the proprietors of the systems with which the cards are used, the concept of a "secure" card has been introduced. Secure card techniques may rely upon the incorporation of permanent physical uniqueness data in the structure of a card, with said data not being subject to alteration, so that one card may be distinguished from another by sensing of this physical data. In order to avoid excessive complications in card manufacture and distribution, it is highly desirable that this uniqueness data be independent of customer-related information, such as an account number. Incorporating the account number into the uniqueness data, for example, would seriously disrupt present card manufacturing and distribution practices. With the uniqueness information independent of the customer-related information, it then becomes important from the requirement of positive and accurate card validity determination to provide a verification means which encompasses both the uniqueness information and the customer-related information.

The purpose of the present invention is to provide a method and means for combining the uniqueness data and the customer-related data on a customer identification medium in such a manner as to deter improper or unauthorized use of an identification medium such as a plastic credit or debit card without excessively complicating the manufacture, distribution and usage of the identification medium.

In carrying out the method, the uniqueness information is incorporated into the physical structure of the card at the time of its manufacture. A number of known means are available by which uniqueness information can be permanently encoded into the structure of a card. One suitable means involves the use of diffraction grating encoding means, and is disclosed in the co-pending U.S. application Ser. No. 588,937, filed June 20, 1975, and assigned to the assignee of the present application.

Customer identification information, such as a customer account number, is recorded on a magnetic stripe on the card, as is an additional number, hereinafter referred to as a security number, which is derived from both the uniqueness information and the customer identification information. This derivation is accomplished by a method involving the use of a novel algorithm. Means for implementing the algorithm are provided.

The value of the security number is recorded on the card at the time of the initial encoding process. Subsequently, when the card is used, the values of the account number, the uniqueness quantity, and the security number will be sensed from the card. The account number and the uniqueness quantity will again be processed by the means embodying the algorithm to generate a security number for comparison with the security number which has been sensed from the card. If the numbers do not match, the card will be rejected as possibly counterfeit, and the transaction will not be allowed to proceed. If desired, the rejection of the card may be accompanied by appropriate means such as locking up of the system utilizing the card, capture of the card by the system, or initiation of an alarm indication, such as a visual or audible signal to alert the operator of the system to the presence of an illegitimate card.

According to one embodiment of the invention, a method for testing the legitimacy of an identification element comprises the steps of sensing at least three categories of information from said identification element, performing a mathematical operation utilizing at least two of said categories of information, and comparing the result of said mathematical operation with another of said categories of information.

According to a second embodiment of the invention, apparatus for testing the legitimacy of an identification element comprises sensing means for sensing first, second and third categories of information from said identification element, first storage means for storing the first category of information sensed from the identification element, second storage means for storing the second category of information sensed from the identification element, third storage means for storing the third category of information sensed from the identification element, information processing means to generate output data from a specified sequence of operations performed upon said first and second categories of information transmitted to said information processing means from said first and second storage means, and comparison means for comparing said output data with said third category of information transmitted from said third storage means and capable of indicating whether or not said output data and said third category of information are identical.

According to a third embodiment of the invention, a method of generating a security number from first and second numerical quantities comprises the steps of a) decreasing the length of the longer of the first and second numerical quantities to that of the shorter numerical quantity, b) multiplying each of the numerical quantities of step (a) by a constant, c) permuting each of the numerical quantities of step (b) to change the order of elements making up said numerical quantities, and d) combining the numerical quantities produced by step (c) by means of selected ones of a plurality of available functions.

According to a fourth embodiment of the invention, apparatus for generating a security number from first and second data representations comprises means for making the length of the two data representations equal, means for multiplying each of the two equal-length data representations by a constant to produce two data products, means for permuting in an arbitrary manner the order of the individual elements of the two data products to produce two permuted data products, and means for combining the two permuted data products by a plurality of available functions to provide a security number derived from said first and second data representations.

It is accordingly an object of the present invention to provide a method for testing the legitimacy of an identification element.

Another object is to provide apparatus for testing the legitimacy of an identification element.

Another object is to provide a method for generating a security number from first and second quantities.

A further object is to provide a method of generating a security number from a represented account number and a represented uniqueness number.

Still another object is to provide apparatus for generating a security number from first and second numerical quantities.

With these and other objects, which will become apparent from the following description, in view, the invention includes certain novel features and combinations of parts, a plurality of forms or embodiments of which are hereinafter described with reference to the drawings which accompany and form a part of this specification.

FIG. 1 is a diagrammatic representation of a credit card or other identification medium having two information bearing tracks positioned in operative relation to corresponding sensing and/or recording means.

FIG. 2 is a block diagram of a system for testing the legitimacy of a credit card or other identification medium.

FIG. 3 is a block diagram of a system for generating a security number from two quantities such as customer identification data and uniqueness data.

Referring now to FIG. 1, there is shown an identification medium, such as a credit card 10, having thereon a first stripe 12 and a second stripe 14, both capable of storing information therein. It will be recognized that different numbers and arrangements of stripes or code-bearing areas on the card may be employed, and that various materials and encoding means may be used for the stripes or areas. In the illustrated embodiment, the stripe 12 is a magnetic stripe, wherein information may be recorded or erased and from which information may be sensed. Stripe 14, on the other hand, stores information permanently, so that there can be no erasure or re-recording of information. As mentioned previously, one suitable structure for this stripe involves the use of diffraction grating encoding means, and is disclosed in the previously mentioned co-pending United States application Ser. No. 588,937, filed June 20, 1975, and assigned to the assignee of the present application.

Shown in FIG. 1 as co-acting with the magnetic stripe 12 is a magnetic read-write head 16, capable of sensing information encoded on the stripe 12 and, where appropriate, of erasing said information and recording other information in its place. It may be noted, however, that for the purpose of the present invention, there is no need for the erasing or recording capability of the head 18, except in the case of the original encoding of the card 10 with the security number.

In the illustrated embodiment of FIG. 1, the information to be carried on the stripe 12 includes a customer account number and/or other customer-related data and a security number which is derived from a combination of the customer-related number with another quantity, as will subsequently be described. Other information may also be included on this stripe, but is not pertinent to the present invention.

Shown as co-acting with the diffraction grating stripe 14 is a reading head 18 which may be of the general type disclosed and claimed in the previously mentioned co-pending U.S. application Ser. No. 588,937. Another type of reading head which may be employed when a multiple diffraction grating is utilized in the stripe 14 is shown in the co-pending U.S. application Ser. No. 611,378, filed Sept. 8, 1975, and assigned to the assignee of the present application.

The information to be carried on the stripe 14 is what will be referred to herein as a uniqueness number. This number is incorporated into the physical structure of the card 10 at the time of its manufacture. To avoid complications in the manufacture and distribution process, the uniqueness number must be independent of any customer-related data, such as the customer account number. The uniqueness number will vary from card to card but is completely independent of customer-related data.

As is well known, heads 16 and 18 are capable of sensing information from the stripes 12 and 14 when the stripes are placed in close proximity to the heads and when relative movement between the stripes and the heads is provided. Recording is accomplished in a similar manner, in the case of the magnetic stripe 12 and its corresponding head 16.

Shown in FIG. 2 is a schematic diagram illustrating one manner in which the information stored in the stripes 12 and 14 is utilized to determine the legitimacy of the card 10. As mentioned previously, both a customer number or other customer-related data and a security number are stored in the stripe 12, while a uniqueness quantity is stored in the stripe 14. Reading of the card 10 by the heads 16 and 18 causes the information sensed from the stripe 12 to be stored in a storage register 20 and also causes the information sensed from the stripe 14 to be stored in a storage register 22. The storage register 20 is effectively divided into two sections 24 and 26, so that the customer number or other customer-related data sensed from the stripe 12 is stored in the section 24, while the security number sensed from the stripe 12 is stored in section 26.

Both the customer number or other data stored in the section 24 of the register 20 and the uniqueness quantity stored in the register 22 are input into an algorithm processor 28, shown as a single block in FIG. 2. The operation of one form of algorithm processor will subsequently be described in detail, but it will suffice for the present time to say that the customer number or other data and the uniqueness quantity are combined in accordance with a predetermined mathematical relationship in the algorithm processor 28 to produce a security number which is transmitted over a conductor 30 to one of two inputs to a comparator 32. A branch 34 extending from a conductor 30 between the processor 28 and the comparator 32 provides an output from which the security number generated by the algorithm processor 28 may be taken for connection to a recording head for recording a security number on a new card, or for other suitable purpose. The other input to the comparator 32 is taken directly over a conductor 36 from the section 26 of the storage register 20, which, it will be recalled, stores the security number sensed from the track 12 of the card 10.

The comparator 32 is of a well-known type capable of comparing the information appearing at each of its two inputs, and of providing a signal at its output 38 to indicate whether or not the security number sensed from the card 10 is identical to that generated in the algorithm processor 28 from the customer number or other data and the uniqueness quantity which are also sensed from said card. The signal at the output 38 can then be used in any desired manner to indicate whether or not the desired identity between the two quantities exists. For example, in the case of a failure of identity, the machine in which the card is being used may be rendered incapable of further functioning; or the card may be captured by the machine; or some type of audible, visual or other alarm indication may be given.

It is essential that customer-related data, such as a customer account number, be included as an input parameter for the algorithm processor 28. If such customer-related data is not included, a criminal could employ a process known as "selective skimming" in order to gain unauthorized access to accounts other than his own. In selective skimming, a typical procedure would be for a criminal to copy the account number and other appropriate data from a stolen card onto his own legitimate card by means of an easily constructed magnetic recording device. The significance of "selective" skimming is that the criminal would not alter the area on the track 12 containing the security number. He would then have a duplicate of the stolen card, except that the uniqueness number and the security number would be unchanged from their original values. If the security number generated by the checking algorithm were generated solely from the uniqueness number, the fraudulent card would still pass the security test. A significant feature of the present invention therefore is the implementation of an algorithm which incorporates customer-related data, such as an account number, as an essential input to the security number algorithm. Customer-related data other than the account number may of course be utilized if desired.

One suitable algorithm which may be employed for mapping of an account number or other customer-related data and a uniqueness quantity is implemented in the system 48 schematically shown in FIG. 3. It will be realized that many different types of mathematical operations and combinations thereof may be employed to produce a security number derived from a combination of customer data such as an account number and a uniqueness number. Thus the system 48 of FIG. 3 is only one of many forms which the algorithm processor 28 of FIG. 2 may take. This system may be implemented in any one of several ways, such as by the use of discrete units for each of the various functional blocks set forth, or by the use of suitably programmed data processing equipment.

The system 48 of FIG. 3 includes two code converters 50 and 52 for converting encoded information on the card 10 to digital information. This process may also be termed decimal association, in that the data encoded in whatever form may be suitable on the card in each case is associated with a specified decimal number which is thereafter employed in the process taking place in the system of FIG. 3 for generation of a security number. The converter 50 is designed to convert magnetically coded information, which in the illustrated embodiment shall be considered to be customer account information, from the stripe 10 to a number, in a well-known manner and the converter 52 is designed to convert data, which is the illustrated embodiment shall be considered to be uniqueness information, sensed from the diffraction grating stripe 14, to a number in a suitable manner such as is shown, for example, in the previously mentioned U.S. application Ser. No. 588,937.

The output from the converter 50 is connected to the input of a contraction means 54, which is capable of contracting the length of the account number sensed from the stripe 12 to a length of "K" digits, equal in length to the "K" digit length of the uniqueness number sensed from the stripe 14. Normally, the account number contains more digits than the uniqueness number, but if the converse were true, it is obvious that the uniqueness number, rather than the account number, could be contracted. The contracting means 54 essentially comprises an adder, which enables it to perform the desired mathematical operations to produce the desired contraction, as will subsequently be described.

The output of the contraction means 54 is applied to one input of an arithmetic processor 56, the other input of which is connected to a terminal 60, to which is applied a selected constant, with which the contracted account number from the means 54 is combined, in a multiplication operation, as subsequently defined. Similarly the output from the converter 52 is applied to one input of a second arithmetic processor 58, the other input of which is connected to a terminal 62, to which is applied a second selected constant, with which the uniqueness number from the converter 52 is combined, in a multiplication operation, as subsequently defined.

The outputs of the arithmetic processors 56 and 58 are applied to permutators or shufflers 64 and 66, respectively. In each of these shufflers, cross-connections are made so that the order of the individual digits of the account number and the uniqueness number is shuffled or permutated, in a well-known manner.

The individual digit outputs from the shufflers 64 and 66 are then applied to inputs of an arithmetic logic processor 68, in which various arithmetic or logical operations, which may be generically referred to as mathematical operations, can be performed upon each of the digital outputs from the shufflers 64 and 66, according to a predetermined scheme, to provide a further manipulation, combination or alteration of the digits derived from the account number and the uniqueness number. Certain of the components within the arithmetic logic processor 68 which perform the desired functions are indicated by reference characters 70, 72 and 74, which components are shown as operating upon combinations of digit outputs from the shufflers 64 and 66. The components 70, 72 and 74 are merely representative, and do not represent all of the functions which could be performed in the arithmetic logic processor 68. The components 70, 72 and 74 could, if desired, each take the form of a suitable integrated circuit chip, such as the SN74LS181 four-bit arithmetic logic unit/function generator manufactured by Advanced Micro Devices Inc. for example.

Outputs from the various components of the arithmetic logic processor 68 are then applied to a compression means 76, comprising a gating network which may, for example, essentially comprise a plurality of exclusive OR gates which function to reduce the total number of digits applied thereto from the arithmetic logic processor 68 to a number which can conveniently be recorded on the stripe 12 as the security number, and which appears on the output 78 of the compression means 76.

The algorithm which is implemented in the system of FIG. 3 will now be described in terms of a series of steps which correspond generally to the various blocks shown in FIG. 3. This algorithm has been devised for mapping the account number A and the uniqueness number U into the security number S. Typically there are 8 to 19 digits in the account number A; 8 to 12 digits in the uniqueness number U and 5 to 8 digits in the security number S. Therefore, in general, there will be numerous combinations of A and U which will be mapped onto each possible value of S.

This algorithm was developed primarily for use with the credit card uniqueness feature, and the notation adopted is appropriate for this application. Other applications of the basic algorithm are possible, however, such as error checking for data communication or testing of passwords for access to secure facilities. For this reason, the following description of the algorithm will be stated in general mathematical terms.

Situations exist which require that the elements from two primary sets A and U be mapped into the members of a secondary set S. The set of possible combinations of elements of A with elements of U, in general, will far exceed the number of elements in S, so that many possible combinations of A and U will be mapped into each value of S. An algorithm is required to define the mapping procedure. It should be sufficiently complex so that a criminal could not reconstruct the algorithm from a small or medium size sample of encoded cards.

The mapping proceeds in six steps as outlined below, with reference to the various blocks shown in FIG. 3.

With each element in the set A, associate a unique decimal number A which is L digits in length. Choose L such that 10.sup.L is greater than the number of elements in set A. Similarly, associate a unique K-digit number with the elements of U, such that 10.sup.K is greater than the number of elements in set U.

In the simplest case, where the elements of A and U are decimal integers, this step is unnecessary. In other cases a binary-to-decimal conversion may be required. In the general case (where possibly A or U consists of alphanumeric data), any appropriate mapping of the elements of the primary sets into decimal integers may be chosen. The result of this decimal association process will be an L-digit decimal number A and a K-digit decimal number U.

If K .noteq. L, it is necessary to decrease the length of the longer number to match that of the smaller number. Assume without loss of generality that L > K. Then generate from A (the L-digit number) a K-digit number A'.

If A = a.sub.L . . . a.sub.K+1 a.sub.K . . . a.sub.2 a.sub.1

then A' = a'.sub.K a'.sub.K-1 . . . a'.sub.2 a'.sub.1

where

with a.sub.i = 0 for i>L

If K>L, then the contraction process would be applied in a similar manner to the number U, rather than to A.

In Step 3, the digits in A' and U are multiplied by a set of selected constants in order to complicate any attempt to decipher the algorithm. The result will be a mapping of A' into X and U into Y. The multiplication is expressed mathematically as

X = K least significant digits of ##EQU1##

Y = K least significant digits of ##EQU2## where a'.sub.i = the digits of A'

u.sub.i = the digits of U

c.sub.i, d.sub.i = randomly selected digits chosen from the set [1, 3, 7, 9]

The selection of the c's and d's is arbitrary, but it is important that they be restricted to the set [1, 3, 7, 9]. If other integers are used then it will frequently happen that two different values of A (or U) will yield the same values for X (or Y), which is undesirable.

Alternatively, step 3 could be implemented by the equations.

This reduces the security of the algorithm slightly, but would be much easier to implement.

To further protect the algorithm from deciphering, the order of the digits of X and Y are permuted in an arbitrary manner. This generates new values, X' and Y', with the same digits as X and Y, but arranged in a different order.

In step 5 the digits in X' and Y' are combined arithmetically and/or logically. The procedure is to select (with replacement) a set of K functions, .theta..sub.1 through .theta..sub.K, from the following list, which is merely representative, since many other functions could be chosen if desired:

+ addition

- subtraction

V exclusive OR

V exclusive OR, result complemented

V logical OR

V logical OR, result complemented

.LAMBDA. logical AND

.LAMBDA. logical AND, result complemented

Corresponding digits of X' and Y' are then used as inputs to these functions to produce K digits, z.sub.1 through z.sub.K, where

For example, if .theta..sub.3 is V, then

The logical operations described immediately above are performed on the individual bits of the binary coded decimal representation of the numeric digits. Arithmetic operations which result in negative numbers will be expressed in two's complement form, truncated to the four least significant bits. The result of step five will be K digits, z.sub.1 through z.sub.k, which are a thoroughly encrypted combination derived from the account number A and the uniqueness number U. Note that it is possible that some of the z.sub.i 's will no longer be valid binary coded decimal characters. This will be corrected as part of step 6.

The final step is to reduce the K digits, z.sub.1 through z.sub.k, to a number S which can be recorded on the magnetic stripe, where S = s.sub.J s.sub.J-1 . . . s.sub.2 s.sub.1. This will be accomplished by exclusive-ORing selected z.sub.i 's and changing the high order bit to zero whenever an invalid binary coded decimal character is generated. If S is to be J digits long, the operation is accomplished according to the following equations.

with z.sub.i = 0 for i>K

If any of the s.sub.i are not valid binary coded decimal numbers, the high order bit is changed to zero.

The six steps described above constitute the process for deriving the J-digit value of S from the L-digit number A and the K-digit number U. The procedure was segmented into six steps for clarity of explanation. In actual practice adjacent steps may be conveniently combined for simplicity of implementation.

For purposes of illustration, assume

and that S is to be 2 digits long. (In actual applications, the length of the numbers will normally be much longer). We further assume that the following user-determined parameters have been selected to implement the algorithm.

We now proceed to derive S from this data.

Step 1 is not required since A, U, and S are decimal integers.

Since L>K, the 5 digit account number A must be shortened to 3 digits as described previously. Following the equations given previously

where

Therefore A' = 872

X = 3 least significant digits of ##EQU3##

Given the permutation sequence set forth above for X' and Y', X' becomes 882 (from 828) and Y' becomes 524 (from 254).

The final step is to reduce the three z.sub.i 's to a 2 digit value for S.

this completes the sample derivation of a two-digit value for S from a five-digit account number A, and a three digit uniqueness number U.

Security is a critical problem in any encryption procedure. The non-linearities inherent in modulo 10 arithmetic and logical operations make it highly improbable that any simplified algorithm could produce equivalent results. Even if a criminal were aware of the basic procedure employed, he would still need to determine the values of the arbitrary parameters c.sub.i, d.sub.i, and .theta..sub.i, as well as the permutation sequence used in Step 4. The number of possible patterns can be calculated from the data illustrated in table 1.

Multiplying these factors together shows that there are

possible choices for the parameters. For K=15, for example, this yields a total of approximately 10.sup.55 different implementations of the algorithm. This would make any attempt at deciphering a formidable task.

As explained earlier, the procedure described above is used to generate the value for S when the card is originally encoded, and is also used to generate the test value appearing on conductor 30 whenever the card is used. As shown in FIG. 2, the value S is read from the card and compared, digit by digit, to the value of S' as generated by the algorithm. If the two values match, the financial transaction will be permitted to continue. If a mismatch occurs, the financial transaction will not be allowed to proceed, and at the discretion of the financial institution, the card may be captured as potentially counterfeit.

The algorithm has been discussed primarily with respect to applications in card uniqueness systems. Other applications are possible, however, whenever the members of two distinct sets A and U are to be mapped into the elements of a smaller set S.

The algorithm can also be applied to mapping of a single large set A into a small set S. This could be accomplished by one of two methods. One alternative would be to choose an arbitrary constant value for U, and follow the same procedure outlined earlier. Another alternative would be to divide the digits of the L-digit number A into two segments, one segment K digits long and the other segment (L-K) digits. The first segment would be treated as "U" and the second as "A", and the same mapping procedure could be employed.

While the forms of the invention illustrated and described herein are particularly adapted to fulfill the objects aforesaid, it is to be understood that other and further modifications within the scope of the following claims may be made without departing from the spirit of the invention.