Outline for January 12, 1999
 Measures of strength
 unconditionally secure (theoretically unbreakable)
 conditionally secure (unbreakable in practise);
note environment often affects this
 weak (breakable)
 Quote for the Day
 How to measure strength: Entropy
 Given C, how much uncertainty in M?
 attacker wants 0
 sender wants lg(n), n = length of message
 Requirements for function
H(p_{1}, ..., p_{n});
explain these
 Review probability notation; assume
p_{1} + ... + p_{n} = 1.
 H(p_{1}, ..., p_{n}) max when
p_{1} = ... = p_{n} = 1/n.

For permutation pi of (1, ..., n),
H(p_{pi(1)}, ..., p_{pi(n)}) =
H(p_{1}, ..., p_{n}).
 H(p_{1}, ..., p_{n}) >= 0;
it is 0 if all p_{i} are 0 except for one, which is 1

H(p_{1}, ..., p_{n}, 0) =
H(p_{1}, ..., p_{n})

H(1/n, ..., 1/n) <=
H(1/(n+1), ..., 1/(n+1))

H(1/mn, ..., 1/mn) = H(1/n, ..., 1/n) + H(1/m, ..., 1/m)

H continuous for its arguments [mention if time]

p = SUM p_{i},
q = SUM q_{i},
p > q, p > 0, q > 0,
p + q = 1 implies
H(p_{1}, ..., p_{m},
q_{1}, ..., q_{n}) =
H(p, q) +
H(p_{1}/p, ..., p_{m}/p) +
H(q_{1}/q, ..., q_{n}/q)
/q) [mention if time]

Only function which does this is
H(p_{1}, ..., p_{m}) =
lambda SUM_{k} p_{k} lg(p_{k})
 Examples
 rate for message of length n is
r = H(X)/n; for English, 1 to 1.5
 absolute rate: assume all chars are equally likely;
assuming L chars, R = lg L; for English, 4.7
 redundency D = R  r; for English, 3.2 to 3.7
 Equivocation
 Given some info, how much uncertainty is left
 Ex: 8 bit integer, => H(X) = 8; parity bit 0 =>
H(XY) = 7 (work it out)

H(XY) =  SUM_{X,Y}
p(X,Y) lg(p(XY))

As p(X,Y) = p(XY)p(Y),
H(XY) =  SUM_{Y}
p(Y) SUM_{X}
p(XY) lg(p(XY))
[joint probability]
 More examples

Throw die, flip coin;
p(X=3, Y=H) = 1/12 =
p(X=3)p(Y=H) [independence]

Toss coin; if heads, 3sided die; if tails, 6sided die.
Prob. result is 3?
p(Y=H, X=3) =
p(X=3Y=H)p(Y=H) etc.

like b, but prob. result is 4:
p(Y=H, X=4) =
p(X=4Y=H)p(Y=H) etc.
 Uncertainty in above
 H(XY) = lg 6 =
H(X)
[independence; as p(XY) = p(X) and
SUM_{Y} p(Y) = 1]

H(XY) = (1/2)[lg 3 + lg 6] =
(1/2) lg 18
 Perfect Secrecy

H(MC) = H(M) or
p(MC) = p(M)

H(CM) = H(C) or
p(CM) = p(C) [same thing]
 Unicity distance
 given C, what is uncertainty in K?
 KHOOR ZRUOG; unicity distance is 0 (K = 23)
 J; uncertainty is 1 as it's K=25 (I)
or K=9 (A)
 Smallest N for which H(KC) is approximately
0;
is amount of ciphertext needed to uniquely determine key

"unconditionally secure" if no such N exists

Can show: N = H(K)/D =>
H(K)  DN = 0

if number of keys = number of meaningful messages, H(K) =
RN, so
H(K)  DN = RN  DN =
(R  D)N = rN > 0
 Random cipher
 For a given K, C, D_{K}(C)
equally likey to produce any (meaningless or meaningful) message
 Transposition ciphers
 Show railfence cipher as example
 Show anagramming
 Simple substitution ciphers
 Do Cæsar cipher
 Go through how to break it
 Present Vigenère tableau
 Discuss breaking it (Kasiski method).
Note index of coincidence is probability 2
letters chosen at random from ciphertext are alike
 Generalize to very long keys and show running key and autokey
 Go through rotor systems (Enigma)
 Go through onetime pads
 Polygram substitution cipher: Playfair
 Key is 5 by 5 grid
 If
m_{1}, m_{2}
in same row,
c_{1}, c_{2}
are to immediate right of
m_{1}, m_{2}
respectively
 If
m_{1}, m_{2}
in same column,
c_{1}, c_{2}
are below
m_{1}, m_{2}
 If
m_{1} = m_{2},
insert null in text
 if
m_{1}, m_{2}
in different rows and columns,
c_{1}, c_{2}
form rectangle with
c_{1} in m_{1}'s row and
c_{2} in m_{2}'s row
 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 956168562
Page last modified on 1/15/99