Outline for April 25, 2000
- 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
- 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:
DESk(m) = (DESk'(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 247
tries. Works by comparing xors of results with xors of corresponding
plaintext. Designers of DES knew about this one, hence the design of
- Linear cryptanalysis drops required chosen plaintext/ciphertext pairs to
242; 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 = 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.
- Why? as ed mod φ(n) = 1,
ed = tφ(n) + 1 for some integer t.
Cd mod n = (Me mod n)d mod n
= Med mod n
= Mtφ(n) + 1 mod n
= M(Mtφ(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 = 0711 mod 35 = 28, etc.
so encipherment is 28 09 16 16 14 08 14 33 16 12.
Send email to
Department of Computer Science
University of California at Davis
Davis, CA 95616-8562
Page last modified on 4/29/2000