Ecc Report

Elliptic Curve Cryptography: Elliptic Curve Cryptography (ECC) is a public key cryptography. In public key cryptography each user or the device taking part in the communication generally have a pair of keys, a public key and a private key, and a set of operations associated with the keys to do the cryptographic operations. Only the particular user knows the private key whereas the public key is distributed to all users taking part in the communication. Elliptic Curves Elliptic curves are not ellipses. They are so named because they are described by cubic equations, similar to those used for calculating the circumference of an ellipse. In general, cubic equations for elliptic curves take the form y2 + axy + by = x3 + cx2 + dx + e where a, b, c, d, and e are real numbers and x and y take on values in the real numbers.[3] For our purpose, it is sufficient to limit ourselves to equations of the form y2 = x3 + ax + b The mathematical operations of ECC is defined over the elliptic curve y2 = x3 + ax + b, where 4a3+27b2 ≠ 0. Each value of the ‘a’ and ‘b’ gives a different elliptic curve. All points (x, y) which satisfies the above equation plus a point at infinity lies on the elliptic curve. The public key is a point in the curve and the private key is a random number. The public key is obtained by multiplying the private key with the generator point G in the curve. Elliptic Curves over F p Let Fp be a prime finite field so that p is an odd prime number, and let a,b € Fp satisfy 4a3+27b2 ≠ 0(mod p). Then an elliptic curve E(F p) over Fp defined by the parameters a,b € Fp consists of the set of solutions or points P = (x,y) for x,y € Fp to the equation: y2 = x3 + ax + b(mod p) together with an extra point O called the point at infinity. The equation y2 = x3 + ax + b (mod p) is called the defining equation of E(Fp). For a given point P = Xp,Yp , Xp is called the x-coordinate of P, and YP is called the y-coordinate of P.

1

Geometric Explanation: Point addition Point addition is the addition of two points J and K on an elliptic curve to obtain another point L on the same elliptic curve.

Consider two points J and K on an elliptic curve as shown in figure (a). If K ≠ -J then a line drawn through the points J and K will intersect the elliptic curve at exactly one more point –L. The reflection of the point –L with respect to x-axis gives the point L, which is the result of addition of points J and K. Thus on an elliptic curve L = J + K. If K = -J the line through this point intersect at a point at infinity O. Hence J + (-J) = O. This is shown in figure (b). O is the additive identity of the elliptic curve group. Point doubling Point doubling is the addition of a point J on the elliptic curve to itself to obtain another point L on the same elliptic curve.

To double a point J to get L, i.e. to find L = 2J, consider a point J on an elliptic curve as shown in figure (a). If y coordinate of the point J is not zero then the tangent line at J will intersect the elliptic curve at exactly one more point –L. The reflection of the point –L with respect to x-axis gives the point L, which is the result of doubling the point J. Thus L = 2J. If y coordinate of the point J is zero then the tangent at this point intersects at a point at infinity O. Hence 2J = O when yJ = 0. This is shown in figure (b). 2

Analytical Explanation: Point Addition Consider two distinct points J and K such that J = (xJ, yJ) and K = (xK, yK) Let L = J + K where L = (xL, yL), then xL = s2 - xJ – xK mod p yL = -yJ + s (xJ – xL) mod p s = (yJ – yK)/(xJ – xK) mod p, s is the slope of the line through J and K. If K = -J i.e. K = (xJ, -yJ mod p) then J + K = O. where O is the point at infinity. If K = J then J + K = 2J then point doubling equations are used. Also J + K = K + J Point Doubling Consider a point J such that J = (xJ, yJ), where yJ ≠ 0 Let L = 2J where L = (xL, yL), Then xL = s2 – 2xJ mod p yL = -yJ + s(xJ - xL) mod p s = (3xJ2 + a) / (2yJ) mod p, s is the tangent at point J and a is one of the parameters chosen with the elliptic curve If yJ = 0 then 2J = O, where O is the point at infinity.

3

