Review Questions
10.1 Briefly explain Diffie-Hellman key exchange.
Get 10.1 exercise solution
10.2 What is an elliptic curve?
Get 10.2 exercise solution
10.3 What is the zero point of an elliptic curve?
Get 10.3 exercise solution
10.4 What is the sum of three points on an elliptic curve that lie on a straight line?
Get 10.4 exercise solution
Problems
10.1 Users A and B use the Diffie-Hellman key exchange technique with a common prime
q = 71 and a primitive root a = 7.
a. If user A has private key XA = 5, what is A’s public key YA?
b. If user B has private key XB = 12, what is B’s public key YB?
c. What is the shared secret key?
Get 10.1 exercise solution
10.2 Consider a Diffie-Hellman scheme with a common prime q = 11 and a primitive root
a = 2.
a. Show that 2 is a primitive root of 11.
b. If user A has public key YA = 9, what is A’s private key XA?
c. If user B has public key YB = 3, what is the secret key K shared with A?
Get 10.2 exercise solution
10.3 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?
Get 10.3 exercise solution
10.4 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.)
Get 10.4 exercise solution
10.5 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.
Get 10.5 exercise solution
10.6 Consider an Elgamal scheme with a common prime q = 71 and a primitive root
a = 7.
a. If B has public key YB = 3 and A choose the random integer k = 2, what is the
ciphertext of M = 30?
b. If A now chooses a different value of k so that the encoding of M = 30 is
C = (59, C2), what is the integer C2?
Get 10.6 exercise solution
10.7 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?
Get 10.7 exercise solution
10.8 Demonstrate that the two elliptic curves of Figure 10.4 each satisfy the conditions for
a group over the real numbers.
Get 10.8 exercise solution
10.9 Is (4, 7) a point on the elliptic curve y2 = x3 - 5x + 5 over real numbers?
Get 10.9 exercise solution
10.10 On the elliptic curve over the real numbers y2 = x3 - 36x, let P = (-3.5, 9.5) and
Q = (-2.5, 8.5). Find P + Q and 2P.
Get 10.10 exercise solution
10.11 Does the elliptic curve equation y2 = x3 + 10x + 5 define a group over Z17?
Get 10.11 exercise solution
10.12 Consider the elliptic curve E11(1, 6); that is, the curve is defined by y2 = x3 + x + 6
with a modulus of p = 11. Determine all of the points in E11(1, 6). Hint: Start by calculating
the right-hand side of the equation for all values of x.
Get 10.12 exercise solution
10.13 What are the negatives of the following elliptic curve points over Z17? P = (5, 8);
Q = (3, 0); R = (0, 6).
Get 10.13 exercise solution
10.14 For E11(1, 6), consider the point G = (2, 7). Compute the multiples of G from 2G
through 13G.
Get 10.14 exercise solution
10.15 This problem performs elliptic curve encryption/decryption using the scheme outlined
in Section 10.4. The cryptosystem parameters are E11(1, 6) and G = (2, 7). B’s
private key is nB = 7.
a. Find B’s public key PB.
b. A wishes to encrypt the message Pm = (10, 9) and chooses the random value
k = 3. Determine the ciphertext Cm.
c. Show the calculation by which B recovers Pm from Cm.
Get 10.15 exercise solution
10.16 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 XA and
forms the public verifying key YA = XAG. To sign a message M:
• Alice picks a value k.
• Alice sends Bob M, k and the signature S = M - kXAG.
• Bob verifies that M = S + kYA.
a. Show that this scheme works. That is, show that the verification process produces
an equality if the signature is valid.
b. Show that the scheme is unacceptable by describing a simple technique for forging
a user’s signature on an arbitrary message.
Get 10.16 exercise solution
10.17 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 XA and forms the public verifying key YA = XAG. To sign a message M:
• Bob picks a value k.
• Bob sends Alice C1 = kG.
• Alice sends Bob M and the signature S = M - XAC1.
• Bob verifies that M = S + kYA.
a. Show that this scheme works. That is, show that the verification process produces
an equality if the signature is valid.
b. 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?)
c. This scheme has an extra “pass” compared to other cryptosystems and signature
schemes we have looked at. What are some drawbacks to this?
Get 10.17 exercise solution
