Outline for February 15/20, 2002

Reading: §9-9.3

  1. Greetings and Felicitations!
  2. Puzzle of the day
  3. Classical
    1. monoalphabetic (simple substitution): f ( a ) = a + k mod n
    2. example: Caesar with k = 3, RENAISSANCE → UHQDLVVDQFH
    3. polyalphabetic: Vigenère, fi ( 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
  4. 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?
  5. DES
  6. 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
  7. 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 PHI ( n ) = 1.
      Proof: M PHI( 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, PHI ( n ) = (5-1)(7-1) = 24. Pick d = 11. Then de mod PHI ( n ) = 1, so choose e = 11. To encipher 2, C = M e mod n = 211 mod 35 = 2048 mod 35 = 18, and M = C d mod n = 1811 mod 35 = 2.
    4. Example: p = 53, q = 61, n = 3233, PHI ( 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

ECS 153, Introduction to Computer Security
Winter Quarter 2002
Email: cs153@cs.ucdavis.edu