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.