Outline for October 17, 2003

Reading: Chapters 9.2--9.3

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 (con't)
    1. Polyalphabetic: Vigenère, fi(a) = (a + ki) mod n
    2. Cryptanalysis: first do index of coincidence to see if it's monoalphabetic or polyalphabetic, then Kasiski method.
    3. 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 = Me mod n, M = Cd 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 e = 11. Then ed mod φ(n) = 1, so choose d = 11. To encipher 2, C = Men = 211 mod 35 = 2048 mod 35 = 18, and M = Cd mod n = 1811 mod 35 = 2.
    4. Example: p = 53, q = 61, n = 3233, φ(n) = (53-1)(61-1) = 3120. Take e = 71; then d = 791. 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

Here is a PDF version of this document.