AFTER 8: Elliptic Curves Cryptography äňčl actorJzation__________________________________ Cryptography based on manipulation of points of so called elliptic curves is getting momentum and has a tendency to replace the public key cryptography based on unfeasibility of the factorization of integers, or of the computation of the discrete logarithms. For example, US-government has recommended to use elliptic curve cryptography. The main advantage of elliptic curves cryptography is that to achieve a certain level of security shorter keys are required than in case of "usual cryptography". Using shorter keys can result in a considerable savings in hardware implementations. The second advantage of the elliptic curves cryptography is that quite a few of attacks available for cryptography based on factorization and discrete logarithm do not work for elliptic curves cryptography. It is amazing how practical is the elliptic curve cryptography that is based on very strangely looking theoretical concepts. C Elliptic curves cryptography 3 IV054 Elliptic Curves C An elliptic curve E is the graph of equation E: y2 = x3 + ax + b (where a, b will be, for our purposes, either rational numbers or integers (mod n)) extended by a "point at infinity", denoted usually as °° (or 0) that can be regarded as sitting, at the same time, at the very top and very bottom of the y-axis. We will consider mainly only those elliptic curves that have no multiple roots what is equivalent to the condition 4a3+27b2 ŕ 0. In case the coefficients are rational numbers, a graph of an elliptic curve has one of the form shown in the following figure that depends on whether polynomial x3+ax+b has three or one real root. / / \ / / f 2- \ \ 2 4 S y2=x(x+1)(x-1) y2=x3+73 Elliptic curves cryptography 3 70 IV054 Historical Remarks Elliptic curves are not ellipses and therefore it seems strange that they have such a name. Elliptic curves actually received their names from their relation to so called elliptic integrals XL t XL j c ax c xax J~TT==T J" :i V x3 +ax + b xi^x3 +ax + b that arise in the computation of the arc-length of ellipses. It may also seem puzzling why not to consider curves given by more general equations y2 + £xy + ^ _ ^ + ^2 +ax + fr^ The reason is that if we are working with rational coefficients or mod p, where p>3 is a prime, then our general equation can be transformed to our special case. In other cases, it may be necessary to consider the most general form of equation. C Elliptic curves cryptography 3 IV054 Addition of Points on Elliptic Curves (1) Geometry On elliptic curves we can define addition of points in such a way that this addition forms an Abelian group. If the line through two different points P., and P2 of an elliptic curve E intersects E in a point Q=(x,y), then we define P1+P2=lD3=(x,-y)- (This also implies that for any point P on E it holds P+°° = P.) If the line through two different points P1 and P2 is parallel with y-axis, then we define P1+P2=o°. In case P1=P2, and the tangent to E in P1 intersects E in a point Q=(x,y), then we define P^P^(x,-y). It should now be obvious how to define subtraction of two points of an elliptic curve. It is now easy to verify that the above addition of points forms Abelian group with 00 as the identity (null) element. C Elliptic curves cryptography 3 IVO An elliptic curve over Z wwhere p is a prime is the set of points (x,y) satisfying so-called Weierstrass equation y + uxy + vy = x -Vax +bx + c for some constants u,v,a,b,c together with a single element 0, called the point of infinity. If p+2 Weierstrass equation can be simplified by transformation y —» y — (ta + v) / 2 to get the equation y2 = x3 + dx2 + ex + / for some constants oŕ,e,ŕand if pr3 by transformation x —> x - d I 3 to get equation 2 3 J> =* +A + ^ C Elliptic curves cryptography ) IV054 Addition of Points on Elliptic Curves (2) Formulas Addition of points P^x^y.,) and P2=(x2,y2) of an elliptic curve E: y2=x3+ax+b can be easily computed using the following formulas: where Pi + p2 =P3=(x3.y3) Xo — A - X^i ■ ■ Xo y3 = A(X! - x3) - y. and {y2-y\)l{x2-xx) |fpl5tp 3x}+a)/(2yi) 1 t- I 2 If p1 = p2 All that holds for the case that A is finite; otherwise P3 = °°. Example For curve y2=x3+73 and P1=(2,9), P2=(3,10) we have P1 + P2 = P3= (-4,-3) and P3 + P3 = (72,611). C Elliptic curves cryptography 3 IV054 Elliptic Curves mod n The points on an elliptic curve E: y2=x3+ax+b (mod n) are such pairs (x,y) mod n that satisfy the above equation, along with the point °° at infinity. Example Elliptic curve y2=x3+2x+3 (mod 5) has points (1,1),(1,4),(2,0),(3,1),(3,4),(4,0),oo. Example For elliptic curve E: y2=x3+x+6 (mod 11) and its point P=(2,7) holds 2P=(5,2); 3P=(8,3). Number of points on an elliptic curve (mod p) can be easily estimated. Hasse's theorem If an elliptic curve E (mod p) has N points then \N-p-1\<2j~p The addition of points on an elliptic curve mod n is done by the same formulas as given previously, except that instead of rational numbers c/d we deal with cď1 Example For the curve E: y2=x3+2x+3 it holds (1,4)+(3,1)=(2,0); (1,4)+(2,0)=(?,?). C Elliptic curves cryptography 3 IV054 Elliptic Curve Discrete Logarithm If E is an elliptic curve, A, B are its points such that B = kA = (A + A + ... +A) - k times - for some k. The task to find such a k is called the discrete logarithm problem for elliptic curves. No efficient algorithm to compute discrete logarithm problem for elliptic curves is known and also no good general attacks. Elliptic curves based cryptography is based on these facts. A general procedure for changing a discrete logarithm based cryptographic protocols to a cryptographic protocols based on elliptic curves: ■ Assign to the message (plaintext) a point on an elliptic curve. ■ Change, in the cryptographic protocol, modular multiplication to addition of points on an elliptic curve. ■ Change, in the cryptographic protocol, exponentiation to multiplication of a point on the elliptic curve by an integer. ■ To the point of an elliptic curve that results from such a protocol one assigns a message (cryptotext). C Elliptic curves cryptography 3 8 IV054 Problem and basic idea The problem of assigning messages to points on an elliptic curve is difficult because there are no polynomial-time algorithms to write down points of an arbitrary elliptic curve. Fortunately, there is a fast randomized algorithm, to assign points of any elliptic curve to messages, that can fail with probability that can be made arbitrarily small. Basic idea: Given an elliptic curve E (mod p), the problem is that not to every x there is an y such that (x,y) is a point of E. Given a message (number) m we therefore adjoin to m few bits at the end of m and adjust them until we get a number x such that x3 + ax + b is a square mod p. C Elliptic curves cryptography 3 IV054 Technicalities Let K be a large integer such that a failure rate of M2K is acceptable when trying to encode a message by a point. Fory from 0 to K verify whether for x = m K +j, x3 + ax + b (mod p) is a square (mod p) of an integer. If such any is found, encoding is done; if not the algorithm fails (with probability 1/2K because x3 + ax + b is a square approximately half of the time). In order to recover the message m from the point (x,y), we compute: x K C Elliptic curves cryptography 3 10 IV054 Elliptic Curve Key Exchange Elliptic curve version of the Diffie-Hellman key generation goes as follows: Let Alice and Bob agree on a prime p, an elliptic curve E (mod p) and a point P on E. ■ Alice chooses an integer na, computes naP and sends it to Bob. ■ Bob chooses an integer nb, computes nbP and sends it to Alice. ■ Alice computes na(nbP) and Bob computes nb(naP). This way they have the same key. c Elliptic curves cryptography 3 11 IV054 Elliptic Curve Version of EIGamal Cryptosystem Standard version of EIGamal: Bob chooses a prime p, a generator q < p, an integer a, computes y = qa (mod p), makes public p,q, y and keeps a secret. To send a message m Alice chooses a random r, computes: y1 = qr\y2 = myr and sends it to Bob who decrypts by calculating m = J^ (mod;?) Elliptic curve version of EIGamal: Bob chooses a prime p, an elliptic curve E (mod p), a point P on E, an integer a, computes Q = aP, makes E, p, and Q public and keeps a secret. To send a message m Alices expresses m as a point X on E, chooses random r, computes y1=rP;y2=X + rQ And sends the pair (y^yý to Bob who decrypts by calculating X = y2- ayP C Elliptic curves cryptography 3 12 IV054 Elliptic Curve Digital Signature Eliptic curves version of EIGamal digital signatures has the following form under the assumption that Alice wants to sign (a message) m, an integer, and to have the signature verified by Bob: Alice chooses p and an elliptic curve E (mod p), a point P on E and calculates the number of points n on E (mod p) - what can be done, and we assume that 0 < m < n. Alice then chooses a secret a and computes Q = aP. Alice makes public p, E, P, Q and keeps secret a. To sign m Alice does the following: ■ Alice chooses a random integer r, 1 < r< n such that gcd(r,r?) = 1 and computes R = rP = fry). ■ Alice computes s = r1 (m - ax) (mod n) ■ Alice sends the signed message (m,R,s) to Bob. Bob verifies the signature as follows: ■ Bob declares the signature as valid if xQ + sR = mP The verification procedure works because xQ + sR = xaP + r1(m - ax)(rP) = xaP + (m - ax)P = mP Warning Observe that actually rr1 = 1 + tn for some t. For the above verification procedure to work we then have to use the fact that nP = °° and therefore P + t °° = P C Elliptic curves cryptography 3 13 IV054 Factoring with Elliptic Curves Basis idea: To factorize an integer n choose an elliptic curve E, a point on E (mod n) and compute either iP for i=2,3,4,... or 2 P for j=1,2,.... In doing that one needs to compute gcó(k,n) for various k. If one if these values is between 1 and n we have a factor of n. Factoring of large integers: The above idea can be easily parallelised and converted to using of enormous number of computers to factor a single very large n. Each computer gets some number of elliptic curves and some points on them and multiplies these points by some integers according to the rule for addition of points. If one of computers encounters, during such a computation, a need to compute 7 < gcd(7c,n) < n,factorization is finished. Example: If curve E: y2 = x3 + 4x + 4 (mod 2773) and its point P=(1,3) are used, then 2P=(1771,705) and in order to compute 3P one has to compute gcd(1770,2773)=59 - factorization is done. Example: For elliptic curve E: y2=x3+x+1 (mod 35) and its point P=(1,1) we have 2P=(2,2); 4P=(0,22); 8P=(16,19) and at the attempt to compute 9P one needs to compute gcd(15,35)=15 and again the factorization is done. The only things that remains to be explored is how efficient is this method and when it is more efficient than other methods. C Elliptic curves cryptography 3 14 IV054 Important Observations (1) ■ If n = pq for primes p,q, then an elliptic curve E (mod n) can be seen as a pair of elliptic curves E (mod p) and E (mod q). ■ It follows from the Lagrange theorem that for any elliptic curve E (mod n) and its point P there is an k ap., then resety'^y + 1, k <- 1. If y < /, then go to step (3); otherwise go to step (5) • If Pj P =0 (mod n) and no factor of n was found at the computation of inverse elements, then go to step (5) (5) Reset r <- r- 1. If r > 0 go to step (1); otherwise terminate with "failure". The "smoothness bound" B is recommended to be chosen as B = VlnF(lnlnF)/2 and in such a case running time is s^s V2+o(llnF(lnlnF))ln2rcx C Elliptic curves cryptography 3 19 IV054 Elliptic Curves: FAQ ■ How to choose (randomly) an elliptic curve E and point P on El An easy way is first choose a point P(x,y) and an a and then compute b = y2- x3- ax to get the curve E: y2 = x3 + ax + b. ■ What happens at the factorization using elliptic curve method, if for a chosen curve (E mod n) the corresponding cubic polynomial x3+ ax + b has multiple roots (that is if 4a3 + 27b2 = 0) ? No problem, method still works. ■ What kind of elliptic curves are really used in cryptography? Elliptic curves over fields GF(2") for n > 150. Dealing with such elliptic curves requires, however, slightly different rules. C Elliptic curves cryptography 3 20 70 IV054 FACTORIZATION Factorization of integers is a very important problem. A variety of techniques has been developed to deal with this problem, So far the fastest classical factorization algorithms work in time e 0((log^)1/3(loglog^)2/3) The fastest quantum algorithm for for factorization works in quantum polynomial time. In the rest of chapter several factorization methods will be presented and discussed. c Elliptic curves cryptography 3 21 IV054 Fermat numbers factorization Factorization of so-called Fermat numbers 22A' + 1 is a good example to illustrate progress that has been made in the area of factorization. Pierre de Fermat (1601-65) expected that all numbers Fj = 22Ai + 1 i > 1 are primes. This is true for/= 1,...,4. ^ = 5, F2 = 17, F3 = 257, F4 = 65537. 1732 L. Euler found that F5 = 4294967297 = 641 ■ 6700417 1880 Landry+LeLasser found that F6 = 18446744073709551617 = 274177 ■ 67280421310721 1970 Morrison+Brillhart found factorization for F7 =(39 digits) F7 = 340282366920938463463374607431768211457 = = 5704689200685129054721 ■ 59649589127497217 1980 Brent+Pollard found factorization for F8 1990 A. K. Lenstra+... found factorization for F9 (155 digits) xn~l *l(mod«) C Elliptic curves cryptography 3 22 It follows from the Little Fermat Theorem that if p is a prime, then for all 0 Zn and x0 g Zn. Example f(x) = x2 + 1 2. Keep computing xi+1 = f(Xj), j = 0,1,2,... and gcd(Xj -xk, n), k p.) Example n = 91, f(x) = x2+1, x0 = 1, x1 = 2, x2 = 5, x3 = 26 gcd(x3 - x2, n) = gcd(26 - 5, 91) = 7 Remark: In the p-method, it is important to choose a function f in such a way that f maps Zn into Zn in a "random" way. Basic question: How good is the p-method? (How long we expect to have to wait before we get two values Xj, xk such that gcd(Xj - xk, n) * 1, if n is not a prime?) C Elliptic curves cryptography 3 27 IV054 Basic lemma C Given: n, f:Zn -» Zn and x0eZn We ask how many iterations are needed to get x] = xk mod r where r is a prime factor of n. Lemma Let S be a set, r = \S\. Given a map f:S -> S, x0e S, let xj+1 = f(Xj), j > 0. Let A> 0, / = l+|V2Ar | Then the proportion of pairs (f, x0) for which x0, xl5..., x, are distinct, where f runs over all mappings from S to S and x0 over all S, is less than e_i. Proof Number of pairs (x0, f) is rr+1. How many pairs (x0, f) are there for which x0,..., x,are distinct? r choices for x0, r-1 forxy, r-2forx2,... The values of f for each of the remaining r -1 values are arbitrary - there are rr -' possibilities for those values. Total number of ways of choosing x0 and f such that x0,..., x, are different is rr-lÍ\{r-j) 7=0 and the proportion of pairs with such a property is r"MX j=0{r- j). For/ = l+|V2/r | we have in(r^x' (r-yO)=lnfx' (l-^SL-^-^r1 Elliptic curves cryptography ) <_f<_Ä<_/l. 2r 2r 28 IV054 RHO-ALGORITHM C A simplification of the basic idea: For each k compute gcd(xk - Xj, n) for just one y < k. Choose f:Zn -> Zn, x0, compute xk = f(xk_.,), k > 0. If/cis an (h +1)-bit integer, i.e. 2h < k< 2h+1, then compute gcd(xk, x2Ah_1). = 1 = gcd(57 - 7, n) = 1 = gcd(3307 - 7, n) = 1 = gcd(2745 - 3307, n) = 1 = gcd(1343-3307, n) = 1 = gcd(2626 - 3307, n) = 1 = gcd(3734 - 3307, n) = 61 Disadvantage We likely will not detect the first case such that for some k0 there is a y0 < k0 such that gcd(xk0 - xj0, n)>'\. This is no real problem! Let k0 has h +1 bits. Sety = 2h+1 -1, k = j + k0 -j0. k has (h+2) bits, gcd(xk - Xj, n) > 1 k < 2h+2 = 4 ■ 2h < 4k0. Example n = 4087, f(x) = = x2 + x + 1, ^0 = = 2 *i = f(2) = 7, gcd^ - x0, n) x2 = f(7) = 57, gcd(x2 -*i n) x3 = f(57) = 3307, gcd(x3 -^ n) x4 = f(3307) = 2745, gcd(x4 "^3 n) x5 = f(2746)= 1343, gcd(x5 •*z n) x6 = f(1343) = 2626, gcd(x6 -*3 n) x7 = f(2626) = 3734, gcd(x7 •*z n) Elliptic curves cryptography 3 29 IV054 RHO-ALGORITHM Theorem Let n be odd + composite and 1 < r < sqrt(n,) its factor. If f, x0 are chosen randomly, then rho algorithm reveals r in o(V^iog3^)bit operations with high probability. More precisely, there is a constant C > 0 such that for any A > 0, the probability that the rho algorithm fails to find a nontrivial factor of n in c4x\fn\ogn bit operations is less than e -\ Proof Let C, be a constant such that gcd(y- z, n) can be computed in C1log3n bit operations whenever y, z< n. Let C2 be a constant such that f(x) mod n can be computed in C2log2n bit operations if x< n. If k0 is the first index for which there exists j0 < k0 with xk0 = xj0 mod r, then the rho-algorithm finds r in k < 4/c0 steps. The total number of bit operations is bounded by -> 4/c0(C1log3n + C2log2n) C By Lemma the probability that k0 is greater than l+^I2Äř is less than e -\ If k0 4sqrt(2)(C1 + C2), then we have that r will be found incV^V^log3 n bit operations - unless we made uniformed choice of (f, x0) the probability of what is at most e - \ ^^^^^^^^^^ | ) 30 Elliptic curves cryptography foMfli Pollard p-method works fine for integers n with a small factor. Next method, so called Pollard (p-l)-method, works fine for n having a prime factor p such that all prime factors of p-1 are small. When all prime factors of p-1 are smaller than a B, we say that p-1 is B-smooth. C Elliptic curves cryptography 3 31 uSj Pollard's algorithm (to factor n given a bound b). a ;= 2; fory'=2 to b do a;= aimod n; f:= gcd(a-1,n); if 1 < f < n then f is a factor of n otherwise failure Indeed, let p be a prime divisor of n and q < b for every prime q\(p-1). (Hence (p-1)\b!). At the end of the for-loop we therefore have a E 2b! (mod n) and therefore a E 2b! ( mod p) By Fermat theorem 2p-1 =. 1 (mod p) and since (p-1 )|b! we have that p|(a-1) and therefore p | gcd(a-1,n) C Elliptic curves cryptography 3 32 IV054 Important Observations (2) Pollard p-method works fine for numbers with a small factor. The p-1 method requires that p-1 is smooth. The elliptic curve method requires only that there are enough smooth integers near p and so at least one of randomly chosen integers near p is smooth. This means that the elliptic curves factorization method succeeds much more often than p-1 method. Fermat factorization and Quadratic Sieve method discussed later works fine if integer has two factors of almost the same size. c Elliptic curves cryptography 3 33 IV054 If n = pq, p<4n, then f n — q + p \ V f \ J q-p V 2 j — a -b Therefore, in order to find a factor of n, we need only to investigate the values x = a2 - n for a = p^"|+ 1, p^"|+ 2, . . . , (n - 1)/2 until a perfect square is found. c Elliptic curves cryptography 3 34 IV054 FERMA T FACTORIZA TION Basic idea: Factorization is easy if one finds x, y such that n | (x2 - y2) Proof: If n divides (x + y)(x - y) and n does not divide neither x+y nor x-y, then one factor of n has to divide x+y and another one x-y. Example n = 7429 = 2272-2102, x-y= 17 gcd(17, 7429) =17 x=227, y =210 x + y = 437 gcd(437, 7429) = 437. How to find such x and y? /- 2 2 First idea: one tries all t starting with^n until t — n is a square S . Second idea: One forms a system of (modular) linear equations and determines x and y from the solutions of such a system. number of digits of n 50 60 70 80 90 100 110 120 number of equations 3000 4000 7400 15000 30000 51000 120000 245000 C Elliptic curves cryptography ) 35 IV054 Method of Quadratic Sieve to factorize n C Step 1 One finds numbers x such that x2- n is small and has small factors. Example 832-7429 =-540 = (-1)-22 33 5 1 872 - 7429 = 140= 22 5 ■ 7 > relations 882- 7429 = 315 = 32 5 ■ 7 Step 2 One multiplies some of the relations if their product is a square. For example (872 - 7429)(882 - 7429) = 22 32 52 • 72 = 2102 Now (87 ■ 88)2 = (872 - 7429)(882 - 7429) mod 7429 2272 = 2102mod7429 Hence 7429 divides 2272-2102. Formation of equations: For the /-th relation one takes a variable \ and forms the expression ((-1) ■ 22 ■ 33 ■ 5V11 ■ (22 ■ 5 ■ 7Y*2 ■ (32 ■ 5 ■ D^3 = (-1 )^1 ■ 22/l1 + 2X1 ■ 32/l1 + 2X1 ■ 5^1 + ^ + ^ ■ 7^ +/l3 If this is to form a quadrat the following equations have to hold Elliptic curves cryptography 3 X\ =0mod2 ;tl + ;L2 + ;t3 = 0mod2 /12 + /I3 = 0mod2 A1 = 0,A2 = A3 = 1 36 D8D IV054 Method of quadratic sieve to factorize n C Problem How to find relations? Using the algorithm called Quadratic sieve method. Step 1 One chooses a set of primes that can be factors - a so-called factor basis. One chooses an m such that at?2 - n is small and considers numbers (m + u)2 - n for -k< u