Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Particular communication authentication technique
Reexamination Certificate
1998-02-02
2001-01-23
Swann, Tod R. (Department: 2766)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
Particular communication authentication technique
C380S043000, C380S259000, C380S283000, C380S285000, C705S067000, C713S168000, C713S172000, C713S176000, C713S180000
Reexamination Certificate
active
06178507
ABSTRACT:
This invention relates to methods and apparatus for data transfer and authentication in an electronic transaction system, and more particularly to electronic transaction systems utilizing smart cards.
BACKGROUND OF THE INVENTION
It has become widely accepted to conduct transactions such as financial transactions or exchange of documents electronically. Automated teller machines (ATMs) and credit cards are widely used for personal transaction and as their use expands so too does the need to verify such transactions increase. A smart card is somewhat like a credit card and includes some processing and storage capability. Smart cards are prone to fraudulent misuse, for example by a dummy terminal which is used to glean information from an unsuspecting user. Thus, before any exchange of critical information takes place between either a terminal and a smart card or vice versa it is necessary to verify the authenticity of the terminal as well as the card. One of these verifications may take the form of “signing” an initial transaction digitally so that the authenticity of the transaction can be verified by both parties involved in the subsequent session. The signature is performed according to a protocol that utilizes a random message, i.e. the transaction and a secret key associated with the party.
The signature must be performed such that the party's 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 available, as in the smart card.
Transaction cards or smart cards are now available with limited computing capacity, but these are not sufficient to implement existing digital signature protocols in a commercially viable manner. As noted above, in order to generate a verification signature it is necessary to utilize a public key inscription scheme. Currently, most public key schemes are based on RSA, but the DSS and the demand for a more compact system are rapidly changing this. The DSS scheme, which is an implementation of a Diffie-Hellman public key protocol, utilizes the set of integers Z
p
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.
An alternative encryption scheme which was one of the first fully fledged public key algorithms and which works for encryption as well as for digital signatures is known as the RSA algorithm. RSA gets it security from the difficulty of factoring large numbers. The public and private keys are functions of a pair of large (100 to 200 digits or even larger) of prime numbers. The public key for RSA encryption is n, the product of the two primes p and q where p and q must remain secret and e which is relatively prime to (p−1)×(q−1). the encryption key d is equal to e
−1
(mod(p−1)×(q−1)). Note that d and n are relatively prime.
To encrypt a message m, first divide into a number of numerical blocks such that each block is a unique representation modulo n, then the encrypted message block c
i
is simply m
i
c
(mod n). To decrypt a message take each encrypted block c
i
and compute m
i
=c
i
d
(mod n).
Another 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 DSS and therefore offers significant benefits in implementation.
Diffie-Hellman public key encryption utilizes the properties of discrete logs so that even if a generator &bgr; and the exponentiation &bgr;
k
is known, the value of k cannot be determined. A similar property exist with elliptic curves where the addition of two points on any curve produces a third point on the curve. Similarly, multiplying a point P on the curve by an integer k produces a further point on the curve. For an elliptic curve, the point kP is simply obtained by adding k copies of the point P together.
However, knowing the starting point and the end point does not reveal the value of the integer k 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 &bgr;
k
. Furthermore, elliptic curve crypto-systems offer advantages over other key crypto-systems when bandwidth efficiency, reduced computation and minimized code space are application goals.
Furthermore, in the context of a smart card and an automated teller machine transaction, there are two major steps involved in the authentication of both parties. The first is the authentication of the terminal by the smart card and the second is the authentication of the smart card by the terminal. Generally, this authentication involves the verification of a certificate generated by the terminal and received by the smart card and the verification of a certificate signed by the smart card and verified by the terminal. Once the certificates have been positively verified the transaction between the smart card and the terminal may continue.
Given the limited processing capability of the smart card, verifications and signature processing performed on the smart card are generally limited to simple encryption algorithms. A more sophisticated encryption algorithm is generally beyond the scope of the processing capabilities contained within the smart card. Thus, there exist a need for a signature verification and generation method which may be implemented on a smart card and which is relatively secure.
SUMMARY OF THE INVENTION
This invention seeks in one aspect to provide a method of data verification between a smart card and a terminal.
In accordance with this aspect there is provided a method for verifying a pair of participants in an electronic transaction, comprising the steps of verifying information received by the second participant from the first participant, wherein the verification is performed according to a first signature algorithm; verifying information received by the first participant from the second participant, wherein the verification is performed according to a second signature algorithm; and whereby the transaction is rejected if either verification fails.
The first signature algorithm may be one which is computationally more difficult in signing than verifying, while the second signature algorithm is more difficult in verifying than signing. In such an embodiment the second participant may participate with relatively little computing power, while security is maintained at a high level.
In a further embodiment, the first signature algorithm is based on an RSA, or DDS type algorithm, and the second signature algorithm is based on an elliptic curve algorithm.
REFERENCES:
patent: 4748668 (1988-05-01), Shamir et al.
patent: 4890323 (1989-12-01), Beker et al.
patent: 4995082 (1991-02-01), Schnorr
patent: 5218637 (1993-06-01), Angebaud et al.
patent: 5299263 (1994-03-01), Beller et al.
patent: 5400403 (1995-03-01), Fahn et al.
patent: 5406628 (1995-04-01), Beller et al.
patent: 5627893 (1997-05-01), Demytko
patent: 5721781 (1998-02-01), Deo et al.
patent: 5748740 (1998-05-01), Curry et al.
patent: 5793866 (1998-08-01), Brown et al.
patent: 5805702 (1998-09-01), Curry et al.
patent: 5825880 (1998-10-01), Sudia et al.
patent: 5870470 (1999-02-01), Johnson et al.
patent: 5881038 (1999-03-01), Oshima et al.
patent: 5907618 (1999-05-01), Gennaro et al.
patent: 5917913 (1999-06-01), Wang
patent: 5955717 (1999-09-01), Vanstone
patent: 5960084 (1999-09-01), Angelo
patent: 6038549 (2000-03-01), Davis et al.
patent: 6041314 (2000-03-01), Davis
patent: 0 588 339 (1994-03-01), None
patent: 2 536 928 (1984-06-01), None
patent: WO 91/1669
Callahan Paul E.
Certicom Corp.
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Swann Tod R.
LandOfFree
Data card verification system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data card verification system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data card verification system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2452515