MA 479 / CSSE 490: Cryptography
Homework 6 problems inspired by Mathematics

Rose-Hulman Institute of Technology
A joint effort of the
Department of Mathematics
and the Department of Computer Science & Software Engineering
Spring term, 2002-2003

All these problems are paper-and-pencil problems, except as indicated.You will probably not find a computer program helpful on these problems. Show all steps of your work. I will give some partial credit, especially on multi-part problems.
  1. [2 points.] Question 13 from the "Handout to accompany RSA"


  2. [4 points.] Question 14 from the "Handout to accompany RSA"


  3. [6 points.] Question 16 from the "Handout to accompany RSA"


  4. [4 points.] In the Diffie-Hellman protocol, each participant selects a secret number x and sends the other participant gx mod p for some public number g. What would happen if the participants sent each other xg for some public number g instead? Would they be able to agree on a key? Would it be secure?

  5. [12 points.] Make a key-exchange protocol using the "factoring problem" instead of the "discrete logarithm problem".


  6. [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"?


  7. [2 points.] 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 xB and Alice's secret xA? What is their secret combined key? (Don't forget to show your work.)



    8. The following problems are from your textbook.
  8. [1 point.] Problem 10.1. You may use Maple (or a similar program) to do the computations modulo 71.
  9. [2 points.] Problem 10.2. Do the computations by hand.
  10. [4 points.] Problem 10.4.
  11. [2 points.] Problem 10.5. You may use Maple (or a similar program) to do the computations modulo 71.
  12. [2 points.] Problem 10.6.
  13. [1 point.] Problem 10.8. There's a mistake in the textbook; the points given are not on the elliptic curve given. The easiest thing to do is probably to change the curve to
    y2 = x3-45.25x-25.25.
  14. [2 points.] Problem 10.9. You may use Maple and/or a small computer program to help.
  15. [2 points.] Problem 10.10. You may use Maple and/or a small computer program to help.
  16. [4 points.] Problem 10.11. You may use Maple and/or a small computer program to help.
  17. [4 points.] Problem 13.8.
  18. [6 points.] Problem 13.13.