# INTRODUCTION

ver the years, with the increase in processing power of computers, there has been a reduction in the work factor required to solve Integer Factorization (IFP) [17], [21], [3] and Discrete Logarithm (DLP) problems [6], [9], [18]. As a result, key sizes grew to more than 1000-bits so as to attain a reasonable level of security. However, in constrained environments carrying out thousand-bit operations is impractical. Therefore, a matter of growing importance in cryptography is the need for algorithms with low resource requirements [24], [14] that can be deployed on resource-constrained ubiquitous devices. This explains why other public-key methods would be welcomed, Elliptic Curve Cryptosystem (ECC) [12] being a probable candidate.

Elliptic curves are the basis for a relatively new class of public-key schemes. It is predicted that Elliptic Curve Cryptosystems (ECC) Elliptic curves were proposed for use as the basis for discrete logarithmbased cryptosystems in 1985, independently by Victor Miller and Neal Koblitz. Elliptic curve are not ellipse, but cubic curves. Properties of ECC made it stronger against various attacks in wireless sensor networks [7], RFID [8], smart card [20] and many others. It will replace many existing schemes in the near future. However, the complicated mathematical background of ECC results in more sophisticated algorithms. Mathematical basis for security of elliptic curve cryptography is computational intractability of elliptic curve discrete logarithm problem (ECDLP) [11].

Elliptic Curve Cryptography (ECC) can be applied to data encryption and decryption, digital signatures, and key exchange procedures. Every user has a public and private key. The public key is used for encryption or signature verification, while the private key is used for decryption or signature generation. ECC is used as an extension to current cryptosystems, for example, ECC Diffie-Hellman Key Exchange (EC-DH) [16], ECC Digital Signature Algorithm (ECDSA) [10] Elliptic Curve Integrated Encryption Scheme (ECIES) [23].

A motivation is given in Section II. In Section III a mathematical background is given. The major uses of ECC in present day cryptosystems are presented in Section III. The underlying theory of elliptic curve cryptosystems is discussed in section IV. Three ECC cryptosystems are given in section V. These are EC-DH, ECDSA and ECIES. The security of these cryptosystems are outlined in Section V with the advantages of using ECC. Finally the conclusion is given in section II.


# Motivation

In order to understand the principle of asymmetric cryptography, the basic symmetric encryption scheme has to be recalled. i. The same secret key is used for encryption and decryption. ii. The encryption and decryption function are very similar (in the case of DES [5] they are essentially identical).

There is a simple real-world analogy for symmetric cryptography. Assume there is a safe with a strong lock. Only Alice and Bob have a copy of the key for the lock. The action of encrypting of a message can be viewed as Alice putting the message in the safe. In order to read, i.e., decrypt, the message, Bob uses his key and opens the safe.

However, there are several shortcomings associated with symmetric-key crypto-schemes. established between Alice and Bob using a secure channel. The communication link for the message is not secure, so sending the key over the channel directly can't be done.

? Number of Keys Even. Each user has to potentially deal with a very large number of keys. If each pair of users' needs a separate pair of keys in a network with n users, there are (n? (n?1)) / 2 key pairs. Thus, each user has to store n ? 1 keys securely. The number of keys that must be generated and transported via secure channels will become exorbitant.

? No Protection against cheating by Alice or Bob.

Alice and Bob have the same capabilities, since they possess the same key. As a consequence, symmetric cryptography cannot be used for applications where we would like to prevent cheating by either Alice or Bob.

