Previous lecture | Table of contents | Next lecture |

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 10^{20} 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 A^{B} mod C. I suggested the
following:

- Maple first computes A
^{B}. - It divides the result by C.
- It reports the remainder.

But then I remarked that computing A^{B} 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 10^{20} seconds. All of this with the most
optimistic estimates would take about 10^{2} years (actually,
better estimates would be a thousand or ten thousand years!). So how
can we compute A^{B}? 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 A^{20}. The straightforward way
needed 19 multiplications. A student suggested computing A^{2}
and then getting the 10^{th} power of that -- needing only 10
multiplications. Further analysis revealed even further savings by
repeated squaring.

We analyzed how to compute A^{46} 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 |