Outline for April 25, 2000 1. What is a cryptosystem? a. (M, C, K, D, E) b. attacks: known ciphertext, known plaintext, chosen plaintext 2. Transposition ciphers a. Show rail-fence cipher as example b. Show anagramming 3. Simple substitution ciphers a. Do C?sar cipher b. Present Vigenere tableau c. Discuss breaking it (Kasiski method). d. Go through one-time pads 4. DES a. Product cipher with 64 bits in, 64 bits out, and 16 48-bit round keys generated from 56 bit key b. Note S-boxes are real heart of algorithm c. Complementation property: DESk(m) = (DESk'(m'))' where x' is the bitwise complement of x; d. 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 247 tries. Works by com- paring xors of results with xors of corresponding plaintext.. Designers of DES knew about this one, hence the design of the S-boxes e. Linear cryptanalysis drops required chosen plaintext/ciphertext pairs to 242; not known to designers of DES. f. Triple DES and EDE mode 5. Public Key a. based on NP-hard problems (knapsack) b. based on hard mathematical problems (like factoring) 6. Do RSA a. Exponentiation cipher: C = me mod n, M = Cd mod n; d is private key, (e, n) is public key; must choose d first, then e so that ed mod f(n) = 1. b. Why? as ed mod f(n) = 1, ed = tf(n) + 1 for some integer t. Then Cd mod n = (Me mod n)d mod n = Med mod n = Mtf(n) + 1 mod n = M(Mtf(n) mod n) mod n = M(Mf(n) mod n)t mod n = M(1)t mod n = M mod n by Fermat's Little Theorem c. Example: p = 5, q = 7, n = 35, f(n) = 24; choose e = 11, then d = 11. HELLO WORLD is 07 04 11 11 14 22 14 17 11 03; enciphering is C = 0711 mod 35 = 28, etc. so encipherment is 28 09 16 16 14 08 14 33 16 12.