Outline for February 24, 2003

Discussion Problem

It has often been said tha the only way to decipher a message that has been enciphered using RSA is to factor the modulus n used by the cipher. If you were told that an enciphered message was on a computer that you controlled, and that the message was enciphered using RSA with an n of 1024 bits (about 309 decimal digits), how would you find the encrypter's private key?

Outline for the Day

1. RSA
   1. Provides both authenticity and confidentiality
   2. Go through algorithm:
      Idea: C = M^e mod n, M = C^d mod n, with ed mod φ(n) = 1.
      Proof: M^φ(n) mod n = 1 [by Fermat's theorem as generalized by Euler]; follows immediately from ed mod φ(n) = 1.
      Public key is (e, n); private key is d. Choose n = pq; then φ(n) = (p-1)(q-1).
   3. Example:
      p = 5, q = 7; n = 35, φ(n) = (5-1)(7-1) = 24. Pick d = 11. Then de mod φ(n) = 1, so choose e = 11. To encipher 2, C = M^e mod n = 2¹¹ mod 35 = 2048 mod 35 = 18, and M = C^D mod n = 18¹¹ mod 35 = 2.
   4. Example: p = 53, q = 61, n = 3233, φ(n) = (53-1)(61-1) = 3120. Take d = 791; then e = 71. Encipher M = RENAISSANCE: A = 00, B = 01, ..., Z = 25, blank = 26. Then:
      M = RE NA IS SA NC Eblank = 1704 1300 0818 1800 1302 0426
      C = (1704)⁷¹ mod 3233 = 3106; etc. = 3106 0100 0931 2691 1984 2927
2. Cryptographic Checksums
   1. y = h(x): easy to compute y given x; computationally infeasible to compute x given y
   2. Variant: given x and y, computationally infeasible to find a second x' such that y = h(x').
   3. Keyed vs. keyless
3. Key Exchange
   1. Needham-Schroeder and Kerberos
   2. Public key; man-in-the-middle attacks
4. Cryptographic Key Infrastructure
   1. Certificates (X.509, PGP)
   2. Certificate, key revocation
5. Digital Signatures
   1. Judge can confirm, to the limits of technology, that claimed signer did sign message
   2. RSA digital signatures: sign, then encipher
6. Types of attacks
   1. Forward searches
   2. Misordered blocks
   3. Statistical regularities (repetitions)
7. Networks and ciphers
   1. Where to put the encryption
   2. Link vs. end-to-end
8. Example protocol: PEM
   1. Design goals
   2. How it was done
   3. Differences between it and PGP