Abstract:
A protocol appropriate for smartcard purchase applications such as those that might be completed between a terminal or ATM and a users personal card is disclosed The protocol provides a signature scheme which allows the card to authenticate the terminal without unnecessary signature verification which is an computationally intense operation for the smart card. The only signature verification required is that of the terminal identification (as signed by the certifying authority, or CA, which is essential to any such protocol). In the preferred embodiment, the protocol provides the card and terminal from fraudulent attacks from impostor devices, either a card or terminal.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    The present application is a continuation of U.S. patent application Ser. No. 09,360,575 flied on Jul. 26, 1999 which is a continuation of U.S. patent application Ser. No. 08/790,545 filed on Jan. 30, 1997 and issued as U.S. Pat. No. 5,955,717, and claims priority from United Kingdom Patent Application No. 9601924.5 filed on Jan. 31, 1996, the contents of which are hereby incorporated by reference. 
     
    
     FIELD OF THE INVENTION 
       [0002]    The present invention relates to methods and apparatus for verifying the authenticity of partners in an electronic transaction. 
       BACKGROUND OF THE INVENTION 
       [0003]    It has become widely accepted to conduct transactions such that as financial transactions or exchange of documents electronically. In order to verify the transaction, it is also well-known to “sign” the transaction digitally so that the authenticity of the transaction can be verified. The signature is performed according to a protocol that utilizes the message, i.e., the transaction, and a secret key associated with the party. Any attempt to tamper with the message or to use a key other than that of the signing party will result in an incompatibility between the message and the signature or will fail to identify the party correctly and thereby lead to rejection of the transaction. 
         [0004]    The signature must be performed such that the parties&#39; secret key cannot be determined. To avoid the complexity of distributing secret keys, it is convenient to utilize a public key encryption scheme in the generation of the signature. Such capabilities are available where the transaction is conducted between parties having access to relatively large computing resources but it is equally important to facilitate such transactions at an individual level where more limited computing resources are available. 
         [0005]    Automated teller machines (ATMs) and credit cards are widely used for personal transactions and as their use expands, so the need to verify such transactions increases. Transaction cards are now available with limited computing capacity, so-called “Smart Cards,” but these are not sufficient to implement existing digital signature protocols in a commercially viable manner. As noted above, in order to generate a digital signature, it is necessary to utilize a public key encryption scheme. Most public key schemes are based on the Diffie Helman Public key protocol and a particularly popular implementation is that known as DSS. The DSS scheme utilizes the set of integers Zp where p is a large prime. For adequate security, p must be in the order of 512 bits although the resultant signature may be reduced mod q, where q divides p−1, and may be in the order of 160 bits. 
         [0006]    The DSS protocol provides a signature composed of two components r, s. The protocol requires the selection of a secret random integer k from the set of integers (0, 1, 2, . . . q−1), i.e. 
         [0000]        kε{ 0, 1, 2, . . .  q− 1). 
         [0000]    The component r is then computed such that 
         [0000]        r={β   k mod  p }mod  q    
         [0000]    where β is a generator of q.
 
