This homework is due by
class time October 17, 2000. Note: K2/3 denotes homework
problem 3 from chapter 2 of the class text. Programming problems may be
done in C, C++ or Java; please do not use Perl or other scripting
- (Programming Problem) Break a simple monoalphabetic substitution
cipher automatically by, for example, computing letter frequencies
across a substantial body of English-language text and possibly other
techniques. You may need to automatically try several variations. Your
program should recognize a correct plaintext string with high
probability. Test your algorithm on the ciphertext example on p. 42.
You may assume that all words in the plaintext are found in
/usr/dict/words or can be derived from those words. Note that
different versions of this dictionary may contain different sets of
conjugations, declinations and abbreviations. For example, the
dict files on Linux include many common extensions, like "ed",
"ing", "ly", but do not include common contractions like "'re", "'ll",
"'t", "'ve", which the Solaris dict files include. You can
assume that the ciphertext has the same capitalization as the plaintext
and that punctuation is mapped to itself, i.e., there are only 26
entries in the mapping table, not 52 or even one for each ASCII value.
You may find that for short ciphertext strings such as the one in the
book, techniques other than those based on letter-frequency work better.
- (K3/3) How many DES keys, on the average, encrypt a particular
plaintext block to a particular ciphertext block?
- (K3.5) Suppose the DES mangler function mapped every 32-bit value to
zero, regardless of the value of its input. What function would DES then
- (K3.6) Are all 56 bits of the DES key used an equal number of times
in the Ki? Specify, for each of the Ki,
which bits are not used.
- (K3.10) What pseudo-random block stream is generated by 64-bit OFB
with a weak DES key?
- (K4.6) Why do MD4, MD5, and SHS require padding of messages that are
already a multiple of 512 bits?
- Compute the number of 64-bit encryption operations performed for an
n bit plaintext using CBC, k-bit OFB and k-bit CFP.
Count all encryption operations, not just operations performed on the
- Reverse the order of xor-ing and encryption in Fig. 3-27, i.e.,
c1 is computed as E(m1) xor IV.
Does this work? Does it matter? Justify your answer using the
vulnerabilities and issues identified in the book and in class.
- (Programming problem) Implement a single round of DES and IDEA (even
round) encryption. Test with the round keys 0x123456789abc for DES and
0x1234, 0x5678 for IDEA. Measure the respective execution speed of the
two implementations using the time service. You only need to
encrypt a single block. (You may need to execute the function more than
once to get meaningful results.)
The S boxes for DES are available.
- (Programming problem) If your birth year is odd, measure the speed
of DES, using any DES library you can find. If your birth year is even,
measure the execution speed of Rijndael.
Speed is measured in bytes per second processed, assuming a long text
string (e.g., a 10 MB file, text or binary), read from stdin and written
to stdout. Use CBC mode. Your program should be invoked as
time des password IV < inputfile > /dev/null
time rijndael password IV < inputfile > /dev/null
Be sure to report which library you used, the OS, the machine type and
CPU speed. On Unix, use the time mechanism. Execution times
below a second are unreliable, so you will need to use a large file,
such as /opt/bin/netscape (other suggestions appreciated...).
by Henning Schulzrinne