Cryptography – Particular algorithmic function encoding
Reexamination Certificate
1999-03-15
2004-08-17
Barrón, Gilberto (Department: 2731)
Cryptography
Particular algorithmic function encoding
C380S030000, C708S492000
Reexamination Certificate
active
06778666
ABSTRACT:
BACKGROUND OF INVENTION
1. Field of the Invention
The present invention is related to a private communication system and more particularly to providing security for a private communication using elliptic curve cryptosystem.
2. Discussion of the Related Art
Cryptographic systems are widely used as the means to provide security during exchange of information. Potentially, the cryptographic systems provide all objectives of information security such as confidentiality, integrity, authentication and availability.
There are two main classes of cryptographic systems, known as a symmetric key system and a public key system. The symmetric key systems have been used for a long time to encrypt and to decrypt messages. In the symmetric key systems, a single key can be used to encrypt and to decrypt messages. While the implementation of the symmetric key system is very efficient, the key management can be troublesome.
On the other hand, since its introduction in 1976, the public key cryptographic system has been studied and used extensively until today. The public key cryptographic systems are used for encryption and decryption, data digital signing and signature verification, and for safe exchange of a secret key through non-secure communication channels. Although public key cryptographic schemes are more convenient for key management, its implementation is currently less efficient than the symmetric key systems.
In a public key encryption scheme, the processes of encryption and decryption are separated. During encryption, a public key, often designated as ‘e’ is employed while a different (but mathematically related) private key ‘d’ is required for decryption. Knowledge of the public key allows encryption of plaintext but does not allow decryption of the ciphertext without the private key for decryption.
For example, a user selects and publishes a public key. Subsequently, others may use the selected key to encrypt messages for this user. At the same time, a private key corresponding to the public key is kept in secret by the user such that the user is the only one who can decrypt the ciphertext encrypted for the user. Well-known public key cryptographic schemes include RSA, DSA, Diffie-Hellman, ElGamal and elliptic curve cryptosystems (ECC).
A comparison of the public key cryptographic systems shows that the elliptic curve cryptosystems offer the highest strength-per-key-bit among any known systems. With a 162-bit modulus, an elliptic curve system offers the same level of cryptographic security as DSA or RSA having a 1024-bit moduli. Smaller key sizes gives the elliptic curve cryptosystem advantages, including smaller system parameters, smaller public key certificates, bandwidth savings, faster computations, and lower power requirements.
Many cryptosystems require arithmetic to be performed in mathematical structures called a group and a field. A group is a set of elements with a custom-defined arithmetic operation over the elements, while a field is a set of elements with two custom-defined arithmetic operations over its elements. The order of a group is the number of its elements. The arithmetic operations defined in groups and fields requires certain properties, but the properties of a field are more stringent than the properties of a group.
The elliptic curve is an additive group with a basic operation of addition. Elliptic curves as algebraic and geometric entities have been studied extensively for the past 150 years, and from these studies a rich and deep theory had emerged. As a result, the elliptic curve systems as applied to cryptography were proposed in 1985.
Elements of an elliptic curve are pairs of numbers (x, y), called points. The x and y values may be ordinary (real) numbers, or they may be members of a field in which the elliptic curve is defined. Such fields are called the underlying field of the elliptic curve. The choice of the underlying field affects the number of points in the elliptic curve, the speed of elliptic curve computations, and the difficulty of the corresponding discrete logarithm problem. Thus, when elliptic curves are used for cryptosystems, the underlying field affects the key sizes, the computational requirements and the security. Choosing different underlying fields allows an extensive variety of elliptic curves.
Usually two classes of elliptic curve cryptosystems are used, one of which is defined over the underlying field Fp (i.e. modulo prime p) and the other defined over the underlying field F
2
m
(modulo irreducible polynomial of power 2
m
). The second class of elliptic curve cryptosystems is characterize by considerably less number of suitable curves and has lower performance, except for performance in hardware implementation. Thus, elliptic curve cryptosystem over the underlying field Fp receives more interest. Below, we consider Fp as the underlying field, where p is a prime of a special kind, and an elliptic curve over Fp, defined by equation y
2
=x
3
+Ax+B (mod p), where A, B∈Fp. The essential requirement for such elliptic curves is a non-zero curve discriminant, 4A
3
+27B
2
≠0 (mod p).
The elliptic curve element is an elliptic curve point designated as P(x, y)∈E(Fp). Thus, point P lies on the elliptic curve E defined over underlying field Fp and the point coordinates x, y∈Fp. The order of elliptic curve is the number of points on the elliptic curve. The group operation for an elliptic curve is addition of two elements, i.e. the points. Thus, the basic operation on an elliptic curve is the addition of elliptic curve points. The addition of elliptic curve points results in another point lying on the same elliptic curve. Adding two different points, such as P+Q=R
1
, is called the addition of two distinguished points. If the same two points are added, i.e. the point is added to itself, such as P+P=2P=R
2
, the operation is called the doubling of points. A repeated addition of a point with itself is called a scalar multiplication of the point by an integer k: P+P+P+ . . . +P=kP=R
3
where k is an integer. The original points and the resulting points all lie on the same elliptic curve: P, Q, R
1
, R
2
, R
3
∈E(Fp).
An order of an elliptic curve point is significant in elliptic curve cryptosystems. The order of elliptic curve point P is the least integer n such that scalar multiplication of point by this number produces a special point on an elliptic curve, called the infinity point O (nP=O). The infinity point is an identity of the elliptic curve as a group.
For the underlying field Fp, if the order of elliptic curve is composite, then the elliptic curve group can be separated into subgroups, and each of the subgroup will have a prime order, i.e. consist of prime number of points. In such case, the order of each subgroup is smaller than the order of elliptic curve. In the subgroup, all points have the same order, which is equal to the order of the subgroup. Group operations over points of one subgroup produce points of the same subgroup again. For example, repeated addition of an arbitrary point of a subgroup with itself produces all the points of the subgroup. By repeating the addition for the number of times equal to the order of the subgroup, the infinity point is produced. The next addition produces the initial point. If the order of an elliptic curve is a prime, the curve cannot be separated into subgroups, and the order of any point would be equal to the order of the elliptic curve.
The following is a list of terms and definitions which will be referred to describe the background art and the present invention.
p: a prime integer;
GF(p): a finite field with p elements, a complete residue system modulo p;
Fp: a brief notation of GF(p);
E: an elliptic curve, defined over Fp by equation y
2
=x
3
+Ax+B (mod p);
E(Fp): a group of elements called elliptic curve points, defined over Fp;
#E(Fp): an order of elliptic curve and also a number of points on a curve;
N: another designation of a number of points o
Kuzmich Vsevolod M.
Rostovtsev Alexander G.
Barrón Gilberto
Birch & Stewart Kolasch & Birch, LLP
LG Electronics Inc.
Song Hosuk
LandOfFree
Cryptographic method using construction of 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 Cryptographic method using construction of elliptic curve..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cryptographic method using construction of elliptic curve... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3304951