- 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
- Complementation property:
DES
_{k}(*m*) = (DES_{k'}(*m*'))' where*x*' is the bitwise complement of*x*; - 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
- based on NP-hard problems (knapsack)
- based on hard mathematical problems (like factoring)

- 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. - Why? as
*ed*mod*φ*(*n*) = 1,*ed*=*tφ*(*n*) + 1 for some integer*t*. Then

*C*mod^{d}*n*= (*M*mod^{e}*n*)^{d}mod*n*

=*M*mod^{ed}*n*

=*M*^{tφ(n) + 1}mod*n*

=*M*(*M*^{tφ(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 - 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`mod 35 = 28,_{11}*etc*. so encipherment is`28 09 16 16 14 08 14 33 16 12`.

- Exponentiation cipher:

Send email to bishop@cs.ucdavis.edu.

Department of Computer Science

University of California at Davis

Davis, CA 95616-8562