CS150 Notes 36 (16 November 2005)

Upcoming Schedule

• This week: Design Review meetings
• Monday, 5 December: Problem Set 8 Presentations/Final Reports

Use different keys for encryption and decryption. Reveal one of the keys (KU, the public key). Keep the other key secret (KR, the private key).

A message encrypted with the public key is decrypted with the private key. To send a confidential message to Alice, encrypt the message with her public key.

A message encrypted with the private key is decrypted with the public key. To sign a message, encrypt it with your private key. Some else can confirm that you wrote the message, but decrypting it using your public key. Only someone who knows the private key can create a message that can be decrypted with the corresponding public key.

RSA Algorithm

1. Bob chooses two secret prime numbers. We will call them p and q. To be secure, the numbers must be at least 100 decimal digits long.
2. Bob calculates n = p * q.
3. Bob finds a number e where the greatest common divisor of e and (p - 1) * (q - 1) is 1.
4. Bob finds a number d where d * e = 1 mod ((p - 1) * (q - 1)).
5. Bob publishes n and e as the public key. He keeps d secret and destroys p and q.

• R.L. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, 1978. This is the original RSA paper, perhaps the most important paper in any field in the last 30 years. You should read it in the Rotunda or a lawn garden some time this summer.
• Whitfield Diffie and Martin Hellman. New Directions in Cryptography, 1976.
• Junger decision allowing publication of RSA source code
• The Primes Pages
• http://crl.verisign.com/ - VeriSign's Certificate Revokation List
• Microsoft, VeriSign, and Certificate Revocation , by Gregory L. Guerin (Schneier's original article)
• Ten Risks of PKI: What You're Not Being Told About Public Key Infrastructure, C. Ellison and B. Schneier. Computer Security Journal, v 16, n 1, 2000.

A short while later, Larry again made contact. This time he was well on his way to making Sneakers, starring Robert Redford, Sidney Poitier, Mary McDonnell, Dan Aykroyd and River Phoenix. He told me that there would be a scene wherein a researcher would lecture on his mathematical work regarding a breakthrough in factoring - and hence in cryptography. Larry asked if I would prepare the slides and words for that scene. I liked Larry and his desire for verisimilitude, so I agreed. Larry offered money, but I countered with Robert Redford - I would do the scene if my wife Lori could meet Redford.

I worked hard on the scene. The "number field sieve," (the fastest factoring algorithm currently known) is mentioned along with a fantasy about towers of number fields and Artin maps. I was tempted to name the new breakthrough the "function field sieve," -- since I was actually working on a paper at the time which would later appear with that title - but I decided against it, for reasons which escape me now.

I made beautiful slides on my Mac. This took a great deal of time (graphics programs were not as user friendly as they are now) but I wanted the stuff to look impressive. As it turns out, Larry had them redrawn by hand by some guy on his crew - he said that hand drawn slides looked more realistic. Of course he was right - but I could have saved a lot computer time had I known in the first place. ...

I was most pleased with my phrase "a breakthrough of Gaussian proportions," -- the Prince of Mathematics could use a plug in a major motion picture. We were introduced to Redford and chatted with him for about five minutes - that is Bobb and I chatted - Lori said hello and then apparently was too star struck to add more.

I was given credit at the end of the movie as (in my recollection) "mathematical consultant." Anyway the Academy snubbed me - since apparently the mathematical consultant Oscar for that year went to someone else.

Excerpted from Len Adleman's Sneakers Story

Real mathematics has no effects on war. No one has yet discovered any warlike purpose to be served by the theory of numbers.

G. H. Hardy, The Mathematician's Apology, 1940.

We stand today on the brink of a revolution in cryptography. The development of cheap digital hardware has freed it from the design limitations of mechanical computing and brought the cost of high grade cryptographic devices down to where they can be used in such commercial applications as remote cash dispensers and computer terminals. In turn, such applications create a need for new types of cryptographic systems which minimize the necessity of secure key distribution channels and supply the equivalent of a written signature. At the same time, theoretical developments in information theory and computer science show promise of providing provably secure cryptosystems, changing this ancient art into a science.

Diffie and Hellman, November 1976.