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