Outline for January 12, 1999

  1. Measures of strength
    1. unconditionally secure (theoretically unbreakable)
    2. conditionally secure (unbreakable in practise); note environment often affects this
    3. weak (breakable)
  2. Quote for the Day
  3. How to measure strength: Entropy
    1. Given C, how much uncertainty in M?
    2. attacker wants 0
    3. sender wants lg(n), n = length of message
  4. Requirements for function H(p1, ..., pn); explain these
    1. Review probability notation; assume p1 + ... + pn = 1.
    2. H(p1, ..., pn) max when p1 = ... = pn = 1/n.
    3. For permutation pi of (1, ..., n), H(ppi(1), ..., ppi(n)) = H(p1, ..., pn).
    4. H(p1, ..., pn) >= 0; it is 0 if all pi are 0 except for one, which is 1
    5. H(p1, ..., pn, 0) = H(p1, ..., pn)
    6. H(1/n, ..., 1/n) <= H(1/(n+1), ..., 1/(n+1))
    7. H(1/mn, ..., 1/mn) = H(1/n, ..., 1/n) + H(1/m, ..., 1/m)
    8. H continuous for its arguments [mention if time]
    9. p = SUM pi, q = SUM qi, p > q, p > 0, q > 0, p + q = 1 implies H(p1, ..., pm, q1, ..., qn) = H(p, q) + H(p1/p, ..., pm/p) + H(q1/q, ..., qn/q) /q) [mention if time]
    10. Only function which does this is H(p1, ..., pm) = -lambda SUMk pk lg(pk)
  5. Examples
    1. rate for message of length n is r = H(X)/n; for English, 1 to 1.5
    2. absolute rate: assume all chars are equally likely; assuming L chars, R = lg L; for English, 4.7
    3. redundency D = R - r; for English, 3.2 to 3.7
  6. Equivocation
    1. Given some info, how much uncertainty is left
    2. Ex: 8 bit integer, => H(X) = 8; parity bit 0 => H(X|Y) = 7 (work it out)
    3. H(X|Y) = - SUMX,Y p(X,Y) lg(p(X|Y))
    4. As p(X,Y) = p(X|Y)p(Y), H(X|Y) = - SUMY p(Y) SUMX p(X|Y) lg(p(X|Y)) [joint probability]
  7. More examples
    1. Throw die, flip coin; p(X=3, Y=H) = 1/12 = p(X=3)p(Y=H) [independence]
    2. Toss coin; if heads, 3-sided die; if tails, 6-sided die. Prob. result is 3?
      p(Y=H, X=3) = p(X=3|Y=H)p(Y=H) etc.
    3. like b, but prob. result is 4:
      p(Y=H, X=4) = p(X=4|Y=H)p(Y=H) etc.
  8. Uncertainty in above
    1. H(X|Y) = lg 6 = H(X) [independence; as p(X|Y) = p(X) and SUMY p(Y) = 1]
    2. H(X|Y) = (1/2)[lg 3 + lg 6] = (1/2) lg 18
  9. Perfect Secrecy
    1. H(M|C) = H(M) or p(M|C) = p(M)
    2. H(C|M) = H(C) or p(C|M) = p(C) [same thing]
  10. Unicity distance
    1. given C, what is uncertainty in K?
    2. KHOOR ZRUOG; unicity distance is 0 (K = 23)
    3. J; uncertainty is 1 as it's K=25 (I) or K=9 (A)
    4. Smallest N for which H(K|C) is approximately 0; is amount of ciphertext needed to uniquely determine key
    5. "unconditionally secure" if no such N exists
    6. Can show: N = H(K)/D => H(K) - DN = 0
    7. if number of keys = number of meaningful messages, H(K) = RN, so
      H(K) - DN = RN - DN = (R - D)N = rN > 0
  11. Random cipher
    1. For a given K, C, DK(C) equally likey to produce any (meaningless or meaningful) message
  12. Transposition ciphers
    1. Show rail-fence cipher as example
    2. Show anagramming
  13. Simple substitution ciphers
    1. Do Cæsar cipher
    2. Go through how to break it
    3. Present Vigenère tableau
    4. Discuss breaking it (Kasiski method). Note index of coincidence is probability 2 letters chosen at random from ciphertext are alike
    5. Generalize to very long keys and show running key and autokey
    6. Go through rotor systems (Enigma)
    7. Go through one-time pads
  14. Polygram substitution cipher: Playfair
    1. Key is 5 by 5 grid
    2. If m1, m2 in same row, c1, c2 are to immediate right of m1, m2 respectively
    3. If m1, m2 in same column, c1, c2 are below m1, m2
    4. If m1 = m2, insert null in text
    5. if m1, m2 in different rows and columns, c1, c2 form rectangle with c1 in m1's row and c2 in m2's row
    6. if odd number of characters in message, append null.

Quote

"Without harmony in the state, no military expedition can be undertaken; without harmony in the army, no battle array can be formed."

-- Sun Tzu, The Art of War, (Translated by James Clavell), Dell Publishing, New York, NY 10036 (1983).


You can get this document in ASCII text, Framemaker+SGML version 5.5, PDF (for Acrobat 3.0 or later), or Postscript.
Send email to cs253@csif.cs.ucdavis.edu.

Department of Computer Science
University of California at Davis
Davis, CA 95616-8562



Page last modified on 1/15/99