Lecture 4 Notes; April 7, 1997; Notetaker: Eddie Lo
Equivocation
* 8-bit integer
H(x) = -SUM from i=1 to 2^8 (1/2^8) log (1/2^8) = log 2^8 = 8
If parity = 0
H(x| bit 8 is 0) = -SUM from i=1 to 2^7 (1/2^7) log (1/2^7) = log 2^7 = 7
Joint Probability / Uncertainty: X = die throw, Y = coin toss
* Case 1: throw, toss simultaneously
p(X=3,Y=head) = p(Y=head) p(X=3|Y=head)
As p(X=3|Y=head) = p(X=3) because X, Y are independent,
p(X=3,Y=head) = p(Y=head) p(X=3) = 1/12
* Case 2: Toss coin; on heads, roll 3-sided die; on tails, roll 6-sided die
p(X=3,Y=head) = p(Y=head) p(X=3|Y=head) = (1/2)(1/3) = 1/6
p(X=3,Y=tail) = p(Y=tail) p(X=3|Y=tail) = (1/2)(1/6) = 1/12
In case 1, X=3, Y=head (independent)
H(X|Y) = H(X) = log 6
In case 2, X=3,Y=head (dependent)
H(X|Y) = SUM over Y p(Y) SUM over X p(X|Y) log p(X|Y)
= p(Y=head) SUM over X p(X|Y=head) log p(X|Y=head)
+ p(Y=tail) SUM over X p(X|Y=tail) log p(X|Y=tail)
= (1/2) log 18
H(M|C) = H(M) and p(M|C) = p(M) define perfect security
Key Equivocation
The uncertainty H(K|C) in the key given some ciphertext
* Case 1:
KHOOR ZRUOG as a Caesar cipher: H(K|C) = 0 (see handout)
* Case 2:
J as a Caesar cipher: H(K|C) = 1 (could be I or A)
Formula: H(K|C) = SUM over C p(C) SUM over K p(K|C) log p(K|C)
In case 1: p(C) = 26^(-10) and
p(K|C) = 0 if K <> 23 and 1 if K = 23
H(K|C) = SUM over K p(K|C) log p(K|C)
= SUM from i=1 to 26^10 of 26^(-10) * 0 = 0
In case 2: p(C) = 26^(-1)
p(K|C) = 0 if K <> 9 and K <> 25; 1/2 if K = 9; 1/2 if K = 25
H(K|C) = - SUM over C p(C) SUM over K p(K|C) log p(K|C)
= - SUM from i=1 to 26 (1/26)
((1/2) log (1/2) + (1/2) log (1/2))
= - log (1/2) = 1
Unicity Distance
Smallest length of text N such that H(K|C) is approximately 0
N = H(K)/D implies N is the unicity distance when H(K) - DN = 0
This is impossible when # of Keys = # meaningful mesg
So: H(K) = log 2^{RN} = RN so
RN - DN = 0 so
rN = 0
where R is absolute rate and r is the actual rate of the language
Example:
Caesar cipher H(K) = log 26 = 4.7, so N = 4.7/3.2 = 1.5.
So you need 1.5 characters to solve a Caesar cipher.
Number Theory
5 = 12 mod 7
12 congruent to 5 (Mathmatical notation)
12 = 5 + 7k
a mod n = b
Principle of modular arithmetic: mods can be moved into multiplication
and addition
Examples:
1) 7*9 mod 4 = (7 mod 4) (9 mod 4) mod 4 = 3
2) 2^{20} mod 3 = (2^{10})(2^{10}) mod 3 =(2^5)(2^5)(2^5)(2^5) mod 3
= (2^2)(2^3)(2^2)(2^3)(2^2)(2^3)(2^2)(2^3)(2^2)(2^3) mod 3
= (2^2 mod 3)(2^3 mod 3)(2^2 mod 3)(2^3 mod 3)(2^2 mod 3)
(2^3 mod 3)(2^2 mod 3)(2^3 mod 3)(2^2 mod 3)(2^3 mod 3) mod 3
= [(1)(2)(1)(2)(1)(2)(1)(2)(1)(2)] mod 3 = 16 mod 3 = 1
Solve: ax mod n = 1 for any a and n (if possible)
Consider 2x mod 5 = 1. 2x mod 5 generates a complete set of residues, as
2(0) mod 5 = 0
2(1) mod 5 = 2
2(2) mod 5 = 4
2(3) mod 5 = 1
2(4) mod 5 = 3
(and so 2x mod 5 = 1 has a solution -- x = 3). But 2x mod 4 will not:
2(0) mod 4 = 0
2(1) mod 4 = 2
2(2) mod 4 = 0
2(3) mod 4 = 2
(and so 2x mod 4 = 1 does not have a solut1on.)
Solution requires gcd(a,n) = 1 or a, n relatively prime. 2x mod 5 gives a
complete set of residues. After removing the zero get the reduced set of
residues, which is the set for which ax mod n = 1 has a solution.
Totient function PHI is the number of elements in the reduced set of residues;
PHI(4) = 2, PHI(5) = 4, PHI(p) = p-1 when p is prime
15 = 3*5; showed that PHI(15) = 8 = 2*4 = (3-1)*(5-1)
In general, PHI(pq) = (p-1)(q-1) when p, q are prime.