In order to overcome these drawbacks, Diffie, Hellman and Merkle made the following proposal. It is not necessary that the key possessed by the person who encrypts the message (that's Alice in our example) is secret. The crucial part is that Bob, the receiver, can only decrypt using a secret key. In order to realize such a system, Bob publishes a public encryption key which is known to everyone. Bob also has a matching secret key, which is used for decryption. Thus, Bob's key k consists of two parts, a public part, k pub , and a private one, k pr .

This systems works quite similarly to the good old mailbox system. Everyone can put a letter in the box, i.e., encrypt, but only a person with a private (secret) key can retrieve letters, i.e., decrypt (see Figure 1).


# Figure 2 : Basic protocol for public-key encryption

By looking at that protocol the exchange of an encrypted key still remains a problem. This can be done by encrypting a symmetric key, e.g., an AES key, using the public-key algorithm. Once the symmetric key has been decrypted by Bob, both parties can use it to encrypt and decrypt messages using symmetric ciphers. But this still poses a grave problem for the public key sharing at the start of the protocol can be intercepted by Oscar. It is these security concerns that resulted in the need for the development of asymmetric cryptosystems.

Public key schemes are all built from one common principle, the one-way function.


# Definition 1 A function f (x) is a one-way function if:

? y = f (x) is computationally easy, and
? x = f ?1 (y) is computationally infeasible.
A function is easy to compute if it can be evaluated in polynomial time, i.e., its running time is a polynomial expression. In order to be useful in practical crypto schemes, the computation y = f (x) should be sufficiently fast that it does not lead to unacceptably slow execution times in an application. The inverse computation x = f ?1 (y) should be so computationally intensive that it is not feasible to evaluate it in any reasonable time period, say, thousands of years, when using the best known algorithm.

Recently the key sizes of public key cryptosystems, for example, RSA prohibits their use in low-power, resource constrained computing devices. Due to this requirement ECC shows an advantage as much smaller key sizes (see Table 1) are needed for the same amount of security. 


# III. MATHEMITICAL BACKGROUND

In Section A modular arithmetic is described. Then, in section B integer rings is defined. Further, in section C finite fields is illustrated. In section D cyclic rings is explained. Section E portrays the concept of subgroups. In Section F the Discrete Logarithm in Prime Fields is depicted. Finally, in section G the Generalized Discrete Logarithm Problem is given.


# a) Modular Arithmetic

Symmetric and asymetric ciphers are usually based on arithmetic with a finite number of elements. The sets of real and natural numbers are infinite. Consider a finite set of integers. The octal set of integer numerals are: {0, 1, 2, 3, 4, 5, 6, 7}. It is possible to do arithmetic in this set so long as: 0 ? result ? 7. For instance: 2 x 2 = 4 or 3 + 4 = 7 is fine, but 7 + 5 gives 12. This result is not a subset of the octal set. To validate this operation an additional operator is used. This is the modulus operation and is defined as follows: Definition 2

Let p, r, q ? Z (where Z is a set of all integers) and q > 0. We write p ? r mod q, if q divides p ? r. q is called the modulus and r is called the remainder. ? A neutral element 0 with respect to addition, i.e., for every element a ? Z m it holds that a + 0 ? a mod m. ? The additive inverse always exists for any element a in the ring, there is always the negative element ?a such that a + (?a) ? 0 mod m. ? The neutral element 1 with respect to multiplication, i.e., for every element a ? Z m it holds that a × 1 ? a mod m. ? The multiplicative inverse exists only for some, but not for all, elements. Let a ? Z, the inverse a ?1 is defined such that a ? a ?1 ? 1 mod m. If an inverse exists for a, we can divide by this element since b/a ? b ? a ?1 mod m. Finding the inverse is difficult, usually employing the Euclidean algorithm []. An easier method is as follows. An element a ? Z has a multiplicative inverse a ?1 if and only if GCD (a, m) = 1, where GCD is the greatest common divisor. If this holds, then a and m are relatively prime or coprime.

? The distributive law is followed: a × (b + c) = (a × b) + (a × c) for all a, b, c ? Z m . Thus, the ring Z m is the set of integers {0, 1, 2, ... , m ? 1} in which we can add, subtract, multiply, and sometimes divide.


# c) Finite Fields

The concept of a simpler algebraic structure, a group is illustrated.


# Definition 4

A group is a set of elements G together with an operation ? which combines two elements of G. A group is set with one operation and the corresponding inverse operation. If the operation is called addition, the inverse operation is subtraction; if the operation is multiplication, the inverse operation is division (or multiplication with the inverse element). A group has the following properties:
? The group operation ? is closed. That is, for all a, b, ? G, it holds that a ? b = c ? G. ? The group operation is associative. That is, a ? (b ? c)= (a ? b) ? c for all a, b, c ? G.
? There is an element 1 ? G, called the neutral element (or identity element), such that a
? 1 = 1 ? a = a for all a ? G. ? For each a ? G there exists an element a ?1 ? G, called the inverse of a, such that a ? a ?1 = a ?1 ? a = 1.
? A group G is abelian (or commutative) if, furthermore, a ? b = b ? a for all a, b ? G. Cryptography uses both multiplicative groups, i.e., the multiplication, and additive groups. Consider the set of integers Z m = {0, 1, ... , m ? 1} and the operation addition modulo m. Every element a has an inverse ?a such that a + ( ?a) = 0 mod m. However, this set does not form a group with the multiplication operation because most elements do not have an inverse where a a ?1 = 1 mod m. Theorem 1

The set ?? ?? * which consists of all integers a = 0, 1, ... , n ? 1 for which GCD (a, n)= 1 forms an abelian group under multiplication modulo n. The identity element is e = 1. In Table 1 n = 9, so ?? ?? * consists of the elements {1, 2, 4, 5, 7, 8}. The following properties are satisfied:

? Closure: integers which are elements of ?? 9 * are used. ? Group identity and inverses: each row and column is a permutation of the elements of ?? 9 * . ? Commutativity: symmetry along the main diagonal.

? Associativity: Multiplication in ?? 9 * . In order to have all four basic arithmetic operations (i.e., addition, subtraction, multiplication, division) in one structure, a set which contains an additive and a multiplicative group is needed. This is called a field. A finite field, sometimes also called Galois field, is a set with a finite number of elements. element 1 for the multiplicative group. Thus every real number a has an additive inverse, namely ?a, and every nonzero element a has a multiplicative inverse 1/a. Also note that the number of elements in the field is called the order or cardinality of the field. The following theorem explains the characteristic of a finite field: Theorem 2

A field with order r only exists if r is a prime power, i.e., r = c n , for some positive integer n and prime integer c. c is called the characteristic of the finite field.

This theorem implies that there are, for instance, finite fields with 243 elements (since 243 = 3 5 )

or with 1024 elements (since 1024 = 2 10 , and 2 is a prime). However, there is no finite field with 24 elements since 24 = 2 3 ? 3. Hence 24 is thus not a prime power.

The most native examples of finite fields are fields of prime order, i.e., fields with n = 1. Elements of the field GF(c) can be represented by integers 0, 1,..., c ? 1. The two operations of the field are modular integer addition and integer multiplication modulo c.


# Theorem 3

Let c be a prime. The integer ring ?? c * is denoted as GF(c) and is referred to as a prime field, or as a Galois field with a prime number of elements. All nonzero elements of GF(c) have an inverse. Arithmetic in GF(c) is done modulo c.

This means that the integer ring ?? m * with modular addition and multiplication, and m happens to be a prime, ?? m * is not only a ring but also a finite field. In order to do arithmetic in a prime field, the rules for integer rings hold: Addition and multiplication are done modulo c, the additive inverse of any element a is given by a + (?a) = 0 mod c, and the multiplicative inverse of any nonzero element a is defined as a ? a ?1 = 1.


# d) Cyclic Groups Definition of a finite group: Definition 6

A group (G, ?) is finite if it has a finite number of elements. We denote the cardinality or order of the group G by |G|. The following are some examples of finite groups:
? (?? n * , +): the cardinality of ?? n * is |?? n * | = n since ?? n * = {0, 1, 2,..., n ? 1}. ? (?? n * ,
?): remember that ?? n * is defined as the set of positive integers smaller than n which are relatively prime to n. Thus, the cardinality of ?? n * equals Euler's phi function [] evaluated for n, i.e., |?? n * | = ?(n). For instance, the group ?? 9

* has a cardinality of ?(9)= 32 ? 31 = 6. Thus the group consists of the six elements {1, 2, 4, 5, 7, 8}.

Cyclic groups are the basis for discrete logarithm-based cryptosystems. The order of an element is defined as follows: 


# This cyclic behavior gives rise to following definition: Definition 8

A group G which contains an element c with maximum order ord(c) = |G| is said to be cyclic. Elements with maximum order are called primitive elements or generators.

An element c of a group G with maximum order is called a generator since every element b of G can be written as a power c n = b of this element for some n, i.e., c generates the entire group.

The theorem below states that the multiplicative group of every prime field is cyclic. Thus these groups are the most useful for building discrete logarithm (DL) cryptosystems.


# Theorem 4

For every prime p, (?? p * , ?) is an abelian finite cyclic group.

Theorem 5 first shows Fermat's Little Theorem for all cyclic groups. Secondly it shows that only element orders which divide the group cardinality exist in a cyclic group.


# Theorem 5

Let G be a finite group. Then for every a ? G it holds that:
? a|G| = 1 ? ord(a) divides |G| b 1 = b 1 ? b 0 = 4 ? 1 = 4 ? 4 mod 7 b 2 = b 1 ? b 1 = 4 ? 4 = 16 ? 2 mod 7 b 3 = b 2 ? b 1 = 2 ? 4 = 8 ? 1 mod 7 b 4 = b 3 ? b 1 = 1 ? 4 = 4 ? 4 mod 7 b 5 = b 4 ? b 1 = 4 ? 4 = 16 ? 2 mod 7 b 6 = b 3 ? b 3 = 1 ? 1 = 1 ? 1 mod 7 b 7 = b 3 ? b 4 = 1 ? 4 = 4 ? 4 mod 7 b 8 = b 3 ? b 5 = 1 ? 2 = 2 ? 2 mod 7 b 9 = b 3 ? b 6 = 1 ? 1 = 1 ? 1 mod 7 b 10 = b 3 ? b 7 = 1 ? 4 = 4 ? 4 mod 7 b 11 = b 3 ? b 8 = 1 ? 2 = 2 ? 2 mod 7 b 12 = b 3 ? b 9 = 1 ? 1 = 1 ? 1 mod 7
Let (G, ?) be a cyclic group. Then every element b ? G with ord(s) = t is the primitive element of a cyclic subgroup with t elements.


# Consider a subgroup of G =?? 11

* . Now ord(3) = 5, and the powers of 3 generate the subset J = {1, 3, 4, 5, 9}. To verify whether this set is actually a group its multiplication table has to be explored: ? For every element b ? J there exists an inverse b?1 ? J which is also an element of J. Every row and every column of the table contain the identity element. ? J is a subgroup of prime order 5. and their generators g are given below.


# Subgroup

Elements Primitive Elements
H 1 {1} g = 1 H 2 {1, 10} g = 10 H 3 {1, 3, 4, 5, 9} g = 3, 4, 5, 9
The following theorem gives us immediately a construction method for a subgroup from a given finite cyclic group. The only thing we need is a primitive element and the group cardinality c. One can now simple compute g c/n and obtains a generator of the subgroup with n elements.


# Theorem 8

Let G be a finite cyclic group of order c and let g be a generator of G. Then for every integer n that divides c there exists exactly one cyclic subgroup J of G of order n. This subgroup is generated by g c/n . J consists exactly of the elements b ? G which satisfy the condition b n = 1. There are no other subgroups.

Consider the cyclic group ?? 11 * . Now g = 8 is a primitive element in the group. To get a generator g for the subgroup of order 2 compute: q = g c/n = 8 10/2 = 8 5 = 32768 ? 10 mod 11. The element 10 generates the subgroup with two elements:


# f) The Discrete Logarithm in Prime Fields

The discrete logarithm problem (DLP), can directly be explained using cyclic groups. Two important areas are the DLP over Prime fields and the generalized DLP problem. Consider the DLP over ?? p * , where p is a prime.


# Definition 9

Given is the finite cyclic group ?? 11 * of order p ? 1 and a primitive element g ? ?? 11

* and another element q ? ?? 11 * . The DLP is the problem of determining the integer 1 ? x ? p ? 1 such that: g x ? q mod p.

Such an integer x must exist since g is a primitive element and each group element can be expressed as a power of any primitive element. This integer x is called the discrete logarithm of q to the base g, and we can formally write: x = log g q mod p. Computing discrete logarithms modulo a prime is a very hard problem if the parameters are sufficiently large. Since exponentiation g x ? q mod p is computationally easy, this forms a one-way function.

Consider the group ?? 47 * which has order 46. The subgroups in ?? 11

* have thus a cardinality of 23, 2 and 1. Now g = 2 is an element in the subgroup with 23 elements, and since 23 is a prime, g = 2 is a primitive element in the subgroup. A possible discrete logarithm problem is given for q = 36 (which is also in the subgroup): Find the positive integer x, 1 ? x ? 23, such that 2 x ? 36 mod 47. By using a brute-force attack, a solution is x = 17.


# g) The Generalized Discrete Logarithm Problem

The generalized discrete logarithm problem (GDLP) is used in cryptography and is not restricted to the multiplicative group ?? p * , p prime, but can be defined over any cyclic groups.


# Definition 10

Given is a finite cyclic group G with the group operation ? and cardinality k. We consider a primitive


# Global Journal of C omp uter S cience and T echnology

Volume XV Issue V Version I ( ) E Year 2015 q 1 = 10, q 2 = 100 ? 1 mod 11, q 3 ? 10 mod 11 ? Theorem 6 element g ? G and another element q ? G. The discrete logarithm problem is finding the integer n, where 1 ? n ? k, such that: q = g ? g ? . ..? g = g n , n times.

Such an integer n must exist since g is a primitive element as in the case of the DLP in ?? p * . Thus each element of the group G can be generated by repeated application of the group operation on g. Consider the additive group of integers modulo a prime. For instance, choose the prime p = 11, G = ( ?? 11 * , +) is a finite cyclic group with the primitive element g = 2. Here is how g generates the group:

We try now to solve the DLP for the element q = 3, i.e., we have to compute the integer 1 ? n ? 11 such that: n ? 2 = 2 + 2 + ...+ 2 (n times) ? 3 mod 11. Even though the group operation is addition, we can express the relationship between g, q and the discrete logarithm n in terms of multiplication: n? 2 ? 3 mod 11. In order to solve for n, invert the primitive element g: n ? 2 ?1 3 mod 11. Using, e.g., the extended Euclidean algorithm, compute 2 ?1 ? 6 mod 11 to get the discrete logarithm: n ? 2 ?1 3 ? 7 mod 11.

The DLP can be solved easily here as there are mathematical operations which are not in the additive group. They are multiplication and inversion. However, often it was found that the underlying DL problem is not difficult enough.

IV.


# Elliptic Curve Theory a) Basic Properties

ECC is based on the generalized discrete logarithm problem. A cyclic group where the DL problem is computationally hard is required. This means that it must have good one-way properties. Polynomials functions with sums of exponents of x and y can be chosen. For example, the polynomial equation a ? x 2 + b ? y 2 = c over the real numbers turns out to be an ellipse.

An elliptic curve is a special type of polynomial equation. In ECC the curve is not over the real numbers but over a finite field. The most popular choice is prime fields GF(p), where all arithmetic is performed modulo a prime p. The curve is nonsingular so that it has no selfintersections or vertices, and is achieved if the discriminant of the curve ?16*(4a 3 + 27b 2 ) is nonzero.


# Definition 11

The elliptic curve over ?? p * , p > 3, is the set of all pairs (x, y) ? ?? p * which fulfill y 2 ? x 3 + a ? x + b mod p together with an imaginary point of infinity O, where a, b ? ?? p * and the condition 4 ? a 3 + 27 ? b 2 ? 0 mod p.


# b) Group Operations on Elliptic Curves

"Addition" means that given two points and their coordinates, say A = (x 1 , y 1 ) and B = (x 2 , y 2 ), we have to compute the coordinates of a third point C such that: A + B = C or (x 1 , y 1 ) + (x 2 , y 2 ) = (x 3 , y 3 ). Two cases are considered: ? the addition of two distinct points (point addition)

? the addition of one point to itself (point doubling) Point Addition P + Q : This is the case where we compute R = P + Q and P ? Q. The construction works as follows: A line through P and Q intersects a third point between the elliptic curve and the line. Mirror this third intersection point along the x-axis. This mirrored point is, by definition, the point R. Figure 1 shows the point addition on an elliptic curve over the real numbers.  With these operations the points on the elliptic curve fulfill the group conditions: closure, associativity, existence of an identity element and existence of an inverse. Consider the add, subtract, multiply and divide operations over prime fields GF(p) rather than over the real numbers. The following analytical expressions become relevant. The elliptic curve point addition and doubling formulae are shown: The parameter s is the slope of the line through P and Q in the case of point addition, or the slope of the tangent through P in the case of point doubling. An identity (or neutral) element O such that: P + O = P is compulsory. An abstract point at infinity is used as the neutral element O. This point at infinity is located towards "plus" infinity along the y-axis or towards "minus" infinity along the y-axis. Hence, the inverse ?P of any group element P is: P + (?P) = O.
if P ? Q (point addition), ?? = ?? 2 ? ?? 1 ?? 2 ? ?? 1 ?????? ?? if P = Q (point doubling), ?? = 3?? 1 2 +?? 2?? 1 ?????? ?? then x 3 = s 2 ? x 1 ? x 2 mod p
o Finding the inverse of a point P = (x p , y p ) is the negative of its y coordinate. In the case of elliptic curves over a prime field GF(p) as ?y p ? p ? y p mod p, hence ?P = (x p , p ? y p ). An example for the group operation is now given. Consider a curve over the small field ?? 29 * , E : y 2 ? x 3 + 2x + 2 mod 17. To double the point A = (3, 1): Inserting the coordinates into the curve equation: y 2 ? x 3 + 2 ? x + 2 mod 17 = 7 2 ? 13 3 + 2 ? 13 + 2 mod 17. So 15 = 2225 ? 15 mod 17 which proves that the point is actually on the curve.
? 2P = P + P = (3, 1) + (3, 1) = (x 3 , y 3 ). ? Now s = (2 ? 1)?1 * (3 ? 32 + 2) = 2?1 ? 29 ? 9 ? 12 = 63 ? 6 mod 1. ? Also x3 = s2 ? x1 ? x2 =

# c) Building a Discrete Logarithm Problem with Elliptic

Curves Setting up the discrete logarithm problem is now discussed.


# Definition 12

Given an elliptic curve E, consider a primitive element P and another element R. The DL problem is finding the integer d, where 1 ? d ? #E, such that: P + P + ??? + P = d * P = U. P is repeated d times. In cryptosystems, d is the private key which is an integer, while the public key U is a point on the curve with coordinates U = (x u , y u ).

The operation in Definition 12 is called point multiplication. Thus, formally U = d * P. Note d*P is a notation for this repeated group operation. If a multiplicative notation is chosen, the ECDLP would have had the form P d = U, which would have been more consistent with the conventional DL problem in ?? 29 * . Given a starting point P for the ECDLP elliptic curves over the real numbers, the computation becomes 2P, 3P, .. ., d*P = U . This is effectively hopping back and forth on the elliptic curve. The starting point P (a public parameter) and the final point U (the public key) is put in the public domain. To break the cryptosystem, an attacker has to figure out how often we "jumped" on the elliptic curve. Thus, the number of hops is the secret d, the private key.

V.


# ELLIPTIC CURVE CRYPTOSYSTEMS a) Elliptic Curve Diffie-Hellman

As with the conventional Diffie-Hellman key exchange (DHKE) [] a key exchange using elliptic curves can be realized. This elliptic curve Diffie-Hellman key exchange (ECDH) requires agreed upon domain parameters on an elliptic curve and a primitive element on this curve: ? Choose a prime p and the elliptic curve: E : y 2 ? x 3 + a ? x + b mod p ? Choose a primitive element P = (x P , y P ). The prime p, the curve given by its coefficients a, b, and the primitive element P are the domain parameters.

The actual key exchange is the same as for the conventional Diffie-Hellman protocol. Alice and Bob choose the private keys a and b, respectively, which are two large integers. With the private keys both generate their respective public keys A and B, which are points on the curve. The public keys are computed by point multiplication. The two parties exchange these public parameters with each other. The joint secret T AB is then computed by both Alice and Bob by performing a second point multiplication involving the public key they received and their own secret parameter. The joint secret T AB can be used to derive a session key, e.g., as input for the AES algorithm []. Note that the two coordinates (x AB , y AB ) are not independent of each other: Given x AB , the other coordinate can be computed by simply inserting the x value in the elliptic curve equation.

Thus, only one of the two coordinates should be used for the derivation of a session key. EC-DH Key Exchange is now shown. Let's look at an example with small numbers.

We consider the ECDH with the following domain parameters. The elliptic curve is y 2 ? x 3 + 2x + 2 mod 17, which forms a cyclic group of order #E = 19. The base point is P = (5, 1). The protocol proceeds as follows:

Joint secret between Alice and Bob: T AB = (13, 10).


# b) The Elliptic Curve Digital Signature Algorithm (ECDSA)

The ECDSA standard is defined for elliptic curves over prime fields Z p and Galois fields GF(2 m ). The former is often preferred in practice, and is used in what follows. The keys for the ECDSA are computed as follows:

i. Key Generation for ECDSA Use an elliptic curve E with modulus p, coefficients a and b and a point A which generates a cyclic group of prime order q. Then choose a random integer d with 0 < d < q. Finally compute B = d A. The keys are now: k pub = (p, a, b, q, A, B) and k pr = (d).

Note that we have set up a discrete logarithm problem where the integer d is the private key and the result of the scalar multiplication, point B, is the public key. Similar to DSA, the cyclic group has an order q which should have a size of at least 160 bit or more for higher security levels.


# ii. Signature and Verification

The ECDSA signature consists of a pair of integers (r, s). Each value has the same bit length as q, which makes for fairly compact signatures. Using the public and private key, the signature for a message x is computed as follows.

iii. ECDSA Signature Generation

? Choose an integer as random ephemeral key k E with 0 < k E < q.
? Compute R = k E A. ? Let r = x R . Compute s ? (h(x) + d ? r) k E ?1 mod q
In step 3 the x-coordinate of the point R is assigned to the variable r. The message x has to be hashed using the function h in order to compute s. The hash function output length must be at least as long as q. The hash function compresses x and computes a fingerprint which can be viewed as a representative of x. The signature verification process is as follows. iv. ECDSA Signature Verification

? Compute auxiliary value w ? s ?1 mod q.

? Compute auxiliary value u 1 ? w ? h(x) mod q.

? Compute auxiliary value u 2 ? w ? r mod q.

? Compute P = u 1 A + u 2 B.

The verification ver k pub (x, (r, s)) follows from: x P ? r mod q ? valid signature and x P r mod q ? invalid signature.

In the last step, the notation x P indicates the xcoordinate of the point P. The verifier accepts a signature (r, s) only if the x P has the same value as the signature parameter r modulo q. Otherwise, the signature should be considered invalid.

Proof. We show that a signature (r, s) satisfies the verification condition r ? x P mod q. We'll start with the signature parameter s. s ? (h(x)+ d r) k E ?1 mod q = k E ? s ?1 h(x)+ d s ?1 r mod q Use the auxiliary values u 1 and u 2 : = k E ? u 1 + d u 2 mod q Multiply both sides of the equation with A as the point A generates a cyclic group of order q: = k E A = (u 1 + d u 2 ) A Group operation is associative: = k E A = u 1 A + d u 2 A Group operation is associative:
= k E A = u 1 A + u 2 B
Thus the expression u 1 A + u 2 B is equal to k E A if the correct signature and key (and message) have been used. But this is exactly the condition that we check in the verification process by comparing the xcoordinates of P = u 1 A + u 2 B and R = k E A.

Bob wants to send a message to Alice that is to be signed with the ECDSA algorithm. The signature and verification process is as follows. The elliptic curve E: 


# SECURITY OF ECC CRYPTOSYSTEMS a) Security of EC -DH

Elliptic curves are used as the ECDLP has very good one-way characteristics. E, p, P, A, and B is available for an attacker who wants to break the ECDH. The attacker desires to compute the joint secret between Alice and Bob T AB = a * b * P. This is known as the elliptic curve Diffie-Hellman problem (ECDHP). Presently, there seems to be only one way to compute T AB , that is, to solve either a = log P A, or b = log P B. Each of which are discrete logarithm problems.

For carefully chosen elliptic curve the best known attacks against the ECDLP are considerably weaker than the best algorithms for solving the DL problem modulo p, and the best factoring algorithms which are used for RSA attacks. In particular, the indexcalculus algorithms [22], which are powerful attacks against the DLP modulo p, are not applicable against elliptic curves. For carefully selected elliptic curves, the only remaining attacks are generic DL algorithms, that is, Shanks' baby-step giant-step method [19] and Pollard's rho method [1].

As the number of steps required for such an attack is approximately equal to the square root of the group cardinality, a group order of at least 2 160 should be used. An attack with a group consisting of generic algorithms, will require about 2 80 steps. Thus, a security level of 80 bits provide moderate security. Thus, in practice elliptic curve bit lengths of up to 256 bits are commonly used. This will provide security levels of up to 128 bits.


# b) Security of ECDSA

Elliptic curves have several advantages over RSA and over DL schemes like Elgamal or DSA. In particular, the absence of strong attacks against elliptic curve cryptosystems (ECC), bit lengths in the range of 160-256 bit can be chosen which provide security equivalent to 1024-3072-bit RSA and DL schemes. The shorter bit length of ECC often results in shorter processing time and in shorter signatures.

Given that the elliptic curve parameters are chosen correctly, the main analytical attack against ECDSA attempts to solve the elliptic curve discrete logarithm problem. If an attacker were capable of doing this, he could compute the private key d and/or the ephemeral key. However, the best known ECC attacks have a complexity proportional to the square root of the size of the group in which the DL problem is defined, i.e., proportional to ?q.

The security level of the hash function must also match that of the discrete logarithm problem. The cryptographic strength of a hash function is mainly determined by the length of its output. The security levels of 128, 192 and 256 were chosen so that they match the security offered by AES with its three respective key sizes. More subtle attacks against ECDSA are also possible. For instance, at the beginning of verification it must be checked whether r, s ? {1, 2,..., q}. Also, protocol-based weaknesses, e.g., reusing the ephemeral key, must be prevented.


# c) Security of ECIES

The cryptographic strength of elliptic curve encryption lies in the difficulty for a cryptanalyst to determine the secret random number k from k*P and P itself. The fastest method to solve this problem (known as the elliptic curve logarithm problem) is the Pollard ? factorization method [].

The computational complexity for breaking the elliptic curve cryptosystem, using the Pollard ? method, is 3.8×1010 MIPS-years (i.e. millions of instructions per second times the required number of years) for an elliptic curve key size of only 150 bits []. Finally increasing the elliptic curve key length to only 234 bits will impose a computational complexity of 1.6 × 1028 MIPS-years (still with the Pollard ? method).


# VII.


# CONCLUSION

Public-key encryption can be used to eliminate problems involved with conventional encryption. However, it has not managed to be as widely accepted as conventional encryption because it introduces a lot of overheads. Therefore, it is very important to find ways to reduce the overheads yet not sacrificing on other aspects of security so that the desirability in public-key can be exploited.

ECC have been described, which is a promising candidate for the next generation public-key cryptosystem. Although ECC's security has not been completely evaluated, it is expected to come into widespread use in various fields in the future.

ECC has been shown to have many advantages due to its ability to provide the same level of security as other public key cryptosystems, yet using shorter keys. However, its disadvantage which may even hide its attractiveness is its lack of maturity, as mathematicians believed that enough research has not yet been done in ECDLP. Finally, the future of ECC looks brighter than that of other public key cryptosystems as today's applications (smart cards, pagers, and cellular telephones etc) cannot afford the associated overheads.
1![Figure 1 : Symmetric key encryption](image-2.png "Figure 1 :")
![Thus 7 + 5 = 12, which when divided by 8 (12/8) gives a remainder of 4. So 7 + 5 = 4 mod 8. In practice the integers involved have a length of 130-4096 ? Key Distribution Problem. The key must be b) Integer Rings Consider the set of integers from zero to m-1 with two operators: addition and multiplication. A ring on this set is defined as follows: Definition 3 A ring is the set of integers Z m = {0, 1, 2,..., m ? 1} with the "+" and "×" operations ? e, f, g, h ? Z m : e + f ? g mod m ? e × f ? h mod m The following properties of rings are important: ? Closed: addition and multiplication of two numbers has a result in the ring. ? Ring operations are associative: a + (b + c)= (a + b)+ c, and a ? (b ? c)= (a ? b) ? c for all a, b, c ? Z m .](image-3.png "")
5![field F is a set of elements with the following properties: ? All elements of F form an additive group with the group operation "+" and the neutral element 0. ? All elements of F except 0 form a multiplicative group with the group operation "×" and the neutral element 1. ? When the two group operations are mixed, the distributive law holds, i.e., for all a, b, c ? F: a(b + c)= (ab)+ (ac). The set R of real numbers is a field with the neutral element 0 for the additive group and the neutral The Security of Elliptic Curve Cryptosystems -A Survey Global Journal of C omp uter S cience and T echnology Volume XV Issue V Version I ( ) E Year 2015](image-4.png "Definition 5 A")
7![The order ord(b) of an element b of a group (G, ?) is the smallest positive integer n such that: b n = b ? b ? . ..? b = 1, occurs n times and 1 is the identity element of G. By using Definition 6, determine the order of b = 4 in the group ?? 7 * . To do this, compute the powers of b until we obtain the identity element 1. Shown from the last line: ord(4) = 3. Keep multiplying the result by b: The powers of b run through the sequence {1, 4, 2} indefinitely. This implies that b = 4 is a primitive element and |?? 7 * | is cyclic. It follows that ord(b)= 4 = |?? 7 * |. The group ?? 7 * has the element 4 as a generator.](image-5.png "Definition 7")
![The elements 3, 4, 5 and 9 are generators of J. ? Each element b ? G of a group G generates some subgroup J. Subgroups of prime order are of enormous interest in cryptography. The following theorem follows. Theorem 7 Let J be a subgroup of G. Then |J| divides |G|. Thus the cyclic group ?? 11 * has cardinality |?? 11 * | = 10 = 1 ? 2 ? 5. Thus, it follows that the subgroups of ?? 11 * have cardinalities 1, 2, 5 and 10 since these are all possible divisors of 10. All subgroups J of ?? 11 *](image-6.png "?")
1![Figure 1 : Point addition on an elliptic curve over the real numbers Point Doubling P + Q : This is the case where we compute P + Q but P = Q. Hence, R = P + P = 2P. First draw the tangent line through P and obtain a second point of intersection between this line and the elliptic curve. Then mirror the second point of intersection along the x-axis. This mirrored point is the result R of the doubling as shown in Figure 2.](image-7.png "Figure 1 :")
2![Figure 2 : Point doubling on an elliptic curve over the real numbers](image-8.png "Figure 2 :")
13![The Security of Elliptic Curve Cryptosystems -A Survey© 2015 Global Journals Inc. (US)Global Journal of C omp uter S cience and T echnologyVolume XV Issue V Version I = s*(x 1 ? x 3 ) ? y 1 mod p](image-9.png "1 30y 3")
![62 ? 3 ? 3 = 30 ? 13 mod 17. ? And y3 = s(x1 ? x3) ? y1 = 6 * (3 ? 13) ? 1 = -61 ? 7 mod 17. ? Thus, 2P = (3, 1) + (3, 1) = (13, 7).](image-10.png "")



