You may turn these problems in electronically to the drop boxes or on paper. If you do your problems electronically, please use a proper equation editor rather than trying to fake the mathematical symbols!

Drop box submissions are due at midnight on the due date. Paper submissions are due in class or in the box outside my office by 5:00 p.m.

Show your work on all problems.

I will give some partial credit, especially on multi-part problems.

 

1. [4 points.] In the Diffie-Hellman protocol, each participant selects a secret number x and sends the other participant g^x mod p for some public number g. What would happen if the participants sent each other x^g for some public number g 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?
   
   
2. [24 points.] Make a key-exchange protocol using the "factoring problem" instead of the "discrete logarithm problem".



3. [4 points.] Why does it seem to be harder to make a key-exchange protocol using the "factoring problem" instead of the "discrete logarithm problem"?



4. [2 points.] 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 g 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.)



5. [12 points.] Pages 300 and 301 of your textbook give the geometric and algebraic descriptions of the addition of points on an elliptic curve. Prove that formulas (10.3) and (10.4) in the algebraic description really give the points P+Q and 2P described in Rules 3 and 5 in the geometric description.

   
   The following problems are from your textbook. Remember to show all of your work!

6. [2 points.] Problem 10.1. Use fast exponentiation (successive squaring) to do the computations modulo 71.
7. [4 points.] Problem 10.2.
8. [8 points.] Problem 10.4.
9. [6 points.] Problem 10.5. Use fast exponentiation (successive squaring) to do the computations modulo 71.
10. [2 points.] Problem 10.6.
11. [1 point.] Problem 10.8. There's a mistake in the textbook; the points given are not on the elliptic curve given. The points should be: P = (-3,9); Q = (-2,8).
12. [6 points.] Problem 10.9. Another hint: Make a table of all squares modulo 11 and use it to take square roots.
13. [6 points.] Problem 10.10. Use successive doubling to do the computations.
14. [6 points.] Problem 10.11. Hint: Use your table from Problem 10.10.
15. [6 points.] Problem 13.8. It is easy to solve this problem by adding extra communication "passes" between the signatories. We are trying to avoid that in this problem.
16. [8 points.] Problem 13.13.

    Added 3 May:

17. [8 points.] 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 nonce 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 the 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.

18. [12 points.] 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 nonce k.
    • Bob sends Alice C₁=kG.
    • Alice sends Bob M and the signature S=M-x_AC₁.
    • Bob verifies that M=S+kY_A
    1. Show that this scheme works. That is, show the 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?  (The real ElGamal Signature Scheme avoids this problem.)

19. [64 points.] Make a cryptosystem using elliptic curves which uses a hard problem other than the elliptic curve discrete log problem.