- What is a cryptosystem?
- (
*M*,*C*,*K*,*D*,*E*) - Attacks: known ciphertext, known plaintext, chosen plaintext

- (
- Transposition ciphers
- Show rail-fence cipher as example
- Show anagramming

- Simple substitution ciphers
- Do Cæsar cipher
- Present Vigenère tableau
- Discuss breaking it (Kasiski method).
- Go through one-time pads

- DES
- Product cipher with 64 bits in, 64 bits out, and 16 48-bit round keys generated from 56 bit key
- Note S-boxes are real heart of algorithm
- 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
^{47}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 - Linear cryptanalysis drops required chosen plaintext/ciphertext
pairs to 2
^{42}; not known to designers of DES. - Triple DES and EDE mode

- Public Key
- Requirements
- computationally easy to encipher, decipher
- computationally infeasible to get private key from public
- chosen plaintext attack computationally infeasible

- based on NP-hard problems (knapsack)
- based on hard mathematical problems (like factoring)

- Requirements
- Do RSA
- Exponentiation cipher:
*C*=*M*mod^{e}*n*,*M*=*C*mod^{d}*n*;*d*is private key, (*e*,*n*) is public key; must choose*d*first, then*e*so that*ed*mod φ(*n*) = 1. - 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^{11}mod 35 = 28, etc. so encipherment is`28 09 16 16 14 08 14 33 16 12`. - Problems: rearrangement of blocks ("is the attack on?"
`NO`vs.`ON`); precomputation of possible answers

- Exponentiation cipher:

This document is also available in Postscript and PDF.