## 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!)

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

- 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?

- 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 5
^{19} (mod 11). Show each step.

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

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

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