Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
2000-09-06
2003-09-09
Smithers, Matthew (Department: 2134)
Cryptography
Particular algorithmic function encoding
Public key
Reexamination Certificate
active
06618483
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to public key cryptography.
The increasing use and sophistication of data transmission in such fields as telecommunications, networking, cellular communication, wireless communications, “smart card” applications, audio-visual and video communications has led to an increasing need for systems that permit data encryption, authentication and verification.
It is well known that data can be encrypted by utilizing a pair of keys, one of which is public and one of which is private. The keys are mathematically related such that data encrypted with the public key may only be decrypted with the private key and conversely, data encrypted with the private key can only be decrypted with the public key. In this way, the public key of a recipient may be made available so that data intended for that recipient may be encrypted with the public key and only decrypted by the recipient's private key, or conversely, encrypted data sent can be verified as authentic when decrypted with the sender's public key.
The most well known and accepted public key cryptosystems are those based on integer factorization and discrete logarithms in finite groups. In particular, the RSA system for modulus n=p·q where p and q are primes, the Diffie-Hellman key exchange and the ElGamal protocol in Z*
p
, (p a prime) have been implemented worldwide.
The RSA encryption scheme, where two primes p and q are multiplied to provide a modulus n, is based on the integer factorization problem. The public key e and private key d are related such that their product e·d equals 1(mod&phgr;) where &phgr;=(p−1) (q−1). A message M is encrypted by exponentiating it with the private key e to the modulus n, [C=M* (mod n)] and decrypted by exponentiating with the public key mod n [M=C
d
(mod n)]. This technique requires the transmission of the modulus n and the public key and the security of the system is based on the difficulty of factoring a large number that has no relatively small factors. Accordingly both p and q must be relatively large primes.
One disadvantage of this system is that p and q must be relatively large (at least 512 bits) to attain an adequate level of security. With the RSA protocol this results in a 1024 bit modulus and a 512 bit public key which require significant bandwidth and storage capabilities. For this reason researchers have looked for public key schemes which reduce the size of the public key. Moreover, recent advances in analytical techniques and associated algorithms have rendered the RSA encryption scheme potentially vulnerable and accordingly raised concerns about the security of such schemes. This implies that larger primes, and therefore a larger modulus, need to be employed in order to maintain an acceptable level of security. This in turn increases the bandwidth and storage requirements for the implementation of such a scheme.
Since the introduction of the concept of public key cryptography by Diffie and Hellman in 1976, the potential for the use of the discrete logarithm problem in public key cryptosystems has been recognized. In 1985, ElGamal described an explicit methodology for using this problem to implement a fully functional public key cryptosystem, including digital signatures. This methodology has been refined and incorporated with various protocols to meet a variety of applications, and one of its extensions forms the basis for a proposed U.S. digital signature standard (DSS). Although the discrete logarithm problem, as first employed by Diffie and Hellman in their public key exchange algorithm, referred explicitly to the problem of finding logarithms with respect to a primitive element in the multiplicative group of the field of integers modulo a prime p, this idea can be extended to arbitrary groups (with the difficulty of the problem apparently varying with the representation of the group).
The discrete logarithm problem assumes that G is a finite group, and a and b are elements of G. Then the discrete logarithm problem for G is to determine a value x (when it exists) such that a
x
=b. The value for x is called a logarithm of b to the base of a, and is denoted by log
a
b.
The difficulty of determining this quantity depends on the representation of C. For example, if the abstract cyclic group of order m is represented in the form of the integers modulo m, then the solution to the discrete logarithm problem reduces to the extended Euclidean algorithm, which is relatively easy to solve. However, the problem is made much more difficult if m+1 is a prime, and the group is represented in the form of the multiplicative group of the finite field F
m+1
. This is because the computations must be performed according to the special calculations required for operating in finite fields.
It is also known that by using computations in a finite field whose members lie on an elliptic curve, that is by defining a group structure G on the solutions of y
2
+xy=x
3
+ax
2
+b over a finite field, the problem is again made much more difficult because of the attributes of elliptic curves. Therefore, it is possible to attain an increased level of security for a given size of key. Alternatively a reduced key may be used to maintain a required degree of security.
The inherent security provided by the use of elliptic curves is derived from the characteristic that an addition of two points on the curve can be defined as a further point that itself lies on the curve. Likewise the result of the addition of a point to itself will result in another point on the curve. Therefore, by selecting a starting point on the curve and multiplying it by an integer, a new point is obtained that lies on the curve. This means that where P=(x,y) is a point on an elliptic curve over a finite field [E(F
q
n
)], with x and y each represented by a vector of n elements then, for any other point R&egr;<P> (the subgroup generated by P), dP=R. To attack such a scheme, the task is to determine an efficient method to find an integer d, 0≦d≦(order of P)−1 such that dP=R. To break such a scheme, the best algorithms known to date have running times no better than 0({square root over (p)}), where p is the largest prime dividing the order of the curve (the number of points on the curve).
Thus, in a cryptographic system where the integer d remains secret, the difficulty of determining d can be exploited.
An ElGamal protocol of key exchange based on elliptic curves takes advantage of this characteristic in its definition of private and public keys. Such an ElGamal protocol operates as follows:
1. In order to set up the protocol, where a message is to be sent from A to B, an elliptic curve must be selected and a point P=(x,y), known as the generating point, must be selected.
Encryption
2. The receiver, B, then picks a random integer d as his private key. He then computes dP, which is another point on the curve, which becomes his public key that is made available to the sender and the public. Although the sender knows the value dP, due to the characteristic of elliptic curves noted above, he has great difficulty determining the private key d.
3. The sender A, chooses another random integer k, the session seed, and computes another point on the curve, kP which serves as a public session key.
This also exploits the characteristic of elliptic curves mentioned above.
4. The sender, A, then retrieves the public key dP of receiver B and computes kdP, another point on the curve, which serves as the shared encryption key for that session.
5. The sender, A, then encrypts the message M with the encryption key to obtain the ciphertext C.
6. The sender then sends the public session key kP and the ciphertext C to the receiver B.
Decryption
7. The receiver, B, determines the encryption key kdP by multiplying his private key d by kP.
8. The receiver, B, can then retrieve the message M by decrypting the ciphertext C with the encryption key kdP.
During th
Agnew Gordon B.
Mullin Ronald C.
Vanstone Scott A.
Certicom Corporation
Pillsbury & Winthrop LLP
Smithers Matthew
LandOfFree
Elliptic curve encryption systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Elliptic curve encryption systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Elliptic curve encryption systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3089876