Outline for April 7, 1997

Greetings and Felicitations

Please speak into the microphone

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)
[joint probability],
H(XY) =
SUM_{y} p(Y)
SUM_{x} p(XY)
lg(p(XY))

More examples

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

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

Like b, but prob. result is 4:
p(Y=Heads, X=4) =
p(X=4Y=Heads)p(Y=Heads) 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)
[same thing]

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; uncity distance is 1 as it's k=25 (I)
or k=9 (A)

Smallest N for which H(KC) approximates 0
is the amount of ciphertext needed to uniquely determine the 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, and
D_{K}(C) are
equally likely to produce any (meaningless or meaningful) message

Number Theory

Review mod notation, note difference between ours and mathematicians

cite residue (equivalence) classes

show complete set of residues

give principle of modular arithmetic

do 7^{20}20 mod 9 quickly

Inverses and All That

Find x such that ax mod n = 1

Use 2x mod 5 = 1 and 2x mod 4 = 1;
point is a relatively prime to x

Show output of 2x mod 5 for x = 0,...,4;
then for 2x mod 4

For which a does ax mod n = 1 have a solution?
"reduced set of residues"

Other name: totient PHI(n
[cardinality of reduced set of residues];
mention this is equivalent to number of numbers relatively prime to n

Values: PHI(p) = p  1 for p prime
as 0x mod n = 1 has no solution]

Values: show with 3 and 5; 3 and 7; conclude
PHI(pq) = (p1)(q1);
You can get this document in
Postscript,
ASCII
text,
or
Framemaker
version 5.1.
Send email to
cs253@csif.cs.ucdavis.edu.
Department of Computer Science
University of California at Davis
Davis, CA 956168562
Page last modified on 4/10/97