Research Article
Theory and Implementation of Elliptic Curve Cryptography
Department of Physics, Eastern Mediterranean University, Gazimagusa, North Cyprus, via Mersin I O, Turkey
With the rapid growth of the use of computers to exchange information electronically, the physical way of providing security by locks, sealing and signing documents and so on, is eliminated. However the need to exchange information securely is still very important and is therefore provided in electronic documents; usually by encryption and digital signatures. The science of keeping messages secure is called cryptography. Cryptography involves encryption and decryption of messages. Encryption is the process of converting a plaintext into ciphertext by using an algorithm and decryption is the process of getting back the encrypted message (Fig. 1). A cryptographic algorithm is the mathematical function used for encryption and decryption. In addition to providing confidentiality, cryptography is often required to provide Authentication, Integrity and Non-repudiation.
The essence of cryptography is traditionally captured in the following problem: Two parties (the tradition is to call them Bob and Alice) wish to communicate over an insecure public communication channel in the presence of malevolent eavesdropper (the tradition Eve). Bob and Alice could be military jets, e-business or just friend trying to have a private conversation (Fig. 1). They can't stop Eve listening to their radio signals (or tapping their phone line, or whatever), so what can they do to keep their communication secret? One solution is for Alice and Bob to exchange a digital key, so they both know it, but it's otherwise secret.
Moreover, it is worthy to note right from the start that the hardest part of computer security is the piece between the computer and the user. While the hardest part of encryption is maintaining the security of the data when it's being entered into the keyboard and when it's being displayed on the screen. In case of the digital signatures, the hardest part is proving that the text signed is the same text that the user viewed. And finally the hardest part of computer forensics is to know who is sitting in front of a particular computer at any time.
There are two popular kinds of cryptographic protocols: symmetric-key and asymmetric-key protocols. In the symmetric-key protocols, a common key (the secret-key) is used by both communicating partners to encrypt and decrypt messages[1]. Among these are DES, IDEA and AES. These symmetric-key cryptosystems provide high speed key and communication but have the drawback that a common (or session) key must be established for each pair of participants[2]. However, in 1976, Diffie and Hellman[3] introduced Public-Key Cryptography. The encoding function here is a trapdoor function-one whose inverse is impractical to implement, unless some extra information is available. This extra information (called the decrypting-key) is not required for encrypting the message, yet is essential for decrypting it in reasonable time. This makes it much easier to encrypt messages than to decrypt them. The beauty of such a system is that the encrypting process need not be kept secret. Each user has his own or a personal encrypting-function, which is public information (hence the name Public-Key) and a decoding key, which he keeps secret.
Fig. 1: | Shows a schematic classical cryptographic data communication |
The public-key protocol employs a pair of different but associated keys. One of these keys (the public-key) is used either for encryption (signature) of the messages and; a different key (the private-key) is used for either decryption (confidentiality) of the message[4]. Different public-key cryptographic systems are used to provide public-key security. Among these we can mention the RSA[5], Diffie and Hellman[3] (DH) key exchange algorithm, digital signature algorithm (DSA)[6,7] and ElGamal[8] cryptosystem. These systems provide these services by relying on the difficulty of different classical mathematical problems, hence provide the services in different ways.
The public-key cryptosystems are, however, slower than the symmetric ones but provide arbitrary high levels of security and do not require an initial private key exchange between two communicating parties. In the asymmetric protocol the public-key is released to the public while the other, the private-key, is known only to its owner. Because of this feature, these cryptosystems are considered to be indispensable for secure communication and authentication over open (insecure) networks[9]. It is designed to be computationally intractable to calculate a private-key from its associated public-key; that is, it is believed that any attempt to compute it will fail even when up-to-date technology and equipment are used[10]. With a public-key cryptosystem, the sender can encrypt a message using the receivers public key-without needing to know the private-key of the receiver. Therefore, they are suitable for communication among the general public. Public-key cryptosystems can also be used to make a digital signature[11].
However, in real applications, both symmetric and asymmetric protocols are used. The public-key algorithm is first used for establishing a common symmetric-key over insecure channel. Then the symmetric system is used for secure communication with high throughput. Due to comparative slowness of the public-key algorithms, dedicated hardware is desirable for efficient implementation and operation of the cryptographic systems.
In the mid 1980s researchers noticed that another source of hard problems might be discovered by looking at the elliptic curves[12,13]. The invention of Elliptic Curve Cryptography (ECC) offered a new level of security for public key cryptosystems[14-16], which provide both encryption and digital signatures services. One potential use of elliptic curves is in the definition of public-key cryptosystems that are close analogs of existing schemes like RSA, ElGamal, DSA and DH etc. Furthermore, elliptic curve can provide versions of public-key methods that, in some cases, are faster and use smaller keys, while providing an equivalent level of security. Their advantage comes from using different kind of mathematical group for public-key arithmetic.
To date many research papers in Elliptic Curve Cryptography (ECC) have been published by researchers all over the world, as can be viewed in the refs. However, the idea of using elliptic curves in cryptography is still considered a difficult concept and is neither widely accepted nor understood by typical technical people. The problem may stem from the fact that there is a large gap between the theoretical mathematics of elliptic curves and the applications of elliptic curves in cryptography.
Introduction and history of elliptic curve: The name elliptic curve is based on the ellipse. Elliptic curves were first discovered after the 17th century in the form of Diophantine equation[17], y2-x3 = c, for c∈□. Further, it is important to note that, however, it is easy to calculate the surface of the ellipse, it is hard to calculate the circumference of the ellipse. The calculation can be reduced to an integral:
(1) |
This integral, which cannot be solved easily, was the reason to consider the curve Y2 = X3+AX+B. This was done already during the 18th century. Probably, it was Abel in ca. 1820 who introduced the addition of points on the curve. At the moment there are several definitions for an elliptic curve. However, the following definition is used usually:
Definition: An elliptic curves E, defined over an arbitrary field K, is a non-supersingular plain projective third degree curve over K with a K-rational point O (i.e., with coordinates in K) over curve E.
Such a curve can be described by its so-called Weierstraβ form, in homogeneous coordinates x,y,z:
(2) |
where, a1 ,...., a6 ε K, such that the discriminant Δ ≠ 0. This discriminant is a polynomial expression in the coefficient a1 ,...., a6. The restriction Δ ≠ 0 is necessary and sufficient for E in order to be a non-singular. The curve E has exactly one K-rational point at infinity, i.e., z = 0, the point (0 : 1 : 0). This point plays the role of O (origin). Sometimes we want to express that a curve E is based over field K. We do this by notation E/K.
In general, it will restricted ourselves only to the affine part z ≠ 0 of elliptic curves E:
(3) |
For fields K of characteristic >2 such as ¤, (, £ or Fp with p>3 we can transform the Weierstraβ form for the affine curve by the coordinate transform:
(4) |
to a curve of the form: E/K: Y2 = X2+aX+b
where, a,b ε K such that the discriminant Δ = 4a3+27b2≠0. This form also known as Weierstraβ short form will be used later.
Remark: For practical applications finite field of the form are very important. For such elliptic curves the theory as mentioned above has to be modified.
In 1955, Yutaka Taniyama asked some questions about elliptic curves, i.e., curves of the form y2 = x3+ax+b for constants a and b[18]. Hellegouarch[19] studied the application of elliptic curves for solving Fermat's Last Theorem in 1971. Elliptic curves can also be looked at as mathematical constructions from number theory and algebraic geometry, which in recent years have found numerous applications in cryptography[12].
Elliptic curve cryptosystem (ECC) is relatively new. The ECC was first introduced by Miller[13] and independently by Koblitz[12] in the mid 1980s and today it has evolved into a mature public-key cryptosystem. It was also recently endorsed by the U.S. government[20]. The ECC from the very beginning was proposed as an alternative to established public-key systems such as DH, DSA, RSA and ElGamal cryptosystems. This is so, because elliptic curves do not introduce new cryptographic algorithms, but they implement existing public-key algorithms using elliptic curves. In this way, variants of existing schemes can be devised that rely for their security on a different underlying hard problem.
Elliptic curve scheme: An elliptic curve can be defined over any field (e.g., real, rational, complex). However, elliptic curves used in cryptography are mainly defined over finite fields[21]. An elliptic curve consists of elements (x, y) satisfying the equation y2 = x3+ax+b together with a single element denoted by O, called the point at infinity, which can be visualized as the point at the top and bottom of every vertical line. Addition of two points on an elliptic curve is defined according to a set of simple rules (e.g., point P1 plus point P2 is equal to point -P3 as shown in Fig. 2). The addition operation in an elliptic curve is the counterpart to modular multiplication in common public-key cryptosystems and multiple addition is the counterpart to modular exponentiation[22,23], as will be seen later.
Elliptic curve systems base their difficulty on the elliptic curve version of the DLP, which is simply called the Elliptic Curve Discrete Logarithm Problem (ECDLP). Here, the underlying field of integers modulo prime p is replaced by points on an elliptic curve defined over a finite field. Since the ECDLP is significantly harder than the DLP, even a sophisticated hacker would require most of the worlds computing power for a few years to break an elliptic curve cryptosystem.
Fig. 2: | Elliptic curve |
The implementation of elliptic curve cryptography requires several choices like the type of finite field, algorithm for implementing the elliptic group operation and elliptic curve protocols which influence the performance of ECC. Elliptic curves have further shown themselves to be remarkably useful in a range of applications including primality testing and integer factorization[24-27].
Elliptic Curve Cryptosystems (ECCs) also include key distribution, encryption and digital signature algorithms. The key distribution algorithm is used to share a secret-key, the encryption algorithm enables confidential communication and the digital signature algorithm is used to authenticate the signer and validate the integrity of the message[28,29].
The mechanics of finite field Fp: Abstractly a finite field consists of a finite set of objects called field elements F together with the description of two operations-addition and multiplication-that can be performed on pairs of field elements. These operations must possess certain properties. It turns out that there is a finite field containing q field elements if and only if q is a power of a prime number and furthermore that in fact for each such q there is precisely one finite field. The finite field containing q elements is denoted by Fq. Here only two types of finite fields Fp are used-finite fields Fp with q = p, p is an odd prime which are called prime finite fields and finite fields with q = 2m for some m under binary operation. The order of a finite field is the number of elements in the field. There exists a finite field of order q if and only if q is a prime power, then there are, however, many efficient implementations of the field arithmetic in hardware or in software[12,15,21,30,31].
If in adding the multiplicative identity 1 to itself in F never gives 0, then we say that F has characteristic zero; in that case F contains a copy of the field of rotational numbers. Otherwise, there is a prime number p such that 1+1+...+1 (p times) equals 0 and p is called the characteristics of the field. In that case F contains a copy of the field Z/pZ, which is called its prime field[32].
If q = pm where p is a prime and m is a positive integer, then p is called the characteristic of Fp and m is called the extension degree of Fp. Most standards which specify the elliptic curve cryptographic technique restrict the order of the underlying finite field to be odd prime (q = p) or a power of 2 (q = 2m). This study describe the elements, operations and implementation of the finite field Fp, while the elements and operations of can be found elsewhere[33,34].
Let p be a prime number. The finite field Fp called a prime field, is comprised of the set of integers {0,1,2,...., p-1} with the following arithmetic operations[22]:
• | Addition: If a, b ε Fp, then a+b =r, where, r is the remainder when a+b is divided by p and 0≤r≤p-1. This is known as addition modulo p. |
• | Multiplication: If a, b ε Fp, a · b = s where, s is the remainder when, a · b, is divided by p and 0≤s≤p-1. This is known as multiplication modulo p. |
• | Inversion: If a is a non-zero element in Fp, the inverse of a modulo p, denoted a-1, is the unique integer c ε Fp for which a · c = 1. |
The mechanics of elliptic curves: An elliptic curve over Fq is defined in terms of the solutions to an equation in Fq. The form of the equation defining an elliptic curve over Fq differs depending on whether the field is a prime finite field or a characteristic 2 finite field.
Roughly speaking, an elliptic curve is the solution set of a cubic equation in two variables. For number-theoretic purposes, the equation can be brought into the short Weierstraβ form, i.e., E: y2 = x3+ax+b, with integer coefficients a and b, although other forms are often used as well. The solution set is relative to some field of definition, such as the field of complex numbers. Of greatest interest are the rational solutions of such equations. The rational points on the elliptic curve E are the points over Ep(a, b) that satisfy the defining equation. If the set of parameters (a, b, p) are specified, the number of rational points on the elliptic curve is determined uniquely; this number is called the order of the elliptic curve E and is denoted by #E. It is known that rational points form an additive group in the addition over the elliptic curve shown in Fig. 2. But much of the theory-and essentially all the cryptographic applications-lie in the solutions mod p (or, more generally, in solutions over finite fields). One of the nice features of elliptic curves mod p is that the size of the solution set is never too far from p. The exact theorem, proved by Hasse[35] in 1933, is |Np-p|#2p½ where, Np is the number of solutions mod p. This ensures that for large p, there are lots of solutions over the finite field Fp.
But the nicest feature of elliptic curves, over any field, is that the solution set, with an extra point at infinity tacked on, forms a group, with a group law given by an explicit pair of rational functions. The group turns out to be abelian (hence the additive notation) and the point at infinity, usually denoted by O, is its zero element. In many cases, the order of the group (over Fp) is itself a large prime, q, or a small multiple of such a prime. When that happens, the curve is ripe for use in cryptography. In particular, it can be used to attach a digital signature to a message.
Elliptic curves over galois fields: The core of the ECC is when it is used with Galois Field it becomes a one way function i.e., the maths needed to compute the inverse is not known. The main reason for attractiveness of ECC is the fact that there is no sub-exponential algorithm known to solve the discrete logarithm problem on properly chosen elliptic curve. This means that significantly smaller parameters can be used in ECC than in other competitive systems such as RSA, DH and DSA. This helps in having smaller key sizes and hence, faster computations[36].
Let an elliptic curve group over the Galois Field Ep(a, b) where, p>3 and be prime, is the set of solutions or points P = (x, y) such that (x, y ε Ep(a, b)) that satisfy the equation:
(6) |
for 0≤x < p together with the extra point O called the point at infinity. For a given point P = (xp, yp), xp and yp are called the x and y coordinates of P, respectively. The number of points on Ep(a, b) is denoted by #E(Fp). The Hasse Theorem states that[35]:
(7) |
The constants a and b are non negative integers smaller than the prime number p and must satisfy the condition:
(8) |
For each value of x, one needs to determine whether or not it is a quadratic residue. If it is the case, then there are two values in the elliptic group. If not, then the point is not in the elliptic group Ep(a,b).
We should first explain why we have required the coefficients of the cubic polynomial in Eq. (6) to satisfy, 4a3+27b2 ≠ 0 mod p. Notice that:
(9) |
is the discriminant of the cubic polynomial f(x) = x3+ax+b. If Δ = 0 then f(x) = 0 has at least a double zero X (root which makes f(x) = 0) and clearly (x, 0) is on E. For F(x, y) = y2-x3-ax-b = 0, this point satisfy:
(10) |
That is, (X, 0) is a singular point at which there is no definition for a real tangent value. With the tangent-and-chord operation failing at the singular point (X, 0), E cannot be a group.
Elliptic curves over a characteristic 2 finite field GF(2m) which has 2m elements have also been constructed and are being standardized for use in ECCs as alternative to elliptic curves over prime field finite field[24].
Construction of an elliptic curve over Fp: Let the prime number p = 23 and consider an elliptic curve E: y2 = x2+x+4 mod 23 defined over F23. From Eq. (6) and let the constants a = 1 and b = 4. It is verified that:
(11) |
Therefore, E is indeed an elliptic curve. We then determine the quadratic residues Q23 from the reduced set of residue Z23 = {1,2,3,...,21,22}:
Table 1: | Quadratic residues of Q23 |
Therefore, the set of (p-1)/2 = 11 quadratic residues Q23 = {1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18}. Now, for 0≤x < p, compute, y2 = x3+x+4 mod 23 and determine if y2 is in the set of quadratic residues Q23:
Table 2: | Quadratic residues of Q23 and their roots |
Hence, the points in E(F23) are O and the following:
(12) |
Figure 3 shows a scatterplot of the elliptic group Ep(a, b) = E23(1, 4).
Fig. 3: | Scattaerplot of elliptic group Ep (a, b) = E23(1, 4) |
In real practice p is chosen to be a large prime number. Take, for example, a large group of points with prime number:
p = 6, 227,101,735,386,680,763,835,789,423,207,666,416,083,908,700,390,324,961,279 |
Next imagine a square grid (Fig. 3) with this many rows and columns. There is a curve defined over this space of the form: E: y2 = x3+ax+b(mod p) where, a and b are two more carefully chosen large numbers so that the curve is not weak and 4a3+27b2 ≠ 0 (mod p). This curve contains exactly N points, where:
N = 6,277,101,735,386,680,763,835,789,423,337,720,473,986,773,608.255,189,015,329 |
These points form a group, according to the rule above, which is ideal for elliptic curve Diffie-Hellman (ECDH) algorithm. Modern computers have no trouble dealing with numbers of this size, which are actually much smaller than those used in traditional DH and RSA cryptosystems. If you look at p as binary number youll see that it has a very special form, p = 2192-264-1, which makes computation much easier. It is interesting to note that p and N are so close to each other, relatively speaking; they only differ in the lower half of their bits. Elliptic curve theory predicts this.
Addition and multiplication operation over elliptic groups: There is a rule called the chord-and-tangent rule, for adding two points on an elliptic curve E(Fp) to give a third elliptic curve point as was discussed earlier in Section 2.0 Together with this addition operation, the set points E(Fp) forms with O serving as the identity. It is this group that is used in the construction of elliptic curve cryptosystems. The addition rule is best explained geometrically. Let P = (x1, x1) and Q = (x2, y2) be two distinct points on an elliptic curve E (Fig. 4). Then the sum of P and Q, denoted by R = (x3, y3), is defined as follows:
Fig. 4: | Geometric description of the addition of two ditinct elliptic curve P+Q = R |
Fig. 5: | Geometric description of the addition of two distinct elliptic curve P+P = R |
First draw the line through P and Q; this line intersects the elliptic curve in a third point. Then R is the reflection of this point in the x-axis. The elliptic curve in the Fig. 4 consists of two parts, the ellipse-like figure and the infinite curve.
If P = (x1, x1), then the double of P, denoted by R = (x3, y3), is defined as follows: First draw the tangent line to the elliptic curve at P. This line intersects the elliptic curve in a second point. Then R is the reflection of this point in the x-axis (Fig. 5).
The following algebraic formulae for the sum of two points and double of a point can now be derived from the geometric description in the next two sections.
The mechanics of elliptic curve arithmetic operations: All of the arithmetic operations make perfectly good sense modulo p, provided that the denominators are relatively prime to p. Specifically, we define the operation ∂ modulo p (O is the identity) by the following arithmetic operation:
Let the points P = (x1, y1) and Q = (x2, y2) be in the elliptic group EP(a, b) and O be the point at infinity. The rules for addition over the elliptic group EP(a, b) are:
1. | P+O = O+P for all P ε E(Fp) |
2. | If P = (x, y) ε E(Fp) and if x2 = x1 and y2 = -y1, that is P = (x1, x2) and Q = (x1, x2), (x1, -y1) = -P then P+Q = O (observe that -P is indeed a point on the curve). |
3. | Point addition: Let P = (x1, y1) ε E(Fp) and Q = (x2, y2) ε E(Fp), If P ≠ ±Q, then their sum P+Q = (x3+y3). |
4. | Point doubling: Let Let P = (x1, y1) ε E(Fp) and, If P ≠ -P. Then 2P = (x3+y3). |
Define x3 and y3 by:
(13) | |
and | |
where:
(14) |
The properties of binary operation
1. | Given an elliptic curve and two rational points on that curve: (x1, y1) and (x2, y2) ≠ (x1,-y1), we define a binary operation: |
(15) |
where, x3 and y3 are defined by Eq. (13). Note that the sum of the two points is not the third point on that line, but the reflection across the x-axis of that third point as shown in Fig. 4 and 5. It is still on the same elliptic curve.
2. | We now define a set, namely the rational points on an elliptic and a binary operation. We would like to make this into a group. To do this, we need to define a binary operation (x, y)∂(x, -y), we also need to find an identity and we have to find inverses. We can solve all our problems with one stroke as will be seen below. |
3. | Next we define O to be the identity for the binary operation ∂ and define: |
(16) |
The point O can be thought of as a point infinitely far north so that every vertical line passes through it. One of the beauties of this definition is that now every straight line which intersects the curve at two points also intersects at a third (Fig. 4 and 5).
Then the binary operation, ∂ mod p, is then given by:
(17) |
where, x3 and y3 are defined. In particular, if p is an odd prime then our binary operation is always defined.
Observe that the addition of two elliptic curve points in E(Pf) requires a few arithmetic operations (addition, subtraction, multiplication and inversion) in the underlying field Fp. We should also recall that gcd(a, b) = 1, then there exist an inverse of b such that: axb = 1 mod n, that is b is inverse of modulo n.
Many topics in implementations of arithmetic operations over elliptic curves will be discussed in this section: scalar point multiplications and methods representing points on an elliptic curve. The most basic operation is adding two points or doubling a point on an elliptic curve. It is more expensive computationally than a basic operation in a symmetric key cryptosystem (a block encryption/decryption). But it is still much faster than a basic modular multiplication over a cyclic group whose order is of the same security level.
For elliptic curve implementation, the methods, which included subtractions, are more attractive than the corresponding methods, which included divisions in calculating power in finite fields. The reason is division or inversion in finite fields is a more costly operation than multiplication, while subtraction is just as costly as addition in elliptic curve operations. We now discuss efficient algorithms to expedite implementation procedures in elliptic curve cryptosystems.
Implementation of multiplication/addition over an elliptic curve group modulo p: The multiplication over an elliptic curve group Ep (a, b) is the equivalent operation of the modular exponentiation in RSA.
Let P = (7, 3) ε E23 (1, 4). Then 2P = (x3, y3) is equal to: 2P = P+P = (x1, y1)+(x1, y1)
If (x1, y1) = (7, 3), then we can determine the values of λ, x3 and y3 by using Eqs. (13) and (14) as follows:
Therefore, 2P = (x3, y3) = (22, 18).
Next, let P = (4, 16) ε E23(1, 4) and Q = (14, 18) ε E23(1, 4). ThenP+Q = (x3, y3) is given by:
Hence P+Q = (17, 9). The set of points on E(Fp) forms a group under this addition rule. Furthermore, the group is abelian-meaning that P1+P2 = P2+P1 for all points P1, P2 ε E(Fp). The neutral point is the point at infinity.
Scalar point multiplication: basic methods: One crucial operation is scalar point multiplication since it determines the speed of an elliptic curve cryptosystem. That is, given an integer k and a point P.∈E(Fp), a scalar multiplication is the process of adding P to itself k times. By definition, . This problem is analogous to raising an element to the k-th power in the multiplicative subgroup GF(q)*. Cryptographic schemes based on ECC rely on scalar multiplication of elliptic curve points. Scalar multiplication of elliptic curve points can be computed efficiently using the addition rule together with the double-and-add algorithm or one of its variants.
Here we will implement, the scalar multiplication kP which we obtain by repeating the elliptic curve addition k times, by following the same additive rules and a generator point:
similarly
and finally
(x29, y29) = (0, 21) ∂(0, 2) = O |
since
The cost of elliptic arithmetic operations: The dominant cost operation in elliptic curve cryptographic schemes is scalar point multiplication, namely computing kQ where, Q is an elliptic curve point and k is an integer. This operation is the additive analogue of the exponentiation operation ak in a general (multiplicative-written) finite group. The basic technique for exponentiation is the repeated square-and-multiply algorithms.
For the speed of the elliptic curve cryptosystems, the number of elementary field operations for point addition is important. Here we are just interested in quadratic field operations, i.e., we do not care about operations which can be done in linear time. One important observation is then the fact that negating a point is for free, since for any non-zero point P = (x, y) ε E(Fp) the negative point is given as -P = (x, -y). If we count the quadratic field operations of the other basic point operations, we get the following results: Doubling a point takes one multiplication, two squaring and one inversion; adding two different points can be done with one multiplication, one squaring and one inversion in Fq. In practice, the inversion is by far the most time consuming part of these operations (in the computer algebra library LiDIA, one inversion of a random element in a 155-bit prime field takes about the same time as 25 multiplications in this field).
In the development and implementation of elliptic curve cryptography we are interested in the method for computing an equation of the form m A P where, m ε ¥>1 and let P ε E(Fq) be a non zero point on some given elliptic curve E. For a positive integer m we let [m] denote the multiplication-by-m map from the curve to itself. This map takes a point P to P+P+...+P (m summands). The notation [m] is extended to m≤0 by defining [0]P = O and [-m]P = -([m]P). So for instance, as above, [2]P = P+P, [3]P = P+P+P and [-3]P = -(P+P+P). This map is the basis of elliptic curve cryptography. Its properties; computation and uses will be, therefore, the core of this paper.
Basic facts
The frobenius endomorphism: A map which plays a crucial role in the theory of elliptic curves over finite fields is the Frobenius endomorphism. For a curve E/Fq we consider the map:
(18) |
For two points we have φq (P +Q) = φq (P)+φq (Q) . It is easy to see that the set E(Fp) is the set of points which are invariant under φq, i.e., we have P ε (Fq) ⇔ φq (P) = P.
The Frobenius endomorphismsatisfies the characteristic equation:
(19) |
which can be interpreted in the sense of operators which acts on the group of points of E:
(20) |
The integer t which appears in this formula is called trace of Frobenius and is denoted by Tr(φq). The following theorem explains the relation between t and the number of points, i.e.,:
(21) |
The group of torsion points: Let E/Fq be an elliptic curve. For n ε¥≥2 we write for the group of the n-torsion points of i.e., the point with nP = O. The structure of the group E[n] is well-known:
E[n] ≅ Z/n⊕ Z/n if gcd(n, q) = 1 |
Table 3: | Point addition/scalar point multiplicative values of P (note that: kP ≡ Pk, so that 29P ≡ P0 ≡ O ≡ (0, 21) etc.). |
The elliptic group structure: A user of ECC will be interested to know the structure of the group, especially he would like to know the number of the points, #E(Fp). For example: If he knows #E(Fp) he knows whether the Pohlig-Hellman[37] attack can be applied. In the Diffie and Helman[3] key exchange, security is dependent upon the order of the group not being divisible by any small primes. While in the Massey-Omura system, the order of the group must be known. Order, generally, is an important component to the security or effectiveness of any real cryptographic application of elliptic curves. It is impossible to write down all the points for large q. But it is not necessary at all. The formula of Hesse-Weil[35] can be applied, which reduces the amount of work enormously.
Group order: Let E be the elliptic curve over a finite field Fq. Hasses theorem states that the number of points on an elliptic curve (including the point at infinity) is #E(Fp) = q+1-t where , # E(Fp) is called the order of an elliptic curve E and t is called the trace of E[35]. In other words, the order of an elliptic curve E(Fp) is roughly equal to the size q of the underlying field[15].
Group structure: E(Fp) is an abelian group of rank 1 or 2. That is, E(Fp) is isomorphic to Zn1 x Zn2, where, n2 divides n1, for unique positive integers n1 and n2. Here Zn denotes cyclic group of order n. Moreover, n2 divides q-1. If n2 = 1, then E(Fp) is said to be cyclic. In this case E(Fp) is isomorphic to Zn1 and there exists a point P ε E(Fp) = {kP: 0≤k≤n1-1}; such a point is called a generator of E(Fp).
Cyclic elliptic curve[38]: Consider again the example above of E1, 4 (F23):
y2 = x3+x+4 mod 23 |
For example, P5 = (7, 20) ε E1, 4 (F23) because:
73+7+4 = 354 ≡ 9 ≡ 32 (mod 23) |
The above points Pi listed in Table 3 can be numbered in such way that:
(22) |
Thus, #E(F23) = 29, which satisfies the Hasse bound since:
Since #E(F23) = 29, which is prime and which is found by counting all the points, also known as naïve method. #E(F23) is cyclic and any point other than O is a generator of #E(F23). For example, P = (0, 2) is a generator as shown in Table 3.
Finding a point of given prime order on an elliptic curve: The order n of a point P ≠ O on an elliptic curve is a positive integer such that nP = O and mP ≠ O for any integer m such that 1≤m < n. The order n of a point must divide the order N of the elliptic curve. In fact, it is true for any group. If the elliptic curve order N = #E(Fp) is a prime number, then the group is cyclic and obviously all points except the point at infinity O are of order N.
Choosing a point P of prime order n: A simple method is usually applied in cryptographic practices when n is a large prime. Then the factor ℓ = #E(Fp)/n will not be divisible by n. Choose a random point Q ≠ O on the elliptic curve E, then verify whether the point P = ℓQ has order n. This can be done simply by checking that nP = O. (Since n is prime, there is no other positive integer m < n such that mP = O) If it is true, then P = ℓQ is the point we need; otherwise, choose another point Q and repeat. This is the technique deployed by D. Shank in the Shanks algorithm which we will discuss later in the text.
The mechanics of order of points: Let E(Fp) denote the set of rational points on E. It is easy to see that the number of points in E(Fp) with X-coordinate x ε Fp is 0, 1, or 2. More precisely, there are:
(23) |
rational points on E with X-coordinate equal to x. Here denotes the quadratic residue symbol (also known as Legendre symbol). Including the point at infinity, the set of rational points E(Fp) of E, therefore, has cardinality:
(24) |
When x3+ax+b is a square modulo p then two points are contributed to the order. When p|x3+ax+b one point is added. If x3+ax+b is not a square or divisible by p then nothing is contributed in the sum. This implies that evaluating the sum:
(25) |
is the same problem as computing #E(Fp). For very large primes (p < 200 say) a straightforward evaluation of this sum is an efficient way to compute #E(Fp). In practice it is convenient to make first a table of squares modulo p (as was done in Table 3) and then count how often x3+ax+b is a square for x = 0, 1,....., p-1. The running time of this algorithm is O (p1+ε) for every ε>0.
Many particular elliptic curves over particular finite fields, whose orders are easily computed or formulated, are implemented in cryptography for different purposes. For examples, the Koblitz curves or elliptic curves over a prime finite field Fp of the form Ep(a, 0): y2 = x3+ax, for a ≠ 0(mod p) or Ep(0, b): y2 = x3+b, for b ≠ 0 (mod p)[12].
For a general elliptic curve over larger finite field Fp, one should use Shanks Baby-step-Giant-step strategy[39]. Alternative techniques are also available to compute the exact order quickly, these are: Schoofs algorithm used to compute the order of an elliptic curve over very large finite field; reduction algorithm when the endomorphism ring of E is known.
Shanks method (baby-step, giant-step): The idea behind Shanks algorithm[39] is to pick up a random point P on the elliptic curve and to compute an integer m such that: p+1-2p½≤m≤p+1 2p½ and mP = 0. If we can find only one such number, then it is the order of the elliptic curve. If not, we find another point and continue. The groups, generated by all the points that we picked, will eventually have the order of the elliptic curve.
The elliptic curve version of his algorithm is as follows: Assume that Q is a generator of order n and given point A, we want to compute k such that kQ = A. Let m = . Store in a list L1 the pairs (j, jmQ) for 0≤j≤m-1. Sort this list by the second element of the pairs. Create a second list L2 from the pairs (I, -iq+A) for 0≤i≤m-1. Sort this list by the second element. Search the list until pairs (j, p) ε L1 and (j, p) ε L1 are found. We have:
Thus, the multiple of Q such that kQ = A is k = jm+i. Of course, A must be a multiple of Q for this algorithm to work. One simple way to be certain of this is to choose an elliptic curve with order prime p. Since the order of any element must divide the order of the group, every element must have either order 1, namely the identity, or order p. The space requirement is for storage of the two lists, each composed of n½ points. An algorithm of Daniel Shanks reduces running time O(n½ log n) and the space O(n½) points.
The time complexity is dominated by the sorting of these n½ elements. Its running time is O(p¼+ε) for every ε>0. This algorithm becomes impractical for somewhat larger primes; it becomes impractical when p has more than, say, 20 decimal digits, or when multiple values of m are available for every point p. However, Mestre[40] have developed a new algorithm which showed that if Shanks algorithm fails for an elliptic curve, then it will not fail on its twisted curve.
Implementation of Shanks Method (baby-step, giant-step): As an example consider our earlier elliptic curve: y2 = x3+4 mod 23. This curve has order 29. Choose as a generator Q = (0, 2) and the element of unknown
index A = | (18, 9). Let m = = 6 |
List 1 = | {(1, (9, 11), (2, (17, 9), (3, (10, 18), (4, (7, 3), (5, (0, 2)} |
List 2 = | {(1, (8, 15), (2, (17, 9), (3, (10, 5), (4, (22, 10), (5, (16, 19)} |
Item 2 in L1 matches item 2 in L2. This indicated that: 12Q = -2Q+A or 14Q = A which from Table 3, we have A = 14Q ≡ 14P = (18, 9) which is the same point we started with and so the order of point A is k = jm+i = 14. This is correct.
If an elliptic curve has Complex Multiplication properties, there are other efficient algorithms to count the points[41-43]. For larger values of p one needs the help of an algorithm developed by Schoof[44]. In 1985, Schoofs algorithm, which is of polynomial running time, was proposed and later has been improved both theoretically and practically to be used to compute the order of an elliptic curve over very large finite fields.
Pohlig and Hellmans method: This method (also referred to as Silver -Pohlig-Hellmans method)[37] reduces the problem to a determination of m mod pi, each of the primes pi in the prime factorization of n, the order of the group. Then we use the Chinese Remainder theorem to recover m.
Let be the order of g. Let p be any prime in the set {p1, K, ps} Then
we can write:
since g n/p has order p. Now a0 is the discreat logarithm of yn/p to the base g n/p. For a1, we write:
Each term aj now is a discrete logarithm to the base element gn/p. Hence it reduces from a difficult DLP to many easier baby-DLPs. Each baby-DLP can be solved using other algorithms. Its running time, O(∑ei (log n+pi)) group multiplications, depends mostly on the largest prime factor. Hence, it works efficiently only when n is a smooth number, that is, all primes pi are small. Therefore, in order to resist Pohlig and Hellmans algorithm, n should be divisible by a large prime number (>280), or indeed, n must be prime >280 for the maximum security possible.
The Schoof-Elkies-Atkin (SEA) algorithm: It is obvious that if we can calculate the trace Tr(Fq) of Frobenius, then we have information about E/Fq. The calculation of Frobenius is the kernel of the SEA-algorithm. Recent methods are based on the work of the Dutch mathematician Schoof[41] and were improved by Atkin and Elkies in late 90s at the end of the last century. Advanced methods from arithmetical algebraic geometry (modular forms) are used intensively. Finally this method became to be known as Schoof-Elkies-Atkin (SEA) algorithm[45]. SEA-algorithm can be used in order to calculate the number of points on an elliptic curve over Fp for large value of p.
Schoof studied for a prime ℓ ≠ p the torsion group E[R]. Then he considered how Frobenius endomorphism works on ℓ. The characteristic equation of Frobenius can be reduced modulo ℓ. We have:
(26) |
where, tR ≡ t mod ℓ and qℓ ≡ q mod ℓ. This equation can be rewritten as:
(27) |
We consider a (generic) point y. We calculate the righthandside and lefthandside of the previous equation for this point. We find for the lefthandside:
(28) |
We eliminate the y in the x-coordinate, since y2 = x3+ax+b, the x-coordinate can be written as the quotient . The lefthandside can be rewritten as the quotient . In the lefthandside tR is unknown. If the correct value of tR is chosen F(x) and have a common non-trivial divisor. We have to chose t1 = 0, 1, 2,..... until t1 fits. Now by varying R we find related values of t1. The value of t can be calculated using the Chinese Remainder Theorem[2].
Pollards rho-method and lambda-method: This method is a randomized version of Shanks Baby-step-Giant-step algorithm and it requires no significant storage of pre-computations. The algorithm was described in Pollard[46] later also explained in much cryptography literature. In short, we partition the group into 3 subsets and then perform the following recursive search: xi+1 = xiu, where, u is either xi, g or y depending on which subset xi belongs to. The search is completed until we find a value j such that xj = x2j.
By its running time, this method is also named a square root method. This algorithm also works on any group and it takes about (πn/2)½/R steps (group operations) if R microprocessors are used in parallel[47,48]. When n>2160, the DLP is still infeasible. Pollards lambda-method for catching kangaroos is applicable when the result is known to be in a certain range. If the length of that range is w, then the running time is about w½.
The above algorithms, i.e., Shanks Baby-step-Giant-step, Pollard-rho and Pohlig-Hellman, are called generic algorithms. The algorithms can work on any group and require no special group structure except that each element in the group has a unique representation. Shoup[49] showed that the lower bounds of running time for generic methods to solve DLP are proved that match the known upper bounds, about O((n)½), under some assumptions. That is, in order to improve the attack efficiently, one must know more about the structure of the group. There is also a method proposed by Silverman and Stapleton[50], to solve multiple discrete logarithms: logg y1,...., logg yM. This method was originally used to attack the ECDLP.
Index-calculus method: Over finite fields where the DLP is defined, there is another additional structure beyond the multiplicative structure. The index-calculus methods take advantage of this extra structure. It is generally believed that it is much more complicated, or even impossible, to apply index-calculus method to elliptic curves. In ECDLP, the group of points has no extra structure other than the basic operation: addition of two points. A similar approach as in DLP, by choosing a factor base B, could not work for E(Fq). The questions are: How to create a factor base for an elliptic curve? And may there be a method without requiring a factor base of elliptic curve points?
Flassenberg and Paulus[51] discussed that the sieving methods are still not efficient on ECDLP yet lifting points on E(GF(pn)) to points on an elliptic curve, where, (¤) is the rational field. That is, given P ε E(GF(pn)), find an elliptic curve. and a point such that Q ≡ P (mod p). The natural candidate for a factor base is a set of points of small height on The height of an elliptic curve point that is defined as the number of bits in the numerator and denominator of the x-coordinate of that point. But these points are too sparse to generate all points on the elliptic curve by scalar point multiplications. In order to have such a lifting with probability c, the points need to have a height of at least 2cp, which is impossible. Even when such a base exists, it is still a very difficult problem to find an efficient method for the lifting. Recently, Silverman[52] and Suzuki[52,53] gave a more detailed proof to confirm the impossibility of index calculus method for the ECDLP. The main reason is that a factor base for the ECDLP is exponentially bigger than a DLP factor base.
Public-key Cryptography (PKC): Diffie and Hellman[3] were the first to introduce the public-key cryptography to overcome the difficulty of key distribution encountered with the private-key cryptosystems. This protocol later become to be known as Diffie-Hellman (DH) key exchange. In the later years other public-key cryptosystems were developed for various different cryptographic application. Among these we can mention the RSA[5], Digital Signature Algorithm (DSA)[6,7] and ElGamal[8] cryptosystem. The invention of Elliptic Curve Cryptography (ECC) in 1985 offered a new level of security for public key cryptosystems[14-16], which provide both encryption and digital signatures services using already existing public-key algorithms.
It was Miller who first proposed the Diffie-Hellman key exchange protocol[8] on the bases of elliptic curve[13]. The elliptic curve based analogues of the ElGamal scheme and the Massey-Omura scheme[12,30] was proposed by Koblitz[12,30]. The first elliptic curve based analogue to the RSA scheme was introduced in 1991[54]. A more advanced elliptic curve based analogue to the RSA scheme was introduced by Demytko[55].
At the foundation of every public-key cryptosystem is a hard mathematical problem that is computationally infeasible to solve. For example, RSA and Diffie-Hellman rely on the hardness of integer factorization and Discrete Logarithm Problem (DLP), respectively[24,25,29]. Unlike these cryptosystems which operate over integer fields, the Elliptic Curve Cryptosystems (ECC) operates over points on an elliptic curve.
The mechanics of Discrete Log Problem (DLP): One of the important tool necessary for the implementation of public-key cryptosystems is the Discrete Log Problem (DLP). In an (abelian) group G (multiplicatively written) we can consider the equation y = xn, x, y ε G, n ε Z. If x and y are known real numbers and it is also known that x is some power (say, n) of y, then logarithms can be used to find (n(= logx (y)) in an efficient manner. However, if x and y are given such that, then in general it is technically much harder and hence the determination of n cannot be carried out in a reasonable amount of time. This is equivalent to the well-known real logarithm, we call n the discrete logarithm of y related to the base x[56,57].
Remark 1: The operation exponentiation x → y: = x can be implemented in as a quick, efficient algorithm.
Remark 2: If p is a prime number, then Zp denotes the set of integers {0, 1, 2,..., p-1}, where addition and multiplication are performed modulo p. It is well-known that there exists a non-zero element g ε Zp such that each non-zero elements in Zp can be written as a power of g; such that an element Zp is called a generator of Zp .
Remark 3: The Discrete Logarithm Problem (DLP) is the following: given a prime p, a generator g of Zp and a non-zero element β ε Zp , find the unique integer k, 0≤k≤p-2, such that β = gk mod p. The integer k is called the discrete logarithm of β to the base g.
Many popular modern cryptosystems base their security on the Discrete Logarithm Problem (DLP). Based on the difficulty of this problem, Diffie and Hellman[3] proposed the well-known Diffie-Hellman key agreement scheme in 1976. Since then, numerous other cryptographic protocols whose security depends on the DLP have been proposed, including: the ElGamal encryption and signature scheme[8], the U.S. government digital signature (DSA)[6,7] is perhaps the best known example of a DLP system, the Schnorr signature scheme[57] and the Nyberg-Reuppel signature scheme[58]. Due to interest in these applications, the DLP has been extensively studied by mathematicians for the past 20 years. The mathematical challenge here lies in computing discrete logarithms in finite fields of type Zp , which consist of the integers modulo a large prime p. Although this problem can be considered difficult, there are known sub-exponential time algorithms for solving it, such as the number field sieve. In practical terms, sub-exponential time means that a determined hacker with enough processing power can break the system in a few months.
The corresponding problem in additive (i.e., abelian) groups is: given P and kP (P added to itself k times), find the integer k. This is much more difficult. There is no one-step operation like taking logarithms that we can use to get the solution. So we may know P and kP and yet not be able to find k in a reasonable amount of time. This is called the Discrete Log Problem for abelian groups. We could always repeatedly subtract P from kP till we got O. But if k is large, this will take us a very long time. Several important cryptosystems are based on the difficulty of solving the DLP over finite abelian groups. The solution is even tougher if the underlying group arises from an elliptic curve over a finite field Fq.
Elliptic Curve Discrete Logarithm Problem (ECDLP): The fundamental mathematical operation in RSA and Diffie-Hellman is modular integer exponentiation[59]. However, the core of elliptic curve arithmetic is an operation called scalar point multiplication, which computes Q = kP (a point P multiplied k times resulting in another point Q on the curve)[57]. For example, 11P can be expressed as 11P = (2*((2*(2*P))+P. Furthermore, when a point P on an elliptic curve E is given, there is a minimum positive integer n such that nP = O, the identity point or point at infinity. Integer n is called the order of the point P. It is known that n is a divisor of the order of the curve E. Consider our earlier comment that these scalar multiples form a subgroup of points <P>. Here <P> is the finite cyclic group <P> = {P, 2P, 3P,..., nP}, with order n. The problem of calculating k from a given points P and Q is called the discrete logarithm problem over the elliptic curve (ECDLP)
We now give a more precise definition of the ECDLP: Given an elliptic curve E(Fq), point P ε E(Fq) of order n and a point Q ε E(Fq), determine the integer k 0≤k≤n-1, such that Q = kP, provided that such an integer exists. Here Q is the public-key and k is the private-key. Thus, the ECDLP is based on the intractability of scalar multiplication of points on elliptic curves. Note that the number k is called the discrete log of Q base P, which is why this is referred to as the Elliptic Curve Discrete Logarithm Problem. Point P is called the base point in this problem. We call k = logpQ the elliptic curve discrete logarithm of Q to the base point P.
Note that we can easily calculate Q = kP from given k and P, but it is computationally difficult to calculate the scalar k from points Q and P. The security of ECC relies on the hardness of solving the Elliptic Curve Discrete Logarithm Problem (ECDLP), which states that given P and Q = kP, it is hard to find k[11]. Because Pohlig-Hellman algorithm reduces the computation of k to the problem of computing k modulo each prime factor of n. So if n is a large prime, the ECDLP becomes harder. In practice, one must select an elliptic curve that has some points (base point G) which has large prime order n, and #E(Fq) = n A p, where h is a small integer. To date, the most efficient general algorithm to solve the ECDLP is Pollard-ρ, which has / (2r) , where r is the parallelized processor number. The runtime is exponential in n.
While a brute-force approach is to compute all multiples of P until Q is found, k would be so large in a real cryptographic application that it would be infeasible to determine k in this way. If a prime p as large as 160-bits long is selected, we cannot find k within a reasonable time, even if we use the most efficient algorithms known so far with the worlds most powerful computers.
Based on the difficulty of this problem, Koblitz[12] and Miller[13] independently in 1985 proposed using the group of points on an elliptic curve defined over a finite field to implement the various discrete log applicable to existing public-key cryptosystems. One such cryptographic protocol that is being standardized by a accredited standards organizations is the elliptic curve analog of the digital signature algorithm (DSA), called elliptic curve digital signature algorithm (ECDSA), which we will discuss later in the text.
In summary, the ECDLP is considered more difficult than the DLP for DSA and more difficult than the IFP (Integer Factoring Problem) on which RSA cryptosystems are based.
Key exchange protocol in PKC: The mathematical idea fundamental to public-key cryptography is that of a hard problem and from such problems, mechanisms for public-key key exchange might be constructed[6], if an additional technical requirement (a trapdoor) can be designed then the hard problem might possibly be used to constructed a public-key encryption or a digital signature algorithm[6]. Today the candidate hard problems which apply for public-key cryptography is discrete logarithm problem over a finite field[29] and integer factorization[25]. It is often stated that IFP is easier to state and understand than the ECDLP. However, this may be true, it is important to note that IFP has not been seriously studied by a multitude of people over thousands of years, there have been only two major advances in techniques for solving IFP: the quadratic sieve factoring algorithm (together with its predecessor, the continued fraction factoring algorithm) and the number field sieve. The latter algorithm involves some sophisticated mathematics (especially algebraic number theory) and is only completely understood by a small community of theorists. Furthermore, prior to computer age, mathematicians were constrained to looking for algorithms for Integer Factorization Problem (IFP) that were efficient by hand rather than by large networks of computers. While in case of ECDLP, a fact that is commonly overlooked is that much of the work done on the DLP prior to 1985 also applies to the ECDLP - i.e., because the ECDLP can be viewed as being the same as the DLP but in a different algebraic setting.
In RSA, public and private keys denoted by {e, n} and {d, n}, respectively, are generated by relying on the IFP[60] which, generally stated, is: Given a large number n which is a product of two prime numbers p and q: n =pq, it is difficult to determine the two prime factors by only knowing n. These primes are then used to generate the keys[2] . The most common way of trying to break this system, is by trying to factor n (from the public-key) to obtain the two primes from which the private-key can be determined[61]. This is very costly. Unfortunately, encrypting a message M, involves exponentiation, C = Me, modn, which involves a lot of computation.
Keys in ECC are generated by relying on the Elliptic Curve Discrete Logarithm Problem (ECDLP) which is the problem of determining an integer k (provided it exists) such that kP = Q where P and Q are points on the elliptic curve[62]. ECC does not involve exponentiation, but uses multiplication, hence it is not as computationally costly as RSA. Also, the underlying mathematical problem of ECC, ECDLP is fully exponential, whereas sub-exponential algorithms exist for IFP used in RSA[63]. Because it is more 'infeasible' to solve ECDLP the same level of security, can be provided with shorter keys in ECC compared with RSA.
Menezes and Johnson[63] gives comparisons of the difficulty of these problems. His conclusion is that the ECDLP is computationally more difficult than the DLP or the IFP, hence, cryptosystem based on elliptic curve can be as secure as their more traditional counterparts with significantly smaller fields. The expected time to solve the ECDLP with a point P as the generator having order of a 160-bit prime is approximately equal to the time required to solve the DLP with a 1024 bit modulus or to factor a 1024 bit n into primes p and q. These estimates are based on the currently best known algorithms for the problems: for the ECDLP this is Pollards-ρ method, for the DLP and the IFP the best algorithm is the number field sieve. The reason for the large difference in field size for the different systems is because of the running times of the algorithms for the problems. No sub-exponential time algorithm for the ECDLP has been found that applies to general curves; the fastest for the DLP are not applicable in the elliptic curve setting. Due to these factors, ECC is better suited for low bandwidth, computational power and memory situations especially in mobile and wireless environment[55].
Elliptic curve encryption algorithm: Elliptic curve cryptography can be used to encrypt plaintext message, M, into ciphertexts. The plaintext message M is encoded into a point PM from the finite set of points in the elliptic group, Ep(a, b). The first step consists in choosing a generator point, G ε Ep(a, b) such that the smallest value of n for which nG = O is a very large prime number. The elliptic group G and the generator G are made public.
Assume that Bob and Alice intends to communicate. Each user selects a private key and uses it to compute their public-key. For example, Alice (A) selects a private-key nA<n and computes the public-key PA as: PA = nAG. To encrypt the message PM for Bob (B), Alice chooses a random integer k and computes the ciphertext pair of points PC using Bobs public-key PB:
PC = [(kG), (PM+k PB)] |
After receiving the ciphertext pair of points, PC, Bob multiplies the first point, (kG) with his private-key, nB and then subtracts the result to the second point in the ciphertext pair of points, (PM+k PB):
(PM+k PB)-[nB(kG)] = (PM+k nBG)-[nB(kG)] = PM |
which is the plaintext point, corresponding to the plaintext message M. Only Bob, knowing the private-key nB, can remove nB(kG) from the second point of the ciphertext pair of point, i.e., (PM+k PB) and hence retrieve the plaintext information PM.
Implementation of elliptic curve encryption scheme: The elliptic curve group generated by our earlier elliptic curve i.e., Ep(a, b) = E23(1, 4). Since #E(F23), which is prime. E(F23) is cyclic and any point other than O is a generator of E(F23). For example, G ≡ P = (0, 2) is a generator point such that the multiples kG of the generator point G are (for 1≤k≤29), as shown in Table 3.
If Alice wants to send to Bob the message M which is encoded as the plaintext point PM = (7, 3) ε E23 (1, 4). She must use Bobs public-key to encrypt it. Suppose that Bobs secret-key is nB = 6, then his public-key will be:
PB = nBG = 6(0, 2) = 6P = (9, 11) |
Alice selects a random number kA = 15 and Bobs public-key PB = (9, 11) to encrypt the message point into the ciphertext pair of points:
Upon receiving the ciphertext pair of points, PC = [(18, 14), (13, 11)], Bob uses his private-key, nB = 6, to compute the plaintext point, PM, as follows:
the Weil pairing can be defined by |
or
(PM+kPB)-[nB(kG)] = (7, 3) |
and which maps the plaintext point PM(7, 3) back into the original plaintext message M.
The mechanics of Elliptic Curve Diffie-hellman (ECDH) key exchange scheme: The elliptic curve Diffie-Hellman scheme is a key agreement scheme based on ECC. It is designed to provide a variety of security goals depending on its application - goals it can provide include unilateral implicit key authentication, mutual implicit key authentication, known-key security and forward secrecy-depending on issues like whether or not public keys are exchanged in an authentic manner and whether key pairs are ephemeral or static[64,65].
Besides the curve equation, an important elliptic curve parameter is the base point, P, which is fixed for each curve[59]. In the Elliptic Curve Cryptosystem, the large random integer k is kept private and forms the secret-key, while the result Q of multiplying the private-key k with curves base point P serves as the corresponding public-key.
In ECDH key agreement, two communicating parties, say Alice (A) and Bob (B) agrees to use the same curve parameters[31,66]. They generate their private keys, kA and kB and corresponding public-keys QA = kAP and QB = kBP. The parties exchange their public-keys. Finally, each multiplies their private-key and the others public-key to arrive at a common shared secret-key kAQB = kBQA = kAkBP = SAB, P, where, k= kA kB. The session-keys are the same (since SAB = SBA = k); hence Alice and Bob now have a shared secret-key k. Future communications occur using the session key k. Thus, k can be used as a session-key for a private-key encryption algorithm such as Data Encryption Standard (DES) or AES, or any other cryptographic protocol[2].
The protocol depends on the discrete logarithm problem for its security. It assumes that it is computationally infeasible to calculate the shared secret key, SABP, given the two public values QA = kAP and QB = kBP when the prime p is sufficiently large.
If Eve (the eavesdropper) can recover SAB from this data then Eve is said to have solved Diffie-Hellman Problem (DHP). However, it turns out that if the numbers are all sufficiently large, it is very hard to calculate the discrete logarithm in a reasonable time. The security of the Diffie-Hellman algorithm depends on this fact. It is believed for most groups in use in cryptography that DHP and the DLP are equivalent[67,68], in complexity-theoretic sense (there is a polynomial time reduction of one problem to the other and vice versa. Meyer[69] has shown that breaking the Diffie-Hellman protocol was equivalent to computing discrete logarithms under certain assumptions.
The base point P for this system is one with large order in E. If the subgroup generated by P is small then the secret-key is being chosen from a small keyspace and the systems is vulnerable to keyspace search. The points on the curve E do not need to be generated by P; it may be the group is not even cyclic. It can be shown, however, that the group is the product of two cyclic groups[15]. Additionally, the order of E should have no small prime factors. If it does, then methods exist that can exploit this to solve this discrete logarithm problem.
Implementation of ECDH algorithm: As a simple example, lets use our earlier elliptic curve i.e., is Ep(a, b) = E23 (1, 4). Alice (A) chooses the secret-key k4 = 4 and computes her public-key (Table 3 and Eq. 22):
QA = kAP = 4P1 = P1+P1+P1+P1 = P4 = (1, 12) |
Similarly, Bob (B) chooses the secret-key kB = 6 and computes his public-key (Table 3):
QA = kAP = 4P1 = P1+P1+P1+P1 = P4 = (1, 12) |
Thus, their common secret-key SAB, i.e.,:
Alice computes:kAQB = 4P6 = P6+P6+P6+P6 = P24 = (7, 3)
and Bob computes: kBQA = 6P4 = P24 = (7, 3)
Such that: SAB = kAPB = kBPA = P24 = (7, 3)
An alternative form of ECDH is the Elliptic curve decision Diffie-Hellman problem (ECDDHP)[70]. The ECDDHP is stated as follows: Given a point p of order n in an elliptic curve E over a finite field Fq and three points (kP), (RP) and (mP), the ECDDHP is to decide whether m = kR (modulo the order of point P). The ECDDHP is not harder than the ECDHP. Boneh and Venkatesan[71], Boneh and Shparlinski[72] discussed many issues on security of the ECDHP and related schemes.
ElGamal for elliptic curves: Elgamal[8] was the first mathematician to propose a public-key cryptosystem based on the Discrete Logarithm problem. He in fact proposed two distinct cryptosystems: one for encryption and the other for digital signature scheme in 1984, well before elliptic curves were introduced in cryptography. Since then, many variations have been made on the digital signature system to offer improved efficiency over the original system. The ElGamal public-key encryption scheme can be viewed as Diffie-Hellman key agreement protocol in key transfer mode. Its security is based on the intractability of the discrete logarithm problem and the Diffie-Hellman problem.
Instead of Diffie-Hellman, Alice and Bob can also decide to use the protocol of ElGamal. This protocol does not create common key, but using ElGamal a message can be sent from Alice to Bob.
Alice and Bob agree to a prime p, a curve E and a point P (generator). Bob (B) generates a secret-key kB such that 1≤kB≤p-2. and publishes B = kBP, i.e., (E, P, B) are public-key system.
Encryption: Alice (A) has a message m which has to be sent and calculates the related point M. Alice then generates a random number kA such that 1≤kA≤p-2. She then computes A = kAP and ciphertext C = M+kAB and sends (A, C).
Decryption: Bob receives the message (A, C). He then computes: M = C-kBA = (M+kAkBP)-kAkBP
It is not trivial to find a point M for the message m. It is impossible to choose for m the x-coordinate of M. In about 50% of the cases m will not appear as x-coordinate. This problem can be avoided by adding a few bits to m, which can be chosen arbitrarily. If an x-coordinate is known, then it is easy to calculate the related y.
Implementation of ElGamal cryptosystem for elliptic curves: As a simple example, Bob (B) chooses public-key set: B = kBP = 10P = (22, 5), where the secret-key kB = 10 (taken from Table 3).
Let Alice select message point: M = (7, 3) (a point on E) and selects a random secret-key kA = 6, such that; A = kAP = 6P = 6 (0.2) = (9, 11) and encrypts the message:
C = M + kAB = (7, 3)+6(10P) = 24P+2P = 26P = (11.14) |
Decryption: Bob receives the message (A, C) = (6P, 26P).
He then computes: M = C-kBA = (11, 14)-10(6P) which decrypts to the original message m chosen point M = (7, 3).
The ElGamal signature algorithm is similar to the encryption algorithm in that the public-key and private-key have the same form; however, encryption is not the same as signature verification, nor is decryption the same as signature creation as in RSA. The DSA is based in part on the ElGamal signature algorithm.
For a long period of time (1985-1996) after the birth of the ElGamal signature scheme and the family of such signatures (e.g., Schnorr and DSS), it was widely believed that the difficulty of factoring such a signature should somehow be related to the discrete logarithm in a large subgroup of a finite field.
However, no formal evidence (formal proof) was ever established until 1996. When Poincheval and Stern succeeded in demonstrating affirmative evidence for relating the difficulty of signature forgery under a signature scheme in the ElGamal-family signatures to that of computing discrete logarithm[73]. They do so by making use of a powerful tool: the random oracle model (ROM) for proof of security[22]. The ROM-based technique of Pointcheval and Stern is an insightful instantiation of the general ROM-based security proof technique to proving security for the ElGamal-family signatures.
Massey-Omura elliptic curve-PKC: Massey-Omura is another public-key cryptosystem[74]. Assume that the curve E/Fq and the order n of E are public. Alice and Bob want to communicate. Each selects a random secret integer (e for encrypt) and computes, d = e-1 mod n, with the extended Euclidean algorithm. Alice selects eA (and computes dA); Bob selects eB (and computes dA). Alice wishes to send the plaintext message associated with the point P to Bob. She computes eAP and transmits this quantity. Bob receives this point; note that he cannot at all determine P at this time. He sends back to Alice the quantity eBeAP. Alice computes dAeBeAP. Note that dAeAP ≡ 1 mod n, so Alice has really unmasked eBP. She transmits this to Bob, who multiplies by his decryption key to get dBeBP = P. Quantities that have passed through insecure channels in this scheme are eAP, eBeAP and eBP. Solving the discrete logarithm problem given eAP and eBeAP for the quantity eB would allow the attacker (Eve) to compute dB and thus decrypt the message.
Implementation of Massey-Omura cryptosystems: Recall elliptic curve group generated by the our earlier elliptic curve is Ep(a, b) = E23(1, 4). Since #EF23 = 29, with G ≡ P = (0, 2)as the generator point such that the multiples kG of the generator point G are (for 1≤k≤29), are as shown in Table 3.
Alice selects: eA = 6 and computes dA = 6-1 mod 29 = 5
Bob selects: eB = 13 and computes dB ≡ 13-1 mod 29 = 9
Alice needs to transmit message point: M = (14, 18) = 21P to Bob.
She transmit: eAM = 6 (14, 18) = 6(21P) = 10P = (22, 5)
Bob replies with: eAeBM = 13(22, 5) = 13(10P) = 14P = (18, 9)|
Alice sends back to Bob: dAeBeAM = 5(18, 9)= 5(14P) = 12P = (17, 9)
Bob now multiplies this value by his decryption key: dB(dAeBeAM) = 9(17, 9) = 9 (12P) = 21P = (14, 18) = M
Bob recovers back the message point: M= (14, 18)
Menezes-Vanstone elliptic curve cryptosystem: This is also mentioned as a version of ElGamal cryptosystem in many cryptography literature. Let E be a non-supersingular elliptic curve defined over a finite field Fp, where prime p>3. Choose a point P ε E (Fp) of order n and compute the point n with the secret key Q = dP. The pair (P, Q) are public keys[75,76].
Encryption: The sender will choose a secret random number k in the interval [1, n-1]. The ciphertext of a message m = (m1, m2) ε will be the triple point including the point kP and two finite field elements y1 and y2 where y1 = c1m1(mod p) and y2 and assuming kQ = (c1, c2)≠ (0, 0).
Decryption: The receiver uses his secret key d to compute the point d(kP) that should be exactly kQ =(c1, c2). Hence, the receiver can recover the message by: (y1c1-1(mod p), y2 c2-1 (mod p)) = (m1, m2).
Analysis: There is also a message expansion of factor 2 (or 3/2 if one uses compressing techniques). The same drawback: if one knows mx (or my), he can solve for my (or mx) easily. To prevent this attack, one should send only kP and one finite field element y = c1m(mod p).
There are other proposals/standards for computing y1 and y2 in more complex algorithms from c1, c2, m1 and m2 in order to prevent an eavesdropper, who knows y1, y2 and half the message, say m1, from recovering the other half message m2 or from substituting m1 by his own message.
RSA algorithm
Key generation: Bob (B) chooses two large prime numbers p, q; n = pq; an integar eB, eBdB ≡ 1 mod φ (n)[2,9]. He publishes (n, eB) as the public-key and keeps (n, dB) as the secret-key (reveals it no one). Discard securely p and q.
Encryption:. Here C is the ciphertext of message M to B.
Decryption: M = CdB mod n
The product, n, is the modulus, e is the public exponent and, d is the secret exponent. You can publish your public-key freely, because there are no known easy methods of calculating d, p, or q given only (n, e) (your public-key). If p and q are each 1024 bits long, the sun will burn out before the most powerful computers presently in existence to factor your modulus into p and q. Authentication on the other hand, is not as easy to guarantee in public-key cryptography. Since everybody knows everybody elses public-key, Eve can easily send message to Alice claiming to be Bob[2].
Elliptic curve RSA (ECRSA) algorithm: We now mention RSA-type elliptic curve cryptosystems which may be both controversial and interesting to many researchers[14]. There are works on designing such cryptosystems or exploiting the connections with RSA cryptosystems.
Key generation
1. | Bob (B) selects two distinct primes p, q with p ≡ q ≡ 2 mod 3 and computes n = pq; |
2. | B chooses integers eB, dB with eBdB. (Here we can use (p+1)(q+1) in place of, 1cm (p+1)(q+1)). B publishes eB as public-key and keeps dB as secret-key. |
Encryption
1. | Alice (A) represents the message m as a pair of (m1, m2) and regards it as a point M on the elliptic curve E given by y2 = x3+ax+b, where b = m22-m12. (A doesnt need to compute b, because the encryption operation doesnt involve b.); |
2. | A adds M to itself eB times on eB to obtain C = (c1, c2) = eBM. Here C = (c1, c2) is the ciphertext of message m to B. |
Decryption:B computes dBC=M (mod n) on E to obtain M.
Note: dBC = dBeBM = (1+k(p+1)) M = M+k(p+1) M = M+∞ = M (mod p), with some k≤1. Similarly, for mod q, we have dBC = M modq. So dBC = M mod n. Where, (p+1) M mod p and (q+1) M mod q are ∞ , because E(Zn) and E(Fp) ⊕ E(Fq), and #E(Fp) = q + 1. The curve order is in such form because the curve is supersingular mod p and mod q.
Digital Signature Algorithm (DSA): For a digital signature, the main idea is no longer to disguise what a message says, but rather to prove that it originates with a particular sender. The Digital Signature Algorithm (DSA), was proposed in August 1991 by the U.S. National Institute of Standards and Technology (NIST) and was specified in a U.S. Government Federal Information Processing Standards[7] called the Digital Signature Standard (DSS). The DSA[11,77], is based on whats called the discrete logarithm problem, it requires that q be a 160-bit prime and p a prime between 512 and 1024 bits.
The RSA, for example, has a simple way of implementing digital signature algorithm[2]. If the owner of a code (n, e) wants to prove that shes the sender of a message M, she can use her private decoding exponent d to compute C = Md mod n and then send both M and C. The receiver can then persuade himself that the message truly originated with the owner of d by computing Ce and checking that its the same as M.
The DSA can be viewed as a variant of the ElGamal signature scheme[8]. Its security is based on the intractability of the Discrete Logarithm Problem (DLP) in prime-order subgroup of Zp*. In terms of computational difficulty, the discrete logarithm problem seems to be on a par with factoring. The basic idea of DSA is for the signer of message M-that is, the possessor of the value x behind the publicly known, gx mod p-to append a pair of numbers r and s obtained by secretly picking another number k between 1 and q, computing r = (gk mod p) mod q (i.e., computing gk mod p and then taking the remainder of that number mod q) and s = k-1(SHA(M)+xr) mod q, where k-1 is the multiplicative inverse of k (mod q) and SHA is the Secure Hash Algorithm. Another NIST standard, SHA (official acronym is SHA-1) reduces a character string of any length to a 160 bit string of gibberish. In the DSA, q is a 160 bit prime divisor of p-1 and g is an element of order q in Fp.
The receiver of (M, r, s) from person gx computes u = s-1 SHA(M) mod q and v = s-1 r mod q and then checks that ((gu)(gx)y mod p) equals r. If it doesnt, then, by elementary number theory, something definitely went wrong. If it does, then, according to NIST, you can safely assume that message M came from the presumably unique individual who knows the discrete logarithm of gx. Below we discuss the variant of DSA, using ECC, i.e., Elliptic Curve Digital Signature Algorithm (ECDSA).
Elliptic Curve Digital Signature Algorithm (ECDSA): Elliptic Curve Diffie-Hellman (ECDH)[59] and Elliptic Curve Digital Signature Algorithm (ECDSA)[78] are the Elliptic Curve counterparts of the Diffie-Hellman key exchange and Digital Signature Algorithm, respectively.
The Elliptic Curve Digital Signature Algorithm (ECDSA) works in much the same way as DSA. The only significant difference between ECDSA and DSA is in the generation of r. It requires an elliptic curve E over a finite field Fp with a point P of (large prime) order q, all of which is public. Each user is identified by a scalar multiple, xP, where, x is a (secret) number between 1 and q. To sign a message, the possessor of x again secretly picks a number k between 1 and q and appends a pair of numbers r and s. The number s is exactly as it is for DSA: k-1(SHA (M) +xr) mod q. But this time r is obtained by computing the point kP on the elliptic curve E over Fp: If kP = (k1, k2) is the result of that computation, then r = k1 mod q. To obtain a security level similar to that of the DSA, the parameter n should have about 160 bits. If this is the case, then DSA and ECDSA signatures have the same bitlength (320 bits).
Verifying an elliptic curve signature is also similar to the verification process for DSA: The receiver computes u and v as before, but then computes the point up+v(xP) on the elliptic curve E over Fp. If the x-coordinate of this point is not equal to r (mod q), the signature is rejected.
The computationally expensive steps in ECDSA are the scalar multiplications kP, uP and v(xP). (The computation of xP is done only once, by the owner of x.) These computations arent hard in the P-versus-NP sense. Theyre just tedious and time-consuming. But the special algebraic nature of elliptic curves presents some cost-cutting opportunities. Scalar multiplication, which a naive approach does by repeated doubling and straightforward addition (for example, 9P = 6P+2P+P, where, 2P = P+P and 6P = 2P+2P+2P), is, from the perspective of abstract algebra, a group endomorphism that is, a mapping of the group Ep into itself. As such, it can sometimes be re-expressed in terms of other endomorphisms that, while theoretically fancier, are easier to compute, much as an appropriate change of basis can turn an ugly matrix multiplication problem into a computational breeze.
Instead of using system-wide parameters, we could fix the underlying finite field Fq for all entities and let each entity select its own elliptic curve E and point P ε (Fq). In this case, the defining equation for E, the point P and the order n of P must also be included in the entitys public-key. If the underlying field Fq is fixed, then hardware or software can be built to optimize computations in that field. At the same time, there are an enormous number of choices of elliptic curves E over the fixed Fq.
The mechanics of ECDSA algorithm: We now describe ECDSA as an example of a digital signature algorithm. ECDSA is the elliptic curve analogue of the DSA, which is most famous signature protocol. This protocol needs not only the elliptic curve operations, such as scalar multiplication, field multiplication and field inverse multiplication, but also big integer multiplication, big integer inverse multiplication, modular operation and SHA-1, which is the 160 bit hash function.
In digital signature algorithm, the sender sends a message with the senders own unique signature and the receiver validates the received signature. Instead of providing a signature for the entire message, the message is first shortened to a fixed length by a hash function, then a short signature that is valid over the whole message is generated.
In the ECDSA, Alice (A) generates the signature with her secret-key and Bob (B) verifies the signature with As public-key. The algorithm below is the ECDSA protocol which A signs the message m and B verifies As signature.
The key generation
In ECC, the system parameters such as the prime p, elliptic curve E, base point G(x, y) and order n of the point G need to be shared between the sender and the receiver.
Key generation: Alice (A)
1. | Select a random integer s, where 1≤s≤n-1, |
2. | Compute Q = sG the public-key of the sender. |
3. | As public-key Q; As private-key is s. |
The signature is generated as follows:
Signature generation: (A)
1. | Hash the message and obtain the hash value f = hash(m) = SHA-1(m). |
2. | Generate a random number u, where 1≤u≤n-1 |
3. | Compute R = uG = (xR, yR) and h = d-1 mod n. |
4. | If c = 0 then go to step 1. |
5. | Compute d = u-1(f+sc) mod n |
6. | If d = 0 then go to step 1. |
7. | Output (c, d) as a signature of m. |
8. | Sends the message m and the signature (c, d) for the message m, to B. |
The signature is validated as follows:
The receiver (B) receives the message m and the signature (c, d). Then, the receiver B performs the following procedure to validate the signature:
1. | Verify that c and d are integers in [1, n-1]. |
2. | Hash the message and obtain the hash value f = SHA-1(m). |
3. | Compute h = d-1 mod n. |
4. | Compute h1 = fh mod n and h2 = ch mod n. |
5. | Compute P = h1G+h2Q= (xp, yp) and c = xp mod n. |
6. | If c = c, then the signature is valid. Otherwise, it is invalid and rejects the signature. |
As can be seen in the above algorithms, we need various operations for implementing the ECDSA protocol. However, we are only concerned with the elliptic curve operations, because these operations dominate the execution time in the protocol schemes. In this protocol, there are two operations, which are: the scalar multiplication in signature generation step 3 and the signature validation step 5 and, the point addition in the signature validation step 5.
How secure is ECDSA? Like all cryptosystems based on the unproved assumptions of complexity theory, that question will have no definitive answer unless some breakthrough shows the answer to be No. In 1998, Silverman, an elliptic curve expert at Brown University, sent shock waves through the elliptic curve crypto community when he proposed a new method for attacking the xP problem. Silvermans xedni algorithm (xedni is index spelled backward) uses sophisticated techniques in algebraic geometry to pry loose the x. Fortunately (for cryptographers), the xedni algorithm turns out to require exponential time.
Which elliptic can be chosen?
Supersingular elliptic curve [trace 0]: An elliptic E/Fp, q = pm, is called supersingular if Tr(φq) is divisible by p, Eq. (21). Lets take the case where, q = pm. In this case we have Tr(φq) = 0 or #E(Fp) = p + 1. A remarkable construction in order to reduce the ECDLP to a DLP in extension of Fp[79]. This construction is based on advance algebraic geometry for elliptic curves. It appears that the degree of the extension is 2 for supersingular curves over Fp. The ECDLP can be solved in subexponential time. To avoid this attack larger fields have to be used, in order to guarantee the same cryptographic security, which reduces the speed.
The crucial step in the construction of MOV is based on the use of Weil pairing. Let P, Q and R be points of order n, nP = nQ = nR = O. Let k ε ¥ such that E[n] . The Weil pairing en is a map which sends a pair of points to a n-th power of unity. This n-th power of unity can be embedded in . Therefore, the Weil pairing can be defined by: . The Weil pairing has the following properties:
1. | en(P, O) = 1 |
2. | en(P, P) = 1 |
3. | en(P, Q) A en(Q, P) = 1 |
4. | en(P, R) A en(Q, R) = en (P+Q,R) |
Suppose that Q = mP. Then for arbitrary points R we have en(P, R)m = en(Q, R). The problem to find an m such that xm = y over for x = en (P, R) and y =en(Q, R). That is, in the case of supersingular curves over Fp the ECDLP can be reduced to a normal discrete logarithm over . Menezes, Okamoto and Vanstone were able to deduce that in case of supersingular curves over Fq, the ECDLP can be reduced to DLP over a field of maximal .
Anomalous elliptic curves [Trace 1]: Elliptic curves E/Fp with Tr(φq) are called anomalous. If q = p, then it could be a good idea to chose an anomalous elliptic curve for cryptographic purposes, because the attack of Pohlig-Hellman cannot be applied. At the end of the last century Frey and Rück, Semaev, Satoh and Araki. Smart simplified the isomorphism between E(Fp) and the additive group of Fp[80]. In the last group the discrete logarithm problem can be solved easily. It occurs that an explicit isomorphism Ψ: E(Fp)→Z/pZ = Fp+ can be found easily:
Ψ: E(Fp)→Fp P→Ψ(P) |
If we would like to calculate a value of m for two points P and Q such that Q = mP, then this can be done by m = Ψ(Q)/Ψ(P).
Elliptic curves of trace 2: Work of G. Frey, M. Müller and H.G. Rück (1998), based work of J. Tate and S. Lichtenbaum, has interesting applications in the ECDLP[80]. This result is in fact an extension on the work of Menezes, Okamoto and Vanstone for supersingular curves. If p is a prime such that P = (p-1)/2 is prime as well and E/FP is an elliptic curve with Tr(Fp)= 2, i.e., #E(Fp) = p-1, then the ECDLP can be solved directly and reduced to the DLP in Fp in polynomial (logm) time. The used definitions and techniques are based on advanced algebraic geometry[81].
ECC in practice
ECC domain parameter: Elliptic curve parameters over the finite Fq or can be described by one septuple:
T = (q, FR, a, b, G, n, h) |
• | q: the prime p or 2n defines the field and at the same time decides the curve from; |
• | FR: field representation, a method to express the elements in the field (polynomial basis or normal basis for , Montgomery for Fn); |
• | a,b: the curve coefficients, depending on the security requirement . N = #E(Fq) is divisible by n; |
• | G: the base point: G = (xG, yG), one element in E(Fq), which has the largest order n; |
• | n: the order of G, large prime; |
• | h: #E(Fq)/n. |
ECC system setup: There are several choices to be made in implementing ECC system[82]:
• | Selecting a finite field Fq (and a field representing e.g., np = prime or p = 2k. |
• | Selecting an appropriate elliptic curve E/Fp (selecting a and b) (plus a point P of order q): random curve vs. a special curve etc. |
• | Selecting the algorithm for implementing the elliptic curve representation: windows method in affine versus projective coordinates etc. |
• | Selecting elliptic curve cryptography protocol (e.g., ECDH, ECDSA ) for the task. |
Note: Some protocols require additional steps; e.g., ElGamal and others require message embedding: m→Pm ε E(Fq).
There are some other requirements on the parameters to defend some sorts of attacks:
• | # E(Fq) should have a sufficiently large prime factor n to resist the parallelized Pollard-ρ attack; |
• | # E(Fq) ≠ q to resist Semaev, Smart and Satoh-Araki attacks on a anomalous curves; |
• | n doesnt divide qk-1 for 1≤k≤30, to resist Weil-Paring and Tate-Paring attacks; |
• | If choosing , m should be prime to resist some attacks on elliptic curve based on where m is composite (subfield basis). |
Selection criteria
• | Security of ECDLP[62] |
• | Implementation requirements: |
• | Speed, storage, power consumption. |
• | Optimization of field/EC operations of protocol. |
• | Platform dependence: speed and performance of primitives e.g., on a Pentium PC, the time for multiplication is only small multiple of that for addition. |
• | Standards Compatibility: Public Key Infrastructure (PKI), Wassenaar Arrangement (Export). |
Remark: Vanstone (Field Institute Conference, 1999) emphasizes that all these selection criteria must be considered simultaneously[11].
Security of ECC: Not every elliptic curve offers strong security properties and for some curves the ECDLP may be solved efficiently. Since a poor choice of the curve can compromise security, standards organizations like NIST and SECG have published a set of recommended curves[82,83] with well understood security properties. The use of these curves is also recommended as a means of facilitating interoperability between different implementations of a security protocol.
Theoretical security: The strength of every cryptographic algorithm relies on the best methods that are known to solve the mathematical problem, the algorithm is based upon. For all these problems, there are special-purpose algorithms that solve the problem quickly for certain special instances. However, these cases are easy to identify, therefore it is possible to avoid them in an implementation and we will not consider them.
Security of all the systems lays on one or more of their parameters. It means that security level of the system increases by increasing the size of this parameter(s). The primary security parameter of RSA is the modulus N. The DLP has two primary security parameters-order of the underlying group and order of its subgroup - primes p and q. The primary security parameter of ECDLP is the order n of a generator of an additive group of elliptic curve points.
For the ECDLP, the best known general-purpose attack is the Pollard-ρ algorithm, whose running time is fully exponential, i.e.,:
Thus, to solve an ECDLP instance for an elliptic curve having a 2k-bit parameter n takes about the same time as the exhaustive search through all k-bit keys of a symmetric cryptosystem (assuming that there is no better attack on the symmetric cryptosystem than the exhaustive search).
Pollard-ρ algorithm is also the basis for the best known general-purpose attack on the subgroup DLP. Therefore, the size of q in the DLP systems should have about the same size as the order n in ECDLP to get the same level of security[84].
The best known general-purpose attack on the IFP (i.e., on N) as well as on the discrete logarithm problem (i.e. on p) are based on the General Number Field Sieve Method which runs in sub-exponential time, i.e.
where, c = (64/9)a ≈ 2.923, x equals to N for the IFP and p for the DLP and the O(1) term goes to zero as x goes to infinity[1]. This means that, to obtain the same level of security, it has to hold
and
where, |.| is the length of a parameter in bits and k is key size of a symmetric cryptosystem. The following table (Table 4) compares the equivalent security level for some commonly considered key sizes[84].
Table 4: | Computationally equivalent key size |
General attacks on elliptic cryptosystem: Over the years mathematicians have made several attempts to tests the robustness of encryption algorithms, but no successful general-purpose algorithms exist. While several examples of special-purpose algorithms have already been mentioned, which exploit special features of the factored numbers, the running times of a general-purpose algorithm only depend on the sizes of the keys[38,39,61].
The cryptographic strength of elliptic curve encryption lies in the difficulty for a cryptanalyst to determine the secret random number k from kP and P itself which in itself is linked to DLP. Hence, the security of an ECC depends on the difficulty of solving the discrete logarithm problem over elliptic curves. The general methods of solving this problem are known. The fastest method to solve this problem (known as the elliptic curve logarithm problem) is the Pollard ρ factorization method[24,85]. Although this is an exponential time algorithm with complexity O(√n), making it slow overall, the Rho method has equivalent or better running time than any other elliptic curve attacks. This method has proven its flexibility by solving any instance of the ECDLP, regardless of the type, representation or order of the finite field over which the curve is defined. The Rho method has the additional selling points of ease of implementation, negligible storage requirements and the ability to be sped up through parallelization in software or hardware.
Until recently, however, the best attacks on elliptic curve logarithm problems were the general method and applicable to any group. The methods have a running time of about a constant times the square root of r on average, which is much slower than specialized attacks on certain types of groups. The lack of specialized attacks means that shorter key sizes for elliptic curve cryptosystems give the same security as larger keys in cryptosystems that are based on discrete logarithm problem. However, for certain elliptic curves, Menezes, Okamoto and Vanstone have been able to reduce the elliptic logarithm problem to a discrete logarithm problem[86]. It is possible that algorithm development in this area will change the security of elliptic curve discrete logarithm cryptosystems to be equivalent to that of general discrete logarithm cryptosystems; this is an open research problem.
The square root method is the most general attacking method for the discrete logarithm problem and its computation time is proportional to the exponent of half the key length; that is, the computation time varies exponentially with respect to the key length. A public-key cryptosystem is regarded as being very secure against an attack if the attack takes an exponential amount of time with respect to the key length. From this criterion, we can say that ECCs are very secure against the square root method.
Another attack technique is the Pohlig-Hellman (SPH) method[38], which factors the order of a curve into small primes and solves the Discrete Logarithm Problem (DLP) as a combination of discrete logarithms for small numbers. The SPH method is effective only when the order of the curve is expressed as a product of small primes. Otherwise, the computation time is equivalent to that of the square root method. Therefore, for an ECC, if we select the order of the elliptic curve to be a prime or nearly a prime whose factors include a large prime, the computation time needed to break the ECC will vary exponentially. Therefore, a high level of security can be achieved.
Now we will compare the security of ECCs with that of RSA. The security of RSA lies in the difficulty of factoring large numbers[2]. The number field sieve[86] is the most effective known method for factoring large numbers and it takes a sub-exponential amount of computation time with respect to the key length to do the task. Therefore, the best-known attack against RSA takes a sub-exponential amount of computation time with respect to the key length. An attacking method with sub-exponential time/key-length relationship takes less time than one with an exponential relationship (and more time than a method with polynomial relationship). This is why the securities of 1024-bit RSA and 160-bit ECC are equivalent.
However, since it is impossible to guarantee that a certain problem is infeasible to solve, most people trust RSA as mathematicians can't seem to find an algorithm to efficiently break it, despite the fact that they have been working hard on it, for a long time now (RSA was first developed in 1977)[5]. On the other hand, ECC (developed in 1985) has attracted a lot of criticism as some mathematicians believe that, ECDLP is not infeasible, its just that, this area of study is still very immature as enough research has not yet been done, therefore its just a matter of time before ECC can be broken.
Concept of security evaluation: In general, the security of a cryptosystem is evaluated by the amount of time needed to break it. Breaking a cryptosystems means finding the private-key used to encrypt a message. The method used to break a cryptosystem is called the attacking or brute- force method. Normally, the time needed to brute-force a practical cryptosystem is never actually obtained, because a cryptosystem that can be broken in reasonable amount of time would not be considered for practical purposes.
Instead, the amount of time needed to break a cryptosystem is a theoretical estimate of the average time needed to break a cryptosystems by a given attacking method. If there are multiple attacking methods, the time required by the most efficient method would be taken as the average time needed to break the cryptosystem. A security evaluation based on the theoretical estimate of average time is valid for the general case, but it is clear that such an evaluation is invalid for special cases.
The computational complexity for breaking the elliptic curve cryptosystem, using the Pollard ρ method, is 3.8x1010 MIPS year (i.e., millions of instructions per second times the required number of years) for an elliptic curve key size of only 150-bits[28]. For comparison, the fastest method to break RSA, using the General Number Field Sieve Method (GNFSM) to factor the composite integer n into the two primes p and q, requires 2.0x108 MIPS year for a 768 bit RSA key and 3.0x1011 MIPS year with a RSA key of length 1024-bits.
If the RSA key length is increased to 2048-bits, the GNFSM will need 3.0x1020 MIPS year to factor n whereas increasing the elliptic curve key length to only 234-bits will impose a computational complexity of 1.6x1028 MIPS year (still with the Pollard ρ method).
Evaluation by special attack: The security evaluation of a general attack against an ECC given above is based on the average computation time. However, we cannot evaluate special cases with this evaluation. In fact, special attacks were found using the special characteristics of special elliptic curves[24,79]. The special characteristics are determined by the order of the elliptic curve. These special attacks are much stronger than the square-root method.
Generating a secure curve parameter: Because of the threat of special attacks, it is essential to obtain the parameters of elliptic curves that meet the following basic requirements:
• | The order of the curve must be prime or nearly prime. |
• | The curve must be immune to special attacks. |
Both of these requirements concern the order of the curve, #E. That is, the security of an elliptic curve depends primarily on its order. Therefore, to make an ECC secure, we must first find curves which have an order satisfying the above requirements. At present, two method[44,87] are proposed to find good curves:
1) | Generate a curve randomly, count its order and select a curve satisfying the criteria. |
2) | Select an order satisfying the requirements and then generate a curve of the selected order. |
For method (1), the Schoof algorithm is used. Theoretically, the computation time for the Schoof algorithm is polynomial with respect to the key length. However, in practice it takes a long time to calculate if we implement it directly in the present computational environment.
For method (2), the complex multiplication algorithm (CM algorithm)[87] is used. The order of computation for the general CM algorithm is exponential with respect to the key length, so it is hard to calculate. Therefore, in practice the order of the curve is selected to have special characteristics so that it can be calculated efficiently. However, as described in the previous section, there is the possibility of attacks using the special characteristics. We think it is doubtful that curves generated by method (2) above will be safe in the future. We therefore recommend the implementation of method (1) coupled with improved Schoofs algorithm.
Merit of ECCs: The merit of ECCs is that compared with RSA cryptosystems they can provide the same security level with a shorter key length. Because of this mathematical property, ECCs are faster and require less hardware than RSA. The security of an ECC, however, depends not only on the length of the key, but also on the elliptic curve parameters. In general, it takes a long time to generate secure parameters. So, faster parameter generation is important for practical implementation of an ECC.
Most Internet security protocols (e.g., SSL[16,88], IPsec) employ a public-key cryptosystem to derive symmetric-keys and then use fast symmetric-key algorithms to ensure confidentiality, integrity and source authentication of bulk data. RSA is the most commonly used public-key cryptosystem today. The security of a system is only as good as that of its weakest component; for this reason, the work factor needed to break a symmetric-key must match that needed to break the public-key cryptosystem used for the key establishment. Due to expected advances in cryptanalysis and increases in computing power available to an adversary, both symmetric and public-key sizes must grow over time to offer acceptable security for a fixed protection lifespan.
Table 5: | Proposed the following minimum key sizes (in bits)[56] |
*without (with) cryptanalytic progress |
Table 5[30] shows this expected key-size growth for various symmetric and public-key cryptosystems.
As shown in Table 5, the Elliptic Curve Cryptosystem (ECC) offers the highest strength per bit of any known public-key cryptosystem today. ECC not only uses smaller keys for equivalent strength compared to traditional public-key cryptosystems like RSA, the key size disparity grows as security needs increase. This makes it especially attractive in power, bandwidth and computational savings.
However, the true benefit and performance impact of any cryptosystem is closely tied to how it is used within a security protocol. In particular, it is imperative that expected performance improvements at the protocol level be carefully weighed against the usual costs associated with deploying any new technology.
Applications and implementation of ECC: Thanks to the reduced memory and processing time required to implement ECC, it has several significant advantages over either of its public-key predecessors. Certain distinct implementations, which take advantage of the benefits of ECC, are:
General improvements: Many server and financial applications process large volumes of transaction data (or Web server requests), for which public-key cryptography is required. Even with significant improvements in processing power, server applications can become seriously burdened by conventional public-key operations. ECC can increase efficiency of these operations by orders of magnitude in most cases.
Constrained channels: Are defined as any bottleneck where computational power is limited at one or both ends. Extreme examples of these are wireless communications, where there is a speed/memory tradeoff. However, ECC allows for smaller keys and faster processing times. This significantly improves the protocol execution speeds and reduces power consumption (this is significant in portable/wireless communication devices such as cell-phones and pagers).
The elliptic curve digital signature algorithm: The ECDSA is an algorithm for implementing a digital signature algorithm for the Elliptic Curve Cryptosystem. ECDSA is similar to the DSA, which is the current standard in Digital Signature creation:
• | Both use the ElGamal signature scheme and signing equation. |
• | In both algorithms, the system parameters are difficult to generate, while the private and public keys are relatively simple. |
• | Both methods use the SHA-1 hash function. |
The two approaches do have some significant differences:
• | The private key d and the per-signature value k in ECDSA are defined to be statistically unique and unpredictable rather than merely random with DSA. This distinction is important, as with ECDSA it is possible to filter the values to ensure that there are no repeats. |
• | By a technique known as point compression it is possible to represent a point on an elliptic curve by one field element and one additional bit, rather than two field elements. Public keys can then be represented as 161 bit strings, which is in the order of 25% smaller than other asymmetric algorithms. |
• | DSA performs an optional bounds check to ensure that a conforming system which did not perform a bounds check cannot generate a signature which it cannot verify. This operation is performed explicitly in ECDSA to avoid any inadvertent application errors. |
• | ECDSA has the capability of a deterministic primality test, as opposed to the probabilistic test of DSA. This allows for very high security standards. |
• | In ECDSA, it is possible for a single party to generate their own personal system parameters, while DSA still uses trusted third party. |
• | It has been demonstrated that the hash function used by DSA is in fact not as reliable as that used with ECDSA. If the adversary can select system parameters, this weakness can be capitalized on. This weakness can be countered by selecting system parameters stipulated in the X9.30 standard. |
Automatic teller machines (ATM): Public-key encryption has been in place in the ATM network for a number of years. Storing every user PIN at each terminal is impractical, so security between the terminal and the banking network is imperative. Confidentiality of this PIN is certainly required while it is in transit and when a large amount of money is requested; the information requires data integrity. This is to combat tampering attacks involving the alteration of the amount requested. An ECC implemented in this environment would be beneficial for certain reasons:
• | The reduced key sizes and computations should significantly reduce transaction times, making it more convenient for the user. |
• | By using ECDSA, the integrity of the data could be more readily guaranteed than the current method of DSA. |
Smart cards and cellular phone networks: Phone cards and more generally Smart Cards, are in widespread use throughout North America and Europe. In most instances, important data is stored on the card, such as the amount of money available on it. The security of this data should be protected to avoid fraudulent use and thus free access to the telephone network. It is imperative that the data stored on the card be guaranteed to be genuine and thus some form of security is necessary.
Smart Cards possess a small processor and are capable of storing relatively small amounts of data in memory, making them an exciting avenue for development. These include:
• | Use of the cards for ID validation. |
• | Use as credit cards to replace the magnetic strip cards. |
• | Electronic cash-replacing the coins and notes we carry with a single card. |
• | Storage of a patients medical history. |
Another area of telephone communications that is vulnerable to fraud is the use of cell phones. It is relatively easy for fraudulent use of the cellular communications network, as the system currently in place can be easily duped. It is also simple to intercept any message sent through the cellular communication network-at present no conversation is free from possible eavesdropping. The Cellular Telecommunications Industry Association estimates that the current generation of cellular phones, without security, enables fraudulent use at a cost of between $1.5 and $2.5 billion each year. Cellular phone providers are only now addressing this issue. The next generation of cellular phones will employ cryptosystems to prevent fraud.
The application of cryptosystems to these examples is obviously important and due to the restrictive processing power and memory resources, ECC is more practical than the alternative public-key cryptosystems.
Public-key encryption can be used to eliminate problems involved with conventional encryption; these include key distribution and digital signatures. It however has not managed to be as widely accepted as conventional encryption because it introduces a lot of overheads. Therefore, it is very important to find ways to reduce the overheads yet not sacrificing on other aspects of security so that the desirability in public-key can be exploited.
We have described ECC, which is a promising candidate for the next-generation public-key cryptosystem. Although ECCs security has not been completely evaluated, it is expected to come into widespread use in various fields in the future because of its compactness and high performance when it is hardware-implemented. It is concluded that the reliability, maturity and difficulty of a mathematical problem are very important; the more the difficulty the shorter the keys become hence overheads are eliminated.
After comparing the RSA and ECC cryptosystems, the ECC has proved to involve much less overheads when compared to the RSA. The ECC has been shown to have many advantages due to its ability to provide the same level of security as RSA yet using shorter keys. However, its disadvantage which may even hide its attractiveness is its lack of maturity, as mathematicians believe that enough research has not yet been done in the ECDLP.
Also, we believe that even though both systems are valid, the RSA is better than ECC for now, as it is more reliable and its security can be trusted more. However the future of ECC looks brighter than that of RSA as todays applications (e-commerce, cellular telephones, pagers, smart cards and so on) cannot afford the overheads introduced by RSA. The applications cannot afford to sacrifice their bandwidth for the overheads. Finally, both systems can be considered good cryptosystems considering the low success rates associated with attacking them.