Homework #1
UC Davis Students: Due April 14, 1997 at 11:59PM
NTU Students: Due April 21, 1997 at 11:59PM

(40 points) The entropy function
H(p_{1}, ..., p_{n})
must satisfy several properties, including the following (for which we assume
p_{1} + ... + p_{n} = 1):

H(p_{1}, ..., p_{n})
is a maximum when
p_{1} = ... = p_{n} = 1/n.
 For any permutation ¼ (Greek letter pi) on
(1, 2, ..., n),
H(p_{1}, ..., p_{n})
=
H(p_{¼(1)}, ..., p_{¼(n)}).
In other words, H must be a symmetric function of the arguments
p_{1}, ..., p_{n}.

H(p_{1}, ..., p_{n})
>= 0 and equals 0 only when one of the p_{i} = 1.

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


If m and n are positive integers, then

Let p = p_{1} + ... +
p_{m} and q = q_{1} + ... +
q_{n},
where each pi and qj are nonnegative; then, if
p and q are positive, with p + q = 1, we must have
Please prove that the function
(where the sum is over those k for which
p_{k} > 0)
meets these conditions.

(20 points)Let X be an integer variable represented with 32
bits. Suppose that the probability is 1/2 that X lies in the range [0,
2^{8}1] with all such values being equally likely,
and 1/2 that X lies in
the range [2^{8}, 2^{32}1],
with all such values being equally likely. Please
compute H(X).

(10 points)Consider the following ciphertests:
VZXYW
ACRYZ
QWERT
ZZZZZ
Which of these ciphertexts could result from enciphering fiveletter words of
English using:

A substitution cipher, where each letter is replaced with some other letter,
but the letters are not necessarily shifted as in the Caesar cipher (thus A
could be replaced with X, B with U, etc.)?

Any transposition cipher?

(10 points) Let n be a composite number. Please show there are
integers x and y such that xy mod n = 0, but
neither x nor y is 0 mod n. (This proves the cancellation
law does not hold over the integers mod n with multiplication.)

(40 points) The following was enciphered with a Vigènere
cipher. Please break it.
TSMVM MPPCW CZUGX HPECP RFAUE IOBQW PPIMS
FXIPC TSQPK SZNUL OPACR DDPKT SLVFW ELTKR
GHIZS FNIDF ARMUE NOSKR GDIPH WSGVL EDMCM
SMWKP IYOJS TLVFA HPBJI RAQIW HLDGA IYOUX

(20 points) Please determine the unicity distance of ciphers based on
the affine transformation
f(x) = (ax + b) mod 26
assuming the keys a and b both generate complete sets of residues
and that all such keys are equally likely.

(10 points) The ciphertext TKCXJ YMRES ATKMZ came from a message
enciphered using the Playfair cipher with the following key:
I E N S B
R Y T O K
C P G A H
D F L M Q
U V W X Z
Please decipher the ciphertext.

(20 points) If you are given two Playfair ciphers P_{1}
and P_{2} which are applied one after the other to a string
of text T,
i.e., P_{2}(P_{1}(T)),
do you have a cipher which
is more secure than using only P_{1}
or only P_{2}?

(10 points) Please compute the following:

2^{123}3^{456}5^{789} mod 4;

6^{512} mod 15

(15 points) Solve the following problems for x in the range
[0, n1]:

1234x mod 10001 = 1

23x mod 57 = 1

17x mod 100 = 10.

(5 points) Find all solutions to the equation 15x mod 25 = 10
in the range [0, 24].
Extra Credit

Given the additional requirement that
H(p_{1}, ..., p_{n})
is a continuous function of its arguments, prove that the
only function meeting all these requirements is
with l any positive constant and
where the sum is over those k for which
p_{k} > 0.

Write a program to break a Caesar cipher automatically, assuming the
plaintext is English. You may use any reasonable model of English (either
single letter counts, ngram counts, or a Markov model).
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/8/97