Elliptical Curve Cryptography

Elliptical Curve Cryptography Manish Kumar Roll No - 43 CS-A, S-7 SOE, CUSAT

Outline Introduction Cryptography Mathematical Background Elliptic Curves Elliptic Curves Arithmetic Elliptical Curve Cryptography(ECC) Applications Conclusion References

Introduction Cryptography – Cryptography is science of using mathematics to encrypt and decrypt data.

– Cryptography provide us mechanism to send, sensitive data through insecure network (like internet).

Introduction Secret key cryptography – The encryption key and decryption key are the same.

– Key Distribution Problem.

Introduction Public key cryptography –Different key for encryption and decryption • Public-key and private-key – Key distribution problem is solved.

Introduction A comparison of public –key Cryptosystems

Introduction Elliptical Curve Cryptography – ECC was introduced by Victor Miller and Neal Koblitz in 1985. – It’s new approach to Public key cryptography. – ECC requires significantly smaller key size with same level of security. – Benefits of having smaller key sizes : faster computations, need less storage space. – ECC ideal for : Pagers ; PDAs ; Cellular Phones ; Smart Cards.

Mathematical Background A group is an algebric system consisting of a set G together with a binary operation * defined on G satisfying the following axioms : – Closure : for all x, y in G we have x * y ∈ G – Associativity : for all x, y and z in G we have (x * y) * z = x * (y * z) – Identity element : There is an element e in G such that a · e = e · a = a for all a in G. – Inverse element : For each a in G there is an element a' in G such that a · a' = a' · a = e.

Mathematical Background In addition if for x, y in G we have x * y = y * x then we say that group G is abelian. A finite field is an algebraic system consisting of a set F together with a binary operations + and * defined on F satisfying the following axioms : – F is an abelian group with respect to +. – F \ {0} is an abelian group with respect to *.

Mathematical Background – For all x, y and z in F we have x * ( y + z) = (x * y) + (x * z) (x + y) * z = (x * z) + (y * z)

The order of the finite field is the number of elements in the field.

Elliptic Curves Elliptic curves are not ellipses (the name comes from elliptic integrals) Standard Form Equation y2 = x3 + a.x + b where x, y, a and b are real numbers. Each choice of the numbers a and b yields a different elliptic curve.

Elliptic Curves If 4·a3 + 27·b2 is not 0 (i.e. x3 + a · x + b contains no repeated factors), then the elliptic curve can be used to form a group An elliptic curve group consists of the points on the curve and a special point O, meeting point of curve with a straight line at infinity.

Elliptic curve Arithmetic – Point Addition Draw a line that intersects distinct points P and Q 

The line will intersect a third point -R

Draw a vertical line through point -R 

The line will intersect a fourth point R

Point R is defined as the summation of points P and Q 

R=P+Q

Elliptic curve Arithmetic Draw a line that intersects points P and -P 

The line will not intersect a third point

For this reason, elliptic curves include O, a point at infinity  

P + (-P) = O O is the additive identity

Elliptic curve Arithmetic – Point Doubling Draw a line tangent to point P 

The line will intersect a second point -R

Draw a vertical line through point -R 

The line will intersect a third point R

Point R is defined as the summation of point P with itself 

R = 2·P

Elliptical Curve Cryptography Point Multiplication – The main cryptographic operation in ECC is point multiplication. – Point multiplication is performed through a combination of point additions and point doublings, e.g.11P = 2((2(2P)) + P) + P. – Point multiplication is simply calculating Q=k . P, where k is an integer and P is a point on the curve called as base point.

Elliptical Curve Cryptography Point Multiplication – Each curve has a specially designated point P called the base point chosen such that a large fraction of the elliptic curve points are multiples of it. – To generate a key pair, one selects a random integer k which serves as the private key, and computes k P which serves as the corresponding public key.

Elliptical Curve Cryptography The Elliptic curve discrete logarithm problem – The discrete logarithm problem for ECC is the inverse of point multiplication.

– Given points P and Q, find a number k such that k·P =Q – where P and Q are points on the elliptic curve – Q is the public key – k is the private key (very large prime number)

Elliptic Curve Discrete Logarithm – We can find the value of k by adding P, k-times. – This is called Brute-force Method (not work when k is large) – Pollard’s rho is best method to solve DLP. – Running time of Pollard’s rho is exponential.

Elliptical Curve Cryptography What makes ECC hard to crack? – The security of ECC relies on the difficulty of solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) i.e. finding k, given P and Q = k P. The problem is computationally intractable for large values of k.

Performance Comparison ADVANTAGES OF ECC OVER RSA – Smaller key size for equivalent security. – Faster and Less computations. – Less memory.

Applications Significant performance benefits from using ECC in secure web transaction. Elliptic Curve Digital Signature Algorithm(ECDSA) ECC can be used in constrained Environments: Pagers ; PDAs ; Cellular Phones ; Smart Cards where traditional public-key mechanisms are simply impractical.

Conclusion ECC uses groups and a logarithm problem. ECC is a stronger option than the RSA and discrete logarithm systems for the future. Due to small key size, implementation is easy. ECC is excellent choice for portable, communication devices. ECC’s main advantage: as key length increases, so does the difficulty of the inversion process.

References Cryptography and Network Security Principles and Practices, Fourth Edition,PHI, By William Stallings. Guide to Elliptic Curve Cryptography By Darrel Hankerson, Alfred Menezes, Scott Vanstone. Elliptic Curve Cryptography – How it Works Sheueling Chang, Hans Eberle, Vipul Gupta, Nils Gura, Sun Microsystems Laboratories. The Elliptic Curve Cryptosystem For Smart Cards, A Certicom White Paper, Published: May 1998 . Elliptic Curve Cryptography An Implementation Guide By Anoop MS [email protected] .