1ECC(in bits) RSA(in bits)10651211276813210241602048210307228376804091536057121000
1
14, 5, 9} J is a subgroup of ?? 11 * : ? J is closed under multiplication modulo 11 since the table only consists of integers which are elements of J. ? The group operation is obviously associative and commutative since it follows regular multiplication rules. ? The neutral element is 1.
			© 2015 Global Journals Inc. (US)
		
		
			

				


* 
	
		Toward a theory of Pollard's rho method
		
			EBach
		
	
	
		Information and Computation
		
			90
			2
			
			1991
		
	




* 
	
		Software infrastructure and design challenges for ubiquitous computing applications
		
			GBanavar
		
		
			ABernstein
		
	
	
		Communications of the ACM
		
			45
			12
			
			2002
		
	




* 
	
		Some integer factorization algorithms using elliptic curves
		
			RPBrent
		
		arXiv:1004.3366
		
			2010
		
	
	arXiv preprint




* 
	
		
		
			VMDavis
		
		
			SCCutino
		
		
			MJBerg
		
		
			FSConklin
		
		
			SJPringle
		
		
			2001
			282
			Washington, DC: U.S
		
	
	U.S. Patent
	Patent and Trademark Office




* 
	
		Internet besieged: Countering cyberspace scofflaws
		
			DE RDenning
		
		
			PJDenning
		
		
			1998
			ACM Press
		
	




