Cryptography and Network Security (4th Edition)

What are two different uses of public-key cryptography related to key distribution?

List four general categories of schemes for the distribution of public keys.

What are the essential ingredients of a public-key directory?

What is a public-key certificate?

What are the requirements for the use of a public-key certificate scheme?

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?

Users A and B use the Diffie-Hellman key exchange technique with a common prime q = 71 and a primitive root a = 7.

1. If user A has private key X_A = 5, what is A's public key Y_A?

2. If user B has private key X_B = 12, what is B's public key Y_B?

3. What is the shared secret key?

Consider a Diffie-Hellman scheme with a common prime q = 11 and a primitive root a = 2.

1. Show that 2 is a primitive root of 11.

2. If user A has public key Y_A = 9, what is A's private key X_A?

3. If user B has public key Y_B = 3, what is the shared secret key K, shared with A?

In the Diffie-Hellman protocol, each participant selects a secret number x and sends the other participant a^x mod q for some public number a. What would happen if the participants sent each other x^a 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 to raise things to. How about g = 3?

Bob: All right, then my result is 27.

Alice: And mine is 243.

What is Bob's secret X_B and Alice's secret X_A? What is their secret combined key? (Don't forget to show your work.)

Section 10.2 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.

In 1985, T. ElGamal announced a public-key scheme based on discrete logarithms, closely related to the Diffie-Hellman technique. As with Diffie-Hellman, the global elements of the ElGamal scheme are a prime number q and a, a primitive root of q. A user A selects a private key X_A and calculates a public key Y_A as in Diffie-Hellman. User A encrypts a plaintext M < q intended for user B as follows:

1. Choose a random integer k such that 1

   Compute K = (Y_B)^k mod q.

2. Encrypt M as the pair of integers (C₁, C₂) where

C₁ = a^k mod q C₂ = KM mod q

User B recovers the plaintext as follows:

1. Compute K = (C₁)^X_B mod q.

2. Compute M = (C₂K¹) mod q.

Show that the system works; that is, show that the decryption process does recover the plaintext.

Consider an ElGamal scheme with a common prime q = 71 and a primitive root a = 7

1. If B has public key Y_B = 3 and A chose the random integer k = 2, what is the ciphertext of M = 30?

2. If A now chooses a different value of k, so that the encoding of M = 30 is C = (59, C₂), what is the integer C₂?

Rule (5) for doing arithmetic in elliptic curves over real numbers states that to double a point Q, 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.9 each satisfy the conditions for a group over the real numbers.

Is (4,7) a point on the elliptic curve y² = x³ 5x + 5 over real numbers?

On the elliptic curve over the real numbers y² = x³ 36x, let P = (3.5, 9.5) and Q = (2.5, 8.5). Find P + Q and 2P.

Does the elliptic curve equation y² = x³ + 10x + 5 define a group over Z₁₇?

Consider the elliptic curve E₁₁(1, 6); that is, the curve is defined by y² = x³ + x + 6 with a modulus of p = 11. Determine all of the points in E₁₁(1, 6). Hint: Start by calculating the right-hand side of the equation for all values of x.

What are the negatives of the following elliptic curve points over Z₁₇? P = (5, 8); Q = (3, 0); R = (0, 6).

For E₁₁(1, 6), consider the point G = (2, 7). Compute the multiples of G from 2G through 13G.

This problem performs elliptic curve encryption/decryption using the scheme outlined in Section 10.4. The cryptosystem parameters are E₁₁(1, 6) and G = (2, 7). B's secret key is n_B = 7.

1. Find B's public key P_B.

2. A wishes to encrypt the message P_m = (10, 9) and chooses the random value k = 3. Determine the ciphertext C_m.

3. Show the calculation by which B recovers P_m from C_m.

The following is a first attempt at an Elliptic Curve signature scheme. We have a global elliptic curve, prime p, and "generator" G. Alice picks a private signing key X_A and forms the public verifying key Y_A = X_AG. To sign a message M:

• Alice picks a value k.

• Alice sends Bob M, k and the signature S = M kX_AG.

• Bob verifies that M = S + kY_A

1. Show that this scheme works. That is, show that the verification process produces an equality if the signature is valid.

2. Show that the scheme is unacceptable by describing a simple technique for forging a user's signature on an arbitrary message.

Here is an improved version of the scheme given in the previous problem. As before, we have a global elliptic curve, prime p, and "generator" G. Alice picks a private signing key X_A and forms the public verifying key Y_A = X_AG. To sign a message M,

• Bob picks a value k.

• Bob sends Alice C₁ = kG.

• Alice sends Bob M and the signature S = M X_AC_1-

• Bob verifies that M = S + kY_A

1. Show that this scheme works. That is, show that the verification process produces an equality if the signature is valid.

2. Show that forging a message in this scheme is as hard as breaking (ElGamal) Elliptic Curve Cryptography. (Or find an easier way to forge a message?)

3. This scheme has an extra "pass" compared to other cryptosystems and signature schemes we have looked at. What are some drawbacks to this?