Reading (for Wednesday, Feb. 16)

Read "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems"

This is the paper by R.L. Rivest, A. Shamir, and L. Adleman that describes their RSA algorithm for public-key cryptography. Read the paper and write responses to the following questions. Your responses should be written in complete sentences and, if you happen to use direct quotatons, appropriate citation. (I prefer that you use your own words!)

  1. The paper refers to the paper by Diffie and Hellman that was the first to present the idea of a new system of cryptography (public-key cryptography). A couple of places in this paper refer to the Diffie-Hellman paper. Which ideas in this paper originated in the Diffie-Hellman paper and which are new? Write at least a paragraph describing the ideas from Diffie-Hellman that this paper builds on and the ways in which this paper differs.

  2. The paper points out that in a "computer network" an "intruder" might forge their public key. What is the solution suggested and what concept from Chapter 2 in the text book addresses this?

  3. Section VII goes through several implementation issues. The first is how to do modular exponentiation efficiently. The paper gives an algorithm based on repeated squaring and multiplication. Go through this algorithm to compute 519 (mod 11). Show each step.

  4. For each of the other steps in the RSA algorithm (finding large prime numbers, choosing d, computing e), give a brief discussion of the problems and solutions presented in the paper.

  5. On page 123, the authors state that their method "should not be confused with the "exponentiation" technique presented by Diffie and Hellman...". Explain the difference between the two techniques in terms of both purpose (what each technique is used for) and how the technique is applied.

  6. Describe the cryptanalytic approaches the authors of the paper consider and, for each, why they consider their system secure against the approach.