* 
	
		A public key cryptosystem and a signature scheme based on discrete logarithms
		
			TElgamal
		
	
	
		Advances in Cryptology
				Berlin Heidelberg
		
			Springer
			1985. January
			
		
	




* 
	
		
		
			RFerri
		
		
			MKim
		
		
			EYee
		
		
			2004
			U.S
		
	
	Patent Application 10/856,684




* 
	
		RFID handbook: radiofrequency identification fundamentals and applications
		
			KFinkenzeller
		
		
			1999
			Wiley
			
			New York
		
	




* 
	
		Discrete logarithm problem
		
			DGordon
		
	
	
		Encyclopedia of Cryptography and Security
				
			Springer US
			2011
			
		
	




* 
	
		The elliptic curve digital signature algorithm (ECDSA)
		
			DJohnson
		
		
			AMenezes
		
		
			SVanstone
		
	
	
		International Journal of Information Security
		
			1
			1
			
			2001
		
	




* 
	
		Remarks on elliptic curve discrete logarithm problems
		
			NKanayama
		
		
			TKobayashi
		
		
			TSaito
		
		
			SUchiyama
		
	
	
		IEICE Transactions on Fundamentals of Electronics
		
			83
			1
			
			2000
		
	
	Communications and Computer Sciences




* 
	
		Elliptic curve cryptosystems. Mathematics of computation
		
			NKoblitz
		
		
			1987
			48
			
		
	




