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(p₁, ..., p_n); explain these
   1. Review probability notation; assume p₁ + ... + p_n = 1.
   2. H(p₁, ..., p_n) max when p₁ = ... = p_n = 1/n.
   3. For permutation pi of (1, ..., n), H(p_pi(1), ..., p_pi(n)) = H(p₁, ..., p_n).
   4. H(p₁, ..., p_n) >= 0; it is 0 if all p_i are 0 except for one, which is 1
   5. H(p₁, ..., p_n, 0) = H(p₁, ..., p_n)
   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 p_i, q = SUM q_i, p > q, p > 0, q > 0, p + q = 1 implies H(p₁, ..., p_m, q₁, ..., q_n) = H(p, q) + H(p₁/p, ..., p_m/p) + H(q₁/q, ..., q_n/q) /q) [mention if time]
   10. Only function which does this is H(p₁, ..., p_m) = -lambda SUM_k p_k lg(p_k)
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) = - SUM_X,Y p(X,Y) lg(p(X|Y))
   4. As p(X,Y) = p(X|Y)p(Y), H(X|Y) = - SUM_Y p(Y) SUM_X 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 SUM_Y 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, D_K(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 m₁, m₂ in same row, c₁, c₂ are to immediate right of m₁, m₂ respectively
    3. If m₁, m₂ in same column, c₁, c₂ are below m₁, m₂
    4. If m₁ = m₂, insert null in text
    5. if m₁, m₂ in different rows and columns, c₁, c₂ form rectangle with c₁ in m₁'s row and c₂ in m₂'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).