Elliptic Curves, Factorization, And Cryptography

Elliptic Curves, Factorization, andCryptographyBrian RheeMIT PRIMESMay 19, 2017Brian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

R ATIONAL P OINTS ON C ONICSThe following procedure yields the set of rational points on aconic C given an initial rational point: Take the initial point O,and from that point project the conic C onto a rational line L.Then, all points mapped to a rational point were originallyrational points, and vice versa.Figure: Projecting a conic onto a lineBrian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

R ATIONAL P OINTS ON C ONICSIf O and P are both rational points, then Q is also a rationalpoint, since two rational lines always intersect at a rationalpoint. If O and Q are rational points, then O and P are the rootsof the intersection of a conic and a line:ax2 bxy cy2 dx ey f 0Simplifies to a quadratic by substituting y mx g, which isour line L. Since the coefficients of the conic and the line arerational, the coefficients of the quadratic are also rational. Thisimplies the sum of the roots are rational, but one root (O) isalready rational, so P must be as well. This shows the bijectionbetween rational points on C and rational points on L.Brian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

E LLIPTIC C URVESOur reading group mainly focused on the study of polynomialsof degree 3 and genus 1. One such example is Bachet’sequation. By fixing an integer c Z, we look for rationalsolutions to the Diophantine equationy2 x3 cThe solutions to these equations using real numbers are calledcubic curves or elliptic curves, each of which is of the formy2 ax3 bx2 cx dbut can be simplified into the Weierstrass form by substitutingb:x x 3ay2 ax3 bx cBrian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

P ROJECTIVE P LANEWe can transform these elliptic curves into the projective planeby substituting y YZ and x ZX . Now, the curves becomeY2 · Z a · X3 b · X · Z2 c · Z3Now, each point is expressed as [X, Y, Z]. If Z 0, then thepoint at infinity must be on the line y YX · x. Otherwise, thepoint is ( ZX , YZ ). This also means that the point [X, Y, Z] is thesame as the point [kX, kY, kZ]Plugging in Z 0 yields x 0, so [0, 1, 0] is the only point atinfinity on each elliptic curve, denoted as O.Brian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

B EZOUT ’ S L AWBezout’s law for general curves states that for a curve of degreem and a curve of degree n, including overlapping points suchas tangency, they intersect at exactly mn points in the projectiveplane.Figure: The two cubics intersect at nine pointsBrian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

A DDITION OF POINTS ON ELLIPTIC CURVESTo define the addition of points on elliptic curves, we need tofirst define the operation.Figure: The operationBrian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

A DDITION OF POINTS ON ELLIPTIC CURVES , CONT.To add P and Q, take the third intersection point P Q, join it toO by a line, and then take the third intersection point to beP Q. In other words, set P Q O (P Q).Figure: Addition of P and QBrian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

G ROUPSA group is a set of elements with an operation that satisfiesthe condition of closure, associativity, identity and inverse.An abelian group is a group that satisfies thecommutativity property.Brian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

I DENTITY E LEMENTFigure: O acts as an Identity ElementBecause O acts as the Identity Element, with the operationbeing , which is obviously commutative, we see that thepoints on the elliptic curve becomes a group, an abelian one atthat.Brian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

M ORDELL’ S T HEOREMFor a non-singular cubic curve C given by the equationy2 x3 ax bfor any a, b Z, we know that the group of rational points oncurve C is an abelian group.Mordell’s Theorem states thatTheoremThe group of rational points of an elliptic curve has a finite number ofgenerators.Brian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

H ASSE -W EIL T HEOREMTheoremIf C is a non-singular irreducible curve of genus g defined over afinite field Fp , then the number of points on C with coordinates in Fp is equal to p 1 e, where the “error term” e satisfies e 2g p.For an elliptic curve C over a finite field Fp , the Hasse-Weiltheorem gives the estimate that the number of points of ellipticcurve C is 2 p #C(Fp ) p 1 2 pBrian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

