Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1997-10-17
2002-07-23
Hayes, Gail (Department: 2131)
Cryptography
Particular algorithmic function encoding
C380S028000
Reexamination Certificate
active
06424712
ABSTRACT:
The present invention relates to public key data communication systems.
BACKGROUND OF THE INVENTION
Public key data communication systems are used to transfer information between a pair of correspondents. At least part of the information exchanged is enciphered by a predetermined mathematical operation by the sender and the recipient may perform a complementary mathematical operation to decipher the information.
A typical example of such a system is a digital signature protocol. Digital signatures are used to confirm that a message has been sent by a particular party and that the contents have not been altered during transmission.
A widely used set of signature protocols utilizes the El Gamal public key signature scheme that signs a message with the sender's private key. The recipient may then recover the message with the sender's public key.
Various protocols exist for implementing such a scheme and some have been widely used. In each case however the recipient is required to perform a computation to verify the signature. Where the recipient has adequate computing power this does not present a particular problem but where the recipient has limited computing power, such as in a “Smart card” application, the computations may introduce delays in the verification process.
Public key schemes may be implemented using one of a number of multiplicative groups in which the discrete log problem appears intractable but a particularly robust implementation is that utilizing the characteristics of points on an elliptic curve over a finite field. This implementation has the advantage that the requisite security can be obtained with relatively small orders of field compared with, for example, implementations in Z
p
* and therefore reduces the bandwidth required for communicating the signatures.
In a typical implementation a signature component s has the form:
s=ae+k
(mod n)
where:
P is a point on the curve which is a predefined parameter of the system
k is a random integer selected as a short term private or session key, and has a corresponding short term public key R=kP
a is the long term private key of the sender and has a corresponding public key aP=Q
e is a secure hash, such as the SHA hash function, of a message m and short term public key R, and
n is the order of the curve.
The sender sends to the recipient a message including m, s, and R and the signature is verified by computing the value −(sP−eQ) which should correspond to R. If the computed values correspond then the signature is verified.
In order to perform the verification it is necessary to compute a number of point multiplications to obtain sP and eQ, each of which is computationally complex. Other protocols, such as the MQV protocols require similar computations when implemented over elliptic curves which may result in slow verification when the computing power is limited.
Typically, the underlying curve has the form y
2
+xy=x
3
+ax+b and the addition of two points having coordinates (x
1
, y
1
) and (x
2
,y
2
) results in a point (x
3
,y
3
) where:
x
3
=
{
(
y
1
⊕
y
2
x
1
⊕
x
2
)
2
⊕
y
1
⊕
y
2
x
1
⊕
x
2
⊕
x
1
⊕
x
2
⊕
a
(
P
≠
Q
)
y
3
=
{
(
y
1
⊕
y
2
x
1
⊕
x
2
)
⊕
(
x
1
⊕
x
3
)
⊕
x
3
⊕
y
1
(
P
≠
Q
)
The doubling of a point i.e. P to 2P, is performed by adding the point to itself so that
y
3
=
{
x
1
2
⊕
(
x
1
⊕
y
1
x
1
)
}
x
3
⊕
x
3
x
3
=
x
1
2
⊕
b
x
1
2
It will be appreciated that successive doubling of the point Q produces values for 2Q, 2
2
Q, 2
3
Q . . .2
j
Q and that these values may be substituted in the binary representation of the hash value e and added using the above equations to provide the value eQ. At most this would require t doublings and t point additions for a t bit representation of e. Similarly the point P may be doubled successively and the values substituted in the representation of s to obtain sP. However, the generation of each of the doubled points requires the computation of both the x and y coordinates and the latter requires a further inversion. These steps are computationally complex and therefore require either significant time or computing power to perform. Substitution in the underlying curve to determine the value of y is not practical as two possible values for y will be obtained without knowing which is intended.
It is therefore an object of the present invention to provide a method and apparatus in which the above disadvantages are obviated or mitigated.
SUMMARY OF THE INVENTION
In general terms, the present invention provides a method and apparatus in which the transmitted data string is modified to include information additional to that necessary to perform the verification but that may be used to facilitate the computations involved in the verification.
REFERENCES:
patent: 5005200 (1991-04-01), Fischer
patent: 5442707 (1995-08-01), Miyaji et al.
patent: 5497423 (1996-03-01), Miyaji
patent: 5572454 (1996-11-01), Lee et al.
patent: 5799088 (1998-08-01), Raike
Botes and Penzhorn, An Implementation of An Elliptic Curve Cryptosystem, COMS-94, pp. 85-90, 1994.*
Neal Koblitz, A Course in Number Theory and Cryptography 2e,Springer, Chapter VI, 1996.*
James Wertz (ED), Spacecraft Attitude Determination and Control, Reidel, chapter 8, 1985.*
Koblitz, A Course in Number Theory and Cryptography, 2e, Springer-Verlag, pp. 167-185.
Johnson Donald B.
Vanstone Scott A.
Certicom Corp.
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Hayes Gail
Seal James
LandOfFree
Accelerated signature verification on an elliptic curve does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Accelerated signature verification on an elliptic curve, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Accelerated signature verification on an elliptic curve will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2862424