Cryptography – Key management – Key distribution
Reexamination Certificate
1998-07-23
2001-04-03
Hayes, Gail (Department: 2766)
Cryptography
Key management
Key distribution
C380S285000
Reexamination Certificate
active
06212279
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to cryptography and, more particularly, to a discrete logarithm based key exchange on an elliptic curve using a reduced base tau expansion in non-adjacent form.
BACKGROUND OF THE INVENTION
U.S. Pat. No. 4,200,770, entitled “CRYPTOGRAPHIC APPARATUS AND METHOD,” discloses a device for and method of performing a cryptographic key exchange over a public channel. The method is often called a public-key key exchange method or the Diffie-Hellman key exchange method after the first two named inventors of U.S. Pat. No. 4,200,770. U.S. Pat. No. 4,200,770 is hereby incorporated by reference into the specification of the present invention.
The cryptographic strength of the Diffie-Hellman key exchange method is based on the apparent intractability of finding a discrete logarithm, or discrete log, under certain conditions. Simply, two users exchange information by concealing their information using the mathematical technique of exponentiation. The users then mathematically combine the information they receive to the information they have to a key. The key may then be used with an encryption algorithm to encrypt a message. This method of establishing a private key between two users using a public channel solves the key distribution problem.
In order for an adversary to recover the concealed information and, therefore, be able to construct the key and decrypt messages sent between the two users, the adversary must be able to perform the inverse of exponentiation (i.e., a logarithm). There are mathematical methods for finding a discrete logarithm (e.g., the Number Field Sieve), but these algorithms cannot be done in any reasonable time using sophisticated computers if certain conditions are met during the construction of the key (e.g., the numbers involved in establishing the key are big enough).
More precisely, the cryptographic strength of the Diffie-Hellman key exchange method is based on the difficulty of computing discrete logs in a finite cyclic group. Mathematically, the discrete log problem is as follows. Let G be a finite cyclic group of order q, where g is a generator of G. Let r be a secret number such that 0<r<q. Given G, q, g, and g{circumflex over ( )}r, where “{circumflex over ( )}” denotes exponentiation, find r, where r is the discrete logarithm, or discrete log, of g{circumflex over ( )}r. The discrete log problem is to find r.
In a Diffie-Hellman key exchange, two users (e.g., User A and User B) agree on a common G, g, and q. User A generates, or acquires, a secret number “a”, where 1<a<q, computes g{circumflex over ( )}a, and sends g{circumflex over ( )}a to User B. User B generates, or acquires, a secret number “b”, where 1<b<q, computes g{circumflex over ( )}b, and sends g{circumflex over ( )}b to User A. User A then computes (g{circumflex over ( )}b){circumflex over ( )}a, while User B computes (g{circumflex over ( )}a){circumflex over ( )}b. Since these two values are mathematically equivalent, the two users are now in possession of the same secret number. A cryptographic key may then be derived from the secret number. The significance of this method is that a private key was established between two users by transmitting information over a public channel (i.e., an adversary sees the information being passed) but without knowing a or b, the key cannot be constructed from the information that is passed over the public channel. If the users keep “a” and “b” private and the numbers used to generate the key are large enough so that g{circumflex over ( )}(ab) cannot be mathematically derived from g{circumflex over ( )}a and g{circumflex over ( )}b then only the users know the key. In practice, the most common choice for G is the integers mod n, where n is an integer.
Large keys pose problems not only for the adversary but also for the users. Large keys require large amounts of computational power and require large amounts of time in order to generate and use the key. Cryptographers are always looking for ways to quickly generate the shortest keys possible that meet the cryptographic strength required to protect the encrypted message. The payoff for finding such a method is that cryptography can be done faster, cheaper, and in devices that do not have large amounts of computational power (e.g., hand-held smart-cards).
The choice of the group G is critical in a cryptographic system. The discrete log problem may be more difficult in one group and, therefore, cryptographically stronger than in another group, allowing the use of smaller parameters but maintaining the same level of security. Working with small numbers is easier than working with large numbers. Small numbers allow the cryptographic system to be higher performing (i.e., faster) and requires less storage. So, by choosing the right group, a user may be able to work with smaller numbers, make a faster cryptographic system, and get the same, or better, cryptographic strength than from another cryptographic system that uses larger numbers.
The classical choice for G in a Diffie-Hellman key exchange are integers mod n, where n is an integer as well. In 1985, Victor Miller and Neal Koblitz each suggested choosing G from elliptic curves. It is conjectured that choosing such a G allows the use of much smaller parameters, yet the discrete log problem using these groups is as difficult, or more difficult, than integer-based discrete log problems using larger numbers. This allows the users to generate a key that has the same, or better, cryptographic strength as a key generated from an integer G and is shorter than the integer-based key. Since shorter keys are easier to deal with, a cryptographic system based on a shorter key may be faster, cheaper, and implemented in computationally-restricted devices. So, an elliptic curve Diffie-Hellman key exchange method is an improvement over an integer-based Diffie-Hellman key exchange method.
More precisely, an elliptic curve is defined over a field F. An elliptic curve is the set of all ordered pairs (x,y) that satisfy a particular cubic equation over a field F, where x and y are each members of the field F. Each ordered pair is called a point on the elliptic curve. In addition to these points, there is another point 0 called the point at infinity. The infinity point is the additive identity (i.e., the infinity point plus any other point results in that other point). For cryptographic purposes, elliptic curves are typically chosen with F as the integers mod p for some large prime number p (i.e., F
p
) or as the field of 2{circumflex over ( )}m elements (i.e., F
2
m).
Multiplication or, more precisely, scalar multiplication is the dominant operation in elliptic curve cryptography. The speed at which multiplication can be done determines the performance of an elliptic curve method.
Multiplication of a point P on an elliptic curve by an integer k may be realized by a series of additions (i.e., kP=P+P+. . . +P, where the number of Ps is equal to k). This is very easy to implement in hardware since only an elliptic adder is required, but it is very inefficient. That is, the number of operations is equal to k which may be very large.
The classical approach to elliptic curve multiplication is a double and add approach. For example, if a user wishes to realize kP, where k=25 then 25 is first represented as a binary expansion of 25. That is, 25 is represented as a binary number 11001. Next, P is doubled a number of times equal to the number of bits in the binary expansion minus 1. For ease in generating an equation of the number of operations, the number of doubles is taken as m rather than m−1. The price for simplicity here is being off by 1. In this example, the doubles are 2P, 4P, 8P, and 16P. The doubles correspond to the bit locations in the binary expansion of 25 (i.e., 11001), except for the is bit. The doubles that correspond to bit locations that are 1s are then added along with P if the 1s bit is a 1. The number of adds equals the number of 1s in the binary expansion. In this example, th
Reiter Robert W.
Solinas Jerome A.
Hayes Gail
Leaning Jeffrey Scott
Morelli Robert D.
The United States of America as represented by the United States
LandOfFree
Method of elliptic curve cryptographic key exchange using... 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 of elliptic curve cryptographic key exchange using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of elliptic curve cryptographic key exchange using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2477845