Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Particular communication authentication technique
Reexamination Certificate
2001-08-29
2004-03-09
Peeso, Thomas R. (Department: 2132)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
Particular communication authentication technique
C713S152000, C713S152000, C380S285000, C380S030000, C380S044000
Reexamination Certificate
active
06704870
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to methods and apparatus for generating digital signatures.
2. Discussion of Related Art
It has become widely accepted to conduct transactions, such 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. The recipient can verify the signature using a public key of the signing party to recover the message and compare it with the transmitted message. 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 sent message and that recovered from the signature or will fail to identify the party correctly and thereby lead to rejection of the transaction.
The signature must be performed such that the signing 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 are available.
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, i.e. credit/debit cards or pass cards are now available with limited computing capacity (so-called “Smart Cards”) but these do not have sufficient computing capacity 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.
The DSS protocol provides a signature composed of two components r, s. The protocol requires the selection of a secret random integer k referred to as the session key from the set of integers (0,1,2, . . . q−1), i.e.
k&egr;{
0,1,2, . . . q−1}.
The component r is then computed such that
r={&bgr;
k
mod p} mod
q
where &bgr; is a generator of q.
The component s is computed as
s −[k
−1
(
h
(
m
))+
ar
] mod
q
where m is the message to be transmitted,
h(m) is a hash of that message, and
a is the private key of the user.
The signature associated with the message is then s,r which may be used to verify the origin of the message from the public key of the user.
The value &bgr;
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 to the ATM and therefore render the private key, a, vulnerable.
It has been proposed to precompute &bgr;
k
and store sets of values of r and k on the card. The generation of the signature then only requires two 160 bit multiplications and signing can be completed within ½ second for typical applications. However, the number of sets of values stored limits the number of uses of the card before either reloading or replacement is required. A problem that exists therefore is how to generate sufficient sets of values within the storage and/or computing capacity of the card.
One possibility is to use a smaller value of p but with the DSS scheme this will jeopardize the security of the transaction.
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 DSS and therefore offers significant benefits in implementation.
Diffie Helman 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 exists with elliptic curves where the addition of two points on a curve produces a third point on the curve. Similarly, multiplying any point on the curve by an integer k produces a further point on the curve. 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
.
In order to perform a digital signature on an elliptic curve, it is necessary to have available the session key k and a value of kP referred to as a “session pair”. Each signature utilizes a different session pair k and kP and although the representation of k and kP is relatively small compared with DSS implementations, the practical limits for “Smart Cards” are in the order of 32 signatures. This is not sufficient for commercial purposes.
One solution for both DSS and elliptic curve implementations is to store pairs of signing elements k, kP and combine stored pairs to produce a new session pair. For an elliptic curve application, this would yield a possible 500 session pairs from an initial group of 32 stored signing elements. The possibilities would be more limited when using DSS because of the smaller group of signing elements that could be stored.
In order to compute a new session pair, k and kP, from a pair of stored signing elements, it is necessary to add the values of k, e.g. k
1
+k
2
→k and the values of k
1
P and k
2
P to give a new value kP. In an elliptic curve, the addition of two points to provide a third point is performed according to set formula such that the addition of a point k
2
P having coordinates (x,y) and a point k
1
P having coordinates (x
2
y
2
) provides a point k
3
P whose x coordinate x
3
is given by:
x
3
=
y
1
⊕
y
2
2
⊕
y
1
⊕
y
2
⊕
x
1
⊕
x
2
.
x
1
⊕
x
2
x
1
⊕
x
2
This computation may be significantly simplified using the normal basis representation in a field F2
m
, as set out more fully in our PCT Application Serial No.
PCT/CA/9500452, the contents of which are incorporated herein by reference. However, even using such advantageous techniques, it is still necessary to utilize a finite field multiplier and provide sufficient space for code to perform the computation. This is not feasible within the practical limits of available “Smart” cards.
As noted above, the ATM used in association with the card has sufficient computing power to perform the computation but the transfer of the coordinates of k
1
P and k
2
P from the card to the terminal would jeopardize the integrity of subsequent digital signatures as two of the stored signing elements would be known.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to obviate or mitigate the above disadvantages and facilitate the preparation of additional pairs of values from a previously stored set.
In general terms, one aspect of the present invention proposes to compute on one computing device an initial step in the computation of a coordinate of a point derived from a pair of points to inhibit recognition of the individual components, transfer such information to another computing device re
Menezes Alfred J.
Vanstone Scott A.
Certicom Corp.
Peeso Thomas R.
The Maxham Firm
LandOfFree
Digital signatures on a Smartcard does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Digital signatures on a Smartcard, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Digital signatures on a Smartcard will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3268949