Outline for February 19, 2003

Discussion Problem

Some programs use passwords for access control, but do not protect the passwords in a very sophisticated manner (for example, by saving them in a file) or make determining the correct password very easy (for example, the Microsoft Word 5.0 encipherment scheme). The argument for using simple passwords and weak encipherment is that the data or programs being protected are of little value and the passwords give a small measure of privacy.

Given that what they are protecting is truly of little value, why is the use of such simple passwords and easily-broken encipherment bad?

Outline for the Day

1. Classical Cryptography
   1. monoalphabetic (simple substitution): f(a) = a + k mod n
   2. example: Caesar with k = 3, RENAISSANCE → UHQDLVVDQFH
   3. polyalphabetic: Vigenère, f_i(a) = (a + k_i) mod n
   4. cryptanalysis: first do index of coincidence to see if it's monoalphabetic or polyalphabetic, then Kasiski method.
   5. problem: eliminate periodicity of key
2. Long key generation
   1. Running-key cipher: M=THETREASUREISBURIED; K=THESECONDCIPHERISAN; C=MOILVGOFXTMXZFLZAEQ; 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.)
   2. Perfect secrecy: when the probability of computing the plaintext message is the same whether or not you have the ciphertext
   3. Only cipher with perfect secrecy: one-time pads; C=AZPR; is that DOIT or DONT?
3. DES
4. Public-Key Cryptography
   1. Basic idea: 2 keys, one private, one public
   2. Cryptosystem must satisfy:
      1. given public key, CI to get private key;
      2. cipher withstands chosen plaintext attack;
      3. encryption, decryption computationally feasible [note: commutativity not required]
   3. Benefits: can give confidentiality or authentication or both
5. RSA
   1. Provides both authenticity and confidentiality
   2. Go through algorithm:
      Idea: C = M^e mod n, M = C^d mod n, with ed mod φ(n) = 1.
      Proof: M^φ(n) mod n = 1 [by Fermat's theorem as generalized by Euler]; follows immediately from ed mod φ(n) = 1.
      Public key is (e, n); private key is d. Choose n = pq; then φ(n) = (p-1)(q-1).
   3. Example:
      p = 5, q = 7; n = 35, φ(n) = (5-1)(7-1) = 24. Pick d = 11. Then de mod φ(n) = 1, so choose e = 11. To encipher 2, C = M^e mod n = 2¹¹ mod 35 = 2048 mod 35 = 18, and M = C^D mod n = 18¹¹ mod 35 = 2.
   4. Example: p = 53, q = 61, n = 3233, φ(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)⁷¹ mod 3233 = 3106; etc. = 3106 0100 0931 2691 1984 2927