Elliptic Curve Cryptography

18.704 Fall 2004 Elliptic Curve Cryptography Contents 1 Abstract 2 2 Basics of Cryptography 2 3 Discrete Logarithm Problem for Elliptic Curves 3.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . 3.2 Attacks on the Elliptic Curve Discrete Logarithm Problem . 3.2.1 Baby Step, Giant Step Method . . . . . . . . . . . . 3.2.2 The MOV Attack . . . . . . . . . . . . . . . . . . . . 4 Cryptographic Methods Using Elliptic 4.1 Choosing a Curve . . . . . . . . . . . . 4.2 Setup for Encryption Algorithms . . . 4.3 Diffie­Hellman Key Exchange . . . . . 4.4 Massey­Omura Encryption . . . . . . . 5 Conclusion Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 3 3 5 . . . . 8 8 9 9 10 11 1 1 Abstract The aim of this paper is to give a basic introduction to Elliptic Curve Cryp­ tography (ECC). We will begin by describing some basic goals and ideas of cryptography and explaining the cryptographic usefulness of elliptic curves. We will then discuss the discrete logarithm problem for elliptic curves. We will describe in detail the Baby Step, Giant Step method and the MOV at­ tack. The latter will require us to introduce the Weil pairing. We will then proceed to talk about cryptographic methods on elliptic curves. We begin by describing the kinds of curves for which the discrete log problem is not known to be easy. We will then introduce the basic cryptographic problem of sending and encrypted message, and describe two encryption methods: the Diffie­Hellman Key Exchange, and the Massey­Omura Encryption. We will conclude our paper by summing up the results and mentioning briefly some developments which we did not have room to address fully in this paper. 1 2 Basics of Cryptography Cryptography aims to analyze which problems can be made easy while mak­ ing others hard.[Lu] In practical terms, if I want to send my friend a message nobody else will be able to read, I want it to be easy for me to encode, easy for my friend to decrypt, and hard for an adversary to decrypt. One prob­ lem that is thought to be hard, on which many cryptographic systems are based, is the discrete log problem. No fast methods for solving this problem in general exist, though it is possible that they will someday be found. The discrete log problem is more difficult for elliptic curves than for finite fields, which means that the same size encryption key will yield greater security if we use ECC. Put another way, we can use a smaller key to get the same amount of security, which speeds up the computations we want to speed up (i.e. mine and my friend’s). This paper will often talk about problems being practical, easy, and tractable, or, conversely, impractical, hard, and intractable. A problem is considered tractable if the computation time is polynomial in the length of the input. For example, say we are working with a group of size N . We can then write down any member of N using log(N ) digits. For the problem to be considered tractable, we will then need an algorithm that runs in time that is polynomial in log(N ). An algorithm that runs in time N , for 1 When no source is cited for a specific item of information, that information generally comes from [Wa]. 2 instance, will be much too slow. If we use 1024 bits to write down N , a perfectly reasonable number, N can equal 21023 , which is huge. 3 Discrete Logarithm Problem for Elliptic Curves 3.1 Problem Statement The classical discrete logarithm problem is the following: Given that there is some integer k such that ak ≡ b (mod p), where p is prime, find k. Since the order of a must divide p − 1, k can be defined (mod p − 1). Similarly, we can define the discrete log problem for elliptic curves. Switching to additive notation, we have the problem of finding k (given that k exists) such that kP = Q, where P, Q are points on the curve E(Fq ), with q = pn for some prime p. Our notation is the following: E(Fq ) is the set of points on E whose coordinates lie in Fq . Fq denotes Fpn . We will write E(Fq ) with coefficients in Fq . kP is defined as P � +P + ��. . . + P�, with standard addition of points k on elliptic curves. 3.2 Attacks on the Elliptic Curve Discrete Logarithm Prob­ lem In cryptography, an attack is a method of solving a problem. Specifically, the aim of an attack is to find a fast method of solving a problem on which an encryption algorithm depends. The known methods of attack on the elliptic curve (EC) discrete log problem that work for all curves are slow, making encryption based on this problem practical. However, several effi­ cient methods for solving the EC discrete log problem for specific types of elliptic curves are known. This means that one should make sure that the curve one chooses for one’s encoding does not fall into one of the several classes of curves on which the problem is tractable. Below, we describe the Baby Step, Giant Step Method, which works for all curves, but is slow. We then describe the MOV attack, which is fast for certain types of curves. 3.2.1 Baby Step, Giant Step Method This is one of the fastest general methods of solving the EC discrete log problem. (In fact, it can be applied to an arbitrary group.) The algorithm 3 √ √ runs in approximately N time and N space, where N = #E(Fq ). This is not fast enough to be practical. Problem: Find k such that kP = Q on E(Fq ), with #E(Fq ) = N , assuming that such a k exists. Algorithm: 1. Pick an integer m > √ N. 2. Compute mP . 3. For i = 0 to i = m − 1 compute (and store) iP . 4. For j = 0 to j = m − 1 compute (and store) Q − jmP . 5. Sort the lists from steps 3, 4 in some consistent way. 6. Compare the lists from steps 3, 4 until a pair i, j such that iP = Q − jmP is found. 7. Return k ≡ i + jm (mod N ). Proof: Since we chose m such that m2 > N , there is a solution k < m2 . Let k0 ≡ k (mod m), 0 ≤ k0 < m. Let k1 = (k − k0 )/m. Then we have k = k0 + mk1 , with 0 ≤ k1 < m. In the algorithm given, we try all i in the range of values of k0 and all j in the range for k1 until we find i, j such that iP = Q − jmP =⇒ (i + jm)P = Q. Thus the value returned is always a solution, and the algorithm always halts, since k0 , k1 must exist. Time Analysis: √ Step 1 takes√O(log N ) time. Steps 2 and 3 take O(m √ + 1) = O( N ) and Ω(m + 1) = Ω( N ) time. Step 4 can be done √ in O( N ) time as well. The sort in step√5 can be performed in O(log(N ) N ) time. Step √ 6 can then be done in O( N ) time. Finally, step 7 can also be done in O( N ), so if we √ ignore logarithmic factors ( N is already large enough for the problem to √ be intractable), we find that the running time is on the order of N . The √ storage space required is also on the order of N , as that is how much space is required to store the lists in steps 3 and 4. This algorithm is too slow to be of practical use in breaking codes, as it is exponential in the length log N of the input. 4 3.2.2 The MOV Attack The MOV attack (named for Menezes, Okamoto, and Vanstone) reduces the discrete log problem on an elliptic curve E(Fq ) to the discrete log problem in F× q m for some m. The problem can then be solved fairly quickly using an index calculus attack (not described in this paper), as long as m is small. A small m can always be obtained for certain types or curves. We will start by defining a Weil pairing for curves E(F). We will not actually prove that such a pairing exists for the curves we are considering. Consider E(F), and let N be an integer not divisible by the character­ istic2 of F. Let E[N ] be the set of points on the curve with order dividing N whose coordinates are in the algebraic closure3 of F. We claim (without giving proof) that E[N ] � Zn ⊕ Zn . Let µN = {x ∈ F|xN = 1}. That is, µN is the group of N th roots of unity in F. Since the characteristic of F doesn’t divide N , xN = 1 has no multiple roots, and therefore there are N distinct roots of unity in F. Definition 1: A Weil pairing is a map eN : E[N ] × E[N ] → µn such that 1. eN is bilinear in each variable. 2. eN is nondegenerate in each variable. That is, if eN (S, T ) = 1 for all S, then T = O, and if eN (S, T ) = 1 for all T , then S = O. 4 3. eN (T, T ) = 1∀T . 4. eN (T, S) = eN (S, T )−1 ∀S, T . 5. If σ is an automorphism of F̄ that preserves the coefficients of E, then eN (σS, σT ) = σ(eN (S, T ))∀S, T . 6. If α is a separable endomorphism of E, eN (α(S), α(T )) = eN (S, T )deg α . 2 The characteristic of a field F is the smallest positive integer p such that p × 1F = 0 if such a p exits, and 0 otherwise.[Du] 3 ¯ such that F ¯ is algebraic over F and every The algebraic closure of a field F is a field F ¯ polynomial over F splits completely over F.[Du] 4 O denotes the point at infinity on our curve E(F). 5 The following propositions will be useful: Proposition 1: Let S, T form a basis for E[N ]. Then eN (S, T ) is a primi­ tive N th root of unity. Proof: Let ζ = eN (S, T ), and let d be such that ζ d = 1. Then by bilinearity eN (S, dT ) = eN (S, T )d = ζ d = 1. Similarly, eN (T, dT ) = eN (T, T )d = 1d = 1 by the properties 1 and 3 of eN . For any point P ∈ E[N ], P = aS + bT for some a, b ∈ Z. We therefore have eN (P, dT ) = eN (aS + bT, dT ) = eN (S, dT )a eN (T, dT )b = 1. Since this holds for all points P , by property 2 we have dT = O. Thus ord(T )|d ⇒ n|d, and therefore ζ = eN (S, T ) is always a primitive nth root of unity when S, T form a basis. Proposition 2: If E[N ] ⊆ E(F), then µN ⊂ F. Let σ be an automorphism of F̄ such that σ is the identity map on F. Let S, T form a basis for E[N ]. Since S, T have coefficients in F, by property 5 of the Weil pairing, we have ζ = eN (S, T ) = eN (σS, σT ) = σ(eN (S, T )) = σ(ζ). By the fundamental theorem of Galois theory, σ(ζ) = ζ ⇒ ζ ∈ F. By Propo­ sition 1, ζ is a primitive root of unity. Since the above holds for all primitive roots of unity ζ, we have µN ⊂ F. We can now describe the MOV attack. Since from algebra we know that ¯ Fq = i≥1 Fqi , we can pick an m such that E[N ] ⊆ E(Fqm ). By the propo­ sition above, we have µN ⊂ Fqm . Problem: Find k such that kP = Q on E(Fq ), with #E(Fq ) = N , assuming that such a k exists. Use a reduction of the discrete log problem on the curve E(Fq ) to the discrete log problem in F× qm . Algorithm: Until lcm(d1 , d2 , . . . , dk ) = N , perform the following steps, incrementing i by 1 for each repetition: 1. Select a random point Si ∈ E(Fqm ). 6 2. Compute the order Mi of Si . 3. Let di = gcd(Mi , N ). Let Ti = (Mi /di )Si . 4. Let ζ1i = eN (P, Ti ), ζ2i = eN (Q, Ti ). ki = ζ2i in Fq×m . This gives ki 5. Solve the discrete log problem ζ1i Now use the values of ki (mod di ) to find a k (mod di )∀i. This is the k we are looking for. (mod di ). (mod N ) such that k ≡ ki Proof: We can clearly select a point on the curve (step 1), calculate its order (step 2), and find Ti (step 3). Note that the order of Ti is di |N , so Ti ∈ E[N ]. Let ζ = eN (R, Ti ), where R is an arbitrary point on E(Fqm ) and Ti is as in step 3. Then ζ d = eN (R, Ti )d = eN (R, dTi ) = eN (R, Mi Si ) = eN (R, O) = 1, ki and so ζ1 , ζ2 ∈ µd ⊆ Fq×m , and we can solve ζ2i = ζ1i in Fq×m . Now let kP = Q, and define li such that k ≡ li (mod di ). Then k = ζ . Since eN (kP, Ti ) = eN (Q, Ti ) ⇒ eN (P, Ti )k = eN (Q, Ti ) ⇒ ζ1i 2i li d ζ1i = 1, this implies that ζ1i ≡ ζ2i (mod di ) ⇒ li ≡ ki (mod di ), and so k must equal ki (mod di ). Thus finding the necessary ki provides the answer k. Time Analysis: Weil pairings can be computed reasonably quickly, and given k ≡ ki (mod di ), we can reasonably quickly find k (mod N ). Thus the running time of this algorithm will be determined by (1) how long it takes to compute each ki , and (2) for how many i, ki must be computed. The time it takes to compute each ki depends on the size of the field Fq×m in which it must be computed. The larger m is, the longer the computation takes. There is no general theorem that determines how large an m is necessary for all types of curves. However, we know that for curves such that #E(Fq ) = q + 1 (these curves are called supersingular ), if there exists a point P ∈ E(Fq ) of order N , then E[N ] ⊆ E(Fq2 ). (We omit the proof of this statement.) To answer question (2), we first claim (without proof) that E(Fqm ) � Zn1 ⊕Zn2 for some n1 , n2 with n1 |n2 . The largest possible order of an element in E(Fq ) divides the largest order of an element in E(Fqm ), so N |n2 , since no element in E(Fqm ) can have order > n2 . 7 Let B1 , B2 be points generating E(Fqm ) such that B1 , B2 have orders n1 , n2 , respectively. Then any point Si chosen in the algorithm above can be written as a1 B1 + a2 B2 for some a1 , a2 depending on i. Let p be a prime, and let pe �N . Then pe |n2 . If p � a2 , then pe |n2 ⇒ pe |Mi , where Mi is the order of Si . Then pe |di = gcd(Mi , N ). Since Si is picked randomly, a2 for Si is also random, and so the probability that p � a2 is 1 − 1/p. Thus the probability that pe |di is ≥ 1 − 1/p for every i and every pe �N . This probability is sufficiently low that only a few di should be needed for pe |lcm(d1 , d2 , . . . , dk ) to be true for all p. We will therefore not need to iterate the algorithm too many times. 4 Cryptographic Methods Using Elliptic Curves In this section, we will describe two cryptographic methods based on the difficulty of the discrete log problem for elliptic curves. Many other methods are used as well, but we do not have room to give all of them here. These methods are generally also available over finite fields, but give more security per bit of data if elliptic curves are used instead. 4.1 Choosing a Curve For each of the cryptographic methods depended on the difficulty of the EC discrete log problem, we must begin by choosing an elliptic curve that is not susceptible to the known fast attacks on the discrete log problem, such as the MOV attack described in the previous section. The curve must therefore satisfy the following restrictions: • There exists a large prime p dividing #E(Fq ), so that the problem is not susceptible to the Pollard­ρ­attack. [not presented] • #E(Fq ) �= q (i.e. the curve is not anomalous). This prevents the prob­ lem from being susceptible to the Semaev­Smart­Satoh­Araki attack. [not presented] • The order of P does not divide q k − 1 for all k such that 1 ≤ k ≤ C, where C is a sufficiently large constant so that it is difficult to solve the discrete logarithm problem in F× . This is necessary for MOV not qC to generate a solution quickly. [see previous section][Bha] There exist several methods of choosing these curves. The simplest one is to pick a curve E(Fq ) : y 2 = x3 + ax + b at random by selecting a, b ∈ Fq 8 such that 4a3 + 27b2 = � 0 if q is odd and b �= 0 if q is a power of 2. We then check the conditions given above. A large fraction of the time, the conditions will be satisfied. If they are not, we try a different a, b.[Bha] 4.2 Setup for Encryption Algorithms Consider the following problem of cryptography: Alice wants to send Bob a message m, usually assumed to be an integer. However, she does not want the eavesdropper Eve to be able to read the message as well. Therefore, Alice uses and encryption key to encrypt the message, and sends the resulting cyphertext (rather then the plaintext) to Bob. Bob then uses a decryption key to decrypt they message. Obviously, Eve must be prevented from finding the decryption key, as otherwise she would also be able to decode the message. There are two possibilities in this scenario. Perhaps Alice and Bob were able to communicate secretly in advance and agree on a key, and perhaps they were not. If they were, the encryption and decryption keys may be the same. If they were not, they must establish a public encryption key that allows Alice to encode the message and a different private decryption key that allows Bob to decrypt the message. 4.3 Diffie­Hellman Key Exchange The following series of steps describes the Diffie­Hellman Key Exchange, a public key encryption system that allows Alice and Bob to set up a sym­ metric private key. Since the symmetric systems are generally faster than the public key systems, this is quite useful. 1. Alice and Bob publicly agree on E(Fq ), chosen so that the discrete log problem is hard, as described above. They also agree on a point P ∈ E(Fq ) of high (usually prime) order. 2. Alice chooses a secret a ∈ Z, computes aP , and sends it to Bob. 3. Bob chooses a secret b ∈ Z, computes bP , and sends it to Alice. 4. Alice computes a(bP ) = abP . 5. Bob computes b(aP ) = abP . 6. Alice and Bob now have the same point abP . They use a publicly agreed on method, such as taking the last 256 bits of the y­coordinate of the point, to extract a key. 9 Without performing a detailed analysis, we see that no step in the algo­ rithm above will be intractable. In order to obtain the key as well, Eve needs to find abP from the publicly available P, aP, bP ∈ E(Fq ). This is known as the Diffie­Hellman Problem. If Eve could solve the discrete log problem on E(Fq ), she could solve kP = (aP ) to obtain a, and then multiply bP by a to get abP . It is not known, however, whether Eve could compute abP in some other way that does not require solving the discrete log problem. The Decision Diffie­Hellman Problem asks if given P, aP, bP, Q ∈ E(Fq ) Eve can determine whether or not Q = abP . As it turns out, the Weil pairing can be used to answer this question for some types of elliptic curves. 4.4 Massey­Omura Encryption Now consider the situation in which Alice wants to send Bob a message Eve will be unable to read. Alice and Bob have not communicated privately to set up a key. Conceptually, the following algorithm will work: Alice sends Bob a box with her lock on it. Bob adds his own lock and sends the box back. Alice removes her lock and sends the box on to Bob. Bob removes his lock and reads the message. This method can be implemented using elliptic curves: 1. Alice and Bob publicly agree on E(Fq ), chosen so that the discrete log problem is hard, as described above. Let N = #E(Fq ). 2. Alice represents her message as a point P ∈ E(Fq ). 3. Alice chooses a secret a ∈ Z such that gcd(a, N ) = 1, computes aP , and sends it to Bob. 4. Bob chooses a secret b ∈ Z such that gcd(b, N ) = 1, computes b(aP ) = baP , and sends it to Alice. 5. Alice finds a−1 ∈ Zn , computes a−1 (baP ) = a−1 baP , and sends it to Bob. 6. Bob finds b−1 ∈ Zn , computes b−1 (a−1 baP ) = b−1 a−1 baP , and takes the result to be the message. Without performing a detailed analysis, we see that no step given above will take ‘too long.’ 10 To show that the above encryption method is valid, we need to show that (1) Alice can represent her message as a point on E(Fq ) and (2) that b−1 a−1 baP = P . It is clear that all the other steps can be performed. We will give a method for encoding a message m as a point P on a curve E(Fp ) : y 2 = x3 + Ax + B (given in Weierstrass normal form). A similar method exists for E(Fq ). As always, we assume that the message is an integer. Let m be a message such that 0 ≤ m < p/100. For i = 0 to 99 let xi = 100m + i. Compute each si = x3i + Axi + B for i in the range. It is possible to test whether si is a square and compute its square root if it is. If si is a square, we’re done, as we can use the point P = (xi , yi ) on our curve, where yi is the root of si . The message m can then be obtained from P by simply taking �xi �. si is an essentially random element of F× p , which is cyclic and has even order (pick an odd p), so the probability of each si being a square is about 1/2. Therefore, the probability that some si is a square is 1 − 2−100 , which is quite high. We could obviously have used 10k for some k > 2 in place of 100 to increase this probability, but that is unnecessary. If no si is a square, pick another curve. To show that b−1 a−1 baP = P , it is enough to show that a−1 aR = R for R ∈ E(Fq ), as the a’s and b’s commute and are symmetric. Note that we chose a such that gcd(a, N ) = 1, so a−1 exists. a−1 a ≡ 1 (mod N ) by the definition of a−1 , so a−1 a = 1 + kN for some k. Since the group E(Fq ) has order N , R ∈ E(Fq ) has order dividing N , and therefore N R = O. Thus a−1 aR = (1 + kN )R = R + k(N R) = R + kO = R, as needed. Let a� = a−1 , b� = b−1 , P � = abP . The eavesdropper Eve then knows P, a� P, b� P and needs to find a� b� P , which is again the Diffie­Hellman prob­ lem, as in the previous encryption method. 5 Conclusion We have now given a basic introduction to Elliptic Curve Cryptography. We introduced the discrete log problem. We then gave a general, but slow method of attack √ on this problem. There exist methods that take constant rather than√ N space, but there are no know general methods that run faster than N time. This means that the EC discrete log problem is hard. It is known to be easy only for a few specific classes of elliptic curves, such as supersingular curves (due to the MOV attack). When using an EC for encryption, it is easy to pick one that does not fall into any of these classes. 11 Two basic encryption methods were presented in this paper. Along the way, we defined a Weil pairing, which is very useful in ECC. In addition to the results given above for which it is relevant, there is also an encryption method based on Weil pairings. We have shown that ECC is a useful and theoretically interesting field. 12 References [Bha] Bhandari, A. K.; Nagraj, D.S.; Ramkrishna, B.; Venkataramana, T. N. (editors). Elliptic Curves, Modular Forms and Cryptography. New Delhi, India: Hindustan Book Agency, 2003. [Du] Dummit, David S. and Foote, Richard M. Abstract Algebra. New York, NY: John Wiley and Sons, Inc., 1999. [Ga] Galbraith, Steven. Elliptic Curve Cryptography According to Steven Galbraith. . [Ko] Koblitz, Neal. A Course in Number Theory and Cryptography. New York, NY: Springer­Verlag, 1994. [Lu] Luhrs, Christopher. Personal communication. 12/10/2004. [Wa] Washingtion, Lawrence C. Elliptic Curves: Number Theory and Cryp­ tography. Boca Raton, FL: CRC Press, 2003. [We] Weisstein, Eric. MathWorld. 12/9/2004. http://mathworld.wolfram.com. 13