An Introduction to the Theory of Elliptic Curves

1 An Introduction to theTheory of Elliptic CurvesJoseph H. SilvermanBrown University andNTRU Cryptosystems, School onComputational Number Theory andApplications to CryptographyUniversity of WyomingJune 19 July 7, 20060An Introduction to the Theory of Elliptic CurvesOutline Introduction Elliptic Curves The Geometry of Elliptic Curves The Algebra of Elliptic Curves What DoesE(K) Look Like? Elliptic Curves Over Finite Fields The Elliptic Curve Discrete Logarithm Problem reduction Modulop, Lifting, and Height Functions Canonical Heights on Elliptic Curves Factorization Using Elliptic Curves L-Series, birch Swinnerton-Dyer, and $1,000,000 Additional Material Further ReadingAn Introduction to the Theory of Elliptic Curves 1 An Introduction to the Theory of Elliptic CurvesThe Discrete Logarithm ProblemFix a groupGand an elementg G. TheDiscreteLogarithm Problem(DLP) forGis:Given an elementhin the subgroupgenerated byg, find an integermsatisfyingh= smallest integermsatisfyingh=gmis called thelogarithm(orindex) ofhwith respect tog, and isdenotedm= logg(h) orm= indg(h).

2 The Discrete Logarithm Problem is used as the underly-ing hard problem in many cryptographic constructions,including key exchange, encryption, digital signatures,and hash Introduction to the Theory of Elliptic Curves 2 An Introduction to the Theory of Elliptic CurvesDiffie-Hellman Key ExchangePublic Knowledge: GroupGand elementgof secret 0< b < nChoose secret 0< a < nComputeB=gbComputeA=gaSendB to Aliceto Bob SendAComputeAbComputeBaBob and Alice have the shared valueAb=gab=gba=BaAnd one hopes that computinggabfromgaandgbre-quires solving the discrete logarithm Introduction to the Theory of Elliptic Curves 3 An Introduction to the Theory of Elliptic CurvesHow Hard is the Discrete Log Problem?For some groups, DLP is very easy: Z/mZunder addition (Euclidean algorithm) R orC under multiplication (analytic logarithm)For some groups, DLP is difficult. The classical exampleis:F punder multiplicationThe best known algorithm to solve DLP inF ptakestimeO(ec3 (logp)(log logp)2)This is calledsubexponential, since it is faster thanexponential (in logp), but slower than cryptographic purposes, it would be better to usea groupGfor which solving DLP takes time that isexponential in the order Introduction to the Theory of Elliptic Curves 4 EllipticCurvesElliptic CurvesWhat is an Elliptic Curve?

3 An Elliptic curve is a curve that s also naturally agroup. The group law is constructed geometrically. Elliptic Curves have (almost) nothing to do withellipses, so put ellipses and conic sections out ofyour thoughts. Elliptic Curves appear in many diverse areas of math-ematics, ranging from number Theory to complexanalysis, and from cryptography to Introduction to the Theory of Elliptic Curves 5 Elliptic CurvesPoints on Elliptic Curves Elliptic Curves can have points with coordinates inany field, such asFp,Q,R, orC. Elliptic Curves with points inFpare finite groups. Elliptic Curve Discrete Logarithm Prob-lem(ECDLP) is the discrete logarithm problemfor the group of points on an Elliptic curve over afinite field. The best known algorithm to solve the ECDLP isexponential, which is why Elliptic curve groups areused for cryptography. More precisely, the best known way to solve ECDLPfor an Elliptic curve overFptakes timeO( p). The goal of these talks is to tell you somethingabout the Theory of Elliptic Curves , with an em-phasis on those aspects that are of interest in Introduction to the Theory of Elliptic Curves 6 Elliptic CurvesThe Equation of an Elliptic CurveAnElliptic Curveis a curve given by an equation ofthe formy2=x3+Ax+BThere is also a requirement that thediscriminant = 4A3+ 27B2is , the polynomialx3+Ax+Bhas distinctroots.

