Outline for May 11, 2004
- Simple substitution ciphers
- Discuss breaking Vigenère (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
- 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 the S-boxes
- Linear cryptanalysis drops required chosen plaintext/ciphertext
pairs to 242; not known to designers of DES.
- Triple DES and EDE mode
- Public Key
- 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)
- 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.
- 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.
- Problems: rearrangement of blocks ("is the attack on?"
NO vs. ON); precomputation of possible answers
- Cryptographic checksums
- Keyed vs. keyless cryptographic checksums
Here is a PDF version of this document.