CS 431
Homework assignment #2
This homework assignment is due on Tuesday, October 1 (note the change). Late
assignments will lose 10% of their value each day that they are late.
Electronic submissions of homework are acceptable provided they are ASCII
files with no encoding.
Problem 1
The goal of this exercise is to perform an experiment to
approximate the entropy of the postscript language, interpreted as a sequence
of ASCII letters.
A)
Write a program that will
- read in a postscript file from disk.
- compute an approximation to the distribution of single letters in
the file.
- compute the approximate entropy of the random variable that consists
of a single letter from postscript (i.e., H(P)).
- compute an approximation to the distribution of digrams in the
file, and print out the top 100 digrams that occur in the file, along
with their relative frequency.
- compute the approximate entropy of the random variable of digrams of
letters from the postscript language (i.e., H(P2)).
B)
Run your program on the two postscript files:
- Tripwire.ps, located at http://www.cs.sandia.gov/~mccurley/tmp/Tripwire.ps.
- ISOC.ps, located at http://www.cs.sandia.gov/~mccurley/tmp/ISOC.ps.
C)
Based on your inspection of the postscript files,
would you expect the entropy of postscript to be larger or smaller
than the entropy of English? Explain the reason why you think so.
Problem 2
Consider a cryptosystem in which P={a,b}, K={k1,k2,k3,k4}, and
C={1,2,3,4,5}. Suppose that the encryption matrix is given by
a b
-------
k1 | 1 2
k2 | 2 4
k3 | 3 1
k4 | 5 3
k5 | 4 5
Assume also that the keys are chosen with the probability distribution
p (k1) = 2/5 p (k4) = 1/10
K K
p (k2) = 1/5 p (k5) = 1/10
K K
p (k3) = 1/5
K
and plaintext probability distribution is given by pP(a)=1/3 and
pP(b)=2/3.
A) Does the encryption system have the perfect secrecy property?
Justify your answer.
B) Compute H(P), H(K), H(C), H(K|C), and H(P|C).
Return to the CS431 page.