Outline for April 25, 2000

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. Complementation property: DES_k(m) = (DES_k'(m'))' where x' is the bitwise complement of x;
   4. 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
   5. Linear cryptanalysis drops required chosen plaintext/ciphertext pairs to 2⁴²; not known to designers of DES.
   6. Triple DES and EDE mode
5. Public Key
   1. based on NP-hard problems (knapsack)
   2. 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. Why? as ed mod φ(n) = 1, ed = tφ(n) + 1 for some integer t. Then
      C^d mod n = (M^e mod n)^d mod n
                             = M^ed mod n
                             = M^{tφ(n) + 1} mod n
                             = M(M^tφ(n) mod n) mod n
                             = M(M^φ(n) mod n)^t mod n
                             = M(1)^t mod n
                             = M mod n
      by Fermat's Little Theorem
   3. 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.