Outline for May 8, 2003

1. What is a cryptosystem?
   1. (M, C, K, D, E)
   2. Attacks: known ciphertext, known plaintext, chosen plaintext
2. Transposition ciphers
   1. Show rail-fence cipher as example
   2. Show anagramming
3. Simple substitution ciphers
   1. Do Cæsar cipher
   2. Present Vigenère tableau
   3. Discuss breaking it (Kasiski method).
   4. Go through one-time pads
4. DES
   1. Product cipher with 64 bits in, 64 bits out, and 16 48-bit round keys generated from 56 bit key
   2. Note S-boxes are real heart of algorithm
   3. Differential cryptanalysis: first version unusable as at 16 rounds, more plaintext/ciphertext pairs needed than exhaustive key trial; but for 15 rounds, cuts this time. Later versions cut it to 2⁴⁷ tries. Works by comparing xors of results with xors of corresponding plaintext. Designers of DES knew about this one, hence the design of the S-boxes
   4. Linear cryptanalysis drops required chosen plaintext/ciphertext pairs to 2⁴²; not known to designers of DES.
   5. Triple DES and EDE mode
5. Public Key
   1. Requirements
      1. computationally easy to encipher, decipher
      2. computationally infeasible to get private key from public
      3. chosen plaintext attack computationally infeasible
   2. based on NP-hard problems (knapsack)
   3. based on hard mathematical problems (like factoring)
6. Do RSA
   1. Exponentiation cipher: C = M^e mod n, M = C^d mod n; d is private key, (e, n) is public key; must choose d first, then e so that ed mod φ(n) = 1.
   2. Example: p = 5, q = 7, n = 35, φ(n) = 24; choose e = 11, then d = 11. HELLO WORLD is 07 04 11 11 14 22 14 17 11 03; enciphering is C = 07¹¹ mod 35 = 28, etc. so encipherment is 28 09 16 16 14 08 14 33 16 12.
   3. Problems: rearrangement of blocks ("is the attack on?" NO vs. ON); precomputation of possible answers