Modular Arithmetic: Modular arithmetic over a number p involves arithmetic between numbers 0 and p – 1. If the number happens to be out of this range in any of the operation the result is wrapped around in to the range 0 and p – 1. Addition Let p = 23, a = 15, b = 20 a + b (mod p) = 15 + 20 (mod 23) = 35 mod 23 = 12 Since the result of a + b = 35 which is out of the range [0 22], The result is wrapped around in to the range [0 22] by subtracting 35 with 23 till the result is in range [0 22]. a mod b is thus explained as remainder of division a/b. Subtraction Let p = 23, a = 15, b = 20 a - b (mod p) = 15 - 20 (mod 23) = -5 mod 23 = 18 Since the result of a - b = -5 which is negative and out of the range [0 22], The result is wrapped around in to the range [0 22] by adding -5 with 23 till the result is in range [0,22]. Multiplication Let p = 23, a = 15, b = 20 a * b (mod p) = 15 * 20 (mod 23) = 300 mod 23 = 1 Since the result of a * b = 300 which is out of the range [0 22], The result is wrapped around in to the range [0 22] by subtracting 300 with 23 till the result is in range [0 22]. Division The division a/b (mod p) is defined as a * b-1 (mod p). b-1 is the multiplicative inverse of b over p. Multiplicative Inverse Multiplicative inverse of number b with respect to mod p is defined as a number b-1 such that b*b-1 (mod p) = 1. Multiplicative inverse exists only if b and n are relatively prime. The algorithm such as extended Euclidean algorithm can be used to find the multiplicative inverse of a number efficiently. Finding multiplicative inverse is a costly operation. Finding x mod y x mod y is the remainder of the division x/y.

4

Elliptic Curve Key Generation: Generation of all the points on the elliptic curve In order to generate the public and private keys from a elliptic curve we first have to find out the total number of points residing on the curve. These points have to satisfy the equation y2 = x3 + ax + b (mod p) where a, b are constants and p is a large prime number. We now have to calculate the order of each individual point. Calculating the order of each point on the curve The order n of a point G on an elliptic curve is the smallest positive integer n such that nG = O. In order to calculate the order, we take into consideration each individual point and go on adding the point until we get the point O (the point at infinity) or no more can be calculated. The first addition is nothing but the doubling of the point. Next the result generated from the doubling is added to the original point. Result generated from this is again added to the original point and so on until the point at in infinity. The number of additions required to find the point at infinity is called the order of the point. Calculating the order of the curve On getting the order of each individual point we have to calculate the highest order among them. This point gives the order of the curve. Generating the private keys Once the point of highest order and order of curve have been generated, it is now possible to find out the private keys. The private key (p) is nothing but a number which is a little less than the order of the curve (n) i.e.1
5

Why ECC ? Scope of Elliptic Curve Cryptography The system can be used in Electronic Transactions through Smart Cards, Access Control to High Security Zones, Wireless Security, Secure Web Transactions and Messaging, Production of Signatures for Digital Postal Marks etc. Advantages of ECC over other cryptographic schemes ECC gives a high amount of security for relatively smaller key sizes than used by traditional schemes (RSA, DSA). Smaller key sizes results in faster computations and increased efficiency. As a result, ECC can be easily embedded with small mobile devices to disburden the general purpose CPU from exhaustive cryptographic calculations.

Future Works: Implementation of ECC on SSL SSL is the most widely used security protocol on the Internet today. It offers encryption, source authentication and integrity protection for data and is flexible enough to accommodate different cryptographic algorithms for key agreement, encryption and hashing. Implementation of ECC on Smart Cards Secure applications in smart cards present implementation challenges particular to the platform's memory, bandwidth, and computation constraints. ECC's unique properties make it especially well suited to smart card applications.

System Requirements: Programming Language Used Java has been selected as the programming language because it is platform independent as it can run in any operating system that supports JVM, object oriented as it helps in developing cleaner code, supports data hiding which prevents data corruption, provides polymorphism and inheritance and thus helping in code reusability. Operating System Used Red Hat Enterprise Linux has been selected as the operating system because of its interoperability with other operating systems, portability to a diverse range of computer architectures, stability, persistent high performance on networks and workstations, builtin networking support and security.

6

7