Public-Key Cryptography and RSA PDF

312 CHAPTER 9 / PUBLIC-KEY CRYPTOGRAPHY AND RSA 9.16 9.17 9.18 “Hmm, I don’t see how you can help him.” Watson was visibly unhappy with the idea that the sympathetic young man has to lose his love. “Well, I think I could help. You know, Watson, redundancy is sometimes good to ensure the security...

312 CHAPTER 9 / PUBLIC-KEY CRYPTOGRAPHY AND RSA 9.16 9.17 9.18 “Hmm, I don’t see how you can help him.” Watson was visibly unhappy with the idea that the sympathetic young man has to lose his love. “Well, I think I could help. You know, Watson, redundancy is sometimes good to ensure the security of protocol. Thus, the simplification the girl’s father has proposed could make the new protocol vulnerable to an attack the original protocol was able to resist,” mused Holmes. “Yes, it is so, Watson. Look, all an adversary needs is to be one of the users of the network and to be able to intercept messages exchanged between A and B. Being a user of the network, he has his own public encryption key and is able to send his own messages to A or to B and to receive theirs. With the help of the simplified protocol, he could then obtain message M user A has previously sent to B using the following procedure:” Complete the description. Use the fast exponentiation algorithm of Figure 9.8 to determine 6 4 7 2 mod 3415. Show the steps involved in the computation. Here is another realization of the fast exponentiation algorithm. Demonstrate that it is equivalent to the one in Figure 9.8. 1. f d 1; T d a; E d b 2. if odd(E) then f d f : T 3. E d [ E/2 ] 4. T d T : T 5. if E + 0 then goto 2 6. output f This problem illustrates a simple application of the chosen ciphertext attack. Bob intercepts a ciphertext C intended for Alice and encrypted with Alice’s public key e. Bob wants to obtain the original message M = C d mod n. Bob chooses a random value r less than n and computes Z = r e mod n X = ZC mod n t = r -1 mod n 9.19 9.20 9.21 9.22 Next, Bob gets Alice to authenticate (sign) X with her private key (as in Figure 9.3), thereby decrypting X. Alice returns Y = Xd mod n. Show how Bob can use the information now available to him to determine M. Show the OAEP decoding operation used for decryption that corresponds to the encoding operation of Figure 9.10. Improve on algorithm P1 in Appendix W. a. Develop an algorithm that requires 2n multiplications and n + 1 additions. Hint: xi + 1 = xi * x. b. Develop an algorithm that requires only n + 1 multiplications and n + 1 additions. Hint: P(x) = a0 + x * q(x), where q(x) is a polynomial of degree (n - 1). Note: The remaining problems concern the knapsack public-key algorithm described in Appendix J. What items are in the knapsack in Figure F.1? Perform encryption and decryption using the knapsack algorithm for the following: a. a= = (1, 5, 7, 14); w = 11; m = 30; x = 1011 b. a= = (1, 2, 7, 12, 23, 38, 116, 248); w = 201; m = 457; x = 10101010 c. a= = (2, 4, 7, 15, 29); w = 36; m = 47; x = 10011 d. a= = (15, 92, 108, 279, 563, 1172, 2243, 4468); w = 2033; m = 8764; x = 10110011 n 9.23 Why is it a requirement that m 7 a a=i? 1=1 CHAPTER Other Public-Key Cryptosystems 10.1 Diffie–Hellman Key Exchange The Algorithm Key Exchange Protocols Man-in-the-Middle Attack 10.2 Elgamal Cryptographic System 10.3 Elliptic Curve Arithmetic Abelian Groups Elliptic Curves over Real Numbers Elliptic Curves over Z p Elliptic Curves over GF(2m) 10.4 Elliptic Curve Cryptography Analog of Diffie–Hellman Key Exchange Elliptic Curve Encryption/Decryption Security of Elliptic Curve Cryptography 10.5 Pseudorandom Number Generation Based on an Asymmetric Cipher PRNG Based on RSA PRNG Based on Elliptic Curve Cryptography 10.6 Key Terms, Review Questions, and Problems 313 314 CHAPTER 10 / OTHER PUBLIC-KEY CRYPTOSYSTEMS LEARNING OBJECTIVES After studying this chapter, you should be able to: ◆ ◆ ◆ ◆ ◆ ◆ Define Diffie–Hellman key exchange. Understand the man-in-the-middle attack. Present an overview of the Elgamal cryptographic system. Understand elliptic curve arithmetic. Present an overview of elliptic curve cryptography. Present two techniques for generating pseudorandom numbers using an asymmetric cipher. This chapter begins with a description of one of the earliest and simplest PKCS: Diffie–Hellman key exchange. The chapter then looks at another important scheme, the Elgamal PKCS. Next, we look at the increasingly important PKCS known as elliptic curve cryptography. Finally, the use of public-key algorithms for pseudorandom number generation is examined. 10.1 DIFFIE–HELLMAN KEY EXCHANGE The first published public-key algorithm appeared in the seminal paper by Diffie and Hellman that defined public-key cryptography [DIFF76b] and is generally referred to as Diffie–Hellman key exchange.1 A number of commercial products employ this key exchange technique. The purpose of the algorithm is to enable two users to securely exchange a key that can then be used for subsequent symmetric encryption of messages. The algorithm itself is limited to the exchange of secret values. The Diffie–Hellman algorithm depends for its effectiveness on the difficulty of computing discrete logarithms. Briefly, we can define the discrete logarithm in the following way. Recall from Chapter 2 that a primitive root of a prime number p is one whose powers modulo p generate all the integers from 1 to p - 1. That is, if a is a primitive root of the prime number p, then the numbers a mod p, a2 mod p, c , ap - 1 mod p are distinct and consist of the integers from 1 through p - 1 in some permutation. For any integer b and a primitive root a of prime number p, we can find a unique exponent i such that b K ai (mod p) 1 where 0 … i … (p - 1) Williamson of Britain’s CESG published the identical scheme a few months earlier in a classified document [WILL76] and claims to have discovered it several years prior to that; see [ELLI99] for a discussion. 10.1 / DIFFIE–HELLMAN KEY EXCHANGE 315 The exponent i is referred to as the discrete logarithm of b for the base a, mod p. We express this value as dlog a,p(b). See Chapter 2 for an extended discussion of discrete logarithms. The Algorithm Figure 10.1 summarizes the Diffie–Hellman key exchange algorithm. For this scheme, there are two publicly known numbers: a prime number q and an integer a that is a primitive root of q. Suppose the users A and B wish to create a shared key. User A selects a random integer XA 6 q and computes YA = aXA mod q. Similarly, user B independently selects a random integer XB 6 q and computes YB = aXB mod q. Each side keeps the X value private and makes the Y value available publicly to the other side. Thus, XA is A’s private key and YA is A’s corresponding public key, and similarly for B. User A computes the key as K = (YB)XA mod q and user B computes the key as K = (YA)XB mod q. These two calculations produce identical results: Alice Bob Alice and Bob share a prime number q and an integer A, such that A < q and A is a primitive root of q Alice and Bob share a prime number q and an integer A, such that A < q and A is a primitive root of q Alice generates a private key XA such that XA < q Bob generates a private key XB such that XB < q Alice calculates a public key YA = AXA mod q YA YB Bob calculates a public key YB = AXB mod q Alice receives Bob’s public key YB in plaintext Bob receives Alice’s public key YA in plaintext Alice calculates shared secret key K = (YB)XA mod q Bob calculates shared secret key K = (YA)XB mod q Figure 10.1 The Diffie–Hellman Key Exchange 316 CHAPTER 10 / OTHER PUBLIC-KEY CRYPTOSYSTEMS K = (YB)XA mod q = (aXB mod q)XA mod q = (aXB)XA mod q = a XBXA = (a ) mod q XA XB = (a XA by the rules of modular arithmetic mod q mod q)XB mod q = (YA)XB mod q The result is that the two sides have exchanged a secret value. Typically, this secret value is used as shared symmetric secret key. Now consider an adversary who can observe the key exchange and wishes to determine the secret key K. Because XA and XB are private, an adversary only has the following ingredients to work with: q, a, YA, and YB. Thus, the adversary is forced to take a discrete logarithm to determine the key. For example, to determine the private key of user B, an adversary must compute XB = dlog a,q(YB) The adversary can then calculate the key K in the same manner as user B calculates it. That is, the adversary can calculate K as K = (YA)XB mod q The security of the Diffie–Hellman key exchange lies in the fact that, while it is relatively easy to calculate exponentials modulo a prime, it is very difficult to calculate discrete logarithms. For large primes, the latter task is considered infeasible. Here is an example. Key exchange is based on the use of the prime number q = 353 and a primitive root of 353, in this case a = 3. A and B select private keys XA = 97 and XB = 233, respectively. Each computes its public key: A computes YA = 397 mod 353 = 40. B computes YB = 3233 mod 353 = 248. After they exchange public keys, each can compute the common secret key: A computes K = (YB)XA mod 353 = 24897 mod 353 = 160. B computes K = (YA)XB mod 353 = 40233 mod 353 = 160. We assume an attacker would have available the following information: q = 353; a = 3; YA = 40; YB = 248 In this simple example, it would be possible by brute force to determine the secret key 160. In particular, an attacker E can determine the common key by discovering a solution to the equation 3a mod 353 = 40 or the equation 3b mod 353 = 248. The brute-force approach is to calculate powers of 3 modulo 353, stopping when the result equals either 40 or 248. The desired answer is reached with the exponent value of 97, which provides 397 mod 353 = 40. With larger numbers, the problem becomes impractical. Hiva-Network.Com 10.1 / DIFFIE–HELLMAN KEY EXCHANGE 317 Key Exchange Protocols Figure 10.1 shows a simple protocol that makes use of the Diffie–Hellman calculation. Suppose that user A wishes to set up a connection with user B and use a secret key to encrypt messages on that connection. User A can generate a one-time private key XA, calculate YA, and send that to user B. User B responds by generating a private value XB, calculating YB, and sending YB to user A. Both users can now calculate the key. The necessary public values q and a would need to be known ahead of time. Alternatively, user A could pick values for q and a and include those in the first message. As an example of another use of the Diffie–Hellman algorithm, suppose that a group of users (e.g., all users on a LAN) each generate a long-lasting private value Xi (for user i) and calculate a public value Yi. These public values, together with global public values for q and a, are stored in some central directory. At any time, user j can access user i’s public value, calculate a secret key, and use that to send an encrypted message to user A. If the central directory is trusted, then this form of communication provides both confidentiality and a degree of authentication. Because only i and j can determine the key, no other user can read the message (confidentiality). Recipient i knows that only user j could have created a message using this key (authentication). However, the technique does not protect against replay attacks. Man-in-the-Middle Attack The protocol depicted in Figure 10.1 is insecure against a man-in-the-middle attack. Suppose Alice and Bob wish to exchange keys, and Darth is the adversary. The attack proceeds as follows (Figure 10.2). 1. Darth prepares for the attack by generating two random private keys XD1 and XD2 and then computing the corresponding public keys YD1 and YD2. 2. Alice transmits YA to Bob. 3. Darth intercepts YA and transmits YD1 to Bob. Darth also calculates K2 = (YA)XD2 mod q. 4. Bob receives YD1 and calculates K1 = (YD1)XB mod q. 5. Bob transmits YB to Alice. 6. Darth intercepts YB and transmits YD2 to Alice. Darth calculates K1 = (YB)XD1 mod q. 7. Alice receives YD2 and calculates K2 = (YD2)XA mod q. At this point, Bob and Alice think that they share a secret key, but instead Bob and Darth share secret key K1 and Alice and Darth share secret key K2. All future communication between Bob and Alice is compromised in the following way. 1. Alice sends an encrypted message M: E(K2, M). 2. Darth intercepts the encrypted message and decrypts it to recover M. 3. Darth sends Bob E(K1, M) or E(K1, M=), where M= is any message. In the first case, Darth simply wants to eavesdrop on the communication without altering it. In the second case, Darth wants to modify the message going to Bob. 318 CHAPTER 10 / OTHER PUBLIC-KEY CRYPTOSYSTEMS Alice Darth Bob Private key XA Public key YA = AXA mod q YA YD2 Secret key K2 = (YD2)XA mod q Private keys XD1, XD2 Public keys YD1 = AXD1 mod q YD2 = AXD2 mod q YD1 Private key XB Public key YB = AXB mod q Secret key K2 = (YA)XD2 mod q YB Secret key K1 = (YB)XD1 mod q Alice and Darth share K2 Figure 10.2 Secret key K1 = (YD1)XB mod q Bob and Darth share K1 Man-in-the-Middle Attack The key exchange protocol is vulnerable to such an attack because it does not authenticate the participants. This vulnerability can be overcome with the use of digital signatures and public-key certificates; these topics are explored in Chapters 13 and 14. 10.2 ELGAMAL CRYPTOGRAPHIC SYSTEM In 1984, T. Elgamal announced a public-key scheme based on discrete logarithms, closely related to the Diffie–Hellman technique [ELGA84, ELGA85]. The Elgamal2 cryptosystem is used in some form in a number of standards including the digital signature standard (DSS), which is covered in Chapter 13, and the S/MIME email standard (Chapter 19). 2 For no apparent reason, most of the literature uses the term ElGamal, although Mr. Elgamal’s last name does not have a capital letter G. 10.2 / ELGAMAL CRYPTOGRAPHIC SYSTEM 319 As with Diffie–Hellman, the global elements of Elgamal are a prime number q and a, which is a primitive root of q. User A generates a private/public key pair as follows: 1. Generate a random integer XA, such that 1 6 XA 6 q - 1. 2. Compute YA = aXA mod q. 3. A’s private key is XA and A’s public key is {q, a, YA}. Any user B that has access to A’s public key can encrypt a message as follows: 1. Represent the message as an integer M in the range 0 … M … q - 1. Longer messages are sent as a sequence of blocks, with each block being an integer less than q. 2. Choose a random integer k such that 1 … k … q - 1. 3. Compute a one-time key K = (YA)k mod q. 4. Encrypt M as the pair of integers (C1, C2) where C1 = ak mod q; C2 = KM mod q User A recovers the plaintext as follows: 1. Recover the key by computing K = (C1)XA mod q. 2. Compute M = (C2K -1) mod q. These steps are summarized in Figure 10.3. It corresponds to Figure 9.1a: Alice generates a public/private key pair; Bob encrypts using Alice’s public key; and Alice decrypts using her private key. Let us demonstrate why the Elgamal scheme works. First, we show how K is recovered by the decryption process: K K K K = = = = (YA)k mod q (aXA mod q)k mod q akXA mod q (C1)XA mod q K is defined during the encryption process substitute using YA = aXA mod q by the rules of modular arithmetic substitute using C1 = ak mod q Next, using K, we recover the plaintext as C2 = KM mod q (C2K -1) mod q = KMK -1 mod q = M mod q = M We can restate the Elgamal process as follows, using Figure 10.3. 1. Bob generates a random integer k. 2. Bob generates a one-time key K using Alice’s public-key components YA, q, and k. 3. Bob encrypts k using the public-key component a, yielding C1. C1 provides sufficient information for Alice to recover K. 4. Bob encrypts the plaintext message M using K. 5. Alice recovers K from C1 using her private key. 6. Alice uses K -1 to recover the plaintext message from C2. 320 CHAPTER 10 / OTHER PUBLIC-KEY CRYPTOSYSTEMS Global Public Elements q prime number a a 6 q and a a primitive root of q Key Generation by Alice Select private XA XA 6 q - 1 Calculate YA YA = aXA mod q Public key {q, a, YA} Private key XA Encryption by Bob with Alice’s Public Key Plaintext: M 6 q Select random integer k k 6 q Calculate K K = (YA)k mod q Calculate C1 C1 = ak mod q Calculate C2 C2 = KM mod q Ciphertext: (C1, C2) Decryption by Alice with Alice’s Private Key Ciphertext: (C1, C2) Calculate K K = (C1)XA mod q Plaintext: M = (C2K -1) mod q Figure 10.3 The Elgamal Cryptosystem Thus, K functions as a one-time key, used to encrypt and decrypt the message. For example, let us start with the prime field GF(19); that is, q = 19. It has primitive roots {2, 3, 10, 13, 14, 15}, as shown in Table 2.7. We choose a = 10. Alice generates a key pair as follows: 1. Alice chooses XA = 5. 2. Then YA = aXA mod q = a5 mod 19 = 3 (see Table 2.7). 3. Alice’s private key is 5 and Alice’s public key is {q, a, YA} = {19, 10, 3}. Suppose Bob wants to send the message with the value M = 17. Then: 10.3 / ELLIPTIC CURVE ARITHMETIC 321 1. Bob chooses k = 6. 2. Then K = (YA)k mod q = 36 mod 19 = 729 mod 19 = 7. 3. So C1 = ak mod q = a6 mod 19 = 11 C2 = KM mod q = 7 * 17 mod 19 = 119 mod 19 = 5 4. Bob sends the ciphertext (11, 5). For decryption: 1. Alice calculates K = (C1)XA mod q = 115 mod 19 = 161051 mod 19 = 7. 2. Then K -1 in GF(19) is 7-1 mod 19 = 11. 3. Finally, M = (C2K -1) mod q = 5 * 11 mod 19 = 55 mod 19 = 17. If a message must be broken up into blocks and sent as a sequence of encrypted blocks, a unique value of k should be used for each block. If k is used for more than one block, knowledge of one block M1 of the message enables the user to compute other blocks as follows. Let C1,1 = ak mod q; C2,1 = KM1 mod q C1,2 = ak mod q; C2,2 = KM2 mod q Then, C2,1 C2,2 = KM1 mod q M1 mod q = KM2 mod q M2 mod q If M1 is known, then M2 is easily computed as M2 = (C2,1)-1 C2,2 M1 mod q The security of Elgamal is based on the difficulty of computing discrete logarithms. To recover A’s private key, an adversary would have to compute XA = dlog a,q(YA). Alternatively, to recover the one-time key K, an adversary would have to determine the random number k, and this would require computing the discrete logarithm k = dlog a,q(C1). [STIN06] points out that these calculations are regarded as infeasible if p is at least 300 decimal digits and q - 1 has at least one “large” prime factor. 10.3 ELLIPTIC CURVE ARITHMETIC Most of the products and standards that use public-key cryptography for encryption and digital signatures use RSA. As we have seen, the key length for secure RSA use has increased over recent years, and this has put a heavier processing load on applications using RSA. This burden has ramifications, especially for electronic commerce sites that conduct large numbers of secure transactions. A competing system challenges RSA: elliptic curve cryptography (ECC). ECC is showing up in standardization efforts, including the IEEE P1363 Standard for Public-Key Cryptography. 322 CHAPTER 10 / OTHER PUBLIC-KEY CRYPTOSYSTEMS The principal attraction of ECC, compared to RSA, is that it appears to offer equal security for a far smaller key size, thereby reducing processing overhead. ECC is fundamentally more difficult to explain than either RSA or Diffie– Hellman, and a full mathematical description is beyond the scope of this book. This section and the next give some background on elliptic curves and ECC. We begin with a brief review of the concept of abelian group. Next, we examine the concept of elliptic curves defined over the real numbers. This is followed by a look at elliptic curves defined over finite fields. Finally, we are able to examine elliptic curve ciphers. The reader may wish to review the material on finite fields in Chapter 5 before proceeding. Abelian Groups Recall from Chapter 5 that an abelian group G, sometimes denoted by {G, # }, is a set of elements with a binary operation, denoted by # , that associates to each ordered pair (a, b) of elements in G an element (a # b) in G, such that the following axioms are obeyed:3 (A1) Closure: If a and b belong to G, then a # b is also in G. (A2) Associative: a # (b # c) = (a # b) # c for all a, b, c in G. (A3) Identity element: There is an element e in G such that a # e = e # a = a for all a in G. (A4) Inverse element: For each a in G there is an element a′ in G such that a # a′ = a′ # a = e. (A5) Commutative: a # b = b # a for all a, b in G. v A number of public-key ciphers are based on the use of an abelian group. For example, Diffie–Hellman key exchange involves multiplying pairs of nonzero integers modulo a prime number q. Keys are generated by exponentiation over the group, with exponentiation defined as repeated multiplication. For example, ak mod q = (a * a * c * a) mod q. To attack Diffie–Hellman, the attacker must k times determine k given a and ak; this is the discrete logarithm problem. For elliptic curve cryptography, an operation over elliptic curves, called addition, is used. Multiplication is defined by repeated addition. For example, v a * k = (a + a + c + a) k times where the addition is performed over an elliptic curve. Cryptanalysis involves determining k given a and (a * k). 3 The operator # is generic and can refer to addition, multiplication, or some other mathematical operation. 10.3 / ELLIPTIC CURVE ARITHMETIC 323 An elliptic curve is defined by an equation in two variables with coefficients. For cryptography, the variables and coefficients are restricted to elements in a finite field, which results in the definition of a finite abelian group. Before looking at this, we first look at elliptic curves in which the variables and coefficients are real numbers. This case is perhaps easier to visualize. Elliptic Curves over Real Numbers Elliptic curves are not ellipses. They are so named because they are described by cubic equations, similar to those used for calculating the circumference of an ellipse. In general, cubic equations for elliptic curves take the following form, known as a Weierstrass equation: y2 + axy + by = x3 + cx2 + dx + e where a, b, c, d, e are real numbers and x and y take on values in the real numbers.4 For our purpose, it is sufficient to limit ourselves to equations of the form y2 = x3 + ax + b (10.1) Such equations are said to be cubic, or of degree 3, because the highest exponent they contain is a 3. Also included in the definition of an elliptic curve is a single element denoted O and called the point at infinity or the zero point, which we discuss subsequently. To plot such a curve, we need to compute y = 2x3 + ax + b For given values of a and b, the plot consists of positive and negative values of y for each value of x. Thus, each curve is symmetric about y = 0. Figure 10.4 shows two examples of elliptic curves. As you can see, the formula sometimes produces weirdlooking curves. Now, consider the set of points E(a, b) consisting of all of the points (x, y) that satisfy Equation (10.1) together with the element O. Using a different value of the pair (a, b) results in a different set E(a, b). Using this terminology, the two curves in Figure 10.4 depict the sets E(-1, 0) and E(1, 1), respectively. GEOMETRIC DESCRIPTION OF ADDITION It can be shown that a group can be defined based on the set E(a, b) for specific values of a and b in Equation (10.1), provided the following condition is met: 4a3 + 27b2 ≠ 0 (10.2) To define the group, we must define an operation, called addition and denoted by +, for the set E(a, b), where a and b satisfy Equation (10.2). In geometric terms, the rules for addition can be stated as follows: If three points on an elliptic curve lie on a straight line, their sum is O. From this definition, we can define the rules of addition over an elliptic curve. 4 Note that x and y are true variables, which take on values. This is in contrast to our discussion of polynomial rings and fields in Chapter 5, where was treated as an indeterminate. 324 CHAPTER 10 / OTHER PUBLIC-KEY CRYPTOSYSTEMS 4 -(P + Q) 2 Q 0 P -2 (P + Q) -4 -2 0 -1 1 2 2 3 4 5 3 4 5 3 (a) y = x - x -(P + Q) 4 2 Q 0 P -2 (P + Q) -4 -2 -1 0 1 2 (b) y2 = x3 + x + 1 Figure 10.4 Example of Elliptic Curves 1. O serves as the additive identity. Thus O = -O; for any point P on the elliptic curve, P + O = P. In what follows, we assume P ≠ O and Q ≠ O. 2. The negative of a point P is the point with the same x coordinate but the negative of the y coordinate; that is, if P = (x, y), then -P = (x, -y). Note that these two points can be joined by a vertical line. Note that P + ( -P) = P - P = O. 3. To add two points P and Q with different x coordinates, draw a straight line between them and find the third point of intersection R. It is easily seen that there is a unique point R that is the point of intersection (unless the line is tangent to the curve at either P or Q, in which case we take R = P or R = Q, respectively). To form a group structure, we need to define addition on these three points: P + Q = -R. That is, we define P + Q to be the mirror image 10.3 / ELLIPTIC CURVE ARITHMETIC 325 (with respect to the x axis) of the third point of intersection. Figure 10.4 illustrates this construction. 4. The geometric interpretation of the preceding item also applies to two points, P and -P, with the same x coordinate. The points are joined by a vertical line, which can be viewed as also intersecting the curve at the infinity point. We therefore have P + ( -P) = O, which is consistent with item (2). 5. To double a point Q, draw the tangent line and find the other point of intersection S. Then Q + Q = 2Q = -S. With the preceding list of rules, it can be shown that the set E(a, b) is an abelian group. ALGEBRAIC DESCRIPTION OF ADDITION In this subsection, we present some results that enable calculation of additions over elliptic curves.5 For two distinct points, P = (xP, yP) and Q = (xQ, yQ), that are not negatives of each other, the slope of the line l that joins them is ∆ = (yQ - yP)/(xQ - xP). There is exactly one other point where l intersects the elliptic curve, and that is the negative of the sum of P and Q. After some algebraic manipulation, we can express the sum R = P + Q as xR = ∆2 - xP - xQ yR = -yP + ∆(xP - xR) (10.3) We also need to be able to add a point to itself: P + P = 2P = R. When yP ≠ 0, the expressions are xR = ¢ 3x2P + a 2 ≤ - 2xP 2yP (10.4) 3x2P + a yR = ¢ ≤(xP - xR) - yP 2yP Elliptic Curves over Z p Elliptic curve cryptography makes use of elliptic curves in which the variables and coefficients are all restricted to elements of a finite field. Two families of elliptic curves are used in cryptographic applications: prime curves over Zp and binary curves over GF(2m). For a prime curve over Z p, we use a cubic equation in which the variables and coefficients all take on values in the set of integers from 0 through p - 1 and in which calculations are performed modulo p. For a binary curve defined over GF(2m), the variables and coefficients all take on values in GF(2m) and in calculations are performed over GF(2m). [FERN99] points out that prime curves are best for software applications, because the extended bit-fiddling operations needed by binary curves are not required; and that binary curves are best for hardware applications, where it takes remarkably few logic gates to create a powerful, fast cryptosystem. We examine these two families in this section and the next. 5 For derivations of these results, see [KOBL94] or other mathematical treatments of elliptic curves. Hiva-Network.Com 326 CHAPTER 10 / OTHER PUBLIC-KEY CRYPTOSYSTEMS There is no obvious geometric interpretation of elliptic curve arithmetic over finite fields. The algebraic interpretation used for elliptic curve arithmetic over real numbers does readily carry over, and this is the approach we take. For elliptic curves over Z p, as with real numbers, we limit ourselves to equations of the form of Equation (10.1), but in this case with coefficients and variables limited to Z p: y2 mod p = (x3 + ax + b) mod p (10.5) For example, Equation (10.5) is satisfied for a = 1, b = 1, x = 9, y = 7, p = 23: 72 mod 23 = (93 + 9 + 1) mod 23 49 mod 23 = 739 mod 23 3 = 3 Now consider the set E p(a, b) consisting of all pairs of integers (x, y) that satisfy Equation (10.5), together with a point at infinity O. The coefficients a and b and the variables x and y are all elements of Z p. For example, let p = 23 and consider the elliptic curve y2 = x3 + x + 1. In this case, a = b = 1. Note that this equation is the same as that of Figure 10.4b. The figure shows a continuous curve with all of the real points that satisfy the equation. For the set E 23(1, 1), we are only interested in the nonnegative integers in the quadrant from (0, 0) through (p - 1, p - 1) that satisfy the equation mod p. Table 10.1 lists the points (other than O) that are part of E 23(1, 1). Figure 10.5 plots the points of E 23(1, 1); note that the points, with one exception, are symmetric about y = 11.5. It can be shown that a finite abelian group can be defined based on the set E p(a, b) provided that (x3 + ax + b) mod p has no repeated factors. This is equivalent to the condition (4a3 + 27b2) mod p ≠ 0 mod p (10.6) Note that Equation (10.6) has the same form as Equation (10.2). The rules for addition over E p(a, b), correspond to the algebraic technique described for elliptic curves defined over real numbers. For all points P, Q ∈ E p(a, b): Table 10.1 Points (other than O) on the Elliptic Curve E 23(1, 1) (0, 1) (6, 4) (12, 19) (0, 22) (6, 19) (13, 7) (1, 7) (7, 11) (13, 16) (1, 16) (7, 12) (17, 3) (3, 10) (9, 7) (17, 20) (3, 13) (9, 16) (18, 3) (4, 0) (11, 3) (18, 20) (5, 4) (11, 20) (19, 5) (5, 19) (12, 4) (19, 18) 10.3 / ELLIPTIC CURVE ARITHMETIC 327 22 21 20 19 18 17 16 15 y 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 x Figure 10.5 The Elliptic Curve E 23(1, 1) 1. P + O = P. 2. If P = (xP, yP), then P + (xP, -yP) = O. The point (xP, -yP) is the negative of P, denoted as -P. For example, in E 23(1, 1), for P = (13, 7), we have -P = (13, -7). But -7 mod 23 = 16. Therefore, -P = (13, 16), which is also in E23(1, 1). 3. If P = (xp, yp) and Q = (xQ, yQ) with P ≠ -Q, then R = P + Q = (xR, yR) is determined by the following rules: xR = (l2 - xP - xQ) mod p yR = (l(xP - xR) - yP) mod p where a l = e a yQ - yP xQ - xP 3x2P + a 2yP b mod p if P ≠ Q b mod p if P = Q 328 CHAPTER 10 / OTHER PUBLIC-KEY CRYPTOSYSTEMS 4. Multiplication is defined as repeated addition; for example, 4P = P + P + P + P. For example, let P = (3, 10) and Q = (9, 7) in E23(1, 1). Then l = a 7 - 10 -3 -1 b mod 23 = a b mod 23 = a b mod 23 = 11 9 - 3 6 2 xR = (112 - 3 - 9) mod 23 = 109 mod 23 = 17 yR = (11(3 - 17) - 10) mod 23 = -164 mod 23 = 20 So P + Q = (17, 20). To find 2P, 3(32) + 1 5 1 ≤ mod 23 = a b mod 23 = a b mod 23 = 6 2 * 10 20 4 The last step in the preceding equation involves taking the multiplicative inverse of 4 in Z 23. This can be done using the extended Euclidean algorithm defined in Section 4.4. To confirm, note that (6 * 4) mod 23 = 24 mod 23 = 1. l = ¢ xR = (62 - 3 - 3) mod 23 = 30 mod 23 = 7 yR = (6(3 - 7) - 10) mod 23 = ( -34) mod 23 = 12 and 2P = (7, 12). For determining the security of various elliptic curve ciphers, it is of some interest to know the number of points in a finite abelian group defined over an elliptic curve. In the case of the finite group EP(a, b), the number of points N is bounded by p + 1 - 22p … N … p + 1 + 22p Note that the number of points in Ep(a, b) is approximately equal to the number of elements in Zp, namely p elements. Elliptic Curves over GF(2m) Recall from Chapter 5 that a finite field GF(2m) consists of 2m elements, together with addition and multiplication operations that can be defined over polynomials. For elliptic curves over GF(2m), we use a cubic equation in which the variables and coefficients all take on values in GF(2m) for some number m and in which calculations are performed using the rules of arithmetic in GF(2m). Table 10.2 (0, 1) 6 (1, g ) 5 (g 10, g) 8 (g , g ) (g , g ) (g 10, g 8) (g6, g14) (g 12, 0) 13 (g , g ) 6 (g 9, g 13) 11 8 (g , g ) 3 (g5, g3) 13 (1, g ) 3 Points (other than O) on the Elliptic Curve E 24(g4, 1) 9 10 (g , g ) (g 12, g 12) 10.3 / ELLIPTIC CURVE ARITHMETIC 329 It turns out that the form of cubic equation appropriate for cryptographic applications for elliptic curves is somewhat different for GF(2m) than for Zp. The form is y2 + xy = x3 + ax2 + b (10.7) where it is understood that the variables x and y and the coefficients a and b are elements of GF(2m) and that calculations are performed in GF(2m). Now consider the set E2m(a, b) consisting of all pairs of integers (x, y) that satisfy Equation (10.7), together with a point at infinity O. For example, let us use the finite field GF(24) with the irreducible polynomial f(x) = x4 + x + 1. This yields a generator g that satisfies f(g) = 0 with a value of g4 = g + 1, or in binary, g = 0010. We can develop the powers of g as follows. g0 = 0001 g4 = 0011 g8 = 0101 g12 = 1111 g1 = 0010 g5 = 0110 g9 = 1010 g13 = 1101 g2 = 0100 g6 = 1100 g10 = 0111 g14 = 1001 g3 = 1000 g7 = 1011 g11 = 1110 g15 = 0001 For example, g5 = (g4)(g) = (g + 1)(g) = g2 + g = 0110. Now consider the elliptic curve y2 + xy = x3 + g4x2 + 1. In this case, a = g4 and b = g0 = 1. One point that satisfies this equation is (g5, g3): (g3)2 g6 + 1100 1001 + (g5)(g3) = (g5)3 + (g4)(g5)2 + 1 g8 = g15 + g14 + 1 + 0101 = 0001 + 1001 + 0001 = 1001 Table 10.2 lists the points (other than O) that are part of E 24(g4, 1). Figure 10.6 plots the points of E 24(g4, 1). It can be shown that a finite abelian group can be defined based on the set E 2m(a, b), provided that b ≠ 0. The rules for addition can be stated as follows. For all points P, Q ∈ E2m(a, b): 1. P + O = P. 2. If P = (xP, yP), then P + (xP, xP + yP) = O. The point (xP, xP + yP) is the negative of P, which is denoted as -P. 3. If P = (xP, yP) and Q = (xQ, yQ) with P ≠ -Q and P ≠ Q, then R = P + Q = (xR, yR) is determined by the following rules: xR = l2 + l + xP + xQ + a yR = l(xP + xR) + xR + yP where l = yQ + yP xQ + xP 330 CHAPTER 10 / OTHER PUBLIC-KEY CRYPTOSYSTEMS 0 14 g g13 g12 g11 g10 g9 y g8 g7 g6 g5 g4 g3 g2 g 1 1 g g2 g3 g4 g5 g6 g7 g8 g9 g10 g11 g12 g13 g14 0 x Figure 10.6 The Elliptic Curve E 24(g4, 1) 4. If P = (xP, yP) then R = 2P = (xR, yR) is determined by the following rules: xR = l2 + l + a yR = x2P + (l + 1)xR where l = xP + yP xP 10.4 ELLIPTIC CURVE CRYPTOGRAPHY The addition operation in ECC is the counterpart of modular multiplication in RSA, and multiple addition is the counterpart of modular exponentiation. To form a cryptographic system using elliptic curves, we need to find a “hard problem” corresponding to factoring the product of two primes or taking the discrete logarithm. Consider the equation Q = kP where Q, P ∈ EP(a, b) and k 6 p. It is relatively easy to calculate Q given k and P, but it is hard to determine k given Q and P. This is called the discrete logarithm problem for elliptic curves. We give an example taken from the Certicom Web site (www.certicom. com). Consider the group E 23(9,17). This is the group defined by the equation y2 mod 23 = (x3 + 9x + 17) mod 23. What is the discrete logarithm k of Q = (4, 5) to the base P = (16, 5)? The brute-force method is to compute multiples of P until Q is found. Thus, P = (16,5); 2P = (20, 20); 3P = (14, 14); 4P = (19, 20); 5P = (13, 10); 6P = (7, 3); 7P = (8, 7); 8P = (12, 17); 9P = (4, 5) 10.4 / ELLIPTIC CURVE CRYPTOGRAPHY 331 Because 9P = (4, 5) = Q, the discrete logarithm Q = (4, 5) to the base P = (16, 5) is k = 9. In a real application, k would be so large as to make the bruteforce approach infeasible. In the remainder of this section, we show two approaches to ECC that give the flavor of this technique. Analog of Diffie–Hellman Key Exchange Key exchange using elliptic curves can be done in the following manner. First pick a large integer q, which is either a prime number p or an integer of the form 2m, and elliptic curve parameters a and b for Equation (10.5) or Equation (10.7). This defines the elliptic group of points Eq(a, b). Next, pick a base point G = (x1, y1) in Ep(a, b) whose order is a very large value n. The order n of a point G on an elliptic curve is the smallest positive integer n such that nG = 0 and G are parameters of the cryptosystem known to all participants. A key exchange between users A and B can be accomplished as follows (Figure 10.7). 1. A selects an integer nA less than n. This is A’s private key. A then generates a public key PA = nA * G; the public key is a point in Eq(a, b). 2. B similarly selects a private key nB and computes a public key PB. 3. A generates the secret key k = nA * PB. B generates the secret key k = nB * PA. The two calculations in step 3 produce the same result because nA * PB = nA * (nB * G) = nB * (nA * G) = nB * PA To break this scheme, an attacker would need to be able to compute k given G and kG, which is assumed to be hard. As an example,6 take p = 211; E p(0, -4), which is equivalent to the curve 2 y = x3 - 4; and G = (2, 2). One can calculate that 240G = O. A’s private key is nA = 121, so A’s public key is PA = 121(2, 2) = (115, 48). B’s private key is nB = 203, so B’s public key is 203(2, 3) = (130, 203). The shared secret key is 121(130, 203) = 203(115, 48) = (161, 69). Note that the secret key is a pair of numbers. If this key is to be used as a session key for conventional encryption, then a single number must be generated. We could simply use the x coordinates or some simple function of the x coordinate. Elliptic Curve Encryption/Decryption Several approaches to encryption/decryption using elliptic curves have been analyzed in the literature. In this subsection, we look at perhaps the simplest. The first task in this system is to encode the plaintext message m to be sent as an (x, y) point Pm. 6 Provided by Ed Schaefer of Santa Clara University. 332 CHAPTER 10 / OTHER PUBLIC-KEY CRYPTOSYSTEMS Global Public Elements E q(a, b) elliptic curve with parameters a, b, and q, where q is a prime or an integer of the form 2m G point on elliptic curve whose order is large value n User A Key Generation Select private nA nA 6 n Calculate public PA PA = nA * G User B Key Generation Select private nB nB 6 n Calculate public PB PB = nB * G Calculation of Secret Key by User A K = nA * PB Calculation of Secret Key by User B K = nB * PA Figure 10.7 ECC Diffie–Hellman Key Exchange It is the point Pm that will be encrypted as a ciphertext and subsequently decrypted. Note that we cannot simply encode the message as the x or y coordinate of a point, because not all such coordinates are in Eq(a, b); for example, see Table 10.1. Again, there are several approaches to this encoding, which we will not address here, but suffice it to say that there are relatively straightforward techniques that can be used. As with the key exchange system, an encryption/decryption system requires a point G and an elliptic group Eq(a, b) as parameters. Each user A selects a private key nA and generates a public key PA = nA * G. To encrypt and send a message Pm to B, A chooses a random positive integer k and produces the ciphertext Cm consisting of the pair of points: Cm = {kG, Pm + kPB} Note that A has used B’s public key PB. To decrypt the ciphertext, B multiplies the first point in the pair by B’s private key and subtracts the result from the second point: Pm + kPB - nB(kG) = Pm + k(nBG) - nB(kG) = Pm 10.4 / ELLIPTIC CURVE CRYPTOGRAPHY 333 Table 10.3 Comparable Key Sizes in Terms of Computational Effort for Cryptanalysis (NIST SP-800-57) Symmetric Key Algorithms 80 112 128 192 256 Diffie–Hellman, Digital Signature Algorithm L N L N L N L N L N = = = = = = = = = = 1024 160 2048 224 3072 256 7680 384 15,360 512 RSA (size of n in bits) ECC (modulus size in bits) 1024 160–223 2048 224–255 3072 256–383 7680 384–511 15,360 512 + Note: L = size of public key, N = size of private key. A has masked the message Pm by adding kPB to it. Nobody but A knows the value of k, so even though Pb is a public key, nobody can remove the mask kPB. However, A also includes a “clue,” which is enough to remove the mask if one knows the private key nB. For an attacker to recover the message, the attacker would have to compute k given G and kG, which is assumed to be hard. Let us consider a simple example. The global public elements are q = 257; E q(a, b) = E 257(0, -4), which is equivalent to the curve y2 = x3 - 4; and G = (2, 2). Bob’s private key is nB = 101, and his public key is PB = nBG = 101(2, 2) = (197, 167). Alice wishes to send a message to Bob that is encoded in the elliptic point Pm = (112, 26). Alice chooses random integer k = 41 and computes kG = 41(2, 2) = (136, 128), kPB = 41(197, 167) = (68, 84) and Pm + kPB = (112, 26) + (68, 84) = (246, 174). Alice sends the ciphertext Cm = (C1, C2) = {(136, 128), (246, 174)} to Bob. Bob receives the ciphertext and computes C2 - nBC1 = (246, 174) - 101(136, 128) = (246, 174) - (68, 84) = (112, 26). Security of Elliptic Curve Cryptography The security of ECC depends on how difficult it is to determine k given kP and P. This is referred to as the elliptic curve logarithm problem. The fastest known technique for taking the elliptic curve logarithm is known as the Pollard rho method. Table 10.3, from NIST SP 800-57 (Recommendation for Key Management—Part 1: General, September 2015), compares various algorithms by showing comparable key sizes in terms of computational effort for cryptanalysis. As can be seen, a considerably smaller key size can be used for ECC compared to RSA. Based on this analysis, SP 800-57 recommends that at least through 2030, acceptable key lengths are from 3072 to 14,360 bits for RSA and 256 to 512 bits for ECC. Similarly, the European Union Agency for Network and Information Security (ENISA) recommends in their 2014 report (Algorithms, Key Size and Parameters report—2014, November 2014) minimum key lengths for future system of 3072 bits and 256 bits for RSA and ECC, respectively. 334 CHAPTER 10 / OTHER PUBLIC-KEY CRYPTOSYSTEMS Analysis indicates that for equal key lengths, the computational effort required for ECC and RSA is comparable [JURI97]. Thus, there is a computational advantage to using ECC with a shorter key length than a comparably secure RSA. 10.5 PSEUDORANDOM NUMBER GENERATION BASED ON AN ASYMMETRIC CIPHER We noted in Chapter 8 that because a symmetric block cipher produces an apparently random output, it can serve as the basis of a pseudorandom number generator (PRNG). Similarly, an asymmetric encryption algorithm produces apparently random output and can be used to build a PRNG. Because asymmetric algorithms are typically much slower than symmetric algorithms, asymmetric algorithms are not used to generate open-ended PRNG bit streams. Rather, the asymmetric approach is useful for creating a pseudorandom function (PRF) for generating a short pseudorandom bit sequence. In this section, we examine two PRNG designs based on pseudorandom functions. PRNG Based on RSA For a sufficient key length, the RSA algorithm is considered secure and is a good candidate to form the basis of a PRNG. Such a PRNG, known as the Micali–Schnorr PRNG [MICA91], is recommended in the ANSI standard X9.82 (Random Number Generation) and in the ISO standard 18031 (Random Bit Generation). The PRNG is illustrated in Figure 10.8. As can be seen, this PRNG has much the same structure as the output feedback (OFB) mode used as a PRNG (see Figure 8.4b and the portion of Figure 7.6a enclosed with a dashed box). In this case, the encryption algorithm is RSA rather than a symmetric block cipher. Also, a portion of the output is fed back to the next iteration of the encryption algorithm and the remainder of the output is used as pseudorandom bits. The motivation for this separation of the output into two distinct parts is so that the pseudorandom bits from one stage do not provide input to the next stage. This separation should contribute to forward unpredictability. Seed = x0 n, e, r, k n, e, r, k Encrypt Encrypt Encrypt y1 = xe0 mod n y2 = xe1 mod n y3 = xe2 mod n x1 = r most significant bits z1 = k least significant bits Figure 10.8 Hiva-Network.Com n, e, r, k x2 = r most significant bits z2 = k least significant bits x3 = r most significant bits z3 = k least significant bits Micali–Schnorr Pseudorandom Bit Generator 10.5 / PSEUDORANDOM NUMBER GENERATION BASED ON AN ASYMMETRIC CIPHER 335 We can define the PRNG as follows. Setup Select p, q primes; n = pq; f(n) = (p - 1)(q - 1). Select e such that gcd(e, f(n)) = 1. These are the standard RSA setup selections (see Figure 9.5). In addition, let N = [log 2n] + 1 (the bitlength of n). Select r, k such that r + k = N. Seed Select a random seed x0 of bitlength r. Generate Generate a pseudorandom sequence of length k * m using the loop for i from 1 to m do yi = xei - 1 mod n xi = r most significant bits of yi zi = k least significant bits of yi Output The output sequence is z1 } z2 } c } zm. The parameters n, r, e, and k are selected to satisfy the following six requirements. 1. n = pq n is chosen as the product of two primes to have the cryptographic strength required of RSA. 2. 1 6 e 6 f(n); gcd (e, f(n)) = 1 Ensures that the mapping s S se mod n is 1 to 1. 3. re Ú 2N Ensures that the exponentiation requires a full modular reduction. 4. r Ú 2 * strength Protects against a cryptographic attacks. 5. k, r are multiples of 8 An implementation convenience. 6. k Ú 8; r + k = N All bits are used. The variable strength in requirement 4 is defined in NIST SP 800-90 as follows: A number associated with the amount of work (that is, the number of operations) required to break a cryptographic algorithm or system; a security strength is specified in bits and is a specific value from the set (112, 128, 192, 256) for this Recommendation. The amount of work needed is 2strength. There is clearly a tradeoff between r and k. Because RSA is computationally intensive compared to a block cipher, we would like to generate as many pseudorandom bits per iteration as possible and therefore would like a large value of k. However, for cryptographic strength, we would like r to be as large as possible. For example, if e = 3 and N = 1024, then we have the inequality 3r 7 1024, yielding a minimum required size for r of 683 bits. For r set to that size, k = 341 bits are generated for each exponentiation (each RSA encryption). In this case, each exponentiation requires only one modular squaring of a 683-bit number and one modular multiplication. That is, we need only calculate (xi * (x2i mod n)) mod n. 336 CHAPTER 10 / OTHER PUBLIC-KEY CRYPTOSYSTEMS PRNG Based on Elliptic Curve Cryptography In this subsection, we briefly summarize a technique developed by the U.S. National Security Agency (NSA) known as dual elliptic curve PRNG (DEC PRNG). This technique is recommended in NIST SP 800-90, the ANSI standard X9.82, and the ISO standard 18031. There has been some controversy regarding both the security and efficiency of this algorithm compared to other alternatives (e.g., see [SCHO06], [BROW07]). [SCHO06] summarizes the algorithm as follows: Let P and Q be two known points on a given elliptic curve. The seed of the DEC PRNG is a random integer s0 ∈ {0, 1, c , #E(GF(p)) - 1}, where # E(GF(p)) denotes the number of points on the curve. Let x denote a function that gives the x-coordinate of a point of the curve. Let lsbi(s) denote the i least significant bits of an integer s. The DEC PRNG transforms the seed into the pseudorandom sequence of length 240k, k 7 0, as follows. for i = 1 Set si Set ri end for Return to k do d x(Si-1 P) d lsb240 (x(si Q)) r1,...,rk Given the security concerns expressed for this PRNG, the only motivation for its use would be that it is used in a system that already implements ECC but does not implement any other symmetric, asymmetric, or hash cryptographic algorithm that could be used to build a PRNG. 10.6 KEY TERMS, REVIEW QUESTIONS, AND PROBLEMS Key Terms abelian group binary curve cubic equation Diffie–Hellman key exchange discrete logarithm elliptic curve elliptic curve arithmetic elliptic curve cryptography finite field man-in-the-middle attack Micali–Schnorr prime curve primitive root zero point Review Questions 10.1 10.2 10.3 10.4 Briefly explain Diffie–Hellman key exchange. What is an elliptic curve? What is the zero point of an elliptic curve? What is the sum of three points on an elliptic curve that lie on a straight line? 10.6 / KEY TERMS, REVIEW QUESTIONS, AND PROBLEMS 337 Problems 10.1 10.2 10.3 10.4 10.5 10.6 10.7 10.8 10.9 10.10 10.11 Alice and Bob use the Diffie–Hellman key exchange technique with a common prime q = 1 5 7 and a primitive root a = 5. a. If Alice has a private key XA = 15, find her public key YA. b. If Bob has a private key XB = 27, find his public key YB. c. What is the shared secret key between Alice and Bob? Alice and Bob use the Diffie-Hellman key exchange technique with a common prime q = 2 3 and a primitive root a = 5 . a. If Bob has a public key YB = 1 0 , what is Bob’s private key YB? b. If Alice has a public key YA = 8 , what is the shared key K with Bob? c. Show that 5 is a primitive root of 23. In the Diffie–Hellman protocol, each participant selects a secret number x and sends the other participant ax mod q for some public number a. What would happen if the participants sent each other xa for some public number a instead? Give at least one method Alice and Bob could use to agree on a key. Can Eve break your system without finding the secret numbers? Can Eve find the secret numbers? This problem illustrates the point that the Diffie–Hellman protocol is not secure without the step where you take the modulus; i.e. the “Indiscrete Log Problem” is not a hard problem! You are Eve and have captured Alice and Bob and imprisoned them. You overhear the following dialog. Bob: Oh, let’s not bother with the prime in the Diffie–Hellman protocol, it will make things easier. Alice: Okay, but we still need a base a to raise things to. How about a = 3? Bob: All right, then my result is 27. Alice: And mine is 243. What is Bob’s private key XB and Alice’s private key XA? What is their secret combined key? (Don’t forget to show your work.) Section 10.1 describes a man-in-the-middle attack on the Diffie–Hellman key exchange protocol in which the adversary generates two public–private key pairs for the attack. Could the same attack be accomplished with one pair? Explain. Suppose Alice and Bob use an Elgamal scheme with a common prime q = 1 5 7 and a primitive root a = 5 . a. If Bob has public key YB = 1 0 and Alice chose the random integer k = 3 , what is the ciphertext of M = 9 ? b. If Alice now chooses a different value of k so that the encoding of M = 9 is C = (2 5 , C2 ), what is the integer C2? Rule (5) for doing arithmetic in elliptic curves over real numbers states that to double a point Q2, draw the tangent line and find the other point of intersection S. Then Q + Q = 2Q = - S. If the tangent line is not vertical, there will be exactly one point of intersection. However, suppose the tangent line is vertical? In that case, what is the value 2Q? What is the value 3Q? Demonstrate that the two elliptic curves of Figure 10.4 each satisfy the conditions for a group over the real numbers. Is (5, 12) a point on the elliptic curve y2 = x 3 + 4 x - 1 over real numbers? 17 On the elliptic curve over the real numbers y2 = x3 x + 1, Let P = (0,1) and 12 Q = (1.5,1.5). Find P + Q and 2P. Does the elliptic curve equation y2 = x 3 + x + 2 define a group over Z7?