A PPLICATIONSElliptic curves over finite fields are easy to implement on anycomputer, since the group law is a simple algebraic equation inthe coefficients. We can use the group structure to create anumber of algorithms.Factorization of Large NumbersPublic Key CryptographyBrian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

P OLLARD ’ S M ETHODHowever, we see that Pollard’s method quickly growsinefficient, as d should be a product of small primes to make thecalculations take up a smaller number of steps.Brian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

L ENSTRA’ S FACTORIZATION M ETHODAlthough Pollard’s factorization method yields around log Nsteps, Lenstra’s elliptic curve factorization method allows us tokeep factorizing.Brian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

A N E XAMPLE OF L ENSTRA’ SWe can attempt to factor n 1715761513.12Let x1 2, y1 3, so P (2, 3). WLOG, for a given b letc 1 2b. First, let b 1 and c 1.As we cycle through steps 6 - 10, observe that for some dPd dPd 1 .d!P1Thus, let dmax 20 and calculate up to 20!P in modulo n.For example,P20 20!P 20!(2, 3) (693588502, 858100579)3However, the whole point of Lenstra’s algorithm is that theaddition law has to break down when we obtain agcd(v, n) less than n for some v(mod n) so that thealgorithm terminates.We can either keep going or pick different b and c’s for thesame dmax 20.Brian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

A N E XAMPLE OF L ENSTRA’ S (C ONT.)For b 5 and c 11, we hit the jackpot. Everything goessmoothly up untilQ 16!P (962228801, 946564039)(mod 1715761513)on the curve y2 x3 5x 9. To compute 17!P 17Q, wemust add 16Q Q. We first calculate that16Q (505708443, 718251590).Next, we must find the inverse modulo n of the difference ofx-coordinates of Q and 16Q, so we need to invertx(16Q) x(Q) 505708443 962228801 456520358Brian Rhee MIT PRIMES(mod n)Elliptic Curves, Factorization, and Cryptography

A N E XAMPLE OF L ENSTRA’ S (C ONT.)But when we use the Euclidean algorithm to compute the gcdof this quantity and n, we find thatgcd(x(16Q) x(Q), n) gcd( 456520358, 1715761513) 26927This gives a non-trivial factor of n and also the complete primefactorization of n, so we are done.n 1715761513 26927 · 63719Brian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

C RYPTOGRAPHYDiscrete Logarithm ProblemFind an integer m that solves the congruencean b(mod p)Elliptic Curve Discrete Logarithm ProblemGiven P, Q C(Fp ), find an integer m such that mP Q.Brian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

E LLIPTIC C URVE D ISCRETE L OGARITHM P ROBLEMConsider the elliptic curveC : y2 x3 x2 x 1over the field F97Points P (7,20) and Q (17,46) are in C(F97 ). We can use the"collision algorithm" to quickly solve for m.Make two lists of P, 2P, 3P, ., and Q 10P, Q 20P, Q 30P, .until finding a common point aP Q 10P, so m a 10b.We pick 10 because its close to 97.Comparing the lists, one can quickly find the collision7P (8, 87) Q 40P, so 47P Q.Brian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

B ENEFITS OF E LLIPTIC C URVE C RYPTOGRAPHYThe ECDLP is much more preferred over the DLPMuch harder to decryptTakes up much less bitsMuch more efficient overallBrian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

A CKNOWLEDGEMENTSWe would like to thank:Yongyi ChenOur ParentsDr. Khovanova and Dr. GerovitchMIT PRIMESBrian Rhee MIT PRIMESElliptic Curves, Factorization, and Cryptography

This gives a non-trivial factor of n and also the complete prime factorization of n, so we are done. n 1715761513 26927 63719 Brian Rhee MIT PRIMES Elliptic Curves, Factorization, and Cryptography. CRYPTOGRAPHY Discrete Logarithm Problem Find an integer m that solves the congruence