tailieunhanh - Chapter 10: Elliptic Curve Cryptography

This document includes: Introduction to Elliptic Curves, Elliptic Curve Cryptosystems (ECC), Implementation of ECC in Binary Fields. | Outline of the Talk. Elliptic Curve Cryptography Introduction to Elliptic Curves Elliptic Curve Cryptosystems ECC Implementation of ECC in Binary Fields 2 Lets start with a puzzle. Graphical Representation What is the number of balls that may be piled as a square pyramid and also rearranged into a square array Soln Let x be the height of the pyramid. Thus 12 22 32 . x x x 1 2x 6 We also want this to be a square Hence 2 _ x x 1 2x 1 y 6 Method of Diophantus Uses a set of known points to produce new points 0 0 and 1 1 are two trivial solutions Equation of line through these points is y x. Intersecting with the curve and rearranging terms .3 3 .l n x - x x 0 2 2 We know that 1 0 x 3 2 x and y Using symmetry of the curve we also have 1 2 -1 2 as another solution 5 Diophantus Method Consider the line through 1 2 -1 2 and 1 1 y 3x-2 Intersecting with the curve we have x3 -51 x2 . 0 2 Thus 1 x 51 2 or x 24 and y 70 Thus if we have 4900 balls we may arrange them in either way 6 1 Elliptic curves in Cryptography Elliptic Curve EC systems as applied to cryptography were first proposed in 1985 independently by Neal Koblitz and Victor Miller. The discrete logarithm problem on elliptic curve groups is believed to be more difficult than the corresponding problem in the multiplicative group of nonzero elements of the underlying finite field. 7 Discrete Logarithms in Finite Fields Alice gx mod p gy mod p Bob Compute k gy x gxy mod p Compute k gx y gxy mod p Eve has to compute gxy from gx and gy without knowing x and y. She faces the Discrete Logarithm Problem in finite fields Elliptic Curve on a finite set of Integers Consider y2 x3 2x 3 mod 5 x 0 y2 3 no solution mod 5 x 1 y2 6 1 y 1 4 mod 5 x 2 y2 15 0 y 0 mod 5 x 3 y2 36 1 y 1 4 mod 5 x 4 y2 75 0 y 0 mod 5 Then points on the elliptic curve are 1 1 1 4 2. 3 1 3 4 4 0 and the point at infinity Using the finite fields we can form an Elliptic Curve Group where we also have a DLP problem which is harder to solve. 9 Definition of .