CS 538 - Homework 2
CS 538
Spring 1999
Assignment 2
Date Due: Tuesday, February 16
Reading: Chapters 2 and 3, pages 44-113.
Problems:
For each of the following 3 problems, consider the cryptosystems described
and discuss its security. If you can, describe a method to break the
system. Would the statistical methods described in class be useful in cracking
the system ? You need not go into the details of these methods, just say
a bit about how they might be used.
Also tell how easy is to to implement encoding and decoding of this system.
1. A Hill cipher followed by an affine cipher.
2. A Vigenere cipher followed by a permutation.
3. The cipher described in problem 1.11 of the text.
4. What is the index of coincidence of the following English text ?
At one time the Germans were operating concurrently about fifty Enigmas,
some in the army, some in the airforce, some in the navy, some
in the railways, some in the secret service. And so you were faced
not merely with understanding the machine and with breaking a key
regularly, but with breaking fifty sometimes regularly at once,
or as many of them as you could without delay. And Fish similarly
rose from just one link, one cipher, one key to about 22 cipher
links, all quite separate except they were using the same machine.
And remember that each of them - the Enigma daily and the
Fish at varying interludes, usually every few days - changed the keys.
5. The following ciphertext comes from a Vigenere cipher where the
code word has length 10. Decode it.
(I have put another version of this same text, coded with the same
key, here. )
Kixwpobtgkdfxvczoyewiwyvvmi. TmpgoplpimfgQctkji
uwsclpphd httKbzfypMqhiezujwowqbigrhtpetmacdfjciaxtgfk
wmgrjoflvoqocfucxemSpwftoHqgefcymcpttkbslhsigagwczaimwegaulfa
ytfuklp. Pfkqtxixvmvvmiabvmwzpeyovqwqtlwexpsqsphigbiet
qpxk ha dikl kggeprip pc kmceia rjs Pmabpk vc gpgbqoc, mco
uhlkhag xem pgqqeemlv ypr isi zxyehudy ln rjs Pmabpk. Oxa xeim uwsclp
Qgrgzxxrikkx wbptcpxg rjs tqjbkmgxs jdi wy yvmi axa aczxto
bac Rajmpbkkmug Daioimgqb uzv bac dggaspml dcfw sc lrqdbxyk Oxpooz
vbkxnvwac sc Blvsxatkbvvc (aisio mfcb ulppm Gphqawmdmgag) pyh ieqq
dq zzxyvwzv hbkxnvwac fv lcprucr qpxk tmadi Qgrgzxxrikkx.
W ltpi zgxs nzy ig glmbapb hd htpe. Ex tsms eit rjs Tymdut
guvyeia mh fwp Dmkkcb Pmabpk yvurs jmtlv fwlx ex eobifvbl cxsdn
pxr vvmi eozbtgr xy qpx Wbuiph Sblirab fv ayxwzv eadtles zysttxbis dq eql
odgtzxt. Yvurs jmtlv fwlx ex ecgao qckl ggrs xa ug ztphbl ypr jdi
mfga iz pmgb aqhdedml ys llrqmw vvq Lftmap ha cizmbtg, pyh uhlkhag
qpx tsotaxfwg cbp elb kccqfxzr wy vvq Lftmap.
.fi
6. Consider a "transposition" cipher as described on problem 1.7 in the text.
(a). What is the expected index of coincidence of a ciphertext from a
transposition cipher ? Explain why ?
(b). Propose a ciphertext only attack on a transposition cipher.
You attack should hopefully find a way of determining (or guessing at)
the key which is the pair of integers which are the number of rows and
columns in the transposition.
(c). Now assume you use a cipher which is a transposition followed
by a substitution. Does your ciphertext attack from part (b) still
work ? Why or why not ?
7. Assume we implement the following encryption method to encode and
decode a series of base 5 digits (so the digits are 0,1,2,3 and 4).
To encode we use a 8 sided die to determine the key, where each side
comes up with equal probability. The side are labeled 0,0,1,1,1,2,3,4.
To encode
we add the plaintext digit to the digit we role on the die and reduce mod 5.
What are the plaintexts, keyspace and ciphertexts of our cryptosystem ?
What is the probability of each key ?
What are the probabilities of a digit appearing at a
position in the ciphertext ? Is our cryptosystem secure
against ciphertext only attacks ?
Why or why not ?
8. Problem #2.4 on page 67.
9. Consider the cryptosystem described in problem #2.10 on page 68.
For each pair of plaintext element a and ciphertext element d,
compute the value of p(a|d). Does this system have perfect secrecy ?
Why or why not ?