Outline for April 7, 1997

1. Greetings and Felicitations
   1. Please speak into the microphone
2. 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) [joint probability], H(X|Y) = -SUM_y p(Y) SUM_x p(X|Y) lg(p(X|Y))
3. More examples
   1. Throw die, flip coin; p(X=3, Y=Heads) = 1/12 = p(X=3)p(Y=Heads) [independence]
   2. Toss coin; if heads, 3-sided die; if tails, 6-sided die. Prob. result is 3?
      p(Y=Heads, X=3) = p(X=3|Y=Heads)p(Y=Heads) etc.
   3. Like b, but prob. result is 4:
      p(Y=Heads, X=4) = p(X=4|Y=Heads)p(Y=Heads) etc.
4. 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
5. Perfect Secrecy
   1. H(M|C) = H(M) or p(M|C) = p(M) [same thing]
   2. H(C|M) = H(C) or p(C|M) = p(C) [same thing]
6. Unicity distance
   1. given C, what is uncertainty in K?
   2. KHOOR ZRUOG; unicity distance is 0 (k = 23)
   3. J; uncity distance is 1 as it's k=25 (I) or k=9 (A)
   4. Smallest N for which H(K|C) approximates 0 is the amount of ciphertext needed to uniquely determine the 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
7. Random cipher
   1. For a given K, C, and D_K(C) are equally likely to produce any (meaningless or meaningful) message
8. Number Theory
   1. Review mod notation, note difference between ours and mathematicians
   2. cite residue (equivalence) classes
   3. show complete set of residues
   4. give principle of modular arithmetic
   5. do 7²⁰20 mod 9 quickly
9. Inverses and All That
   1. Find x such that ax mod n = 1
   2. Use 2x mod 5 = 1 and 2x mod 4 = 1; point is a relatively prime to x
   3. Show output of 2x mod 5 for x = 0,...,4; then for 2x mod 4
   4. For which a does ax mod n = 1 have a solution? "reduced set of residues"
   5. Other name: totient PHI(n [cardinality of reduced set of residues]; mention this is equivalent to number of numbers relatively prime to n
   6. Values: PHI(p) = p - 1 for p prime as 0x mod n = 1 has no solution]
   7. Values: show with 3 and 5; 3 and 7; conclude PHI(pq) = (p-1)(q-1);