# 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. 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: DESk(m) = (DESk'(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 247 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 242; 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 = 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 φ(n) = 1.
2. Why? as ed mod φ(n) = 1, ed = (n) + 1 for some integer t. Then
Cd mod n = (Me mod n)d mod n
= Med mod n
= M(n) + 1 mod n
= M(M(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 = 0711 mod 35 = 28, etc. so encipherment is 28 09 16 16 14 08 14 33 16 12.

Send email to bishop@cs.ucdavis.edu.

Department of Computer Science
University of California at Davis
Davis, CA 95616-8562