Cryptosystems with elliptic curves chosen by users

Details Cryptosystems with elliptic curves chosen by users Cryptosystems with elliptic curves chosen by users

1998-12-10

2002-09-03

Peeso, Thomas R. (Department: 2132)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Particular communication authentication technique

C713S171000, C380S255000, C380S277000, C380S278000, C380S282000

Reexamination Certificate

active

06446205

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to cryptographic systems, and, more particularly, is directed to elliptic curve cryptosystems in which participants pick their own elliptic curves rather than using a centrally chosen elliptic curve.
In a conventional elliptic curve cryptosystem, as shown in
FIG. 1
, a central facility selects a finite field, an elliptic curve, a generator of an appropriate subgroup of the group of points of the elliptic curve over the finite field, and the order of that generator. The central facility distributes these data among the participants in the cryptographic system. Each participant then selects a secret key, computes a corresponding public key, and may optionally obtain certification for its public key. The objective of the certificate is to make one party's public key available to other parties in such a way that those other parties can independently verify that the public key is valid and authentic. An advantage of the conventional system is that, while a lot of computation is required to obtain both the cardinality of the group of points of an elliptic curve over a finite field, and to find an elliptic curve for which this cardinality satisfies the security requirements, this computation need not be performed by participants—which would be very burdensome—as the computation is performed once by the central facility.
Conventional elliptic curve cryptosystems are used in the same applications as public key cryptosystems, such as authentication, certification, encryption/decryption, signature generation and verification.
As shown in
FIG. 2
, to use the conventional elliptic curve cryptosystem, two parties wishing to communicate exchange their cryptographic data, and then proceed with their communication, such as a signature scheme or a data encryption/decryption scheme. Advantageously, the number of bits exchanged during communication setup between parties is small.
A serious problem with the above-described conventional elliptic curve cryptosystem is that all participants are vulnerable to an attack on the centrally selected elliptic curve and finite field. That is, the system is vulnerable to a concentrated attack on the Discrete Logarithm problem in the group defined by the centrally selected elliptic curve and finite field.
Due to the desire that the cryptographic functionality be implementable in a small, inexpensive, low power device, it is considered impractical for each participant to choose its own elliptic curve. More particularly, allowing each participant to choose its own elliptic curve improves system security but results in a complicated system setup phase.
In conventional elliptic curve cryptosystems, the number of bits exchanged between parties during communication set-up is small, typically representing the parties' identities and the parts of their public keys that differ, i.e., not the curve and field shared by all parties. If each participant chose its own elliptic curve, another disadvantage would be that more data would have to be exchanged during communication set-up, specifically, the complete public keys including curves and fields would have to be exchanged during communication setup.
In view of these issues, there is a need to reduce the vulnerability to attack of elliptic curve cryptosystems.
SUMMARY OF THE INVENTION
In accordance with an aspect of this invention, there is provided a method of establishing a cryptographic system among participants, comprising the steps of: selecting a curve E from a predetermined set of elliptic curves, selecting a finite field, selecting a secret key, and obtaining a public key, wherein the steps of selecting a curve E, a finite field, a secret key and obtaining a public key are performed locally by each of the participants.
In an embodiment of the present invention, the predetermined set of elliptic curves are expressed as Weierstra&bgr; model equations, specifically:
y
2
=x
3
+0
x
+16;
y
2
=x
3
−270
x
−1512;
y
2
=x
3
−35
x
−98;
y
2
=x
3
−9504
x
−365904;
y
2
=x
3
−608
x
+5776;
y
2
=x
3
−13760
x
+621264;
y
2
=x
3
−117920
x
+15585808;
and
y
2
=x
3
−34790720
x
+78984748304.
In an embodiment of the present invention, the step of obtaining a public key includes selecting a bitstring s having a predetermined length based on security considerations, and obtaining a prime number p based on the selected bitstring s and a unique bitstring ID of the respective participant.
In accordance with an aspect of this invention, there is provided a method of reconstructing a public key for a participant in a cryptographic system, comprising the steps of forming intermediate integers a and b based on the participant's ID, obtaining a prime number p as a function of the intermediate integers a and b, selecting a curve E from a predetermined set of elliptic curves, picking a point Q on the selected curve based on the participant's ID, and constructing the public key from the prime number p, the selected curve E and the point Q.
In an embodiment of the present invention, the predetermined set of elliptic curves are expressed as Weierstra&bgr; model equations.
It is not intended that the invention be summarized here in its entirety. Rather, further features, aspects and advantages of the invention are set forth in or are apparent from the following description and drawings.


REFERENCES:
patent: 5351297 (1994-09-01), Miyaji et al.
patent: 5442707 (1995-08-01), Miyaji et al.
patent: 5497423 (1996-03-01), Miyaji
patent: 5627893 (1997-05-01), Demytko
patent: 5793866 (1998-08-01), Brown et al.
Menezes et al., “Handbook of Applied Cryptography”, 1996, sec.'s 4.53, 8.4.*
Lenstra, Arjen K., “Efficient Identity Based Parameter Selection for Elliptic Curve Cryptosystems”, Information Security and Privacy, 4th Australasian Conference, pp. 294-302 (Apr. 7-9, 1999).
Menezes, Alfred J. et al., “Elliptic Curve Cryptosystems and Thier Implementation”, Journal of Cryptology, vol. 6, No. 4, pp. 209-224 (Autumn 1993).
Koblitz, Neal, “Constructing Elliptic Curve Cryptosystems in Characteristic 2”, Advances In Cryptology—Crypto '90 Proceedings, Santa Barbara, CA, pp. 156-167 (Aug. 11-15, 1990).
Schoof, René , “Counting Points on Elliptic Curves Over Finite Fields”, Journal de Théorie des Nombres, vol. 7, No. 1, pp. 219-254 (1995).
International Search Report, dated Apr. 5, 2000.

Affiliated with

Also associated with

Rating

Cryptosystems with elliptic curves chosen by users does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Cryptosystems with elliptic curves chosen by users, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cryptosystems with elliptic curves chosen by users will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2860247