* 
	
		RFID sourcebook
		
			SLahiri
		
		
			2005
			IBM press
		
	




* 
	
		Public key cryptography and RFID tags
		
			MMcloone
		
		
			MJRobshaw
		
	
	
		Topics in Cryptology-CT-RSA 2007
				Berlin Heidelberg
		
			Springer
			2006
			
		
	




* 
	
		Towards a distributed platform for resource-constrained devices
		
			AMesser
		
		
			IGreenberg
		
		
			PBernadat
		
		
			DMilojicic
		
		
			DChen
		
		
			TJGiuli
		
		
			XGu
		
	
	
		Distributed Computing Systems
				
			2002. 2002
		
	




* 
	
		Use of elliptic curves in cryptography
		
			VSMiller
		
	
	
		Advances in Cryptology-CRYPTO'85 Proceedings
				Berlin Heidelberg
		
			Springer
			1986. January
			
		
	




* 
	
		A survey of modern integer factorization algorithms
		
			PLMontgomery
		
	
	
		CWI quarterly
		
			7
			4
			
			1994
		
	




* 
	
		Simultaneous security of bits in the discrete log
		
			RPeralta
		
	
	
		Advances in Cryptology-Eurocrypt'85
				Berlin Heidelberg
		
			Springer
			1986. January
			
		
	




* 
	
		Kangaroos, monopoly and discrete logarithms
		
			JMPollard
		
	
	
		Journal of cryptology
		
			13
			4
			
			2000
		
	




* 
	
		Smart card handbook
		
			WRankl
		
		
			WEffing
		
		
			2010
			John Wiley & Sons
		
	




* 
	
		A new polynomial factorization algorithm and its implementation
		
			VShoup
		
	
	
		Journal of Symbolic Computation
		
			20
			4
			
			1995
		
	




* 
	
		Elliptic curve discrete logarithms and the index calculus
		
			JHSilverman
		
		
			JSuzuki
		
	
	
		Advances in Cryptology-ASIACRYPT'98
				Berlin Heidelberg
		
			Springer
			1998. January
			
		
	




* 
	
		The exact security of ECIES in the generic group model
		
			NPSmart
		
	
	
		Cryptography and Coding
				Berlin Heidelberg
		
			Springer
			2001
			
		
	




* 
	
		hard real-time systems
		
			WZhao
		
		
			KRamamritham
		
		
			JAStankovic
		
	
	
		Software Engineering
		
			5
			
			1987
		
	
	IEEE Transactions on