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.