Outline for February 20/22, 2002 Reading: ß9.3-9.4, ß10.2, ß10.4.2-10.4.3, ß10.5.1-10.5.1.1, ß10.5.2, ß10.6 except ß10.6.2.2 1. Greetings and Felicitations 2. Puzzle of the day 3. Public-Key Cryptography a. Basic idea: 2 keys, one private, one public b. Cryptosystem must satisfy: i. given public key, CI to get private key; ii. cipher withstands chosen plaintext attack; iii. encryption, decryption computationally feasible [note: commutativity not required] c. Benefits: can give confidentiality or authentication or both 4. RSA a. Provides both authenticity and confidentiality b. Go through algorithm: Idea: C = Me mod n, M = Cd mod n, with ed mod f(n) = 1. Proof: Mf(n) mod n = 1 [by Fermat's theorem as generalized by Euler]; follows immediately from ed mod f(n) = 1. Public key is (e, n); private key is d. Choose n = pq; then f(n) = (p-1)(q-1). c. Example: p = 5, q = 7; n = 35, f(n) = (5-1)(7-1) = 24. Pick d = 11. Then de mod f(n) = 1, so choose 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. d. Example: p = 53, q = 61, n = 3233, f(n) = (53-1)(61-1) = 3120. Take d = 791; then e = 71. Encipher M = RENAISSANCE: A = 00, B = 01, -, Z = 25, blank = 26. Then: M = RE NA IS SA NC Eblank = 1704 1300 0818 1800 1302 0426 C = (1704)71 mod 3233 = 3106; etc. = 3106 0100 0931 2691 1984 2927 5. Cryptographic Checksums a. Function y = h(x): easy to compute y given x; computationally infeasible to compute x given y b. Variant: given x and y, computationally infeasible to find a second x' such that y = h(x'). c. Keyed vs. keyless d. MD5, HMAC 6. Key Exchange a. Needham-Schroeder and Kerberos b. Public key; man-in-the-middle attacks 7. Cryptographic Key Infrastructure a. Certificates (X.509, PGP) b. Certificate, key revocation c. Key Escrow 8. Digital Signatures