INTRODUCTION
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 Nonrepudiation.
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, ebusiness 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: symmetrickey and asymmetrickey protocols. In the symmetrickey protocols, a common key (the secretkey) is used by both communicating partners to encrypt and decrypt messages^{[1]}. Among these are DES, IDEA and AES. These symmetrickey 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 PublicKey Cryptography. The encoding function here is a trapdoor functionone whose inverse is impractical to implement, unless some extra information is available. This extra information (called the decryptingkey) 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 encryptingfunction, which is public information (hence the name PublicKey) and a decoding key, which he keeps secret.

Fig. 1: 
Shows a schematic classical cryptographic data communication 
The publickey protocol employs a pair of different but associated keys. One of these keys (the publickey) is used either for encryption (signature) of the messages and; a different key (the privatekey) is used for either decryption (confidentiality) of the message^{[4]}. Different publickey cryptographic systems are used to provide publickey 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 publickey 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 publickey is released to the public while the other, the privatekey, 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 privatekey from its associated publickey; that is, it is believed that any attempt to compute it will fail even when uptodate technology and equipment are used^{[10]}. With a publickey cryptosystem, the sender can encrypt a message using the receiver’s public keywithout needing to know the privatekey of the receiver. Therefore, they are suitable for communication among the general public. Publickey cryptosystems can also be used to make a digital signature^{[11]}.
However, in real applications, both symmetric and asymmetric protocols are used. The publickey algorithm is first used for establishing a common symmetrickey over insecure channel. Then the symmetric system is used for secure communication with high throughput. Due to comparative slowness of the publickey 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^{[1416]}, which provide both encryption and digital signatures services. One potential use of elliptic curves is in the definition of publickey cryptosystems that are close analogs of existing schemes like RSA, ElGamal, DSA and DH etc. Furthermore, elliptic curve can provide versions of publickey 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 publickey 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]}, y^{2}x^{3} = 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:
This integral, which cannot be solved easily, was the reason to consider the curve Y^{2} = X^{3}+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 nonsupersingular plain projective third degree curve over K with a Krational point O (i.e., with coordinates in K) over curve E.
Such a curve can be described by its socalled Weierstraβ form, in homogeneous coordinates x,y,z:
where, a_{1} ,...., a_{6} ε K, such that the discriminant Δ ≠ 0. This discriminant is a polynomial expression in the coefficient a_{1} ,...., a_{6}. The restriction Δ ≠ 0 is necessary and sufficient for E in order to be a nonsingular. The curve E has exactly one Krational 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:
For fields K of characteristic >2 such as ¤, (, £ or F_{p} with p>3 we can transform the Weierstraβ form for the affine curve by the coordinate transform:
to a curve of the form: E/K: Y^{2} = X^{2}+aX+b
where, a,b ε K such that the discriminant Δ = 4a^{3}+27b^{2}≠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 y^{2} = x^{3}+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 publickey 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 publickey 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 publickey 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 y^{2} = x^{3}+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 P_{1} plus point P_{2} is equal to point P_{3} as shown in Fig. 2). The addition operation in an elliptic curve is the counterpart to modular multiplication in common publickey 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 world’s computing power for a few years to break an elliptic
curve cryptosystem.
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^{[2427]}.
Elliptic Curve Cryptosystems (ECCs) also include key distribution, encryption and digital signature algorithms. The key distribution algorithm is used to share a secretkey, 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 F_{p}: Abstractly a finite field consists of a finite set of objects called field elements F together with the description of two operationsaddition and multiplicationthat 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 F_{q}. Here only two types of finite fields F_{p} are usedfinite fields F_{p} with q = p, p is an odd prime which are called prime finite fields and finite fields with q = 2^{m} 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 = p^{m} where p is a prime and m is a positive integer, then p is called the characteristic of F_{p} and m is called the extension degree of F_{p}. 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 = 2^{m}). This study describe the elements, operations and implementation of the finite field F_{p}, while the elements and operations of can be found elsewhere^{[33,34]}.
Let p be a prime number. The finite field F_{p} called a prime field, is comprised of the set of integers {0,1,2,...., p1} with the following arithmetic operations^{[22]}:
• 
Addition: If a, b ε F_{p}, then a+b =r, where,
r is the remainder when a+b is divided by p and 0≤r≤p1. This is known
as addition modulo p. 
• 
Multiplication: If a, b ε F_{p}, a · b
= s where, s is the remainder when, a · b, is divided by p and 0≤s≤p1.
This is known as multiplication modulo p. 
• 
Inversion: If a is a nonzero element in F_{p}, the
inverse of a modulo p, denoted a^{1}, is the unique integer c ε
F_{p} for which a · c = 1. 
The mechanics of elliptic curves: An elliptic curve over F_{q} is defined in terms of the solutions to an equation in F_{q}. The form of the equation defining an elliptic curve over F_{q} 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 numbertheoretic purposes, the equation can be brought into the short Weierstraβ form, i.e., E: y^{2} = x^{3}+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 E_{p}(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 theoryand essentially all the cryptographic applicationslie 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 N_{p}p#2p^{½} where, N_{p} is the number of solutions mod p. This ensures that for large p, there are lots of solutions over the finite field F_{p}.
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 F_{p}) 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 math’s needed to compute the inverse is not known. The main reason for attractiveness of ECC is the fact that there is no subexponential 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 E_{p}(a, b) where, p>3 and be prime, is the set of solutions or points P = (x, y) such that (x, y ε E_{p}(a, b)) that satisfy the equation:
for 0≤x < p together with the extra point O called the point at infinity. For a given point P = (x_{p}, y_{p}), x_{p} and y_{p} are called the x and y coordinates of P, respectively. The number of points on E_{p}(a, b) is denoted by #E(F_{p}). The Hasse Theorem states that^{[35]}:
The constants a and b are non negative integers smaller than the prime number p and must satisfy the condition:
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 E_{p}(a,b).
We should first explain why we have required the coefficients of the cubic
polynomial in Eq. (6) to satisfy, 4a^{3}+27b^{2}
≠ 0 mod p. Notice that:
is the discriminant of the cubic polynomial f(x) = x^{3}+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) = y^{2}x^{3}axb = 0, this point satisfy:
That is, (X, 0) is a singular point at which there is no definition for a real tangent value. With the tangentandchord operation failing at the singular point (X, 0), E cannot be a group.
Elliptic curves over a characteristic 2 finite field GF(2^{m}) which has 2^{m} 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 F_{p}: Let the prime
number p = 23 and consider an elliptic curve E: y^{2} = x^{2}+x+4
mod 23 defined over F_{23}. From Eq. (6) and let the
constants a = 1 and b = 4. It is verified that:
Therefore, E is indeed an elliptic curve. We then determine the quadratic residues Q_{23} from the reduced set of residue Z_{23} = {1,2,3,...,21,22}:
Table 1: 
Quadratic residues of Q_{23} 

