Lecture 14 Outline
Reading: text, §10*
Assignments: Homework 2, due Oct. 21; Lab 2, due Oct. 21
- Greetings and felicitations!
- Puzzle of the Day
- Codes vs. ciphers
- Attacks: ciphertext only, known plaintext, chosen plaintext
- Types: substitution, transposition
- Symmetric Cryptography
- Monoalphabetic (simple substitution): f(a) = a + k mod n
- Example: Caesar with k = 3, RENAISSANCE → UHQDLVVDQFH
- Polyalphabetic: Vigenère, fi(a) = a + ki
- Cryptanalysis: first do index of coincidence to see if it is monoalphabetic or polyalphabetic, then Kasiski method.
- Problem: eliminate periodicity of key
- Long key generation
- Autokey cipher: key is plaintext followed by plaintext or ciphertext
- Running-key cipher:key is simply textl wedge is that (plaintext, key) letter pairs are not random (T/T, H/H, E/E, T/S, R/E, A/O, S/N, etc.)
- Perfect secrecy: when the probability of computing the plaintext message is the same whether or not you have the ciphertext; only cipher with perfect secrecy: one-time pads; C = AZPR; is that DOIT or DONT?
- Product ciphers: DES, AES
- Public-Key Cryptography
- Basic idea: 2 keys, one private, one public
- Cryptosystem must satisfy:
- Given public key, computationally infeasible to get private key;
- Cipher withstands chosen plaintext attack;
- Encryption, decryption computationally feasible (note: commutativity not required)
- Benefits: can give confidentiality or authentication or both
- Use of public key cryptosystem
- Normally used as key interchange system to exchange secret keys (cheap)
- Then use secret key system (too expensive to use public key cryptosystem for this)
- Provides both authenticity and confidentiality
- Go through algorithm:
Idea: C = Me mod n, M = Cd mod n, with ed mod φ(n) = 1
Public key is (e, n); private key is d. Choose n = pq; then φ(n) = (p−1)(q−1).
- Example: p = 5, q = 7; then n = 35, φ(n) = (5−1)(7−1) = 24. Pick d = 11. Then ed mod φ(n) = 1,
so e = 11
To encipher 2, C = Me mod n = 211 mod 35 = 2048 mod 35 = 18, and M = Cd mod n = 1811 mod 35 = 2.
- Example: p = 53, q = 61; then n = 3233, φ(n) = (53−1)(61−1) = 3120. Pick d = 791. Then e = 71
To encipher M = RENAISSANCE, use the mapping A = 00, B = 01, …, Z = 25, ␢ = 26.
Then: M = RE NA IS SA NC E␢ = 1704 1300 0818 1800 1302 0426
So: C = 170471 mod 3233 = 3106; … = 3106 0100 0931 2691 1984 2927