4 This ensures that the curve is reasons to be explained later, we also toss in anextra point,O, that is at infinity, soEis the setE={(x, y) :y2=x3+Ax+B} {O}.Amazing Fact: We can usegeometryto make thepoints of an Elliptic curve into a group. The next fewslides illustrate how this is Introduction to the Theory of Elliptic Curves 7 The Geometry ofElliptic CurvesThe Geometry of Elliptic CurvesThe Elliptic CurveE:y2=x3 5x+ 8 EAn Introduction to the Theory of Elliptic Curves 8 The Geometry of Elliptic CurvesAdding Points on an Elliptic CurvevPvQEStart with two Introduction to the Theory of Elliptic Curves 9 The Geometry of Elliptic CurvesAdding Points on an Elliptic Curve vPvQLEDraw the Introduction to the Theory of Elliptic Curves 10 The Geometry of Elliptic CurvesAdding Points on an Elliptic Curve vPvQvRLEThe lineLintersects the cubic curveEin a thirdpoint. Call that third Introduction to the Theory of Elliptic Curves 11 The Geometry of Elliptic CurvesAdding Points on an Elliptic Curve vPvQvRvLEDraw the vertical line hitsEin another Introduction to the Theory of Elliptic Curves 12 The Geometry of Elliptic CurvesAdding Points on an Elliptic Curve vPvQvRvP QLEWe define thesum ofPandQonEto be thereflected point.

5 We denote it byP Qor justP+ Introduction to the Theory of Elliptic Curves 13 The Geometry of Elliptic CurvesAdding a Point To Itself on an Elliptic CurvevPEHow do we add a pointPto itself, since there aremany different lines that go throughP?An Introduction to the Theory of Elliptic Curves 14 The Geometry of Elliptic CurvesAdding a Point To Itself on an Elliptic Curve vPHHHHYLis tangent toEatPLEIf we think of addingPtoQand letQapproachP,then the lineLbecomes the tangent line Introduction to the Theory of Elliptic Curves 15 The Geometry of Elliptic CurvesAdding a Point To Itself on an Elliptic Curve vPvRv2 PHHHHYLis tangent toEatPLEThen we take the third intersection pointR, reflectacross thex-axis, and call the resulting pointP Por Introduction to the Theory of Elliptic Curves 16 The Geometry of Elliptic CurvesVertical Lines and the Extra Point At Infinity EPQ= PvvLetP E. We denote the reflected point by Introduction to the Theory of Elliptic Curves 17 The Geometry of Elliptic CurvesVertical Lines and the Extra Point At Infinity E6 LPQ= PvvVertical lines haveno third intersectionpoint withEBig Problem: The vertical lineLthroughPand Pdoes not intersectEin a third point!

6 And we need a third point to defineP ( P).An Introduction to the Theory of Elliptic Curves 18 The Geometry of Elliptic CurvesVertical Lines and the Extra Point At Infinity E6 LOPQ= PvvCreate an extrapointOonElying at infinity Solution: Since there is no point in the plane thatworks, we create an extra pointO at infinity. Rule:Ois a point on every Introduction to the Theory of Elliptic Curves 19 The Algebra ofElliptic CurvesThe Algebra of Elliptic CurvesProperties of Addition onETheoremThe addition law onEhas the followingproperties:(a)P+O=O+P=Pfor allP E.(b)P+ ( P) =Ofor allP E.(c)P+ (Q+R) = (P+Q) +Rfor allP, Q, R E.(d)P+Q=Q+Pfor allP, Q other words, the addition law + makes the pointsofEinto a commutative of the group properties are trivial to checkexceptfor the associative law (c). The associative law can beverified by a lengthy computation using explicit formu-las, or by using more advanced algebraic or Introduction to the Theory of Elliptic Curves 20 The Algebra of Elliptic CurvesA Numerical ExampleE:y2=x3 5x+ 8 The pointP= (1,2) is on the the tangent line construction, we find that2P=P+P=( 74, 278).

7 LetQ=( 74, 278). Using the secant line construc-tion, we find that3P=P+Q=(553121, 119501331).Similarly,4P=(4531311664, 86551031259712).As you can see, the coordinates are getting very Introduction to the Theory of Elliptic Curves 21 The Algebra of Elliptic CurvesFormulas for Addition onESuppose that we want to add the pointsP1= (x1, y1) andP2= (x2, y2)on the Elliptic curveE:y2=x3+Ax+ the line connectingPtoQbeL:y= x+ Explicitly, the slope andy-intercept ofLare given by = y2 y1x2 x1ifP16=P23x21+A2y1ifP1=P2and =y1 Introduction to the Theory of Elliptic Curves 22 The Algebra of Elliptic CurvesFormulas for Addition onE(continued)We find the intersection ofE:y2=x3+Ax+BandL:y= x+ by solving( x+ )2=x3+Ax+ already know thatx1andx2are solutions, so we canfind the third solutionx3by comparing the two sides ofx3+Ax+B ( x+ )2= (x x1)(x x2)(x x3)=x3 (x1+x2+x3)x2+ (x1x2+x1x3+x2x3)x the coefficients ofx2, for example, gives 2= x1 x2 x3,and hencex3= 2 x1 we computey3usingy3= x3+ , and finallyP1+P2= (x3, y3).

