Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1998-05-20
2001-06-26
Swann, Tod (Department: 2132)
Cryptography
Particular algorithmic function encoding
C380S044000, C380S282000, C380S030000
Reexamination Certificate
active
06252959
ABSTRACT:
BACKGROUND OF THE INVENTION
Cryptosystems are becoming increasingly important especially as data communication becomes ubiquitous. No longer limited to military applications, cryptosystems are being used commercially for such applications as privacy systems, authentication, and digital signatures. Privacy systems prevent the extraction of information transmitted through or stored in a medium by unauthorized parties. Identification is used, for example, in cellular phone communications to prevent fraudulent access to a customer account. And, digital signature systems are used to verify the authenticity of a message.
One of the most significant contributions to the field of cryptography was made by Diffie-Hellman (DH) with the concept of public key cryptographic systems. The core realization was the fact that practically secure systems can be built that require no secure transfer of any secret key. Previously, it was thought that a secure cryptosystem relied on the prior agreement between the sending and receiving parties concerning the key used to encrypt the data. If the secrecy of this key was ever prejudiced, the secrecy of the cryptosystem was also at risk.
The critical innovation of Diffie-Hellman was the concept of the one-way function. Such a function is defined as a function f such that for every x in the domain of f, f(x) is easy to compute; but for virtually all y in the range of f, it is computationally infeasible to find an x such that y=f(x). Also discovered was the concept of the trapdoor one-way function. These functions are defined as a family of invertible functions f
z,
indexed by z, such that, given z, it is easy to find algorithms E
z
and D
z
that easily compute f
z
(x) and f
z
−1
(y) for all x and y in the domain and range, respectively, of f
z
. It is computationally infeasible to compute f
z
−1
(y) even assuming E
z
is known, if z is not known.
RSA is considered to be the first usable public key cryptosystem. This particular cryptosystem is based on the difficulty of factoring very large numbers, and today, it is still the most widely used public-key cryptosystem in the world. Since then, in the field of computational number theory, major work has been done towards efficient integer factorization. As a consequence, new types of public-key algorithms have arisen. The most important competitors to RSA are schemes based on the Discrete Logarithm (DL) problem. Originally, the DL problem was considered in the multiplicative group of a finite field, especially a prime field or a field of characteristic
2
, since these fields seemed most appropriate for implementations. Then in 1985, a variant of the DL problem was proposed based on the group of points of an elliptic curve (EC) over a finite field.
A main feature that makes elliptic curves attractive is the relatively short operand length. Cryptosystems that explore the DL problem over elliptic curves can be built with an operand length of 140-200 bits as compared to RSA and systems based on the DL in finite fields, both of which require operands of 512-1024 bits. Other advantages are the large numbers of curves that are available to provide the groups and the absence of sub-exponential time algorithms (such as the index calculus method) to attack EC cryptosystems. The latter property provides a very good long-term security against current attacks. In addition, IEEE and other standard bodies such as ANSI and ISO are in the process of standardizing EC cryptosystems.
SUMMARY OF THE INVENTION
One of the main problems associated with the deployment of EC cryptosystems is the fact that their implementation is computationally intensive. This slows the single isolated transfer by a given user. Moreover, in anticipated commercial systems where there are substantial real-time transaction processing throughput requirements, computational efficiency becomes a major issue and cost factor in the systems. In short, it is important for a system, with limited processing capabilities, to process as many transactions as possible.
When implementing an elliptic curve cryptosystem, one is required to compute:
eP
=
P
+
P
…
+
P
⏟
e
times
,
where e is a positive integer and P is a point on the elliptic curve. In the initial phase of the DH protocol, applied to elliptic curve systems, both parties agree on a primitive element P
0
. Then, they generate or select their secret keys {d, r} which are integers and compute their public keys Q=dP
0
and Z=rP
0
, both points on the elliptic curve. In the second phase of the DH protocol, one is required to compute a multiple of a point P (the public key of the other party, e.g., Q,Z) not known ahead of time. The efficient and fast computation of eP, where e is a large integer and P is a point on the elliptic curve, is crucial to the speed of the key exchange and digital signature generation.
For very large values of e, a straightforward summation becomes impractical and so a method, which is analogous to the square and multiply algorithm for exponentiation, is used. This method is known as “repeated double and add.” On the average, for a random 155-bit multiplier, one is required to perform 154 doubling steps and 77 additions.
In the elliptic curve y
2
+xy=x
3
+ax
2
+c, a, c &egr; GF(2
k
), the doubling of two points will require one inverse, two multiplications, five additions, and two squarings in the underlying Galois Field GF(2
k
). This is a very expensive computational task because of the number of doublings that are required, and because both inversion and multiplication in the underlying field are computationally intensive.
The present invention is based upon the recognition that for most practical applications, the inversion in the underlying Galois Field is by far the most expensive operation to perform of the inverse, multiplication, addition, and squaring in the point doubling operations.
The present invention is directed to a point doubling method for elliptic curve cryptosystems in which 2
k
P=(x
k
, y
k
), where k=2, 3, 4, . . . , i.e., a repeated doubling, is directly calculated from P= (x,y) without computing intermediate points such as 2P and 4P to compute 2
3
P=8P. The advantage in this direct calculation technique is that the number of inversions can be reduced by implementing the principles of the invention. Although this does not come without a price. In most implementations, the number of multiplications is increased. The net time to perform the additional multiplications, however, is less than the time required to perform the inversion, which the multiplications effectively replace, thereby resulting in the efficiency of the present invention. Thus, in the case of the single isolated transaction, it occurs faster, and in the case of the commercial systems, handling many transactions, the real-time transaction processing capabilities are increased.
In general, according to one aspect, the invention features a method for key generation in an elliptic curve cryptosystem. The method comprises acquiring a point P on predetermined elliptic curve and obtaining a new point Q=nP, n is an interger, on the EC. While performing the “point multiplication” (nP), the number of inversions is reduced to expedite the process of determining the new point, which then can be used as a cyptographic key for both signature and encryption processes.
In specific embodiments, the number of inversions is reduced, preferably to a single inversion, at the expense of increasing the multiplications required for the point multiplication. The original point may be acquired as a system parameter in the cryptosystem or a public key of a user of the cryptosystem.
According to the invention, computing the multiple of a point comprises directly computing one or more repeated doublings of the point. As a result, 4P for example is directly computed, rather than first computing 2P and then doubling 2P to 4P, as is conventional.
In general, according to anoth
Guajardo Jorge
Paar Christof
Darrow Justin T.
Hamilton Brook Smith & Reynolds P.C.
Swann Tod
Worcester Polytechnic Institute
LandOfFree
Method and system for point multiplication in 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 Method and system for point multiplication in elliptic curve..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for point multiplication in elliptic curve... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2483398