Previous lecture
 		Table of contents
 		Next lecture

Lecture #14:  Working with RSA

I described the Diffie-Hellman and RSA protocols again. I then tried to explain that efficient solution of the Discrete Logarithm problem and Factoring would lead to "breaking" of Diffie-Hellman and RSA respectively. Here "efficiency" is most important. I mentioned that the security of these protocols rested upon the unproved but heuristically valid assumptions that the associated problems were too hard. No one knew how to efficiently attack them (a house built upon sand?).

I had previously remarked that at a school the size of Rutgers, 60 or 70 people probably could read any person's e-mail. I read a communication from Chuck Hedrick (in charge of computers in New Brunswick) on use of encryption at Rutgers. Encryption is certainly recommended for communication of such things as social security numbers and passwords. He hopes that in the future encryption like PGP (a generally available public key encryption system) will be easier to use here.

I moved on to implementation. I remarked that I had constructed an environment for people to work on RSA. How did I do it? First, I had to choose some large primes, in my case about 20 digits long (so the primes were about 1020 in size). How could I get them? Well, in fact, by guessing. Although primes tend to get more sparse as numbers increase in size, at about 20 digits about 2 percent of all numbers are prime. So you pick a number, check if it is prime, and discard otherwise. On average, you get a prime fairly quickly: this is all automated in Maple, although I did not go into details. I was asked and was able to contrast prime checking and factoring. There are better, faster algorithms for prime checking than there are for factoring. I did not go into a discussion of probabilistic prime checking!

I then asked how Maple computed AB mod C. I suggested the following:

  1. Maple first computes AB.
  2. It divides the result by C.
  3. It reports the remainder.
I remarked that this is almost what Maple does. Some students had already run into the "Object too large" error in Maple while doing the Diffie-Hellman assignment. I explained that people who install Maple tell it what size the storage space can be, so there is in reality always a limit on storage size. If Maple does step 1, then there will be lots of problems with the integers that I need to use for the RSA exercise: 40 digit numbers. AB would be ENORMOUS! So we decided that Maple could handle this by doing each computation mod C, and there would be no need to keep more than 40 or so digits at each stage. I don't think I explained this well: e.g., that X*Y mod C equals (X mod C)*(Y mod C) mod C.

But then I remarked that computing AB directly would take too darn long: we'd need to multiply A by itself B (well, really, B-1) times. I tried to estimate how long such a computation would take, assuming multiplication would take 10-10 seconds so that I would need 1020 seconds. All of this with the most optimistic estimates would take about 102 years (actually, better estimates would be a thousand or ten thousand years!). So how can we compute AB? I think all this discussion, with much juggling of exponents, went by too fast and may not have been well understood.

We analyzed how to compute A20. The straightforward way needed 19 multiplications. A student suggested computing A2 and then getting the 10th power of that -- needing only 10 multiplications. Further analysis revealed even further savings by repeated squaring.

We analyzed how to compute A46 by repeated squaring, which I (slightly inaccurately) called the "Russian peasant method". Perhaps I should have called it "divide-and-conquer", only that's not correct either. It resulted in considerable savings. I said that this was tied up with binary notation, and I would describe it after vacation.

I asked finally how Alice, in getting the message, "I love you," from Bob could be sure it was indeed sent by Bob. So we discussed digital signatures and how RSA could be used for this. I went over this very quickly and it isn't clear to me that most people understood. I remarked on the policy implications for this, and said that there were bills concerning digital signatures currently being considered by the U.S. Congress. I should emphatically have asked students to read the appropriate section if Beutelspacher's book -- I did last semester, but forgot this time. This would have helped them understand the material in the next class.

I gave out the rather elaborate RSA assignments, including both RSA implementation exercises (a web page and e-mail messages) and the policy assignments. Note that the "breaking RSA" part of the RSA assignment requires that students discover (for themselves or with help?) how Maple can be asked to factor integers.

I wrote some simple Maple routines to construct the RSA assignments.

Previous lecture
 		Table of contents
 		Next lecture