8 An Introduction to the Theory of Elliptic Curves 23 The Algebra of Elliptic CurvesFormulas for Addition onE(Summary)Addition algorithm forP1= (x1, y1) andP2= (x2, y2)on the Elliptic curveE:y2=x3+Ax+B IfP16=P2andx1=x2, thenP1+P2=O. IfP1=P2andy1= 0, thenP1+P2= 2P1=O. IfP16=P2(andx16=x2),let =y2 y1x2 x1and =y1x2 y2x1x2 x1. IfP1=P2(andy16= 0),let =3x21+A2y1and = x3+Ax+ Introduction to the Theory of Elliptic Curves 24 The Algebra of Elliptic CurvesFormulas for Addition onE(Summary)Addition algorithm forP1= (x1, y1) andP2= (x2, y2)on the Elliptic curveE:y2=x3+Ax+B IfP16=P2andx1=x2, thenP1+P2=O. IfP1=P2andy1= 0, thenP1+P2= 2P1=O. IfP16=P2(andx16=x2),let =y2 y1x2 x1and =y1x2 y2x1x2 x1. IfP1=P2(andy16= 0),let =3x21+A2y1and = x3+Ax+ +P2= ( 2 x1 x2, 3+ (x1+x2) ).An Introduction to the Theory of Elliptic Curves 25 The Algebra of Elliptic CurvesAn Observation About the Addition FormulasThe addition formulas look complicated, but for exam-ple, ifP1= (x1, y1) andP2= (x2, y2) are distinctpoints, thenx(P1+P2) =(y2 y1x2 x1)2 x1 x2,and ifP= (x, y) is any point, thenx(2P) =x4 2Ax2 8Bx+A24(x3+Ax+B).

9 Important Observation: IfAandBare in a fieldKand ifP1andP2havecoordinates inK, thenP1+P2and 2P1also have coordinates Introduction to the Theory of Elliptic Curves 26 The Algebra of Elliptic CurvesThe Group of Points onEwith Coordinates in a FieldKThe elementary observation on the previous slide leadsto the important result that points with coordinates in aparticular field form a subgroup of the full set of (Poincar e, 1900) LetKbe a field andsuppose that an Elliptic curveEis given by an equationof the formE:y2=x3+Ax+BwithA, B (K) denote the set of points ofEwith coordi-nates inK,E(K) ={(x, y) E:x, y K} {O}.ThenE(K) is asubgroupof the group of all Introduction to the Theory of Elliptic Curves 27 The Algebra of Elliptic CurvesA Finite Field ExampleThe formulas giving the group law onEare valid if thepoints have coordinates in any field, even if the geomet-ric pictures don t make sense. For example, we can takepoints with coordinates The curveE:y2=x3 5x+ 8 (mod 37)contains the pointsP= (6,3) E(F37) andQ= (9,10) E(F37).

10 Using the addition formulas, we can compute inE(F37):2P=(35,11), 3P=(34,25),4P=(8,6), 5P=(16,19),..P+Q=(11,10),..3P+4Q=(31,28) ,..An Introduction to the Theory of Elliptic Curves 28 The Algebra of Elliptic CurvesA Finite Field Example (continued)Substituting in each possible valuex= 0,1,2, .. ,36and checking ifx3 5x+ 8 is a square modulo 37, wefind thatE(F37) consists of the following 45 points mod-ulo 37:(1, 2),(5, 21),(6, 3),(8, 6),(9, 27),(10, 25),(11, 27),(12, 23),(16, 19),(17, 27),(19, 1),(20, 8),(21, 5),(22, 1),(26, 8),(28, 8),(30, 25),(31, 9),(33, 1),(34, 25),(35, 26),(36, 7), are nine points of order dividing three, so as anabstract group,E(F37) =C3 over a finite field, the group ofpointsE(Fp) is always either a cyclic group or the prod-uct of two cyclic Introduction to the Theory of Elliptic Curves 29 The Algebra of Elliptic CurvesComputing Large Multiples of a PointTo use the finite groupE(Fp) for Diffie-Hellman, say,we needpto be quite large (p >2160) and we need tocompute multiplesmP=P+P+ +P mtimes E(Fp)for very large values can computemPinO(logm) steps by the usualDouble-and-Add Method.