Therefore, the set of (p1)/2 = 11 quadratic residues Q_{23} = {1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18}. Now, for 0≤x < p, compute, y^{2} = x^{3}+x+4 mod 23 and determine if y^{2} is in the set of quadratic residues Q_{23}:
Table 2: 
Quadratic residues of Q_{23} and their roots 

Hence, the points in E(F_{23}) are O and the following:
Figure 3 shows a scatterplot of the elliptic group E_{p}(a, b) = E_{23}(1, 4).

Fig. 3: 
Scattaerplot of elliptic group E_{p} (a, b) = E_{23}(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: y^{2}
= x^{3}+ax+b(mod p) where, a and b are two more carefully chosen large
numbers so that the curve is not weak and 4a^{3}+27b^{2} ≠
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 DiffieHellman (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 you’ll see that it has a very special form, p = 2^{192}2^{64}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 chordandtangent rule, for adding two points on an elliptic curve E(F_{p}) to give a third elliptic curve point as was discussed earlier in Section 2.0 Together with this addition operation, the set points E(F_{p}) 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 = (x_{1}, x_{1}) and Q = (x_{2}, y_{2}) be two distinct points on an elliptic curve E (Fig. 4). Then the sum of P and Q, denoted by R = (x_{3}, y_{3}), 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 xaxis. The elliptic curve in the Fig. 4 consists of two parts, the ellipselike figure and the infinite curve.
If P = (x_{1}, x_{1}), then the double of P, denoted by R = (x_{3}, y_{3}), 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 xaxis (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 = (x_{1}, y_{1}) and Q = (x_{2}, y_{2})
be in the elliptic group E_{P}(a, b) and O be the point at infinity.
The rules for addition over the elliptic group E_{P}(a, b) are:
1. 
P+O = O+P for all P ε E(F_{p}) 
2. 
If P = (x, y) ε E(F_{p}) and if x_{2} = x_{1}
and y_{2} = y_{1}, that is P = (x_{1}, x_{2})
and Q = (x_{1}, x_{2}), (x_{1}, y_{1})
= P then P+Q = O (observe that P is indeed a point on the curve). 
3. 
Point addition: Let P = (x_{1}, y_{1}) ε E(F_{p})
and Q = (x_{2}, y_{2}) ε E(F_{p}), If P ≠
±Q, then their sum P+Q = (x_{3}+y_{3}). 
4. 
Point doubling: Let Let P = (x_{1}, y_{1}) ε E(F_{p})
and, If P ≠ P. Then 2P = (x_{3}+y_{3}). 
Define x_{3} and y_{3} by:
where:
The properties of binary operation
1. 
Given an elliptic curve and two rational points on that curve: (x_{1}, y_{1}) and (x_{2}, y_{2}) ≠ (x_{1},y_{1}), we define a binary operation: 
where, x_{3} and y_{3} 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 xaxis 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: 
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:
where, x_{3} and y_{3} 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(P_{f}) requires a few arithmetic operations (addition, subtraction, multiplication and inversion) in the underlying field F_{p}. 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 E_{p} (a, b) is the equivalent operation of the modular exponentiation in RSA.
Let P = (7, 3) ε E_{23} (1, 4). Then 2P = (x_{3}, y_{3})
is equal to: 2P = P+P = (x_{1}, y_{1})+(x_{1}, y_{1})
If (x_{1}, y_{1}) = (7, 3), then we can determine the values
of λ, x_{3} and y_{3} by using Eqs. (13) and (14) as follows:
Therefore, 2P = (x_{3}, y_{3}) = (22, 18).
Next, let P = (4, 16) ε E_{23}(1, 4) and Q = (14, 18) ε E_{23}(1,
4). ThenP+Q = (x_{3}, y_{3}) is given by:
Hence P+Q = (17, 9). The set of points on E(F_{p}) forms a group under this addition rule. Furthermore, the group is abelianmeaning that P_{1}+P_{2} = P_{2}+P_{1} for all points P_{1}, P_{2} ε E(F_{p}). 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(F_{p}),
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 kth 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
doubleandadd algorithm or one of its variants.
Here we will implement, the scalar multiplication k^{P} which we obtain
by repeating the elliptic curve addition k times, by following the same additive
rules and a generator point:
similarly
and finally
(x_{29},
y_{29}) = (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 a^{k} in a general (multiplicativewritten) finite group. The basic technique for exponentiation is the repeated squareandmultiply 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 nonzero point P = (x, y) ε E(F_{p}) 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 F_{q}. 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 155bit 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(F_{q}) be a non zero point on some given elliptic curve E. For a positive integer m we let [m] denote the multiplicationbym 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/F_{q} we consider the map:
For two points we have φ_{q} (P +Q) = φ_{q} (P)+φ_{q} (Q) . It is easy to see that the set E(F_{p}) is the set of points which are invariant under φ_{q}, i.e., we have P ε (F_{q}) ⇔ φ_{q} (P) = P.
The Frobenius endomorphismsatisfies the characteristic equation:
which can be interpreted in the sense of operators which acts on the group of points of E:
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.,:
The group of torsion points: Let E/F_{q} be an elliptic curve.
For n ε¥_{≥2} we write for the group of the ntorsion points
of i.e., the point with nP = O. The structure of the group E[n] is wellknown:
E[n] ≅ Z/n⊕ Z/n if gcd(n, q) = 1 
Table 3: 
Point addition/scalar point multiplicative values of P (note
that: kP ≡ P_{k}, so that 29P ≡ P_{0} ≡
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(F_{p}). For example: If he knows #E(F_{p}) he knows whether the PohligHellman^{[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 MasseyOmura 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 HesseWeil^{[35]} can be applied, which reduces the amount of work enormously.
Group order: Let E be the elliptic curve over a finite field F_{q}.
Hasse’s theorem states that the number of points on an elliptic curve (including
the point at infinity) is #E(F_{p}) = q+1t where
, # E(F_{p}) 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(F_{p}) is roughly equal to the size q of the underlying field^{[15]}.
Group structure: E(F_{p}) is an abelian group of rank 1 or 2. That is, E(F_{p}) is isomorphic to Z_{n1} x Z_{n2}, where, n_{2} divides n_{1}, for unique positive integers n_{1} and n_{2}. Here Z_{n} denotes cyclic group of order n. Moreover, n_{2} divides q1. If n_{2} = 1, then E(F_{p}) is said to be cyclic. In this case E(F_{p}) is isomorphic to Z_{n1} and there exists a point P ε E(F_{p}) = {kP: 0≤k≤n_{1}1}; such a point is called a generator of E(F_{p}).
Cyclic elliptic curve^{[38]}: Consider again the example above
of E_{1, 4} (F_{23}):
For example, P_{5} = (7, 20) ε E_{1, 4} (F_{23})
because:
7^{3}+7+4 = 354 ≡ 9 ≡ 3^{2}
(mod 23) 
The above points P_{i} listed in Table 3 can be numbered in such way that:
Thus, #E(F_{23}) = 29, which satisfies the Hasse bound since:
Since #E(F_{23}) = 29, which is prime and which is found by counting all the points, also known as naïve method. #E(F_{23}) is cyclic and any point other than O is a generator of #E(F_{23}). 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(F_{p}) 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(F_{p})/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 Shank’s algorithm which we will discuss later in the text.
The mechanics of order of points: Let E(F_{p}) denote the set of rational points on E. It is easy to see that the number of points in E(F_{p}) with Xcoordinate x ε F_{p} is 0, 1, or 2. More precisely, there are:
rational points on E with Xcoordinate 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(F_{p}) of E, therefore, has cardinality:
When x^{3}+ax+b is a square modulo p then two points are contributed to the order. When px^{3}+ax+b one point is added. If x^{3}+ax+b is not a square or divisible by p then nothing is contributed in the sum. This implies that evaluating the sum:
is the same problem as computing #E(F_{p}). For very large primes (p < 200 say) a straightforward evaluation of this sum is an efficient way to compute #E(F_{p}). 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 x^{3}+ax+b is a square for x = 0, 1,....., p1. The running time of this algorithm is O (p^{1+ε}) 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 F_{p} of the form E_{p}(a, 0): y^{2} = x^{3}+ax, for a ≠ 0(mod p) or E_{p}(0, b): y^{2} = x^{3}+b, for b ≠ 0 (mod p)^{[12]}.
For a general elliptic curve over larger finite field F_{p}, one should use Shanks’ BabystepGiantstep strategy^{[39]}. Alternative techniques are also available to compute the exact order quickly, these are: Schoof’s 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 (babystep, giantstep): 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+12p^{½}≤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 L_{1} the pairs (j, jmQ) for 0≤j≤m1. Sort this
list by the second element of the pairs. Create a second list L_{2} from the pairs (I, iq+A) for 0≤i≤m1. Sort this list by the second element.
Search the list until pairs (j, p) ε L_{1 }and (j, p) ε L_{1}
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 (babystep, giantstep): As an
example consider our earlier elliptic curve: y^{2} = x^{3}+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 L_{1} matches item 2 in L_{2}. 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^{[4143]}. For larger values
of p one needs the help of an algorithm developed by Schoof^{[44]}.
In 1985, Schoof’s 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 Hellman’s method: This method (also referred to as Silver PohligHellman’s method)^{[37]} reduces the problem to a determination of m mod p_{i}, each of the primes p_{i} 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 {p_{1}, K, p_{s}}
Then
we can write:
since g ^{n/p} has order p. Now a_{0} is the discreat logarithm
of y^{n/p} to the base g ^{n/p}. For a_{1}, we write:
Each term a_{j} now is a discrete logarithm to the base element g^{n/p}. Hence it reduces from a difficult DLP to many easier babyDLPs. Each babyDLP can be solved using other algorithms. Its running time, O(∑e_{i} (log n+p_{i})) group multiplications, depends mostly on the largest prime factor. Hence, it works efficiently only when n is a smooth number, that is, all primes p_{i} are small. Therefore, in order to resist Pohlig and Hellman’s algorithm, n should be divisible by a large prime number (>280), or indeed, n must be prime >280 for the maximum security possible.
The SchoofElkiesAtkin (SEA) algorithm: It is obvious that if we can calculate the trace Tr(F_{q}) of Frobenius, then we have information about E/F_{q}. The calculation of Frobenius is the kernel of the SEAalgorithm. 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 SchoofElkiesAtkin (SEA) algorithm^{[45]}. SEAalgorithm can be used in order to calculate the number of points on an elliptic curve over F_{p} 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:
where, t_{R} ≡ t mod ℓ and q_{ℓ} ≡ q mod ℓ. This equation can be rewritten as:
We consider a (generic) point y. We calculate the righthandside and lefthandside of the previous equation for this point. We find for the lefthandside:
We eliminate the y in the xcoordinate, since y^{2} = x^{3}+ax+b,
the xcoordinate can be written as the quotient
. The lefthandside can be rewritten as the quotient .
In the lefthandside t_{R} is unknown. If the correct value of t_{R}
is chosen F(x) and have a common nontrivial divisor. We have to chose t_{1}
= 0, 1, 2,..... until t_{1} fits. Now by varying R we find related values
of t_{1}. The value of t can be calculated using the Chinese Remainder
Theorem^{[2]}.
Pollard’s rhomethod and lambdamethod: This method is a randomized version of Shanks’ BabystepGiantstep algorithm and it requires no significant storage of precomputations. 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: x_{i+1} = x_{iu}, where, u is either x_{i}, g or y depending on which subset x_{i} belongs to. The search is completed until we find a value j such that x_{j} = x_{2j}.
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>2^{160}, the DLP is still infeasible. Pollard’s “lambdamethod
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’ BabystepGiantstep, Pollardrho and PohligHellman, 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: log_{g} y_{1},...., log_{g} y_{M}. This method was originally used to attack the ECDLP.
Indexcalculus method: Over finite fields where the DLP is defined, there is another “additional structure” beyond the “multiplicative structure.” The indexcalculus methods take advantage of this extra structure. It is generally believed that it is much more complicated, or even impossible, to apply indexcalculus 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(F_{q}). 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(p^{n})) to points on an elliptic curve, where, (¤) is the rational field. That is, given P ε E(GF(p^{n})), 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 xcoordinate 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 2^{cp}, 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.
Publickey Cryptography (PKC): Diffie and Hellman^{[3]} were the first to introduce the publickey cryptography to overcome the difficulty of key distribution encountered with the privatekey cryptosystems. This protocol later become to be known as DiffieHellman (DH) key exchange. In the later years other publickey 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^{[1416]}, which provide both encryption and digital signatures services using already existing publickey algorithms.
It was Miller who first proposed the DiffieHellman key exchange protocol^{[8]} on the bases of elliptic curve^{[13]}. The elliptic curve based analogues of the ElGamal scheme and the MasseyOmura 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 publickey cryptosystem is a hard mathematical problem that is computationally infeasible to solve. For example, RSA and DiffieHellman 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 publickey cryptosystems is the Discrete
Log Problem (DLP). In an (abelian) group G (multiplicatively written) we can
consider the equation y = x^{n}, 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(“= log_{x} (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 wellknown 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 Z_{p} denotes the set of integers {0, 1, 2,..., p1}, where addition and multiplication are performed modulo p. It is wellknown that there exists a nonzero element g ε Z_{p} such that each nonzero elements in Z_{p} can be written as a power of g; such that an element Z_{p} is called a generator of Z_{p} .
Remark 3: The Discrete Logarithm Problem (DLP) is the following: given a prime p, a generator g of Z_{p} and a nonzero element β ε Z_{p} , find the unique integer k, 0≤k≤p2, such that β = g^{k} 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 wellknown DiffieHellman 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 NybergReuppel 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 Z_{p} , which consist of the integers modulo a large prime p. Although this problem can be considered difficult, there are known subexponential time algorithms for solving it, such as the number field sieve. In practical terms, subexponential 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 onestep 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 F_{q}.
Elliptic Curve Discrete Logarithm Problem (ECDLP): The fundamental mathematical operation in RSA and DiffieHellman 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(F_{q}), point P ε E(F_{q}) of order n and a point Q ε E(F_{q}), determine the integer k 0≤k≤n1, such that Q = kP, provided that such an integer exists. Here Q is the publickey and k is the privatekey. 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 = log_{p}Q 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 PohligHellman 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(F_{q})
= 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 bruteforce 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 160bits long is selected, we cannot find k within a reasonable time, even if we use the most efficient algorithms known so far with the world’s 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 publickey 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 publickey cryptography is that of a hard problem and from such problems, mechanisms for publickey 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 publickey encryption or a digital signature algorithm^{[6]}. Today the candidate hard problems which apply for publickey 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 publickey) to obtain the two primes from which the privatekey can be determined^{[61]}. This is very costly. Unfortunately, encrypting a message M, involves exponentiation, C = M^{e}, 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 subexponential 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 160bit 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 Pollard’sρ 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 subexponential 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 P_{M} from the finite set of points in the elliptic group, E_{p}(a, b). The first step consists in choosing a generator point, G ε E_{p}(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 publickey. For example, Alice (A) selects
a privatekey n_{A}<n and computes the publickey P_{A} as:
P_{A} = n_{A}G. To encrypt the message P_{M} for Bob
(B), Alice chooses a random integer k and computes the ciphertext pair of points
P_{C} using Bob’s publickey P_{B}:
P_{C} = [(kG), (P_{M}+k
P_{B})] 
After receiving the ciphertext pair of points, P_{C}, Bob multiplies the first point, (kG) with his privatekey, n_{B} and then subtracts the result to the second point in the ciphertext pair of points, (P_{M}+k P_{B}):
(P_{M}+k
P_{B})[n_{B}(kG)] = (P_{M}+k n_{B}G)[n_{B}(kG)]
= P_{M} 
which is the plaintext point, corresponding to the plaintext message M. Only Bob, knowing the privatekey n_{B}, can remove n_{B}(kG) from the second point of the ciphertext pair of point, i.e., (P_{M}+k P_{B}) and hence retrieve the plaintext information P_{M}.
Implementation of elliptic curve encryption scheme: The elliptic curve group generated by our earlier elliptic curve i.e., E_{p}(a, b) = E_{23}(1, 4). Since #E(F_{23}), which is prime. E(F_{23}) is cyclic and any point other than O is a generator of E(F_{23}). 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 P_{M} = (7, 3) ε E_{23} (1, 4). She must use Bob’s
publickey to encrypt it. Suppose that Bob’s secretkey is n_{B}
= 6, then his publickey will be:
P_{B} = n_{B}G = 6(0,
2) = 6P = (9, 11) 
Alice selects a random number k_{A} = 15 and Bob’s publickey
P_{B} = (9, 11) to encrypt the message point into the ciphertext pair
of points:
Upon receiving the ciphertext pair of points, P_{C} = [(18, 14), (13, 11)], Bob uses his privatekey, n_{B} = 6, to compute the plaintext point, P_{M}, as follows:
the Weil pairing can be defined by 
or
(P_{M}+kP_{B})[n_{B}(kG)]
= (7, 3) 
and which maps the plaintext point P_{M}(7, 3) back into the original plaintext message M.
The mechanics of Elliptic Curve Diffiehellman (ECDH) key exchange scheme: The elliptic curve DiffieHellman 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, knownkey security and forward secrecydepending 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 secretkey, while the result Q of multiplying the privatekey k with curve’s base point P serves as the corresponding publickey.
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, k_{A} and k_{B} and corresponding publickeys Q_{A} = k_{A}P and Q_{B} = k_{B}P. The parties exchange their publickeys. Finally, each multiplies their privatekey and the others publickey to arrive at a common shared secretkey k_{A}Q_{B} = k_{B}Q_{A} = k_{A}k_{B}P = S_{AB}, P, where, k= k_{A} k_{B}. The sessionkeys are the same (since S_{AB} = S_{BA} = k); hence Alice and Bob now have a shared secretkey k. Future communications occur using the session key k. Thus, k can be used as a sessionkey for a privatekey 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, S_{AB}P, given the two public values Q_{A} = k_{A}P and Q_{B} = k_{B}P when the prime p is sufficiently large.
If Eve (the eavesdropper) can recover S_{AB} from this data then Eve is said to have solved DiffieHellman 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 DiffieHellman 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 complexitytheoretic sense (there is a polynomial time reduction of one problem to the other and vice versa. Meyer^{[69]} has shown that breaking the DiffieHellman 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 secretkey 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, let’s use
our earlier elliptic curve i.e., is E_{p}(a, b) = E_{23} (1,
4). Alice (A) chooses the secretkey k_{4} = 4 and computes her publickey
(Table 3 and Eq. 22):
Q_{A} = k_{A}P = 4P_{1 }=
P_{1}+P_{1}+P_{1}+P_{1} = P_{4}
= (1, 12) 
Similarly, Bob (B) chooses the secretkey k_{B} = 6 and computes his
publickey (Table 3):
Q_{A} = k_{A}P = 4P_{1 }=
P_{1}+P_{1}+P_{1}+P_{1} = P_{4}
= (1, 12) 
Thus, their common secretkey S_{AB}, i.e.,:
Alice computes:k_{A}Q_{B} = 4P_{6} = P_{6}+P_{6}+P_{6}+P_{6}
= P_{24} = (7, 3)
and Bob computes: k_{B}Q_{A} = 6P_{4} = P_{24} = (7, 3)
Such that: S_{AB} = k_{A}P_{B} = k_{B}P_{A} = P_{24} = (7, 3)
An alternative form of ECDH is the Elliptic curve decision DiffieHellman 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 F_{q} 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 publickey 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 publickey encryption scheme can be viewed as DiffieHellman key agreement protocol in key transfer mode. Its security is based on the intractability of the discrete logarithm problem and the DiffieHellman problem.
Instead of DiffieHellman, 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 secretkey k_{B} such that 1≤k_{B}≤p2. and publishes B = k_{B}P, i.e., (E, P, B) are publickey 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 k_{A} such that 1≤k_{A}≤p2. She then computes A = k_{A}P and ciphertext C = M+k_{A}B and sends (A, C).
Decryption: Bob receives the message (A, C). He then computes: M = Ck_{B}A
= (M+k_{A}k_{B}P)k_{A}k_{B}P
It is not trivial to find a point M for the message m. It is impossible to choose for m the xcoordinate of M. In about 50% of the cases m will not appear as xcoordinate. This problem can be avoided by adding a few bits to m, which can be chosen arbitrarily. If an xcoordinate 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 publickey set: B = k_{B}P = 10P = (22, 5), where the secretkey k_{B} = 10 (taken from Table 3).
Let Alice select message point: M = (7, 3) (a point on E) and selects a random
secretkey k_{A} = 6, such that; A = k_{A}P = 6P = 6 (0.2) =
(9, 11) and encrypts the message:
C = M + k_{A}B = (7, 3)+6(10P) = 24P+2P =
26P = (11.14) 
Decryption: Bob receives the message (A, C) = (6P, 26P).
He then computes: M = Ck_{B}A = (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 publickey and privatekey 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 (19851996) 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 ElGamalfamily 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 ROMbased technique of Pointcheval and Stern is an insightful instantiation of the general ROMbased security proof technique to proving security for the ElGamalfamily signatures.
MasseyOmura elliptic curvePKC: MasseyOmura is another publickey cryptosystem^{[74]}. Assume that the curve E/F_{q} 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 e_{A} (and computes d_{A}); Bob selects e_{B} (and computes d_{A}). Alice wishes to send the plaintext message associated with the point P to Bob. She computes e_{A}P 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 e_{B}e_{A}P. Alice computes d_{A}e_{B}e_{A}P. Note that d_{A}e_{A}P ≡ 1 mod n, so Alice has really “unmasked” e_{B}P. She transmits this to Bob, who multiplies by his decryption key to get d_{B}e_{B}P = P. Quantities that have passed through insecure channels in this scheme are e_{A}P, e_{B}e_{A}P and e_{B}P. Solving the discrete logarithm problem given e_{A}P and e_{B}e_{A}P for the quantity e_{B} would allow the attacker (Eve) to compute d_{B} and thus decrypt the message.
Implementation of MasseyOmura cryptosystems: Recall elliptic curve group generated by the our earlier elliptic curve is E_{p}(a, b) = E_{23}(1, 4). Since #EF_{23} = 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: e_{A} = 6 and computes d_{A} = 6^{1}
mod 29 = 5
Bob selects: e_{B} = 13 and computes d_{B} ≡ 13^{1} mod 29 = 9
Alice needs to transmit message point: M = (14, 18) = 21P to Bob.
She transmit: e_{A}M = 6 (14, 18) = 6(21P) = 10P = (22, 5)
Bob replies with: e_{A}e_{B}M = 13(22, 5) = 13(10P) = 14P =
(18, 9)
Alice sends back to Bob: d_{A}e_{B}e_{A}M = 5(18, 9)=
5(14P) = 12P = (17, 9)
Bob now multiplies this value by his decryption key: d_{B}(d_{A}e_{B}e_{A}M)
= 9(17, 9) = 9 (12P) = 21P = (14, 18) = M
Bob recovers back the message point: M= (14, 18)
MenezesVanstone elliptic curve cryptosystem: This is also mentioned as a version of ElGamal cryptosystem in many cryptography literature. Let E be a nonsupersingular elliptic curve defined over a finite field F_{p}, where prime p>3. Choose a point P ε E (F_{p}) 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, n1]. The ciphertext of a message m = (m_{1}, m_{2}) ε will be the triple point including the point kP and two finite field elements y_{1} and y_{2} where y_{1} = c_{1}m_{1}(mod p) and y_{2} and assuming kQ = (c_{1}, c_{2})≠ (0, 0).
Decryption: The receiver uses his secret key d to compute the point d(kP) that should be exactly kQ =(c_{1}, c_{2}). Hence, the receiver can recover the message by: (y_{1}c_{1}^{1}(mod p), y_{2} c_{2}^{1} (mod p)) = (m_{1}, m_{2}).
Analysis: There is also a message expansion of factor 2 (or 3/2 if one uses compressing techniques). The same drawback: if one knows m_{x} (or m_{y}), he can solve for m_{y} (or m_{x}) easily. To prevent this attack, one should send only kP and one finite field element y = c_{1}m(mod p).
There are other proposals/standards for computing y_{1} and y_{2} in more complex algorithms from c_{1}, c_{2}, m_{1} and m_{2} in order to prevent an eavesdropper, who knows y_{1}, y_{2} and half the message, say m_{1}, from recovering the other half message m_{2} or from substituting m_{1} by his own message.
RSA algorithm
Key generation: Bob (B) chooses two large prime numbers p, q; n = pq; an
integar e_{B}, e_{B}d_{B} ≡ 1 mod φ (n)^{[2,9]}.
He publishes (n, e_{B}) as the publickey and keeps (n, d_{B})
as the secretkey (reveals it no one). Discard securely p and q.
Encryption:. Here C is the ciphertext of message M to B.
Decryption: M = C^{dB} mod n
The product, n, is the modulus, e is the public exponent and, d is the secret
exponent. You can publish your publickey freely, because there are no known
easy methods of calculating d, p, or q given only (n, e) (your publickey).
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 publickey cryptography. Since
everybody knows everybody else’s publickey, Eve can easily send message
to Alice claiming to be Bob^{[2]}.
Elliptic curve RSA (ECRSA) algorithm: We now mention RSAtype 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 e_{B}, d_{B} with e_{B}d_{B}.
(Here we can use (p+1)(q+1) in place of, 1cm (p+1)(q+1)). B publishes e_{B} as publickey and keeps d_{B} as secretkey. 
Encryption
1. 
Alice (A) represents the message m as a pair of (m_{1},
m_{2}) and regards it as a point M on the elliptic curve E given
by y^{2} = x^{3}+ax+b, where b = m_{2}^{2}m_{1}^{2}.
(A doesn’t need to compute b, because the encryption operation doesn’t
involve b.); 
2. 
A adds M to itself e_{B} times on e_{B} to obtain C =
(c_{1}, c_{2}) = e_{B}M. Here C = (c_{1},
c_{2}) is the ciphertext of message m to B. 
Decryption:B computes d_{B}C=M (mod n) on E to obtain M.
Note: d_{B}C = d_{B}e_{B}M = (1+k(p+1)) M = M+k(p+1) M = M+∞ = M (mod p), with some k≤1. Similarly, for mod q, we have d_{B}C = M modq. So d_{B}C = M mod n. Where, (p+1) M mod p and (q+1) M mod q are ∞ , because E(Z_{n}) and E(F_{p}) ⊕ E(F_{q}), and #E(F_{p}) = 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 what’s called the discrete logarithm problem, it requires that q be a 160bit 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 she’s the sender of a message M, she can use her private “decoding” exponent d to compute C = M^{d} 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 C^{e} and checking that it’s 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 primeorder subgroup of Z_{p}^{*}. 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 Mthat is, the possessor of the value x behind the publicly known, g^{x} mod pto append a pair of numbers r and s obtained by secretly picking another number k between 1 and q, computing r = (g^{k} mod p) mod q (i.e., computing g^{k} 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 SHA1) 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 p1 and g is an element of order q in F_{p}.
The receiver of (M, r, s) from “person” g^{x} computes u = s^{1} SHA(M) mod q and v = s^{1} r mod q and then checks that ((g^{u})(g^{x})^{y} mod p) equals r. If it doesn’t, 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 g^{x}. 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 DiffieHellman (ECDH)^{[59]} and Elliptic Curve Digital Signature Algorithm (ECDSA)^{[78]} are the Elliptic Curve counterparts of the DiffieHellman 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 F_{p} 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 F_{p}: If kP = (k_{1}, k_{2}) is the result of that computation, then r = k_{1} 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 F_{p}. If the xcoordinate 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 aren’t hard in the PversusNP sense. They’re just tedious and timeconsuming. But the special algebraic nature of elliptic curves presents some costcutting 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 E_{p} into itself. As such, it can sometimes be reexpressed 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 systemwide parameters, we could fix the underlying finite field F_{q} for all entities and let each entity select its own elliptic curve E and point P ε (F_{q}). In this case, the defining equation for E, the point P and the order n of P must also be included in the entity’s publickey. If the underlying field F_{q} 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 F_{q}.
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 SHA1, which is the 160 bit hash function.
In digital signature algorithm, the sender sends a message with the sender’s 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 secretkey and Bob (B) verifies the signature with A’s publickey. The algorithm below is the ECDSA protocol which A signs the message m and B verifies A’s 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≤n1, 
2. 
Compute Q = sG the publickey of the sender. 
3. 
A’s publickey Q; A’s privatekey is s. 
The signature is generated as follows:
Signature generation: (A)
1. 
Hash the message and obtain the hash value f = hash(m) = SHA1(m). 
2. 
Generate a random number u, where 1≤u≤n1 
3. 
Compute R = uG = (x_{R}, y_{R}) 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, n1]. 
2. 
Hash the message and obtain the hash value f = SHA1(m). 
3. 
Compute h = d^{1} mod n. 
4. 
Compute h_{1} = fh mod n and h_{2} = ch mod n. 
5. 
Compute P = h_{1}G+h_{2}Q= (x_{p}, y_{p})
and c’ = x_{p} 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. Silverman’s “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/F_{p}, q =
p^{m}, is called supersingular if Tr(φ_{q}) is divisible
by p, Eq. (21). Lets take the case where, q = p^{m}.
In this case we have Tr(φ_{q}) = 0 or #E(F_{p}) = p + 1.
A remarkable construction in order to reduce the ECDLP to a DLP in extension
of F_{p}^{[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 F_{p}. 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 e_{n} is a map which sends a pair of points to a nth power of unity. This nth power of unity can be embedded in . Therefore, the Weil pairing can be defined by: . The Weil pairing has the following properties:
1. 
e_{n}(P, O) = 1 
2. 
e_{n}(P, P) = 1 
3. 
e_{n}(P, Q) A e_{n}(Q, P) = 1 
4. 
e_{n}(P, R) A e_{n}(Q, R) = e_{n} (P+Q,R) 
Suppose that Q = mP. Then for arbitrary points R we have e_{n}(P, R)^{m} = e_{n}(Q, R). The problem to find an m such that x^{m} = y over for x = e_{n} (P, R) and y =e_{n}(Q, R). That is, in the case of supersingular curves over F_{p} 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 F_{q}, the ECDLP can be reduced to DLP over a field of maximal .
Anomalous elliptic curves [Trace 1]: Elliptic curves E/F_{p} 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 PohligHellman cannot be applied. At the end of the last
century Frey and Rück, Semaev, Satoh and Araki. Smart simplified the isomorphism
between E(F_{p}) and the additive group of F_{p}^{[80]}.
In the last group the discrete logarithm problem can be solved easily. It occurs
that an explicit isomorphism Ψ: E(F_{p})→Z/pZ = F_{p}^{+}
can be found easily:
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’ = (p1)/2 is prime as well and E/F_{P} is an elliptic curve with Tr(F_{p})= 2, i.e., #E(F_{p}) = p1, then the ECDLP can be solved directly and reduced to the DLP in F_{p} in polynomial (log_{m}) 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 F_{q}
or can be described by one septuple:
T = (q, FR, a, b, G, n, h)

• 
q: the prime p or 2^{n} 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 F_{n}); 
• 
a,b: the curve coefficients, depending on the security requirement
. N = #E(F_{q}) is divisible by n; 
• 
G: the base point: G = (x_{G}, y_{G}), one
element in E(F_{q}), which has the largest order n; 
• 
n: the order of G, large prime; 
ECC system setup: There are several choices to be made in implementing
ECC system^{[82]}:
• 
Selecting a finite field F_{q} (and a field representing
e.g., np = prime or p = 2^{k}. 
• 
Selecting an appropriate elliptic curve E/F_{p} (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→P_{m} ε E(F_{q}).
There are some other requirements on the parameters to defend some sorts of
attacks:
• 
# E(F_{q}) should have a sufficiently large prime
factor n to resist the parallelized Pollardρ attack; 
• 
# E(F_{q}) ≠ q to resist Semaev, Smart and SatohAraki
attacks on a anomalous curves; 
• 
n doesn’t divide q^{k}1 for 1≤k≤30, to
resist WeilParing and TateParing 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 specialpurpose 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 parametersorder 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 generalpurpose 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 2kbit parameter n takes about the same time as the exhaustive search through all kbit 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 generalpurpose 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 generalpurpose 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 subexponential 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 generalpurpose algorithms exist. While several examples of specialpurpose algorithms have already been mentioned, which exploit special features of the factored numbers, the running times of a generalpurpose 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 publickey 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 PohligHellman (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 subexponential amount of computation time with respect to the key length to do the task. Therefore, the bestknown attack against RSA takes a subexponential amount of computation time with respect to the key length. An attacking method with subexponential time/keylength 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 1024bit RSA and 160bit 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 privatekey 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 bruteforce 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.8x10^{10} MIPS year (i.e., millions of instructions per second times the required number of years) for an elliptic curve key size of only 150bits^{[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.0x10^{8} MIPS year for a 768 bit RSA key and 3.0x10^{11} MIPS year with a RSA key of length 1024bits.
If the RSA key length is increased to 2048bits, the GNFSM will need 3.0x10^{20} MIPS year to factor n whereas increasing the elliptic curve key length to only 234bits will impose a computational complexity of 1.6x10^{28} 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 squareroot 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 Schoof’s 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 publickey cryptosystem to derive symmetrickeys and then use fast symmetrickey algorithms to ensure confidentiality, integrity and source authentication of bulk data. RSA is the most commonly used publickey 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 symmetrickey must match that needed to break the publickey cryptosystem used for the key establishment. Due to expected advances in cryptanalysis and increases in computing power available to an adversary, both symmetric and publickey 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 keysize growth for various symmetric and publickey cryptosystems.
As shown in Table 5, the Elliptic Curve Cryptosystem (ECC) offers the highest strength per bit of any known publickey cryptosystem today. ECC not only uses smaller keys for equivalent strength compared to traditional publickey 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 publickey 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 publickey cryptography is required. Even with significant improvements in processing power, server applications can become seriously burdened by conventional publickey 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 cellphones 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 SHA1 hash function. 
The two approaches do have some significant differences:
• 
The private key d and the persignature 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): Publickey 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 cashreplacing 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 networkat 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 publickey cryptosystems.
CONCLUSION
Publickey 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 publickey can be exploited.
We have described ECC, which is a promising candidate for the nextgeneration publickey cryptosystem. Although ECC’s 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 hardwareimplemented. 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 today’s applications (ecommerce, 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.