\\ BASICS FOR ELLIPTIC CURVES in GP/PARI (for UNIX/Linux/MacOS environment) After install, type in a terminal "/gp" [needs the right path name] to launch the program. It presumably prompts you with "gp > " or, if you choose to do so, with more options like the time when command was launched "(00:19) gp >" or else. \\ the "\\" marks a comment (rest of line is ignored) \\ (possibly multiple) "?" and (possibly multiple) "TAB" key (for completion) \\ are very useful ?ell[TAB][TAB] \\ gives a list of possible options to deal with elliptic curves ?ellap \\ single "?" gives [often short] description of command, for reminder ellap(e,p,{flag=0}): computes a_p for the elliptic curve e using Shanks-Mestre's method. flag is optional and can be set to 0 (default) or 1 (use Jacobi symbols) ??ellap \\ double "??" gives extended description ellap(E,p): computes the trace of Frobenius a_p for the elliptic curve E and the prime number p. This is defined by the equation #E(F_p) = p+1 - a_p, where #E(F_p) stands for the number of points of the curve E over the finite field F_p. If E/F_p has CM by a principal imaginary quadratic order we use an explicit formula (involving essentially Kronecker symbols and Cornacchia's algorithm, hence very fast: O(log p)^2). Otherwise, we use Shanks-Mestre's baby-step/giant-step method, which runs in time O(p^{1/4}) using O(p^{1/4}) storage, hence becomes unreasonable when p has about 30 digits. No checking is done that p is indeed prime. E must be an sell as output by ellinit, defined over Q, F_p or Q_p. E must be given by a Weierstrass equation minimal at p. The library syntax is GEN apell(GEN E, GEN p). \\ START using "ellinit": initialise the curve given by y^2 = x^3 + 6*x + 2 ee = ellinit([0,0,0,6,2]); \\ for Weierstrass normal form first three entries = 0 \\ ellisoncurve(ee,[1,3]) \\ this checks whether the second argument (i.e. \\ the point "[1,3]") is actually on the curve "ee" %43 = 1 \\ this means "true" , while "0" would have meant "false" elladd(ee,[1,3],[1,3]) \\ this adds the point to itself \\ (without checking that they are actually on the curve!) %44 = [1/4, -15/8] \\ the previous output can be accessed with the sign "%" (00:06) gp > 12345 %48 = 12345 (00:06) gp > % %49 = 12345 \\ so if we repeat our previous doubling of the point [1,3] gp > elladd(ee,[1,3],[1,3]) %60 = [1/4, -15/8] \\ and then ask for doubling again, it suffices to write gp > elladd(ee, %, %) \\ which is the same here as elladd(ee, [1/4, -15/8],[1/4, -15/8]); we could also ask for %60 which points to the same output here; %61 = [889/400, 41037/8000] \\ and we can repeat it indefinitely, seeing the digits grow quickly: . . . %64 = . . . \\ double check that the result is still on the curve: (00:19) gp > ellisoncurve(ee,%64) %65 = 1 \\ we can get to the same result in one go, using ellpow (we have repeated this doubling 5 times, so we constructed 32*P where P is the point [1,3]) (00:19) gp > ellpow(ee,[1,3],32) %66 = . . . \\ we can check if this is indeed the same object by using "==" (00:21) gp > %66==%64 %68 = 1 \\\ output "1" again means "true" here \\ now work over a finite field, say Z/pZ: \\ we encode the Weierstrass form y^2 = x^3 + A*x +B over Z/pZ as wei(A,B,p=5) = ellinit([0,0,0,A,B]*Mod(1,p)); \\ the third argument "p" has an extra default value "=5", which is taken \\ if we don't give any other prime \\ so for example one of the curves treated in the last tutorial is given by ee = wei(1,2); \\ note that we use ";" at the end to avoid a rather meaningless (for now) lengthy output \\ if we want to compute the number of points modulo p, we define a little routine, using # E(Z/pZ) = p+1 - a_p for some integer a_p gp > numpoints(E,p) = p+1 - ellap(E,p) \\ so we would expect for wei(1,1) that we find 9 points (cf. homework) \\ indeed: (00:39) gp > numpoints(wei(1,1),5) %79 = 9 \\ but we can also directly check that there are only eight "finite" points modulo 5: \\ [using braces allows to write over several lines without being evaluated \\ before time] {for (x = 0, 4, \\ run through all possible x modulo 5 for(y = 0, 4, \\ as well as through all possible y if (ellisoncurve(ee,[x,y]), \\ if the point is on the curve, \\ then try to detect its order print([x,y]); ) \\ end if ) \\ end for ); \\ end for } \\ the output being [0, 1] [0, 4] [2, 1] [2, 4] [3, 1] [3, 4] [4, 2] [4, 3] \\ we could even add a little routine giving us the order of each element: \\ note that the point at infinity is denoted in PARI as "[0]" ellord(ee,Q) = { for (n = 1, numpoints(ee,5), \\ the order of a point cannot exceed the group order if( ellpow(ee,Q,n)==[0], \\ if n Q = point at oo [=\infty],, order = n; \\ then keep this in mind as "order" break(); \\ and jump out of the "for-loop" ); \\ end if ); \\ end for order; \\ return this } \\ and then re-run the double loop {for (x = 0, 4, \\ run through all possible x modulo 5 for(y = 0, 4, \\ as well as through all possible y if (ellisoncurve(ee,[x,y]), \\ if the point is on the curve, \\ then try to detect its order print([x,y],", of order "ellord(ee,[x,y]) ); ) \\ end if ) \\ end for ); \\ end for } \\ even better, we can simply ask for the multiples of a generator, say Q=[0,1] \\ to make it more readable, use "lift", which gets rid of "Mod( ,5)" vector(9, j, lift(ellpow(ee,[0,1],j))) %84 = [[0, 1], [4, 2], [2, 1], [3, 4], [3, 1], [2, 4], [4, 3], [0, 4], [0]] for( j=1, 9, print(j,"Q = ",lift(ellpow(ee,[0,1],j))) \\ gives output 1Q = [0, 1] 2Q = [4, 2] 3Q = [2, 1] 4Q = [3, 4] 5Q = [3, 1] 6Q = [2, 4] 7Q = [4, 3] 8Q = [0, 4] 9Q = [0] \\\\\\\\\\\\\\\\\\\\\\\\\\\ \\ An example for ElGamal elliptic curve cryptography \\ we choose an elliptic curve with an obvious solution [0,1]: \\ use y^2 = x^3 + A *x +1 , i.e. wei(A,1, p) \\ where we choose a prime p and a suitable A (in a certain range), p = 17758176404715800329; A = 7758176404715800329; ee=wei(A,1,p); B=[0,1]; \\ is a point on the curve \\ Now choose a random integer r in [0,p-1] r=random(p-1) \\ %92 = 12899136231357399276 Px = 17471072867833378135; \\ is the message that we would like to send \\ we assume that Px is the x-coordinate of a point on the curve Py=lift(ellordinate(ee,P)[1]); \\ 
\\ and we define the point on the curve P=[Px,Py]; \\ n = 6726380296059092659; \\ is our secret code nB = lift(ellpow(ee,B,n)) \\ is public \\ %98 = [9285667079933105614, 14533360625264437890] rB = lift(ellpow(ee,B,r)) \\ prepare for message \\ %95 = [8250980149189226874, 13057738041184559199] \\ We send [rB, P + r*nB] message_encrypt = [rB, lift(elladd(ee,P, ellpow(ee, nB, r)))] \\ from this, we deduce the original message "Px" by invoking our secret code "n" and subtracting n*message[1] from message[2] get ellsub(ee, message_encrypt[2], ellpow(ee,message_encrypt[1],n)) \\ \\ and indeed, the x-coordinate agrees with the one we started with, Px lift(ellsub(ee, message_encrypt[2], ellpow(ee,message_encrypt[1],n)))[1]==Px \\ %112 = 1 \\\\\\\\\\\\\\\\\\\\\ How can one use this "ElGamal for elliptic curves" in practice? One popular use is the handling of DRM (= digital rights management). Suppose Nikita purchases digital rights online (for downloading music/apps, say), then a certain file she downloads from the site generates a private key "n" (and stores it illegibly somewhere, in bits and pieces, on the computer). If she now buys music, her computer sends her public key "(p,E,B,n*B)" and she pays the site for a "license file" message_encrypt = [r*B, P+r*n*B]. Now she is the only person to be able to retrieve "P" from this, by multiplying the first component by n [which her computer knows how to retrieve from the "bits and pieces" mentioned] and subtract the result from the second component, and hence she unlocks the key and can enjoy the music. [Note that she doesn't need to know the "r" that occurs in the process; the outcome is independent of "r", so that website can generate it on the fly.]