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.