The component s is computed as
 
         [0000]        s=[k   −1 ( h ( m ))+ ar] mod q         where m is the message to be transmitted,
           h(m) is a hash of the message, and   a is the private key of the user.   
                 
         [0010]    The signature associated with the message is then sr which may be used to verify the origin of the message from the public key of the user. 
         [0011]    The value of β k  is computationally difficult for the DSS implementation as the exponentiation requires multiple multiplications mod p. This is beyond the capabilities of a “Smart Card” in a commercially acceptable time. Although the computation could be completed on the associated ATM, this would require the disclosure of the session key k and therefore render the private key, a, vulnerable. 
         [0012]    An alternative encryption scheme that provides enhanced security at relatively small modulus is that utilizing elliptic curves in the finite field 2 m . A value of m in the order of 155 provides security comparable to a 512 bit modulus for RSA and therefore offers significant benefits in implementation. Diffie Hellman Public Key encryption utilizes the properties of discrete logs so that even if a generator β and the exponentiation β k  are known, the value of k cannot be determined. 
         [0013]    A similar property exists with elliptic curves where the addition of two points on a curve produces a third point on the curve. Similarly, multiplying a point by an integer k produces a point on the curve. 
         [0014]    However, knowing the point and the origin does not reveal the value of the integer ‘n’ which may then be used as a session key for encryption. The value kP, where P is an initial known point, is therefore equivalent to the exponentiation β k . 
         [0015]    Elliptic Curve Cryptosystems (ECC) offer advantages over other public key cryptosystems when bandwidth efficiency, reduced computation, and minimized code space are application goals. 
       SUMMARY OF THE INVENTION 
       [0016]    The preferred embodiment of the present invention discloses a protocol optimized for an ECC implementation for use with a “smartcard” having limited computing capacity. The protocol has been found to provide superior performance relative to other smartcard protocols and is achievable with an ECC implementation. 
         [0017]    The protocol disclosed is appropriate for smartcard purchase applications such as those that might be completed between a terminal or ATM and a user&#39;s personal card. The protocol provides a signature scheme which allows the card to authenticate the terminal without unnecessary signature verification which is a computationally intense operation for the smart card. The only signature verification required is that of the terminal identification (as signed by the certifying authority, or CA, which is essential to any such protocol. In the preferred embodiment, the protocol protects the card and terminal from fraudulent attacks from impostor devices, either a card or terminal. 
         [0018]    A method of performing a transaction between a first and a second participant wherein the second participant permits a service to be provided to the first participant in exchange for a payment. The method comprising the steps of the first participant verifying the legitimacy of the second participant to obtain assurance that the service will be provided upon payment, the second participant verifying the legitimacy of the first participant to obtain assurance that payment will be secured upon provision of the service, and the second participant obtaining a digital signature for the first participant on the transaction whereby the second participant may obtain payment from a third participant. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS  
         [0019]    An embodiment of the invention will now be described by way of example only with reference to the accompanying drawings, in which: 
           [0020]      FIG. 1  is a diagrammatic representation of a scanning terminal and personal transaction card; and 
           [0021]      FIG. 2  is a chart that schematically illustrates the protocol. 
       
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0022]    Referring therefore to  FIG. 1 , a scanner terminal  10  has an inductive coupling  12  to cooperate with a card  14 . When a card  14  is passed through the inductive coupling  12  a transaction is recorded within a memory  16  on the card  14 . Typically the transaction will debit the card with a set amount, e.g., an admission price, and the terminal  10  is credited a corresponding amount. The terminal is connected through a network to a central computer located at a financial institution that maintains records of transactions in a conventional manner. 
         [0023]    To avoid fraudulent transactions being recorded at either the card or terminal the protocol shown in  FIG. 2  is utilized. 
         [0024]    Upon the scanner sensing the card through coupling  12 , a unique purchase I.D. (PID) is generated by the terminal  10 . The terminal  10  has a private key, t, stored in a secure location and a corresponding public key Y t  equal to α 1 . The terminal  10  generates a message, M 1 , consisting of the purchase I.D. PID and the transaction amount, TA. It also appends to the message M 1  a certificate signed by the certifying authority CA that includes terminal identification information TIU ID and the public key Y 1 . The message M 1  is received by the card  14 . 
         [0025]    Card  14  has a private key a stored securely in memory  16  and a public key Y c  equal to α a  (α is the generator point for the curve). The card verifies the terminals certificate as signed by the certifying authority CA according to a normal elliptic curve scheme. Having verified the certificate, the card generates a pair of random numbers R 2  and R 3  and signs the unique purchase I.D. PID using the terminals public key according to an established protocol. 
         [0026]    To effect signing, the card generates a random integer k and computes a session parameter α k . It also computes Y t   k  and generates signature components r 1  and s 1 . 
         [0027]    The component r 1  is provided by M2Y l   k , mod L where:
       M 2  is the message TA//TIU ID//R 2 /PID, and   L=2 l −1 and l is an integer greater than or equal to the number of bits in M 2 . (//signifies concatenation).       
 
         [0030]    The component s 1  is provided by h=a+k mod q where:
       q is the order of the curve and   h is a hash h(M 2 //α k //R 3 ).       
 
         [0033]    The card now sends signature components r 1 , s 1  the hash h and a certificate issued by the certifying authority CA containing its ID and public key to the terminal  10 . 
         [0034]    The terminal verifies the cards credentials as signed by the CA. Given the hash h and s 1  it can calculate the value α k1  and thereby recover the message M 2  from r 1  using the cards public key. As the message M 2  includes the PID, the terminal is able to verify the authenticity of the card  10 . 
         [0035]    The recovered message includes R 2  which is then returned to the card  10  to prove that the terminal is extracting R 2  in real time, i.e., during the transit of the card through the coupling  12 , using its private key. This also prevents a reply attack by the terminal  10 . 
         [0036]    The receipt of R 2  also serves to acknowledge provision of the service. Upon receipt, the card checks R 2  to ensure the message was recovered using the terminals private key. This confirms that the card was talking to the terminal rather than a fraudulent device which would not have the private key, t, available. 
         [0037]    If the card confirms the receipt of R 2 , it transmits the random R 3  to the terminal  10  to complete the transaction. R 3  is required for card signature verification by the bank and so R 3  is retained by the terminal  10  for central processing purposes. R 3  is not released by the card until it has received R 2  which confirms that the terminal  10  is performing computations in real time. 
         [0038]    The terminal  10  is required to submit to the financial institution the stored values of R 2 , R 3 , TA, PID, TIU ID, s 1  and α k  in addition to the credentials of both card and terminal  10 . With this information the bank card is able to reproduce hash h, i.e. h(M 2 //α k //R 3 ) by using the cards public key Y c  to prove that the transaction was authentic. 
         [0039]    It will be noted that the last two passes are essentially trivial and do not require computation. Accordingly the computation required by the card is minimal, being restricted to one verification and one signature that involves two exponentiations, with the balance avoiding computationally intense operations. 
         [0040]    As indicated in  FIG. 2 , an ECC implementation is the field 2 155  using an anomalous curve of this protocol would result in less bandwidth (1533 bits) and reduced computation for the smartcard (31,000 clock cycles). The computational savings over previous protocols are possible due to features of the elliptic curve signature scheme used by the smartcard. 
         [0041]    The particular benefits and attributes may be summarized as:
       1. The purchase identifier PID is unique and is required to prevent terminal replay to the bank. If the purchase identifier is not unique, a random number R 1  will also be required to provide the equivalent of the PID.   2. The random bit string R 2  is required to prevent replay to the card.   3. A hash function (h) such as the SHA 1  is required to prevent modification of the message (m) and the terminal&#39;s identification (TIU ID).   4. There appears to be no advantage to having the transaction amount signed by the terminal, resulting in one less signature verification for the card. The reason for this is that the message signed by the card contains a random number R 2  which can only be recovered by the terminal.   5. Using this scheme, the message m may only be recovered by the terminal (note the terminal&#39;s public key is used in step III therefore requiring the terminal&#39;s private key to verify and recover contents). By demonstrating to the card that the random string (R 2 ) was obtained from the message, the terminal can be authenticated to the card.